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

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

#T1 史上最简洁的题面

#题意简述

给定一个 \(n(n\leq 25)\) 个点 \(m(m\leq\frac{n(n-1)}{2})\) 条边的无向图，对于每一个在 \([0,m]\) 内的 \(i\)，求有多少中黑白染色方案使得有 \(i\) 条边两端的点都是黑色的。

#大体思路

考虑枚举当前图中被染黑的点，计算这张图中的黑边（两段点都是黑点的边）的个数，注意到如果被染黑的点确定，那么不管最后被染黑的点是哪一个，最终黑边的个数都是一定的。

以二进制状态表示当前哪些点染黑了、哪些点没被染黑，设当前状态为 \(x\)，不妨令该图中最后一个被染黑的点是 \(u=pos(lowbit(x))\)，\(pos(x)\) 表示 \(x\) 在二进制表示下的位数；再来考虑会有哪些边被染成黑色：\((u,v)\in E\) 且 \(v\) 已经被染黑；我们容易得到 \(u\) 的连边情况，用二进制表示出来，与 \(x\) 做 \(\text{and}\) 运算得到的结果的 \(1\) 的个数就是新加入的边的个数，转移即可。可以用 bitset 进行优化，时间复杂度为 \(O(\dfrac{n\cdot2^n}w)\).

#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
const int N = 1010;
const int M = 4e7;
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;
}

bitset <30> p[N];

int n, m, cnt[N], f[M], pos[M];

#define lowbit(x) (-(x)&(x))

int main() {
    read(n), read(m);
    for (int i = 0; i < n; ++ i)
      pos[(1 << i)] = i + 1;
    for (int i = 1; i <= m; ++ i) {
        int u, v; read(u), read(v);
        p[u][v] = 1, p[v][u] = 1;
    }
    for (int i = 1; i <= n; ++ i) p[i] >>= 1;
    f[0] = 0; cnt[0] = 1;
    for (int i = 1; i < (1 << n); ++ i) {
        int t = i, lt = pos[lowbit(i)];
        bitset <30> bt(t);
        bt &= p[lt]; t -= lowbit(i);
        f[i] = f[t] + bt.count(); ++ cnt[f[i]];
    }
    for (int i = 0; i <= m; ++ i)
      printf("%d ", cnt[i]);
    return 0;
}

#T2 史上第二简洁的题面

#题意简述

给定一个长度为 \(n(n\leq10^5)\) 的序列 \(a(a_i\leq10^5)\)，给定 \(m(m\leq10^5)\) 个询问 \(l,r,x\)，求 \(a_l,a_{l+1},\dots,a_r\) 中有多少个数与 \(x(x\leq10^5)\) 互质。

#大体思路

考虑莫比乌斯反演： \[ [(a_i,x)=1]=\sum\limits_{d|(a_i,x)}\mu(d)=\sum\limits_{d|a_i,d|x}\mu(d), \] 于是有 \[ \begin{aligned} &\sum\limits_{i=l}^r[(a_i,x)=1]=\sum\limits_{i=l}^r\sum\limits_{d|a_i,d|x}\mu(d)=\sum\limits_{d|x}\mu(d)\sum\limits_{i=l}^r[d|a_i]\\ =&\sum\limits_{d|x}\mu(d)\cdot(sum_r-sum_{l-1})=\sum\limits_{d|x}\mu(d)\cdot sum_{d,r}-\sum\limits_{d|x}\mu(d)\cdot sum_{d,l-1} \end{aligned} \] 其中 \(sum_{d,x}\) 表示 \(a_1,a_2,\dots,a_x\) 中 \(d\) 的倍数的个数。

于是我们可以将原本的一个询问拆成两个，然后将这 \(2m\) 个询问按右端点排序，依次处理。时间复杂度为 \(O((n+m)\sqrt{a_{MAX}})=O(n\sqrt 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
const int N = 200010;

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;}
template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

struct Query {int op, r, x, id;} q[N];

int n, m, a[N], mu[N], prm[N], pcnt, nprm[N], sum[N], ans[N];

vector <int> P[N];

void euler(int x) {
    mu[1] = 1;
    for (int i = 2; i <= x; ++ i) {
        if (!nprm[i]) prm[++ pcnt] = i, mu[i] = -1;
        for (int j = 1; j <= pcnt; ++ j) {
            if (prm[j] * i > x) break;
            nprm[prm[j] * i] = true;
            if (i % prm[j]) mu[i * prm[j]] = -mu[i];
            else break;
        }
    }
}

inline bool cmp(Query x, Query y) {return x.r < y.r;}

#define pbk(x) push_back(x)

inline void get_list(int x) {
    if (P[x].size()) return;
    for (int i = 1; i * i <= x; ++ i) if (!(x % i)) {
        P[x].pbk(i); if (i != x / i) P[x].pbk(x / i);
    }
}

int main() {
    read(n); read(m); euler(N >> 1);
    for (int i = 1; i <= n; ++ i) read(a[i]);
    for (int i = 1; i <= m; ++ i) {
        int l, r, x; read(l), read(r), read(x);
        q[(i << 1) - 1] = (Query){-1, l - 1, x, i};
        q[(i << 1)] = (Query){1, r, x, i};
    }
    sort(q + 1, q + (m << 1) + 1, cmp);
    for (int i = 1, j = 1; i <= m << 1; ++ i) {
        for (; j <= n && j <= q[i].r; ++ j) {
            get_list(a[j]);
            for (auto k : P[a[j]]) ++ sum[k];
        }
        get_list(q[i].x);
        for (auto k : P[q[i].x])
          ans[q[i].id] += q[i].op * mu[k] * sum[k];
    }
    for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
    return 0;
}

#T3 史上第三简洁的题面

#题意简述

有 \(n(n\leq 2000)\) 个人排成一排，从左到右编号为 \(1,\dots,n\)，接下来你每次可以指定两个相邻的人战斗，输的一方将会离开队伍，直到最后只有一个人留在队伍里，这个人将会称为最后的赢家。你知道任意两个人打谁会赢，求哪些人可能会成为最后的赢家。

#大体思路

考虑一个人 \(x\) 在 \([l,r]\) 能获胜当且仅当能在 \([l, x]\) 获胜且能在 \([x,r]\) 获胜。

设 \(lasL_x\) 表示在当前区间长度下，\(x\) 作为左端点，作为右端点可以获胜的点的集合，\(lasR_x\) 意义类似。设当前区间为 \([l,r]\)，则该区间内可以获胜的人是 \(lasL_l\cap lasR_R\).

每次将当前区间向左/右扩展一位，维护转移即可。时间复杂度 \(O(n^3)\)，发现转移可以用 bitset 优化，时间复杂度为 \(O(\dfrac {n^3} w)\).

#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
const int N = 2010;
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; char s[N];

bitset <N> mp[N], beat[N], res, lasL[N], lasR[N];

int main() {
    read(n);
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; ++ j)
          beat[i][j] = s[j] ^ 48;
    }
    for (int i = 1; i <= n; ++ i)
      lasL[i][i] = 1, lasR[i][i] = 1;
    for (int len = 1; len < n; ++ len)
      for (int l = 1, r = len; r <= n; ++ l, ++ r) {
          res = lasL[l] & lasR[r];
          if (r != n && (beat[r + 1] & res).any())
            lasL[l][r + 1] = 1;
          if (l != 1 && (beat[l - 1] & res).any())
            lasR[r][l - 1] = 1;
      }
    res = lasL[1] & lasR[n];
    for (int i = 1; i <= n; ++ i)
      if (res[i]) printf("%d ", i);
    return 0;
}

#T4 史上第四简洁的题面

#题意简述

给定一张 \(n(n\leq10^6)\) 个点 \(m(m\leq2\times10^6)\) 条带权边 \((w_i\leq10^9)\) 的无向图，指定一个终点 \(V\)，有一条边不能通行，但不知道是哪一条，问对于图中的所有点，在最优策略下最坏情况到达 \(v\) 经过边的边权和。

#大体思路

“最优策略”即为走最短路，于是“最坏情况”一定是不能通行的边是最短路树上的边，于是我们可以求得断掉最短路树上 \(x\) 向父亲的边时的最短路径 \(val_x\)，设答案为 \(f_x\)，那么有 \[ \begin{aligned} f_v&=\max\{val_v,\min\limits_{(u,v)\in E}\{f_u+w(i,v)\}\}\\ &=\min\limits_{(u,v)\in E}\{\max\{val_v,f_u+w(i,w)\}\}, \end{aligned} \] 这个式子类似于求最短路的式子，用类似 dijkstra 的算法处理一下就可以得到。

我们的复杂度瓶颈是求 \(val_x\)，直接断开最短路树上的边计算的时间复杂度是 \(O(n^2\log n)\)，考虑优化。

我们考虑最短路树，当从多条边到 \(x\) 得到的距离都是最小距离时，只保存一条作为树边。不难发现，断掉 \(x\) 向父亲的边后，\(x\) 的最短路最多只经过一条非树边，于是我们可以考虑对于每一条非树边 \((u,v)\)，有哪些点会在向父亲的边被断开后将 \((u,v)\) 作为惟一的非树边经过。注意到 \(x\) 经过非树边 \((u,v)\) 的后距离是 \(dis_u+dis_v+w(u,v)-dis_x\)，且 \(x\) 必然在 \(u\) 从最短路树上到 \(v\) 的路径上，且不是 LCA，于是我们设计出一下维护方法：

对于非树边 \((u,v)\)，我们将 \(dis_u+dis_v+w(u,v)\) 作为它的新的权值，从小到大排序，在最短路树上对 \(u\to v\) 的路径进行并查集合并，同时修改对应的 \(val\)，注意不能更新 LCA 的 \(val\)，每个点最多被更新一次，时间复杂度为 \(O(n)\).

于是总体时间复杂度为 \(O((n+m)\log 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#define ll long long
#define plli pair <long long, int>
#define mp(a, b) make_pair(a, b)
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 1000010;
const int M = 2000010;
const ll INF = 1e17;

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;}
template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

struct Edge {int u, v, nxt, tag; ll w, val;} e[M << 1], et[M << 1];

int n, m, head[N], ecnt(2), ect2(1);

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

priority_queue <plli > q;

int vis[N]; ll dis[N];

void dijkstra(int u) {
    mset(vis, 0); mset(dis, 0x3f);
    dis[u] = 0; q.push(mp(0, u));
    while (q.size()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue; vis[x] = true;
        for (int i = head[x]; i; i = e[i].nxt)
          if (dis[e[i].v] > dis[x] + e[i].w) {
              dis[e[i].v] = dis[x] + e[i].w;
              q.push(mp(-dis[e[i].v], e[i].v));
          }
    }
}

int fath[N], dep[N], fa[N]; ll val[N], f[N];

inline int find(int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}

void get_info(int x, int father) {
    fath[x] = father, dep[x] = dep[father] + 1, vis[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt) {
        if (vis[e[i].v] || dis[e[i].v] != dis[x] + e[i].w) continue;
        e[i].tag = 1; get_info(e[i].v, x);
    }
}

inline ll calc(int k) {return dis[e[k].u] + dis[e[k].v] + e[k].w;}

void mark(int k) {
    int u = et[k].u, v = et[k].v; ll w = et[k].val;
    if (!dep[u] || !dep[v]) return;
    u = find(u), v = find(v);
    while (u != v) {
        if (dep[u] < dep[v]) swap(u, v);
        val[u] = w, fa[u] = fath[u]; u = find(u);
    }
}

void get_ans(int u) {
    while (q.size()) q.pop();
    mset(vis, 0); mset(f, 0x3f);
    f[u] = 0; q.push(mp(0, u));
    while (q.size()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue; vis[x] = true;
        for (int i = head[x]; i; i = e[i].nxt) if (!vis[e[i].v])
          if (f[e[i].v] > Max(val[e[i].v], f[x] + e[i].w)) {
              f[e[i].v] = Max(val[e[i].v], f[x] + e[i].w);
              q.push(mp(-f[e[i].v], e[i].v));
          }
    }
}

signed main() {
    int st; read(n), read(m), read(st);
    for (int i = 1; i <= m; ++ i) {
        int u, v; ll w; read(u), read(v), read(w);
        add_edge(u, v, w), add_edge(v, u, w);
    }
    dijkstra(st); mset(vis, 0); get_info(st, 0);
    for (int i = 2; i < ecnt; i += 2) {
        if (e[i].tag || e[i ^ 1].tag) continue;
        et[ect2] = e[i]; et[ect2 ++].val = calc(i);
    }
    auto cmp = [](Edge x, Edge y){return x.val < y.val;};
    sort(et + 1, et + ect2, cmp); mset(val, 0x3f); 
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    for (int i = 1; i < ect2; ++ i) mark(i);
    for (int i = 1; i <= n; ++ i) val[i] -= dis[i];
    get_ans(st);
    for (int i = 1; i <= n; ++ i)
      printf("%lld ", f[i] > INF / 10 ? -1 : f[i]);
    return 0;
}