题目链接：https://codeforces.com/contest/1029
A - Many Equal Substrings
题意：给一个长度为 (n(1leq nleq50)) 的字符串 (t) ，和一个正整数 (k(1leq kleq50)) ，要求构造一个最短的字符串 (s) ，使得 (t) 在 (s) 中恰好出现 (k) 次。
题解：看起来就像KMP算法，来个 (O(n^3)) 的做法就可以了，枚举重叠部分的两个开始位置，然后判断是否重叠，用此找出最长的重叠位置。但是直接复制一个前缀函数来用最简单。
在模板中提供的前缀函数是要求从0开始的，而 (pi(n)) 即为整个字符串除去字符串本身的首尾重叠的最长长度。
注意留够空间。
int pi[3005];
void GetPrefixFunction(char *s, int sl) {
pi[0] = 0, pi[1] = 0;
for(int i = 1, k = 0; i < sl; ++i) {
while(k && s[i] != s[k])
k = pi[k];
pi[i + 1] = (s[i] == s[k]) ? ++k : 0;
}
}
char s[3005];
void test_case() {
int n, k;
scanf("%d%d%s", &n, &k, s);
GetPrefixFunction(s, n);
int p = pi[n];
int top = n;
--k;
while(k--) {
for(int i = 0; i < n - p; ++i) {
s[top] = s[top - (n - p)];
++top;
}
}
s[top] = ' ';
puts(s);
}
B - Creating the Contest
题意：给一个长度为 (n(1leq n leq 2cdot 10^5)) 的严格单调递增的数列，要求从中选出若干个数，使得除了最大的那个数外，每个数都存在一个比它大且不超过它的两倍的数。
题解：很显然最容易满足“比某个数大且不超过它的两倍”的是它的下一个数，意思是一旦断掉就要重新开始咯。
int a[200005];
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int ans = 1, cur = 1;
for(int i = 2; i <= n; ++i) {
if(a[i] > a[i - 1] * 2)
cur = 1;
else {
++cur;
ans = max(ans, cur);
}
}
printf("%d
", ans);
}
C - Maximal Intersection
题意：给 (n(2leq n leq 3cdot 10^5)) 条线段，移除恰好一条线段使得剩下的 (n-1) 条线段的交尽可能长。
题解：上次不是做过一个矩形版的吗？我还是用扫描线做的。这个直接维护线段的前缀交和后缀交就可以了。
int l[300005], r[300005];
int pl[300005], pr[300005];
int sl[300005], sr[300005];
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d%d", &l[i], &r[i]);
pl[0] = -INF, pr[0] = INF;
for(int i = 1; i <= n; ++i) {
pl[i] = max(pl[i - 1], l[i]);
pr[i] = min(pr[i - 1], r[i]);
}
sl[n + 1] = -INF, sr[n + 1] = INF;
for(int i = n; i >= 1; --i) {
sl[i] = max(sl[i + 1], l[i]);
sr[i] = min(sr[i + 1], r[i]);
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
int L = max(pl[i - 1], sl[i + 1]);
int R = min(pr[i - 1], sr[i + 1]);
//printf("L=%d R=%d
", L, R);
ans = max(ans, R - L);
}
printf("%d
", ans);
}
D - Concatenated Multiples
题意：给 (n(2leq n leq 2cdot 10^5)) 个正整数和一个正整数 (k) ，求有多少个有序数对 ((i,j) (i eq j)) 使得第 (i) 个数后面接上第 (j) 个数之后被 (k) 整除。
题解：处理出每个数模 (k) 的余数，分长度存储在map里面。然后枚举第一个数和第二个数的长度（第一个数左移的量），就可以在对应的map里面查到有多少个数满足题意了。最后把 ((i,i)) 的情况去掉。
注意：1e9接在1e9后面是大概1e19，会溢出。要考虑模运算对四则运算的等价变换。
int a[200005];
map<int, int> m[11];
int GetLen(int x) {
int len = 1;
while(x >= 10) {
x /= 10;
++len;
}
return len;
}
ll GetXX(int x, int len, int k) {
ll cur = 1;
while(len--)
cur *= 10;
cur += 1;
cur %= k;
cur *= x;
cur %= k;
return cur;
}
void test_case() {
int n, k;
scanf("%d%d", &n, &k);
ll ans = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
int len = GetLen(a[i]);
m[len][a[i] % k]++;
if(GetXX(a[i], len, k) == 0)
--ans;
}
for(int i = 1; i <= n; ++i) {
ll cur = a[i];
for(int j = 1; j <= 10; ++j) {
cur *= 10;
cur %= k;
int t = (k - cur) % k;
auto it = m[j].find(t);
if(it != m[j].end())
ans += (*it).second;
}
}
printf("%lld
", ans);
}
E - Tree with Small Distances
题意：给一棵 (n(1 leq n leq 2 cdot 10^{5})) 个节点的无权无向树，加入尽可能少的边，使得从节点1出发到达各个节点的距离不超过2。
题解：显然这些边都应该从节点1出发。和官方题解一样想了一个理所当然的贪心。首先以节点1为根节点，处理这棵树的各个距离>2的叶子，这些叶子是必定要去除的，方法只有两种，要么直接连接(1,l)，这样最多只能把叶子的父亲pl也去除；要么连接(1,pl)，可以把pl关联的点全部去除。
官方题解中具体的实现，就是要把所有等待去除的点加入set，然后取出距离最远的点x，这个x肯定是当前剩余树的“叶子”，把x的父亲px关联的点全部去掉。
但是其实没必要选择最深的叶子，随便哪个叶子都是一样的。那么在dfs的时候进行后序遍历就可以先让叶子们逐个被处理，那么复杂度就是 (O(n)) 。
vector<int> G[200005];
int P[200005];
queue<int> Q;
bool vis[200005];
void dfs(int u, int p, int dep) {
P[u] = p;
for(auto &v : G[u]) {
if(v == p)
continue;
dfs(v, u, dep + 1);
}
if(dep > 2)
Q.push(u);
}
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1, 0);
int cnt = 0;
while(!Q.empty()) {
int u = Q.front();
Q.pop();
if(vis[u])
continue;
++cnt;
int p = P[u];
vis[p] = 1;
for(auto &v : G[p])
vis[v] = 1;
}
printf("%d
", cnt);
}
F - Multicolored Markers
题意：给 (a(1 leq a leq 10^{14})) 个红色小正方形，给 (b(1 leq b leq 10^{14})) 个蓝色小正方形，要求用光所有的小正方形，拼一个最小周长的红蓝长方形，且满足：红色连成长方形或蓝色连成长方形。
题解：枚举 (a) 的因子和 (b) 的因子存下来，再枚举 (n=a+b) 的因子 (d) ，考虑把红色的放进 ({d,frac{n}{d}}) 的长方形中，容易贪心知道肯定是短边对短边、长边对长边容易符合，这个可以（均摊） (O(1)) 维护。蓝色同理。
vector<ll> faca, facb;
void test_case() {
ll a, b;
scanf("%lld%lld", &a, &b);
ll n = a + b;
ll ans = LINF;
for(ll i = 1; i * i <= a; ++i) {
if(a % i == 0)
faca.push_back(i);
}
for(ll i = 1; i * i <= b; ++i) {
if(b % i == 0)
facb.push_back(i);
}
int pa = 0, pb = 0;
for(ll i = 1; i * i <= n; ++i) {
if(n % i == 0) {
while(pa + 1 < faca.size() && faca[pa + 1] <= i)
++pa;
while(pb + 1 < facb.size() && facb[pb + 1] <= i)
++pb;
//printf("pa=%d pb=%d
", pa, pb);
//printf("a=%lld b=%lld
", faca[pa], facb[pb]);
if(faca[pa] <= i && a / faca[pa] <= n / i || facb[pb] <= i && b / facb[pb] <= n / i)
ans = min(ans, i + n / i);
//printf("i=%lld ans=%lld
", i, ans);
}
}
printf("%lld
", 2 * ans);
}