题意 经典的 威佐夫博弈（Wythoff Game）： 有两堆石子，数量分别为 $a$ 和 $b$ 每次可以进行两种操作： 从任意一堆取任意多石子 从两堆中取相同数量的石子 最后把石子全部取完的人获胜 要求：判断先手在初始状态下是否能获胜。 解析 威佐夫博弈中，有两种关键状态： P-position（必败点）：如果先手处于此状态，必败 N-posi…

题意 给定正整数 $a,b$，求同余方程 $ax\equiv1\pmod b$ 的最小正整数解 $x$。 解析 由于题目没有保证 $b$ 为质数，所以不能用费马小定理，需要使用拓展欧几里得算法求乘法逆元。 前置芝士 $a$ 在模 $b$ 下存在乘法逆元，当且仅当 $\gcd(a,b)=1$。此时存在整数 $x,y$ 使 $a x + b y = 1…

题意 即维护一棵线段树，支持单点修改+区间查询。 芝士——线段树 线段树（Segment Tree）是一种树状数据结构，主要用来高效处理区间查询（RMQ）与区间修改问题。 下图就是一棵简单的线段树，每一个节点都是其子节点之和，叶子结点用于存储数值，非叶子结点用于维护区间和。 graph TD A["[1,4] sum=10"]--&…

题目传送门 题目大意 根据经过贡献值和字典序排列后的字符串确定资历深浅，贡献值大的资历浅。 思路 利用 STL 中的 map 容器将姓名作为下标存储贡献值的优先级（STL 容器不熟的点这）。 定义一个二维数组，存储 $n_i$ 与 $n_j$ 的大小关系，优先级高的为 $1$，低的为 $0$​。 具体实现详见代码注释。 代码实现 //改自Yulic…

方法1：模拟 Alice 筛法（TLE） 根据题意模拟即可（注意：真因数指不包括 $n$ 的所有 $n$​ 的因数）。 代码： #include<bits/stdc++.h> #define int long long using namespace std; inline void solve() { int n; cin>&g…

这题是典型的排列组合（以下讨论数字个数时都已排除了 $0$） 总的字符串数：字符串长度为 $10000$，且每个位置可以选择的数字有 $9$ 个数字可选，因此，所有可能的字符串总数为：$9^{10000}$。 不包含数字 3：去掉 $3$ 后共有 $8$ 个数字可选，因此不包含 $3$ 的字符串数为：$8^{10000}$。 不包含数字 7：去掉 …

双倍经验。 思路 这是一道简单的二维动态规划问题，在每一步向北或向西走时，比较到达该点时，向北走和向西走路上该种矿物的数量总和，并取大的一个。 为了计算更快，可以通过建立 $a$，$b$ 两个前缀和数组来表示该路径上两种矿物的多少。 状态转移 根据思路，不难得出，状态转移方程为： $$ dp[i][j]=\max(a[i][j]+dp[i-1][j…

题目大意 给出两把梯子的高长度 $x$ 和 $y$，以及交叉点 $c$ 的高度，求道路的宽（即两梯子底端之间的距离）。 解题思路 数学 + 二分 可以利用梯子的长度和梯子与地面的夹角来求得道路的宽。 设梯子 $x$ 与 $y$ 与地面的夹角分别为 $\alpha$ 和 $\beta$，道路的宽设为 $w$，梯子 $x$ 的底端与交叉点在地面的水平投…

题目大意 找到满足 $s_1\operatorname{and}s_2=s$ 的字符串对 $(s_1,s_2)$ 的数量，且 $s_1$ 和 $s_2$ 的长度都要与 $s$ 相同，并给出了字符转为数字，进行比较的规则。 解题思路 由于字符串 $s_1$ 和 $s_2$ 的每一位进行与运算的结果都对应着 $s$ 的相应位置，因此我们可以对 $s$ …

题目大意 给定一个只包含字符 a 和 b 的字符串，通过删除字符（可以不删除）将其转化为满足以下条件的最长字符串： 字符串可以分为三段。 第一段和第三段仅包含 a。 第二段仅包含 b。 每一段都可以为空。 解决思路 可以使用动态规划解决，$dp_{i,j}$ 表示前 $i$ 个字符，第 $j$ 段时，最长美丽字符串的长度，其中 $j\in{0,1,…