Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
曾经有一棵包含 nn 个节点的无向树。为了让它更有趣，每条无向边都被随意赋予了一个方向，使其变成了一棵有向树。
现在树的结构和边的方向都遗失了，但给出了一份记录了这棵树连通性的矩阵。该连通性矩阵表现为 nn 个长度为 nn 的 01 字符串。如果第 ii 行的第 jj 个字符是 1，则代表在原图中存在一条从节点 ii 到节点 jj 的有向路径；如果是 0 则代表无法到达。（特别地，任何节点都始终可以到达它自身）。
你需要根据给出的连通性矩阵，判断是否存在符合条件的有向树结构。如果存在，请构造并输出任意一种满足条件的边连接方式；如果不存在，则指出无解。

输入格式
第一行包含一个整数 tt (1≤t≤1041 \le t \le 10^4)，表示测试用例的数量。
每个测试用例的第一行包含一个整数 nn (2≤n≤5002 \le n \le 500)，表示树的节点数量。
接下来的 nn 行，每行包含一个长度为 nn 的仅由 0 和 1 组成的字符串。第 ii 个字符串的第 jj 个字符为 1 当且仅当节点 ii 可以到达节点 jj。
保证所有测试用例中 n3n^3 的总和不超过 5003500^3。

输出格式
对于每个测试用例，如果存在满足条件的有向树，输出 Yes（大小写均可），并在随后的 n−1n-1 行中输出你构造的有向边。每行输出两个整数 xx 和 yy，表示存在一条从 xx 指向 yy 的有向边（即 x→yx \to y）。如果有多种合法的树结构，输出其中任意一种即可。
如果不存在满足条件的解，输出 No。

样例输入

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
11
4
1000
1111
1010
0001
4
1111
0111
0010
0111
4
0011
0111
0011
0001
4
1000
0110
0010
1111
4
1000
0110
1010
1111
5
10000
01011
00111
00010
00001
5
10000
11000
10101
10111
00001
5
10000
01101
00100
01110
10001
4
1100
0100
0011
0001
4
1110
0100
0010
0101
3
100
111
101

样例输出

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
Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1

样例说明
对于第一个测试用例，节点 11 和 44 只能到达它们自身；节点 22 可以到达所有节点；节点 33 可以到达节点 11 和 33。构造的有向边为 2→32 \to 3，2→42 \to 4，3→13 \to 1，该结构刚好满足所有可达性限制。
对于第二个测试用例，可以证明不存在任何一种满足给出连通性的树结构。

说白了，就是给你点与点之间的联通情况，你要重建出一颗有向的树，能够满足题目的要求。

思路讲解

如果只是做一个 D1 的话，还是非常 easy 的。

image

只要一个点比如说 6，不出现在其他 2 可达的点中（比如说图上的 4,3,5,1）的可达性表上，那么 2,6 直接相连。（⚠️注意，之所以这么连，是因为如果不连这条边，可达性就无法满足了，我们采用这一策略是为了连最少的边，达到题目要求）

这个做法的正确性是这样的，如果不连我们的算法所选择的边，可达性就无法满足了。如果比我们的这个做法连的边更多，要么你一定会改变这个可达性规律，要么你会把一棵树，变成一个环。多也不行，少也不行，那我们的做法就是正确的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<pair<ll,ll>> edges;
for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    for (auto a:nodes) {
        bool ok=true;
        for (auto b:nodes) {
            if (b==a) continue;
            // 检查是否出现在其他点的可达性表上
            if (Reach[b][a]=='1') {
                ok=false;
                break;
            }
        }
        if (ok) {
            edges.push_back({i,a});
        }
    }
}

当然，最后需要写一个校验程序，也非常 easy 啊，先写一个东西校验这个树结构是否正确，然后再直接跑一遍可达性判断，看看和题目给出的是否一致。

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
do {
    if (SZ(edges)!=N-1) {
        cout<<"No\n";
        return;
    }
    vector<vector<ll>> g(N+2);
    for (auto [u,v]:edges) {
        merge(u,v);
        g[u].push_back(v);
    }
    // 对化为无向图后，树的可达性作校验
    set<ll> st;
    for (int i=1;i<=N;++i) {
        ll fai=find(i);
        st.insert(fai);
    }
    if (SZ(st)!=1) {
        cout<<"No\n";
        return;
    }
    // 直接模拟，校验我们所构造
    vector<vector<char>> R(N+2,vector<char>(N+2,'0'));
    for (int i=1;i<=N;++i) {
        queue<ll> q;
        q.push(i);
        R[i][i]='1';
        while (!q.empty()) {
            ll a=q.front();
            q.pop();
            for (auto v:g[a]) {
                if (R[i][v]=='1') {
                    continue;
                }
                R[i][v]='1';
                q.push(v);
            }
        }
    }
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            if (Reach[i][j]!=R[i][j]) {
                cout<<"No\n";
                return;
            }
        }
    }
}while (false);

AC代码

AC
https://codeforces.com/contest/2208/submission/366753217

心路历程（WA，TLE，MLE……）

Posted on Edited on

基本情况

image

这个打的不算太好。

但是，说实话嘛，这个 C 确实没对上脑电波。 Codeforces Round 1086 (Div. 2)——CF-2208-C. Stamina and Tasks（赛时 AC）（确实，乘法衰减，概率 dp，都是用这个反向居多） 所以说做的比较慢。

这个 A 唐完了，我以为要构造那个矩阵，就过只要判断 yes，no。还因为 > 写成了 ≥ WA 了一发。

image

心得感悟

还是要看清楚是不是需要构造。

Posted on Edited on

题目大意

题目要求总结：

给定多组测试。每组有 n 个任务，必须按编号从 1 到 n 依次处理。你初始体力为 S=1。

对每个任务 i（参数为 c_i, p_i）只有两种选择：

  • 放弃：本任务得分不变，体力不变。

  • 完成：本任务获得 S * c_i 分，然后体力变为S = S * (1 - p_i / 100)。

目标是在处理完所有任务后，使总得分最大。

输入规模：多组数据，sum(n) <= 1e5。

输出要求：每组输出一个实数最大值，误差满足 1e-6 即可。

样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
2
2
10 0
20 5
3
10 5
10 80
20 5

Output
30.0000000000
29.0000000000

样例解释：

  • 第 1 组：做第 1、2 个任务最优。
    第 1 个得 1*10=10，且 p=0 体力不变；第 2 个得 1*20=20；总分 30。

  • 第 2 组：最优是做第 1 个，放弃第 2 个，做第 3 个。
    做完第 1 个后体力 S=1*(1-5/100)=0.95；第 3 个得 0.95*20=19；总分 10+19=29。

思路讲解

这道题目，就是主要要注意到，就是我们不难发现，最后一个数，我们肯定是要选的，因为最后一个数对整体的贡献一定是有的，一定是正的。或者，你可以这样想，我们前面先选了一堆数，那么最后一个数一定是要选的，因为选择他，对你的答案一定是增加的，你也不用考虑后续节点的情况，因为他后面也没有东西了。

我们说白了，选不选一个数，我们就是怕这个后效性嘛，我们直接反过来，直接对所有选择的后缀进行这个乘法衰减。

但是，再前面的数字，那就不一定了，其对整体的贡献，就是新的答案 ans*(100-p)/100.0+A[i].c，如果说比原来的 ans 还小，那就开摆，否则就算了。

1
2
3
4
5
6
for (ll i=N;i>=1;--i) {
    ll c=A[i].c,p=A[i].p;
    if (ans*(100-p)/100.0+A[i].c>ans) {
        ans=ans*(100-p)/100.0+A[i].c;
    }
}

AC代码

AC

https://codeforces.com/contest/2208/submission/366718643

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目描述
定义集合 SS 的 kk-mex 为未在 SS 中出现的第 kk 小的非负整数。例如，集合 [1,2,1][1, 2, 1] 的 11-mex 是 00，22-mex 是 33。

给定一个长度为 nn 的非负整数数组 a1,a2,…,ana_1, a_2, \ldots, a_n。你需要判断是否存在一个非负整数数组 b1,b2,…,bnb_1, b_2, \ldots, b_n（其中 0≤bi≤1090 \le b_i \le 10^9），使得对于所有 1≤i≤n1 \le i \le n，前缀 [b1,…,bi][b_1, \ldots, b_i] 的 (n−i+1)(n-i+1)-mex 恰好等于 aia_i。

如果存在这样的数组，请构造并输出任意一个满足条件的数组 bb；如果不存在，请报告无解。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数 nn（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5），表示数组 aa 的长度。
第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n（0≤ai≤1090 \le a_i \le 10^9）。
保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式
对于每个测试用例，如果存在满足条件的数组 bb，第一行输出 YES（不区分大小写），第二行输出 nn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_n（0≤bi≤1090 \le b_i \le 10^9）。
如果不存在，仅输出一行 NO。

样例数据

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
Input:
6
3
3 3 1
3
2 1 3
1
0
1
2
4
7 5 2 2
6
6 6 6 4 3 3

Output:
YES
2 0 2
NO
YES
67
NO
NO
YES
5 2 1 5 2 0

样例解释
在第一组测试用例中，a=[3,3,1]a = [3, 3, 1]。我们可以验证数组 b=[2,0,2]b = [2, 0, 2] 满足条件：

  • 当 i=1i=1 时，需要计算前缀 [b1]=[2][b_1] = [2] 的 (3−1+1)(3-1+1) 即 33-mex。未在数组中出现的非负整数依次为 0,1,3,4,…0, 1, 3, 4, \dots，其中第 33 小的是 33，等于 a1a_1。

  • 当 i=2i=2 时，需要计算前缀 [b1,b2]=[2,0][b_1, b_2] = [2, 0] 的 (3−2+1)(3-2+1) 即 22-mex。未在数组中出现的非负整数依次为 1,3,4,…1, 3, 4, \dots，其中第 22 小的是 33，等于 a2a_2。

  • 当 i=3i=3 时，需要计算前缀 [b1,b2,b3]=[2,0,2][b_1, b_2, b_3] = [2, 0, 2] 的 (3−3+1)(3-3+1) 即 11-mex。未在数组中出现的非负整数依次为 1,3,4,…1, 3, 4, \dots，其中第 11 小的是 11，等于 a3a_3。

在第二组测试用例中，a=[2,1,3]a = [2, 1, 3]。可以证明不存在任何满足条件的数组 bb，因此输出 NO。

在第三组测试用例中，a=[0]a = [0]。构造 b=[67]b = [67] 满足条件，因为前缀 [b1]=[67][b_1] = [67] 的 11-mex 是 00，恰好等于 a1a_1。

思路讲解

首先，需要这样子想，每一个 a 代表什么？可以这样子想：

image

不难发现：（使用归纳法）

image

当然，我们可以换成这个 i。

image

为什么可以 = 呢？

image

其实这个规律还是没有那么难以观察出来的，毕竟这个 a1 代表第 n 个空，a2 代表第 n-1 个空，你也很难想象第 n-1 个空在第 n 个空后面是吧？

我觉得上面 AI 的这个角度还是挺好的，但是我其实觉得稍微有点扯。

然后我们还是没有想到怎么做？那应该是对 a 的性质探索的还不够多！（继续沿着探索 a 的性质的这条路走）

其实光有这个递减性质，其实还是不够的，我们不妨多探索一些性质，比如说 ai+1 其取值范围到底是在哪里？

image

image

通过上面的推导，我们不难得出如下结论：

image

这道题目，我们的做法需要用到 dsu on next 技巧。那么要注意这个合并方向。

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
vector<ll> B(N + 2);
ll cur;
vector<ll> wp;
ll top_b = 0;
for (int i = 1; i <= N; ++i) {
  // 我觉得一般来说，你还是不要用哨兵节点，老老实实特判比较好，确保初值正确
    if (i == 1) {
        if (A[i] > N) {
            cout << "NO\n";
            return;
        }
        if (A[i] == N) {
            wp.push_back(i);
            cur = N;
        } else if (A[i] == N - 1) {
            B[i] = mod;
            cur = N - 1;
        } else {
            cout << "NO\n";
            return;
        }
        merge(A[i], A[i] - 1);
        continue;
    }
    if (A[i] == cur) {
      // wp 存储的就是我们存下来的，等待填充的 B 数组中的位置
        wp.push_back(i);
    } else {
        ll fcur = find(cur);
        if (fcur < A[i]) {
            cout << "NO\n";
            return;
        }
        // 之所以要 merge A[i] 和 A[i-1]，是因为 A[i] 是一个空，也不要填充 b 了。
        merge(A[i], A[i] - 1);
        for (ll j = fcur; j > A[i]; --j) {
            merge(j, j - 1);
            if (wp.empty()) {
                cout << "NO\n";
                return;
            }
            B[wp.back()] = j;
            wp.pop_back();
        }
        cur = A[i];
        B[i] = mod;
    }
}
while (!wp.empty()) {
    if (!merge(top_b, top_b - 1)) {
        cout << "NO\n";
        return;
    }
    B[wp.back()] = top_b;
    wp.pop_back();
    top_b++;
}
cout << "YES\n";
for (int i=1;i<=N;++i) {
    cout<<B[i]<<" ";
}

AC代码

AC
https://codeforces.com/contest/2207/submission/367198322

心路历程（WA，TLE，MLE……）

对拍拍出来的数据。

1
2
3
4
1
4
4 4 3 1

Posted on Edited on

【G09 筛法求欧拉函数】 https://www.bilibili.com/video/BV1VP411p7Bs/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

image

这个对的原因是，显然，和 pkp^k 不互素的只有 p 的倍数，因此就是 ϕ(pk)=pk−(p的倍数的数量)\phi(p^k)=p^k-(p 的倍数的数量)。

1⋅p,2⋅p,3⋅p,4⋅p,5⋅p,6⋅p,…,(pk−1−2)⋅p,(pk−1−1)⋅p,pk−1⋅p1 \cdot p,\quad 2 \cdot p,\quad 3 \cdot p,\quad 4 \cdot p,\quad 5 \cdot p,\quad 6 \cdot p,\quad \ldots,\quad (p^{k-1} - 2) \cdot p,\quad (p^{k-1} - 1) \cdot p,\quad p^{k-1} \cdot p

p 的倍数的系数可以从 11 一直取到 pk−1p^{k-1}，所以一共 pk−1p^{k-1} 个。最后一项 pk−1⋅p=pkp^{k-1} \cdot p = p^k，刚好是上界。

因此 ϕ(pk)=pk−pk−1\phi(p^k)=p^k-p^{k-1}。

有了上面的这个公式，就不难推出如下式子。

image

其实这个式子，形象化的理解，就是不断的把 n 里面，p 的倍数（p 都是质数，因此倍数与倍数之间互不干扰）给筛掉。

当然，如果进行朴素相减，会出现问题。

image

不过，那为什么乘积不会出现这个问题呢？答案就是容斥原理。

image

这就是乘法的容斥原理。因为乘法的本质就是在枚举子集，只要一个负号，让其符合这个容斥原理的奇减偶加特性即可。

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

/*
 * 试除法求一个数的欧拉函数（也就是求 [1,n] 内与其互素的数的个数）
 * 2026-03-13: AC https://codeforces.com/gym/106380/submission/366492238
 */
long long euler_phi(long long n) {
    long long res = n;
    // p 从 2 开始，逐个递增，试到 sqrt(n) 为止
    for (long long p = 2; p * p <= n; p++) {
        // 如果 p 能整除 n，那么 p 一定是质数。
        // 为什么？因为如果 p 是合数，比如 p = 6 = 2 × 3，
        // 那么在 p=2 和 p=3 的时候，n 中的 2 和 3 已经被除干净了，
        // 此时 n 不可能被 6 整除，所以 n % 6 != 0，这个 if 进不来。
        // 因此能进到这个 if 里的 p，一定是质因子。
        if (n % p == 0) {
            // 发现质因子 p，对 res 乘上 (1 - 1/p) 这个因子
            // 即 res = res / p * (p - 1)
            res = res / p * (p - 1);
            // 把 n 中所有的 p 除干净
            // 这样后续更大的 p 的倍数就不可能再整除 n 了
            while (n % p == 0) n /= p;
        }
    }
    // 循环结束后，如果 n > 1，说明 n 还剩一个大于 sqrt(原始n) 的质因子
    // （一个数最多只有一个大于 sqrt 的质因子）
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

image

那么都有上面的，非常符合直觉的计算公式了，我们也是非常 easy 的能够证明这个东西。

image

只要把这个东西全部列出来，就非常容易的可以证明。当然，要求 n，m 互素，否则他们的质数项一定会有交集，那么就失效了，积性函数性质。

image

这是 Euler 定理（欧拉定理）。

对于任意正整数 mm 和整数 aa，若 gcd⁡(a,m)=1\gcd(a, m) = 1，则

aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}

image

证明：考虑模 mm 的缩系（即 11 到 mm 中所有与 mm 互素的数构成的集合 SS，共 φ(m)\varphi(m) 个元素）。当 gcd⁡(a,m)=1\gcd(a, m) = 1 时，把 SS 中每个元素都乘以 aa，得到的集合模 mm 后恰好还是 SS（因为乘以 aa 是模 mm 缩系上的一个双射）。于是把所有元素的乘积写出来：

∏x∈S(ax)≡∏x∈Sx(modm)\prod_{x \in S} (ax) \equiv \prod_{x \in S} x \pmod{m}

左边提出 aa：

aφ(m)×∏x∈Sx≡∏x∈Sx(modm)a^{\varphi(m)} \times \prod_{x \in S} x \equiv \prod_{x \in S} x \pmod{m}

因为 ∏x∈Sx\prod_{x \in S} x 与 mm 互素（因为 SS 中每个元素都与 mm 互素，这里我们用到了 S 的定义）（说白了，只要是除数和 m 互素，就有逆元，就可以除），可以两边消掉，就得到 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}。

它的特殊情况是 Fermat 小定理：当 m=pm = p 为素数时，φ(p)=p−1\varphi(p) = p - 1，即 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}。