Codeforces Round #423 (Div. 1)

A. String Reconstruction

题意：给定若干个限制$(S, \left<a_i\right>)$，表示字符串第$a_i$个开始匹配。$S$要求构造一个字典序最小的合法串。
花神游历各国弱化版。用并查集维护下一个没有确定的位置即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
string str[MAXN];
int n;
vector<int> vec[MAXN];
char s[MAXN];
int fa[MAXN];
inline int findf(int nd)
{ return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
void link(int i, int j)
{
    i = findf(i), j = findf(j);
    if (i != j) fa[i] = j;
}
char S[MAXN];
int main()
{
    scanf("%d", &n);
    int max_r = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        str[i] = s;
        int num, d; scanf("%d", &num);
        for (int j = 1; j <= num; j++) {
            scanf("%d", &d);
            vec[i].push_back(d);
        }
        // cerr << vec[i][num-1]+str[i].size()-1 << endl;
        max_r = max(max_r, int(vec[i][num-1]+str[i].size()-1));
    }
    for (int i = 1; i <= max_r; i++) S[i] = '-';
    memset(fa, 0, sizeof fa);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vec[i].size(); j++) {
            int pos = findf(vec[i][j]), pt = pos-vec[i][j];
            while (pt < str[i].size()) {
                S[pos] = str[i][pt];
                if (S[pos-1] != '-') link(pos-1, pos);
                link(pos, pos+1);
                pos = findf(pos), pt = pos-vec[i][j];
            }
        }
    }
    for (int i = 1; i <= max_r; i++) {
        if (S[i] == '-')
            putchar('a');
        else
            putchar(S[i]);
    }
    puts("");
    return 0;
}

B. High Load

题意：构造一个$n$个节点$k$个叶子的树，使得任意两个叶子距离的最大值最小。

当$n-1\le k$时，显然就是搞一个菊花，剩余部分直接连在菊花的根上。

否则安排$k$个节点连接$k$个叶子，递归处理。

#include <bits/stdc++.h>
using namespace std;
int n, k;
const int MAXN = 200005;
struct node {
    int to, next;
} edge[MAXN*2];
int head[MAXN], top = 0;
void push(int i, int j)
{
    edge[++top] = (node) {j, head[i]}, head[i] = top;
} 
int pt_top = 0;
int rt;
void build(int n, vector<int> &leaves)
{
    int k = leaves.size();
    if (n-1 <= k) {
        int L = pt_top;
        rt = pt_top+1;
        for (int i = 2; i <= n; i++) {
            push(pt_top+i, pt_top+1);
            push(pt_top+1, pt_top+i);
        }
        for (int i = 0; i < n-1; i++) {
            push(pt_top+i+2, leaves[i]);
            push(leaves[i], pt_top+i+2);
        }
        for (int i = n-1; i < leaves.size(); i++) {
            push(leaves[i], pt_top+1);
            push(pt_top+1, leaves[i]);
        }
        return;
    }
    for (int i = 0; i < k; i++) {
        push(leaves[i], pt_top+i+1);
        push(pt_top+i+1, leaves[i]);
    }
    for (int i = 0; i < k; i++)
        leaves[i] = pt_top+i+1;
    pt_top += k;
    build(n-k, leaves);
}
int len_eg[MAXN], eg_top = 0;
int x[MAXN], y[MAXN], xy_top = 0;
void dfs(int nd, int f, int dep)
{
    int flag = 1;
    for (int i = head[nd]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == f) continue;
        flag = 0, ++xy_top, x[xy_top] = nd, y[xy_top] = to;
        dfs(to, nd, dep+1);
    }
    if (flag == 1)
        len_eg[++eg_top] = dep;
}
vector<int> vec;
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++) vec.push_back(++pt_top);
    build(n-k, vec);
    dfs(rt, 0, 0);
    sort(len_eg+1, len_eg+eg_top);
    cout << len_eg[eg_top]+len_eg[eg_top-1] << endl;
    for (int i = 1; i <= xy_top; i++)
        printf("%d %d\n", x[i], y[i]);
    return 0;
}

C. DNA Evolution

给定一个只有$ACTG$的字符串，有两种操作：

1. 改变一个位置的字符
2. 询问$l,r,S$，问$Str[l..r]$和$S^{\infty}$的匹配数，$|S|\le 10$。

考虑枚举$S$中每一个位置$t$的贡献，即是在$l..r$中与模$l+t-1$同余位置相同的。只需要用$100$个树状数组大力维护一下...