官方题解](https://codeforces.com/blog/entry/87356)
有 \(T(1\leq T \leq 1000)\) 组数据。
给定两个正整数 \(n,k(1\leq n,k \leq 10^9)\)，尝试构造一个正整数组成的数列 \(\{a_n\}\)，使得 \(\displaystyle\sum\limits_{i=1}^{n} a_i\) 是 \(k\) 的倍数，并且使得 \(\{a_n\}\) 的最大项尽可能的小。
很显然，这个数列的和可以是一个大于等于 \(n\) 的任意值，而且显然倍数越小越好。
那么我们的做法就是：找到一个 \(k\) 的倍数中大于等于 \(n\) 的最小值，然后构造数列，使得和为这个值即可。
怎么构造：尽可能平均赋值，平均不了就只能选一些项加 \(1\) 了。
给出代码：
#include<bits/stdc++.h>
using namespace std;
int n, k;
void solve()
{
scanf("%d%d", &n, &k);
int K = k;
//感谢这题，贡献了我cf生涯的第一次Hacked：循环加（被注释掉的那行）是会被特殊数据T掉的
//（我当时也想到了，鬼知道我当时怎么认为不会T的）
//while (K < n) K += k;
if (K < n) K = (n % k == 0) ? n : (n/k + 1) * k;
if (K % n == 0) printf("%d\n", K / n);
else printf("%d\n", K / n + 1);
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
有 \(T(1\leq T \leq 1000)\) 组数据。
给定正整数 \(n,k(2\leq n \leq 100, 1\leq k \leq 100)\)。
现在有一个物品的原价为 \(p_0(1\leq p_0 \leq 10^9)\)，接下来第 \(i(1\leq i < n)\) 个月的价格变化量为 \(p_i(1 \leq p_i \leq 10^9)\)。如果某次的价格变化幅度超过了 \(k\%\)，那么认为这件商品的通胀指数有亿点高。
商店老板不希望他的商品的通胀指数超标，所以希望对一部分 \(p_i(0 \leq i < n)\) 加上一些数字，使得最后通胀指数不会超标。现在我们需要求出总修改量的最小值。
这次比赛的好心情到这题开始就结束了（就离谱），然后到第二天早上得知自己被 \(Hacked\) 之后跌到了谷点（逃
用人话翻译一下，就是说，对于任意 \(1 \leq i < n\)， 都有 \(\frac{p_i}{\displaystyle\sum\limits_{j=0}^{i-1} p_j} \leq \frac{k}{100}\)（好像更不像人话了）
我想了各类方法：DP，二分，图论，分数规划，数据结构维护，。。。。。
知道第二天，才发现了一个血淋淋的事实：对于 \(p_i\)，只能加不能减！！！
这样的话，题目似乎就变得比较显然了：
如果第 \(i\) 天不符合要求，那么只能扩大前 \(i-1\) 天的和；如果第 \(i-1\) 天不符合要求，那么只能扩大前 \(i-2\) 天的和，与此同时，最好之前在扩大前 \(i-1\) 天的和的时候，扩大的不是第 \(i-1\)天......
这样，我们发现了一个铁的事实：我们只需要增加 \(p_0\)即可，并且可以保证这一定是最优解！
方法有两种，一种是二分判定，一种是从后向前递推，两个方法都能过，不过后者时间复杂度更低，而且似乎更好写
//只有思路，代码是借鉴这位大佬的
//原地址：https://www.cnblogs.com/HotPants/p/14348300.html
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k;
long long p[N];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i)
scanf("%lld", &p[i]);
long long sum = p[0], res = 0;
for (int i = 1; i < n; ++i) {
if (100 * p[i] > k * sum) {
long long delta = (100 * p[i] - k * sum + k - 1) / k;
res += delta;
sum += delta;
}
sum += p[i];
}
printf("%lld\n", res);
}
return 0;
}
这题似乎并不能简单概括题意，所以还是老老实实去读题吧。
找图中的最长环？好像直接建图并且 DFS 就好，但是可能时空复杂度有点高（我暂时没有看到有人这么写
不过，这题似乎并不需要这么写：我们看到图上的环的构成方式就可以猜测，这个环无非是多个链之间相互拼接而成。
所以说，我们只需要从前往后递推就行了，如果碰上无法成环或者可以重新组成新环的情况就要随时更新。一路上记得更新最大值，最后输出即可。
（重新组成新环，可以看一下第三组样例，把第一和第三根链子互相换一下，就可以明白了）
不想写了，这题够折磨人了，直接上代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n;
long long c[N], a[N], b[N];
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &c[i]);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; ++i)
scanf("%lld", &b[i]);
long long ans = -1, tmp;
for (int k = 2; k <= n; ++k) {
if (a[k] == b[k] || k == 2) {
tmp = abs(a[k] - b[k]) + 2;
ans = max(ans, tmp + c[k] - 1);
}
else {
if (tmp + c[k-1] - 1 -abs(a[k] - b[k]) >= abs(a[k] - b[k]))
tmp += 2 + (c[k - 1] - 1) - abs(a[k] - b[k]);
else tmp = 2 + abs(a[k] - b[k]);
ans = max(ans, tmp + c[k] - 1);
}
}
printf("%lld\n", ans);
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
有 \(n+1\) 个城市（\(n \leq 3*10^5\)），标号从 \(0\) 开始，用一个字符串表示每个城市的链接情况，如果第 \(i\) 位为 \(L\)，表示有一条有向边从 \(i\) 连向 \(i-1\) ，反之对应。在这张图上，每从一个节点走到另外一个节点上，就会导致整个图上的所有边的方向反转一次。对于每个点，输出他能到达几个点。
这个图显然具有奇偶性。
从左向右，只有 \(RLRLRL......\) 这样的形式才能一直走下去，从右向左则是反过来。
如果暴力判断，复杂度是 \(O(n^2)\) 的，很容易 \(T\)。
显然，我们可以通过一些方法，将复杂度降到 \(O(n)\)，但是我似乎并不是很会（逃
我们可以建立两个图，一个正图一个反图，正图和反图内部没有边，两个图之间互相连边（说白了就是二分图）。
二分图的构造很显然：每个点拆成两个点，然后分列左右，之间根据这个图的关系相互连边（发现其实连的就是无向边）。
对于每个城市，就相当于左边对应的点所在的联通分量的大小。
暴力枚举的复杂度是 \(O(n^2)\) 的，但是好像用 \(Tarjan\) 可以优化。我没学过 \(Tarjan\)，但是这个复杂度应该可以证明是 \(O(n)\) 的。
原文：https://www.cnblogs.com/cyhforlight/p/14353498.html