Educational Codeforces Round 103 (Rated for Div. 2)
A. K-divisible Sum
题意
构造 个正整数，让它们的总和能被 整除。问这些数里的最大值最小能是多少。
思路
每个数至少是 1，所以总和至少是 。先找不小于 的最小 的倍数，再把这个总和尽量均分到 个数里。
均分后最大值就是总和除以 向上取整，用整数除法和余数处理就行，时间 。
代码
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
int T;
ll n, k;
int main() {
cin >> T;
while(T--) {
cin >> n >> k;
ll tmp = n / k;
if(tmp) {
ll t = k;
k *= tmp;
if(n % k) k += t;
}
tmp = k / n;
if(k % n) cout << tmp + 1 << endl;
else cout << tmp << endl;
}
return 0;
}B. Inflation
题意
数组第一项是初始价格，后面每项是当月涨价额。当月涨价额占之前累计价格的比例不能超过 ，可以给数组里的数增加整数，问最少总共加多少。
思路
需要补的数都加到第一项最好，这样能帮到后面的每个月，也不会抬高某个月的涨价额。
前 项的和是 s[i]，要满足下一项的比例，就需要补到 s[i] + x >= ceil(100 * p[i+1] / k)。每个月分别算缺口，取最大值和 0 就行，时间 。
代码
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 117;
int T;
int n, k;
ll p[maxn], m[maxn], s[maxn], ans;
int main() {
cin >> T;
while(T--) {
cin >> n >> k;
ans = 0;
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + p[i];
for(int i = 1; i <= n; i++) m[i] = (p[i + 1] * 100 / k + ((p[i + 1] * 100) % k ? 1 : 0)) - s[i];
for(int i = 1; i < n; i++) if(m[i] < 0) m[i] = 0;
for(int i = 1; i < n; i++) ans = max(ans, m[i]);
cout << ans << endl;
}
return 0;
}C. Longest Simple Cycle
题意
有 条链，第 条有 个点。从第二条开始，把链的两个端点分别连到前一条链的第 个点。问整个图里最长的简单环有多少条边。
思路
先交换一下，统一让 。从左往右扫，l 记已经接到当前链两端之间、绕过前面那些链的最长路径；再加上当前链的 条边，就能闭成一个环。
往下一条链接的时候，要么只用两个连接点之间的这一段，长度是 b[i+1] - a[i+1]；要么沿用前面的路径，绕过当前链两侧，长度是 l + c[i] - 1 - (b[i+1] - a[i+1])。取大的，再加上两条连接边。
如果两个连接点重合，前面的路径就接不过去了，从这里重新开始。每条链只看一次，时间 。
代码
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 17;
int T;
int n;
ll a[maxn], b[maxn], c[maxn], ans;
int main() {
cin >> T;
while(T--) {
cin >> n;
ans = 0;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) if(a[i] > b[i]) swap(a[i], b[i]);
ll l = 0;
for(int i = 1; i < n; i++, l+= 2) {
if(b[i + 1] == a[i + 1]) {
l += c[i] - 1;
if(i != 1) ans = max(l, ans);
l = 0;
continue;
}
if(i > 1) ans = max(ans, l + c[i] - 1);
l += c[i] - 1 - (b[i + 1] - a[i + 1]);
if(b[i + 1] - a[i + 1] > l || i == 1) l = b[i + 1] - a[i + 1];
}
// cout << l << endl;
l += c[n] - 1;
ans = max(l, ans);
cout << ans << endl;
}
return 0;
}D. Journey
题意
一条线上有 座城市，相邻城市之间的路有方向。每走一步，所有道路的方向都会翻转，问分别从每座城市出发，最多能访问多少座不同城市。
思路
道路方向只和已经走了奇数步还是偶数步有关，把每座城市拆成两层就行。一层表示走了偶数步，另一层表示走了奇数步，走一条路时切换层。
一条初始向右的路，把左边的偶数层和右边的奇数层连起来；初始向左就反过来。走过去后道路翻转，马上也能原路返回，所以这些连接可以直接用并查集合并。
在直线上，同一连通块里每座城市只会出现一种奇偶状态，块大小就是能访问的城市数。从每座城市的偶数层查大小即可，时间 。
代码
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 17;
int T;
int n;
int fa[maxn], sz[maxn], p[maxn];
int getf(int x) {
if(fa[x] == x) return x;
return fa[x] = getf(fa[x]);
}
void merge(int x, int y) {
int fx = getf(x), fy = getf(y);
if(fx == fy) return;
fa[fy] = fx, sz[fx] += sz[fy], sz[fy] = 0;
}
int main() {
cin >> T;
while(T--) {
cin >> n;
n++;
string str;
cin >> str;
p[0] = -1, p[n] = -1;
for(int i = 1; i < n; i++) p[i] = str[i - 1] =='L' ? 0 : 1;
for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1, fa[i + n] = i + n, sz[i + n] = 1;
for(int i = 1; i <= n; i++) {
if(p[i - 1] == 0) merge(i - 1 + n, i);
if(p[i] == 1) merge(i + 1 + n, i);
}
for(int i = 1; i <= n; i++) {
cout << sz[getf(i)] << " \n"[i == n];
}
}
return 0;
}