「考试总结」ZROI-21-NOIP冲刺-TEST7 总结

发表于 分类于
ZROI-21-NOIP冲刺-TEST7 总结

#T1 tournament

Time Limit: 1s Memory Limit: 512MiB

#题意简述

Zbox 投资了一家电子竞技俱乐部, 现在这家俱乐部需要参加一个杯赛.

这次的杯赛中总共有 \(2^n(n\leq18)\) 支参赛队伍, 队伍之间的实力差距很大, 不妨认为一场比赛实力较强的队伍必然会获胜.

不妨认为实力最弱的队伍编号为 \(1\)，次弱的编号为 \(2\)，…，最强的编号为 \(2^n\).

赛程如下所示:

序列 \(p_1,p_2,\dots,p_{2^n}\) 将在输入中给出, 每个位置上的数字表示在这个位置上的是编号为这个数字的队伍.

由于 Zbox 非常有钱, 他可以花钱使得他投资的队伍和另一只队伍交换位置(也可以不交换).

现在 Zbox 希望他的队伍能够赢下尽可能多的比赛, 但他却忘了将他投资的队伍编号告诉你, 因此你需要输入对于每个编号的队伍, 进行一次交换位置操作后, 至多能在这场杯赛中赢下几轮.

#大体思路

发现 \(x\) 可以赢 \(i\) 场当且仅当存在一个开始位置为 \(k2^{i}+1(k\in N)\) 的长度为 \(2^i\) 的区间的次大值小于 \(x\)，于是我们可以用 st 表维护出是否存在长度为 \(2^i\) 且起始位置为 \(k2^i+1(k\in N)\) 的区间的次大值为 \(x\)，然后即可得到是否存在长度为 \(2^i\) 且起始位置为 \(k2^i+1(k\in N)\) 的区间的次大值小于等于 \(x\)，然后对于每个数 \(O(1)\) 查询是否存在合法区间次大值小于等于 \(x-1\) 即可，总体时间复杂度为 \(O(n\cdot2^n)\).

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N = 300010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}

int n, lmt, a[N], mx[20][N], sec[20][N], vis[20][N], ans[N];

int main() {
    read(n); lmt = 1 << n;
    for (int i = 1; i <= lmt; ++ i) read(a[i]);
    for (int i = 1; i <= lmt; ++ i) mx[0][i] = a[i], sec[0][i] = -INF;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j + (1 << i) - 1 <= lmt; j += (1 << i)) {
          if (mx[i - 1][j] < mx[i - 1][j + (1 << i - 1)]) {
              mx[i][j] = mx[i - 1][j + (1 << i - 1)];
              sec[i][j] = Max(sec[i - 1][j + (1 << i - 1)], mx[i - 1][j]);
          } else {
              mx[i][j] = mx[i - 1][j];
              sec[i][j] = Max(sec[i - 1][j], mx[i - 1][j + (1 << i - 1)]);
          }
          vis[i][sec[i][j]] |= 1;
      }
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= lmt; ++ j)
        vis[i][j] |= vis[i][j - 1];
    for (int i = 1; i <= lmt; ++ i)
      for (int j = 1; j <= n; ++ j)
        if (vis[j][a[i] - 1]) ans[a[i]] = j;
    for (int i = 1; i <= lmt; ++ i) printf("%d ", ans[i]);
    return 0;
}

#T2 inversion

Time Limit: 1s Memory Limit: 512MiB

#题意简述

给定一个 \(n(n\leq3\times 10^5)\) 个点的树，你可以选定树上任意点为起点，走出一条长度为 \(k(k\leq3\times10^5)\) 的路径，这条路径的贡献是按顺序将这条路径所经过的点的编号排列得到的序列的逆序对数，问整棵树的贡献和。

#大体思路

考虑树上一条长度为 \(k\) 的路径会以两种顺序计算两遍代价，考虑一个长度为 \(k+1\) 序列 \(a_i\) 在正反计算两遍逆序对数会有哪些性质，不难发现，对于数 \(a_i,a_j\)，无序数对 \((a_i,a_j)\) 必然会被计算恰好一次，于是整个序列的贡献便是 \(\binom{k+1}{2}\)。

我们将这个结论放回到树上，也就是对于一个长度为 \(k\) 的路径，它具有 \(k+1\) 个点，正反计算两遍得到的贡献就是 \(\binom{k+1} 2\)，于是我们只需要计算长度为 \(k\) 的路径的个数即可。

这里采用长链剖分进行计算，时间复杂度为 \(O(n)\).

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#define ll long long

const int N = 500010;
const ll MOD = 1e9 + 7;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Edge {int u, v, nxt;} e[N << 2];

int n, head[N], ecnt(1), K;

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

int son[N], mxd[N], *dp[N], buf[N << 3];

void dfs(int x, int fa) {
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == fa) continue; dfs(e[i].v, x);
        if (mxd[e[i].v] > mxd[son[x]]) son[x] = e[i].v;
    }
    mxd[x] = mxd[son[x]] + 1;
}

int *p = buf; ll cnt = 0;

void DP(int x, int fa) {
    dp[x] = p++; dp[x][0] = 1;
    if (son[x]) DP(son[x], x);
    if (mxd[x] > K) (cnt += dp[x][K]) %= MOD;
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == fa || e[i].v == son[x]) continue;
        DP(e[i].v, x);
        for (int j = max(0, K - mxd[x]); j < mxd[e[i].v] && j < K; ++j)
          (cnt += 1ll * dp[e[i].v][j] * dp[x][K - j - 1]) %= MOD;
        for (int j = 1; j <= mxd[e[i].v]; ++j)
          dp[x][j] = (dp[x][j] + dp[e[i].v][j - 1]) % MOD;
	}
}
int main() {
    read(n), read(K);
    for (int i = 1; i < n; ++ i) {
        int u, v; read(u), read(v);
        add_edge(u, v), add_edge(v, u);
    }
    dfs(1, 0), DP(1, 0);
    printf("%lld", cnt * (1ll * (K + 1) * K / 2 % MOD) % MOD);
    return 0;
}

#T3 tree

Time Limit: 1s Memory Limit: 512 MiB

#题意简述

给定一个 \(n(n\leq5\times10^5)\) 个点的基环树，每条边的价值为断开这条边后的树的直径，如果断开后不再连通，那么这条边的价值为 \(-1\)，要求计算所有边的价值。

#大体思路

又是一个考场上想出来没调出来的题QnQ

考虑到树的直径共有两种：一种是不经过环的子树上的直径，另一种经过环。

对于第一种，我们可以直接通过树形 DP 进行计算；而对于第二种，我们考虑断开环上的每一条边后复制一遍，设 \(f_i\) 表示断开 \(i\) 后面的边得到的最大直径，按如下 DP 方程进行计算： \[ f_{i}=\max\limits_{i-len<j<k\leq i}\{g_j+g_k+k-j\}, \] 其中 \(g_x\) 表示以 \(x\) 为根的子树的最大深度，对上面的式子进行变形得到： \[ f_i=\max_{i-len<j<i}\{g_j-j+\max\limits_{j<k\leq i}\{g_k+k\}\}, \] 不难发现上面的式子可以通过同时维护两个单调队列进行优化（注意边界！），整体时间复杂度是 \(O(n)\).

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const int N = 2000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}

struct Edge {int u, v, nxt;} e[N], te[N];

int n, head[N], ecnt(2), vis[N], endpos, pre[N], spc[N], nxt[N];
int ring[N], rcnt, ve[N], f[N], g[N], ans, pos[N];

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

bool get_ring(int x, int fa) {
    vis[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == fa) continue; pre[e[i].v] = i;
        if (vis[e[i].v]) {endpos = e[i].v; return true;}
        if (get_ring(e[i].v, x)) return true; 
    }
    return false;
}

void get_ring_list() {
    int now = endpos;
    do {
        ring[++ rcnt] = now;
        ve[pre[now]] = ve[pre[now] ^ 1] = 1;
        nxt[e[pre[now]].u] = pre[now] / 2;
        now = e[pre[now]].u;
    } while (now != endpos);
    for (int i = 1; i <= rcnt; ++ i)
      ring[i + rcnt] = ring[i];
}

void dp_on_tree(int x, int fa) {
    g[x] = 0, f[x] = 0;
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == fa || ve[i] || ve[i ^ 1]) continue;
        dp_on_tree(e[i].v, x);
        f[x] = Max(f[x], f[e[i].v]);
        f[x] = Max(f[x], g[x] + g[e[i].v] + 1);
        g[x] = Max(g[x], g[e[i].v] + 1);
    }
}

int q1[N], q2[N], frt1 = 0, tal1 = -1, frt2 = 0, tal2 = -1;

int main() {
    read(n);
    for (int i = 1; i <= n; ++ i) {
        read(te[i].u), read(te[i].v);
        add_edge(te[i].u, te[i].v);
        add_edge(te[i].v, te[i].u);
    }
    get_ring(1, 0); get_ring_list(); reverse(ring + 1, ring + rcnt * 2 + 1);
    for (int i = 1; i <= rcnt; ++ i) dp_on_tree(ring[i], 0), ans = Max(ans, f[ring[i]]);
    for (int i = 1; i <= rcnt; ++ i) spc[nxt[ring[i]]] = ans;
    for (int i = 1; i <= rcnt; ++ i) {
        while (frt1 <= tal1 && g[ring[q1[tal1]]] - q1[tal1] < g[ring[i]] - i) -- tal1;
        while (frt2 <= tal2 && g[ring[q2[tal2]]] + q2[tal2] < g[ring[i]] + i) -- tal2;
        q1[++ tal1] = i, q2[++ tal2] = i;
    }
    for (int i = rcnt + 1; i <= rcnt << 1; ++ i) {
        while (frt1 <= tal1 && q1[frt1] <= i - rcnt) ++ frt1;
        while (frt2 <= tal2 && q2[frt2] <= q1[frt1]) ++ frt2;
        while (frt2 <= tal2 && g[ring[q2[tal2]]] + q2[tal2] < g[ring[i]] + i) -- tal2; q2[++ tal2] = i;
        spc[nxt[ring[i]]] = Max(spc[nxt[ring[i]]], g[ring[q1[frt1]]] - q1[frt1] + g[ring[q2[frt2]]] + q2[frt2]);
        while (frt1 <= tal1 && g[ring[q1[tal1]]] - q1[tal1] < g[ring[i]] - i) -- tal1; q1[++ tal1] = i;
    }
    for (int i = 1; i <= n; ++ i)
      if (ve[i << 1]) printf("%d\n", spc[i]);
      else printf("-1\n");
     return 0;
}

#T4 turing machine

Time Limit: 1s Memory Limit: 512MiB

#题意简述

给定程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
read(n);read(T);
for i = 1 to n do
    read(a[i]);//a[i] must be 0 or 1
for t = 1 to T do
begin
    for i = 2 to n do
        do_swap[i]=(a[i-1]==0) and (a[i]==1)
    for i = 2 to n do
        if (do_swap[i]) then
            swap(a[i-1],a[i]);
end
for i = 1 to n do
    write(a[i],' ');

其中 \(n,T\leq10^6\)，优化该程序。

#大体思路

首先理解给定的程序，是对于给定的 01 串，每次将所有前一位是 0 的 1 向前移动一位，问 \(T\) 次变化后的 01 串。

于是我们对每一个 1 进行考虑，考虑他在哪些变化中不会向前移动，显然除了两者开始时相邻的情况外，在左边的 1 不会被阻止的变化，右边的 1 一定也不会在该次变化中被阻止，于是我们可以用队列维护被阻止的次数。开始时所有的变化都在队列中，显然当两者距离大于 \(1\) 时，由于最开始两者同步变化，当前者停下时，两者的距离减一次变化一定不会阻止后者；剩下的部分则是当后者停下后（变化结束后）多余的阻挡和有效的阻挡。整体时间复杂度 \(O(n)\).

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 2000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, m, a[N], q[N], frt, tal = -1, tot;

int main() {
    read(n), read(m);
    for (int i = m - 1; ~i; -- i) q[++ tal] = i;
    for (int i = 1, lst = 0; i <= n; ++ i) {
        int x; read(x); if (!x) continue;
        int len = i - lst - 1; ++ tot;
        q[++ tal] = -tot; tal = max(frt - 1, tal - len);
        while (frt <= tal && q[frt] + tot >= m) ++ frt;
        a[i - m + tal - frt + 1] = 1, lst = i;
    }
    for (int i = 1; i <= n; ++ i) printf("%d ", a[i]);
    return 0;
}