Sakana~
0%

The 2022 ICPC Asia Regionals Online Contest (I) 部分题解

发表于 更新于 分类于

2022 ICPC网络赛第一场题解

The 2022 ICPC Asia Regionals Online Contest (I) 部分题解

https://pintia.cn/market/item/1571156622976593920

A 01 Sequence

重要结论：一段连续的1，其贡献为长度除2上取整

简要说明：对于一段连续的1，从两头往中间删最优（这样子删的时候被连带着误删的1最少），依照此策略，两两一删，最后如果中间剩下一个也能带走两0

（可以把连续的01看成一块一块的）

故可以预处理每一段连续1的长度的前缀和，记为len[i]

对于每一段查询：

  • 如果没有截断1（红色情况），可以直接用前缀和算；
  • 1被截断了（绿蓝情况），端点的1特殊考虑一下

image-20220920234255214

如何更好地处理端点：可以搞前缀数组+后缀数组

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
#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;
char s[N];
int len[N], l[N], r[N];

int cal (int L, int R) {
    int ll = L + r[L], rr = R - l[R];
    if (ll >= rr)   return (R - L + 1) / 2;
    return len[rr] - len[ll-1] + (r[L] + l[R] + 1) / 2;
}

int main () {
    int n, m;
    scanf ("%d%d%s", &n, &m, s+1);

    int lst = -1;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
            if (lst == i - 1)   lst = -1;
            else    len[i] = 1, lst = i;
        }
        len[i] += len[i-1];
    }

    for (int i = 1; i <= n; i++) {
        if (s[i] == '0')    l[i] = 0;
        else    l[i] = l[i-1] + 1;  
    }

    for (int i = n; i >= 1; i--) {
        if (s[i] == '0')    r[i] = 0;
        else    r[i] = r[i+1] + 1;
    }

    while (m --) {
        int l, r;
        scanf ("%d%d", &l, &r);
        int ans = cal (l, r), len = (r - l + 1) / 3;
        printf ("%d\n", max (0, len - ans));
    }
}

//连续1的len/2上取整
//

C Delete the Tree

就两种操作：删掉一个度为2的点 or 随便删掉一个点。想要把所有的点删完，问操作2最少多少次

显而易见，这个二叉树里面只有度数为1和2的点。要是度数为2的话肯定优先第一种操作（因为他不会改变别的点的度数，同时又能把自己删掉），度数为1的话就只能采取第二种操作了，所以直接统计度数为1的点即可。

特别注意只有一个点的情况

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
#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;
int d[N];

void solve () {
    int n, ans = 0;
    scanf ("%d", &n);
    if (n == 1) {
        printf ("1\n");
        return ;
    }
    for (int i = 1; i <= n; i++)    d[i] = 0;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf ("%d%d", &u, &v);
        d[u] ++, d[v] ++;
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] == 1)     ans ++;
    }
    printf ("%d\n", ans);
}

int main () {
    int t;
    scanf ("%d", &t);
    while (t --) {
        solve ();
    }
}

//1. 删掉一个度为2的点
//2. 删掉一个点
//操作2尽可能少

//统计度数即可

J Gachapon

观察样例，手动模拟求期望的过程，不难发现，后面的概率在相乘的时候能够逐项约分，从而消掉。

所以只需枚举首项概率，然后看是否满足要求即可。

（简陋的分析过程）

解方程的过程：

似乎有妙妙式子，然而我只会嗯做😭

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
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;
int x, y;

int main () {
    ios::sync_with_stdio (0);cin.tie (0);cout.tie(0);
    cin >> x >> y;
    for (int a = 1; a <= 10000 ; a++) {
        int sum = (x+1)*(x-2)/2, A = x*(a-x+2);
        int fz = a*y - A - sum, fm = a - A - sum;

        if (fz * fm <= 0 || a + 3 - x <= 1)   continue;
        fz = abs (fz), fm = abs (fm);
        int dx = __gcd (fz, fm);
        fz /= dx, fm /= dx;
        if (fz > 10000 || fm > 10000)   continue; //important

        //cout << "a=" << a << endl;
        cout << fz << ' ' << fm << endl;
        for (int i = 0; i <= x - 3; i++)    cout << "1 " << a - i << endl;
        cout << "1 1\n";
        break;
        
    }
}

//p = (d+2*a*y) / (d+2*a), d = x*x - (2*a+3)*x + 2;
//枚举a,满足p > 0 && a+3-x > 1

H Step Debugging

dfs，碰到 repeat 就进入递归求次数

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int mod = 20220911;
int ans;

int dfs () {
    int cnt = 0;
    string s;
    while (cin >> s, s != "for") {
        if (s == "library")     cnt ++;
        else if (s == "repeat") cnt += dfs ();        
    }
    int num;
    cin >> num;
    cin >> s; //妹有用的times
    return num * cnt % mod;
}

signed main () {
    string s;
    while (cin >> s, s != "fin") {
        if (s == "library")     ans ++;
        else if (s == "repeat") ans += dfs ();
    }
    cout << ans % mod;
}