考察知识点：快速幂 题目很长，但是意思很简单，就是判断 xax^axa 和 yby^byb 是否相等。 使用快速幂优化即可。 时间复杂度：O(log⁡a+log⁡b)O(\log a+\log b)O(loga+logb) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector&l...

考察知识点：枚举 数据范围较小，套三重循环枚举即可。 时间复杂度：O(n3)O(n^3)O(n3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<p...

考察知识点：数学、快速幂 nnn 个格子处于同一排，忽略限制最多有 mnm^nmn 种涂法。 考虑让小明不开心的涂法，易知这样的涂法有 m(m−1)n−1m(m-1)^{n-1}m(m−1)n−1 种，因为第一个格子可以从 mmm 种颜色中任选，后面的格子只能从与上一个格子不同的 m−1m-1m−1 种颜色中任选。 最终答案即为 mn−m(m−1)n−1m^n-m(m-1)^{n-1}mn−m(m−1)n−1，用快速幂优化即可。 时间复杂度：O(log⁡n)O(\log n)O(logn) #include <bits/stdc++.h> using namespace std; ...

A. 递归函数的次数 题目链接：A. 递归函数的次数 考察知识点：递归、滚动数组 递归函数调用次数满足递推式 an=an−1+an−2+an−3+1a_n = a_{n-1} + a_{n-2} + a_{n-3} + 1an​=an−1​+an−2​+an−3​+1，其中 a1=a2=a3=1a_1 = a_2 = a_3 = 1a1​=a2​=a3​=1。 由于 n≤100,000,000n \leq 100,000,000n≤100,000,000，所以不能直接递归或者迭代求解，考虑使用滚动数组优化。 时间复杂度：O(n)O(n)O(n) #include <bits/stdc++...

考察知识点：模拟 大模拟题，需要考虑的情况比较多，下面的代码提供了一种写法。 时间复杂度：O(kq)O(kq)O(kq) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef ...

考察知识点：构造 由题易知，构造的回文串个数与字符串中出现次数为奇数的字符个数有关，所有成对出现的字符都不用单独构造。若所有字符都成对出现，则也至少需要构造 1 个回文串。 因此回文串的个数应为 max(n, 1)，其中 n 为出现次数为奇数的字符个数。 将单独出现的字符作为回文串的中心，其余字符成对出现在中心两侧即可。 时间复杂度：O(∣s∣)O(|s|)O(∣s∣) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef...

考察知识点：前缀和 定义 sum(a)=∑i=1naisum(a)=\sum\limits_{i=1}^{n} a_isum(a)=i=1∑n​ai​，考虑计算 sum(a′)sum(a')sum(a′)。 sum(a′)=∑i=1nai′=∑i=1n(sum(a)−ai)=∑i=1nsum(a)−∑i=1nai=(n−1)sum(a)sum(a') = \sum\limits_{i=1}^{n} a'_i = \sum\limits_{i=1}^{n} (sum(a)-a_i) = \sum\limits_{i=1}^{n} sum(a) - \sum\limits_{i=1}^{n} a_...

考察知识点：二分 不难看出每种礼包的构成：「1 个 U 盘 + 1 个鼠标」 + 1 个「U 盘 / 鼠标 / 键盘」 设 U 盘、鼠标、键盘数量为 a0,b0,ca_0, b_0, ca0​,b0​,c，分配完每个礼包本身含有的 1 个 U 盘和 1 个鼠标后的 U 盘、鼠标数量为 a,ba, ba,b，礼包数量为 mmm，则有以下关系式：  a=a0−ma = a_0 - ma=a0​−m b=b0−mb = b_0 - mb=b0​−m a,b,c≥0a, b, c \geq 0a,b,c≥0 a+b+c≥ma + b + c \geq ma+b+c≥m  由于相邻两位大佬的礼包不能相同...

考察知识点：递归 递归求解：  当补给次数超过 3 次或当前糖果数量小于 0 时，返回。 当当前位置超过 n 时，更新答案并返回。  时间复杂度：O(2n)O(2^n)O(2n) + 剪枝 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typ...

考察知识点：前缀和 使用 x[i]x[i]x[i] 记录数字 iii 的圈数，s[i]s[i]s[i] 记录 ∑j=1ix[j]\sum\limits_{j=1}^{i} x[j]j=1∑i​x[j]，即前缀和。 则数字 aaa 到 bbb 的总圈数为 s[b]−s[a−1]s[b] - s[a-1]s[b]−s[a−1]。 时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ...

考察知识点：贪心 考虑两头牛时的情况，有以下 4 种移动方式：  两头牛同时向左移动：距离不变 两头牛同时向右移动：距离不变 左边的牛向左移动，右边的牛向右移动：距离增大 左边的牛向右移动，右边的牛向左移动：距离可能减小  其中前两种情况对答案没有影响，第三种情况可以直接忽略，第四种情况需要考虑。 推广到 n 头牛，可以知道最优的情况只会出现在「所有牛都往一个方向移动」或「靠左的牛往右边移动，靠右的牛往左边移动」这两种移动方法中。 因此，用变量 ans 记录初始距离（也即所有牛往同一方向移动的距离），循环枚举牛群的分界点，比较记录最优的距离，即为答案。 时间复杂度：O(nlog⁡n)O(n \...

考察知识点：贪心 由题易知，最坏情况下也只需要 3 次排序即可，因此考虑 0 ~ 3 次排序的情况：  当数组本身有序时，不需要排序，输出 0； 当最大值或最小值已经就位时，只需要排序 1 次，输出 1； 当最大值与最小值都不在头尾时，需要排序 2 次，输出 2； 当最大值位于头部，最小值位于尾部时，需要排序 3 次，输出 3。  根据条件判断即可。 时间复杂度：O(n)O(n)O(n) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull...

考察知识点：递归、滚动数组 递归函数调用次数满足递推式 an=an−1+an−2+an−3+1a_n = a_{n-1} + a_{n-2} + a_{n-3} + 1an​=an−1​+an−2​+an−3​+1，其中 a1=a2=a3=1a_1 = a_2 = a_3 = 1a1​=a2​=a3​=1。 由于 n≤100,000,000n \leq 100,000,000n≤100,000,000，所以不能直接递归或者迭代求解，考虑使用滚动数组优化。 时间复杂度：O(n)O(n)O(n) #include <bits/stdc++.h> using namespace std;...

分别对 n+1 项进行判断，需要考虑的情况较多，有：  系数为 0 时，不需要输出该项； 系数为正且该项不是第一个输出项时，需要输出 +； 系数为负时，需要输出 -； 系数绝对值为 1 且不为常数项时，不需要输出系数； 常数项不需要输出 x 和指数。 非常数项指数为 1 时，不需要输出指数。  #include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; int a[n + 1]; for (int i = 0; i <= n; i++) cin >> a[i...