Znzryb's Blog
0%

Posted on

基本情况

乱打的，比较狗屎了。

image

心得感悟

感觉还是要做中国的省赛，感觉中国的题目和国外的题目还是风格有所不同吧。

题目 I take from the richer

就是这个排序一遍以后直接模拟。

不难发现，肯定是先选小的数，因为先选大的数，小的数就没法贡献了。

这种一定要小心这个加上一个负数，要用这个 max 0ll 去兜底。

image

https://codeforces.com/gym/106380/submission/366235168

题目 Just reseat!

模拟题，不多说了。

https://codeforces.com/gym/106380/submission/366229614

题目 Do you play Ballance?

直接分类讨论。

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<A_b_c> A(N+2);
vector<ll> cnt(10);
for (int i=1;i<=N;++i) {
    ll a,b,c;
    cin>>a>>b>>c;
    A[i]={a,b,c};
    if (A[i]==A_b_c{1,0,0}) {
        cnt[1]++;
    }else if (A[i]==A_b_c{0,1,0}) {
        cnt[2]++;
    }else if (A[i]==A_b_c{0,0,1}){
        cnt[3]++;
    }
}
if (cnt[1] && cnt[2] && cnt[3]) {
    cout<<3<<"\n";
    return;
}
for (int i=1;i<=N;++i) {
    if (A[i]==A_b_c{1,0,0}) {

    }else if (A[i]==A_b_c{0,1,0}) {

    }else if (A[i]==A_b_c{0,0,1}){

    }else {
        if (A[i].a && cnt[1]) {
            ++cnt[1];
        }else if (A[i].b && cnt[2]) {
            ++cnt[2];
        }else if (A[i].c && cnt[3]) {
            ++cnt[3];
        }else if (A[i]==A_b_c{1,1,0}) {
            ++cnt[4];
        }else if (A[i]==A_b_c{1,0,1}) {
            ++cnt[5];
        }else if (A[i]==A_b_c{0,1,1}) {
            ++cnt[6];
        }else if (A[i]==A_b_c{1,1,1}) {
            ++cnt[7];
        }
    }
}
ll ans1=ll(bool(cnt[1]))+ll(bool(cnt[2]))+ll(bool(cnt[3]));
ll ans2=ll(bool(cnt[4]))+ll(bool(cnt[5]))+ll(bool(cnt[6]));
ll ans=ans1;
if (ans1) {
    if (ans2) {
        ++ans;
    }
}else {
    if (ans2<=2) {
        ans=1;
    }else {
        ans=2;
    }
}
if (ans==0 && cnt[7]) {
    ++ans;
}
cout<<ans<<"\n";

https://codeforces.com/gym/106380/submission/366228036

Posted on Edited on

题目大意

题目描述
Capoo 的初始 rating 为 x=0x=0。
现在有 nn 场比赛，对于第 ii 场比赛，它的难度为 aia_i，隐藏分数为 bib_i。每场比赛最多只能参加一次。
只有当当前 rating x≤aix \le a_i 时，Capoo 才能参加第 ii 场比赛。参加完该场比赛后，Capoo 的 rating 将会更新为 max⁡(bi,x)\max(b_i, x)。
你可以自由安排参加这 nn 场比赛的顺序，求 Capoo 最多能参加多少场比赛。

输入格式
第一行包含一个整数 nn（1≤n≤1061 \le n \le 10^6）。
接下来的 nn 行，每行包含两个整数 aia_i 和 bib_i（0≤ai,bi≤10180 \le a_i, b_i \le 10^{18}），分别表示第 ii 场比赛的难度和隐藏分数。

输出格式
输出一行一个整数，表示 Capoo 最多能参加的比赛场数。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
10
19 18
6 15
5 8
4 20
18 3
16 9
0 7
5 17
2 13
15 17

输出:
5

样例解释

注意，这个人比较喜欢挑战这个难题。
一种最多参加 55 场比赛的合法顺序如下：

  1. 初始时 x=0x = 0。

  2. 参加第 77 场比赛（a7=0,b7=7a_7=0, b_7=7）：满足 x≤a7x \le a_7（0≤00 \le 0），参加后 xx 更新为 max⁡(0,7)=7\max(0, 7) = 7。

  3. 参加第 55 场比赛（a5=18,b5=3a_5=18, b_5=3）：满足 x≤a5x \le a_5（7≤187 \le 18），参加后 xx 更新为 max⁡(7,3)=7\max(7, 3) = 7。

  4. 参加第 66 场比赛（a6=16,b6=9a_6=16, b_6=9）：满足 x≤a6x \le a_6（7≤167 \le 16），参加后 xx 更新为 max⁡(7,9)=9\max(7, 9) = 9。

  5. 参加第 1010 场比赛（a10=15,b10=17a_{10}=15, b_{10}=17）：满足 x≤a10x \le a_{10}（9≤159 \le 15），参加后 xx 更新为 max⁡(9,17)=17\max(9, 17) = 17。

  6. 参加第 11 场比赛（a1=19,b1=18a_1=19, b_1=18）：满足 x≤a1x \le a_1（17≤1917 \le 19），参加后 xx 更新为 max⁡(17,18)=18\max(17, 18) = 18。
    总计参加了 55 场比赛，可以证明这是最多能参加的比赛场数。

思路讲解

将所有比赛分成两组：

  • 安全组 A：bi≤aib_i \le a_i。参加后 x←max⁡(x,bi)≤aix \leftarrow \max(x, b_i) \le a_i，也就是说参加这场比赛不会把 xx 抬到超过它自身的门槛 aia_i。对后续的影响很温和。

  • 危险组 B：bi>aib_i > a_i。参加后 xx 必然跳到 bib_i（因为 bi>ai≥xb_i > a_i \ge x），对后续影响大。

为什么这个分组有用？因为安全组内部，如果按 aia_i 升序排列，全部都能参加——每次参加后 x≤aix \le a_i，而下一场的 aa 更大，必然满足条件。所以安全组是"稳赚不赔"的。

下一步应该关注：安全组全做了，危险组怎么尽可能多地塞进来**？（把安全组给固定住）**

image

第三层：排序与交错——两组的最优合并策略

  • 安全组按 aia_i 升序排。

  • 危险组按 bib_i 升序排（参加后 xx 跳到 bib_i，越小越好，留给后面的空间越大）。

一下的这个规则就是，在上面情况下，B 不会影响 A？（先不要去想 B 会不会生效）

关键的交错规则：在做每一个危险组比赛 BjB_j（bb 值为 bjb_j）之前，先把安全组中所有 ai<bja_i < b_j 的比赛做完。

为什么？做完 BjB_j 后 x=bjx = b_j，那些 a<bja < b_j 的安全组比赛就再也做不了了。提前做掉它们不会抬高 xx（因为安全组的 b≤a<bjb \le a < b_j），不影响 BjB_j 的可行性。

这样，安全组的比赛一场都不会浪费——它们总是在 xx 被抬高之前被消化掉。最终的答案就是：

安全组全部+按上述交错策略能做的危险组数量\text{安全组全部} + \text{按上述交错策略能做的危险组数量}

不难想到，危险组按照这个 b 从小到大排比较好，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
auto forward=[&]() -> bool {
    while (idx1<SZ(safeA) && idx2<SZ(dangerA) && safeA[idx1].a<dangerA[idx2].b) {
        cur_ability=max(cur_ability,safeA[idx1].b);
        ++idx1;
    }

    if (cur_ability<=dangerA[idx2].a) {
        cur_ability=max(cur_ability,dangerA[idx2].b);
        ++ans;
    }
    ++idx2;
    if (idx2<SZ(dangerA)) {
        return true;
    }
    return false;
};
while (forward()) {
}

AC代码

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

Posted on Edited on

题目大意

题目描述
给定一个长度为 nn 的正整数数组，求有多少个非空连续子数组满足以下条件：子数组内所有元素的和，能够被该子数组中所有元素包含的数字字符的最大值整除。

（注：数字字符指组成数字的 0∼90 \sim 9。例如，数组 [2025, 11, 15] 中包含的数字字符有 0,1,2,50, 1, 2, 5，其最大值为 55。）

输入格式
第一行包含一个整数 TT（1≤T≤1041 \le T \le 10^4），表示测试用例的数量。
对于每个测试用例：
第一行包含一个整数 nn（1≤n≤1051 \le n \le 10^5），表示数组长度。
第二行包含 nn 个正整数 x1,x2,…,xnx_1, x_2, \dots, x_n（1≤xi≤1091 \le x_i \le 10^9），表示数组元素。
保证所有测试用例中 nn 的总和不超过 10510^5。

输出格式
对于每个测试用例，输出一行一个整数，表示满足条件的非空子数组数量。

样例输入

1
2
3
4
5
2
3
213 12 21
7
314 880 246 170 493 474 129

样例输出

1
2
4
7

样例解释
以第一个测试用例 [213, 12, 21] 为例，考察其所有非空子数组：

  • [213]：包含数字 1,2,31, 2, 3，最大数字为 33。子数组元素和为 213213，213 mod 3=0213 \bmod 3 = 0，满足条件。

  • [12]：包含数字 1,21, 2，最大数字为 22。子数组元素和为 1212，12 mod 2=012 \bmod 2 = 0，满足条件。

  • [21]：包含数字 1,21, 2，最大数字为 22。子数组元素和为 2121，21 mod 2≠021 \bmod 2 \neq 0，不满足条件。

  • [213, 12]：包含数字 1,2,31, 2, 3，最大数字为 33。子数组元素和为 213+12=225213 + 12 = 225，225 mod 3=0225 \bmod 3 = 0，满足条件。

  • [12, 21]：包含数字 1,21, 2，最大数字为 22。子数组元素和为 12+21=3312 + 21 = 33，33 mod 2≠033 \bmod 2 \neq 0，不满足条件。

  • [213, 12, 21]：包含数字 1,2,31, 2, 3，最大数字为 33。子数组元素和为 213+12+21=246213 + 12 + 21 = 246，246 mod 3=0246 \bmod 3 = 0，满足条件。

满足条件的子数组共有 4 个。

思路讲解

≤d 比=d 好计数得多，那为什么不使用 f(≤d)-f(≤d-1) 得到 f(=d) 呢？

不过，要注意到，就是光一个 d 是不够描述这个 f 函数的。

定义 $ f(≤d，big_d)$ 指的是最大 digit 是 ≤d≤d 而且可以被 bigdbig_d 整除的这个子段数量。

因此，不难发现 $ f(=d，big_d)=f(≤d,big_d)-f(≤d-1,big_d)$。

使用这一容斥方法解决该问题，是因为我们发现在编程中，我们发现，很难对 最大 digit=d 进行计数（你要是不信的话可以自此试试）。

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
for (int big_d=1;big_d<=9;++big_d) {
    vector<ll> F(10+2);
    for (int d=big_d-1;d<=big_d;++d) {
        vector<ll> R(big_d);
        for (int i=1;i<=N;++i) {
            if (mx_d[i]>d) {
                // if (find_mx) {
                //     ans+=R[0];
                // }
                R.assign(big_d,0);
                continue;
            }
            // cal(A[i]);
            ll rem=A[i]%big_d;
            rotate(R.rbegin(),R.rbegin()+rem,R.rend());
            R[rem]++;
            F[d]+=R[0];

            // if (find_mx) {
            //     ans+=R[0];
            // }
        }
    }
    ans+=F[big_d]-F[big_d-1];
}

AC代码

AC
https://codeforces.com/gym/106380/submission/366441214

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

Posted on

题目大意

题目描述

给定一个正整数 nn 以及两个长度为 nn 的排列 rr 和 cc。
请构造一个 n×nn \times n 的矩阵，满足以下所有条件：

  1. 矩阵中的所有元素均为 [0,n][0, n] 范围内的整数。

  2. 矩阵第 ii 行元素的 MEX\text{MEX} 值为 rir_i。

  3. 矩阵第 ii 列元素的 MEX\text{MEX} 值为 cic_i。

注：数组的 MEX\text{MEX} 值是指数组中未出现的最小非负整数。题目保证必然存在符合上述条件的矩阵。

输入格式

第一行包含一个整数 TT（1≤T≤1031 \le T \le 10^3），表示测试用例的数量。
对于每个测试用例：
第一行包含一个正整数 nn（1≤n≤2×1031 \le n \le 2 \times 10^3）。
第二行包含一个长度为 nn 的排列 r1,r2,…,rnr_1, r_2, \dots, r_n。
第三行包含一个长度为 nn 的排列 c1,c2,…,cnc_1, c_2, \dots, c_n。
保证所有测试用例中 nn 的总和不超过 2×1032 \times 10^3。

输出格式

对于每个测试用例，输出 nn 行，每行包含 nn 个整数，表示满足所有条件的矩阵。如果有多个符合条件的矩阵，输出其中任意一个即可。

样例数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入:
2
4
2 1 3 4
3 4 1 2
5
2 1 4 3 5
1 4 2 5 3

输出:
0 0 4 1
2 3 4 0
1 2 0 1
0 1 2 3
0 0 0 0 1
0 0 0 2 0
2 3 3 1 0
2 1 0 4 2
0 2 1 3 4

样例解释

以第一个测试用例为例，n=4n = 4，r=[2,1,3,4]r = [2, 1, 3, 4]，c=[3,4,1,2]c = [3, 4, 1, 2]。
对于输出的矩阵：

  • 第 11 行元素为 [0,0,4,1][0, 0, 4, 1]，其中包含 0,1,40, 1, 4，未出现的最小非负整数为 22，等于 r1r_1。

  • 第 22 行元素为 [2,3,4,0][2, 3, 4, 0]，其中包含 0,2,3,40, 2, 3, 4，未出现的最小非负整数为 11，等于 r2r_2。

  • 第 33 行元素为 [1,2,0,1][1, 2, 0, 1]，其中包含 0,1,20, 1, 2，未出现的最小非负整数为 33，等于 r3r_3。

  • 第 44 行元素为 [0,1,2,3][0, 1, 2, 3]，其中包含 0,1,2,30, 1, 2, 3，未出现的最小非负整数为 44，等于 r4r_4。

同理观察列方向上的 MEX\text{MEX} 值：

  • 第 11 列元素为 [0,2,1,0][0, 2, 1, 0]，包含 0,1,20, 1, 2，其 MEX\text{MEX} 值为 33，等于 c1c_1。

  • 第 22 列元素为 [0,3,2,1][0, 3, 2, 1]，包含 0,1,2,30, 1, 2, 3，其 MEX\text{MEX} 值为 44，等于 c2c_2。

  • 第 33 列元素为 [4,4,0,2][4, 4, 0, 2]，包含 0,2,40, 2, 4，其 MEX\text{MEX} 值为 11，等于 c3c_3。

  • 第 44 列元素为 [1,0,1,3][1, 0, 1, 3]，包含 0,1,30, 1, 3，其 MEX\text{MEX} 值为 22，等于 c4c_4。

所有行和列的 MEX\text{MEX} 值均完全符合输入的排列要求，该矩阵合法。

思路讲解

不难注意到这样一个构造方法。

image

然后，其实我们自己也想到了，一个构造方法，可以通过行列交换，得到新的，任何符合要求的这个 mex 矩阵。

通过行交换，可以使得列的条件依然得到满足。通过列交换，可以使得行的条件依然得到满足。

因此，现应用行交换，再应用列交换，就可以把一个这个构造方法变成任何东西。

1
2
3
4
5
6
7
8
for (int i_R=1;i_R<=N;++i_R) {
    ll i=R[i_R];
    for (int j_C=1;j_C<=N;++j_C) {
        ll j=C[j_C];
        cout<<maze[i][j]<<" ";
    }
    cout<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106380/submission/366322358

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

Posted on Edited on

The 21st Hunan Provincial Collegiate Programming Contest

可以优先做国内的这个省赛

2025 National Invitational of CCPC (Zhengzhou), 2025 CCPC Henan Provincial Collegiate Programming Contest

郑州的这个 CCPC 邀请赛。

我感觉国内的这个感觉和国外不大一样，可以优先 vp 国内的省赛（国内区域赛可以留到比赛前 vp，没必要最近 vp）。

The 2025 Jiangsu Collegiate Programming Contest, The 2025 Guangdong Provincial Collegiate Programming Contest

2025 National Invitational of CCPC (Zhengzhou), 2025 CCPC Henan Provincial Collegiate Programming Contest

The 15th Shandong CCPC Provincial Collegiate Programming Contest

image

ICPC Asia Dhaka Regional Onsite 2025 — Replay Contest

cf 上做的人很多

image