Sakana~
0%

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

发表于 更新于 分类于

2022 ICPC网络赛第二场题解

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

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

E - An Interesting Sequence

由 gcd(x, y)==1 且 和尽可能小，不难想到相邻构造这种方式，然后最小的质数是2，所以对于第三项之后的序列，直接2, 3, 2, 3, … 或者3, 2, 3, 2, … 这样构造即可

前两项就是k, p，p是与k互质的最小素数。根据p来确定是2,3,2,3,… 还是 3,2,3,2…

如果p != 2，就是2,3,2,3,…。因为 >2的素数必然不可能含2的因子，所以与2的gcd一定为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
#include <bits/stdc++.h>

using namespace std;
int n, k, p;
long long ans;

bool is_prime (int x) {
    for (int i = 2; i*i <= x; i++) {
        if (x % i == 0)     return false;
    }
    return true;
}

int main () {
    cin >> n >> k;
    //找到与k互质的最小p
    for (int i = 2; ; i++) {
        if (is_prime (i) && __gcd (i, k) == 1) {
            p = i;
            break;
        }
    }

    ans += 1ll*k + p + 1ll*(n-2)/2*5;
    if (n & 1) {
        if (p != 2)     ans += 2; //k, p, 2, 3, 2, ..., 2
        else    ans += 3;  //k, p, 3, 2, 3, ..., 3
    } 
    cout << ans;
}

//k, p, 2, 3, 2, 3, ...
//k, p, 3, 2, 3, 2, ...

J - A Game about Increasing Sequences

这题竟然就是我猜的结论（但是赛时没想明白证明）——两边只要有一条能走的奇数路径就是A赢

大致证明（不是很严谨）：

只有左右两条路可走，如果该条路径长度为奇数，那先走上这条路的人必胜；反之，为偶数的话，就必输。所以如果存在一条大且奇（即起点较大或两起点相等）的路，那么Alice必胜，因为走上这条路之后就只能沿此路一直往下走了。

如果存在一条小且奇的路的话（则另一条路为大且偶），A 如果选择走偶数路径，就必输，所以他只能选奇数那条走。此时到了B做选择，B如果顺着奇数路径走的话，必输（因为A走了一个之后，奇数-1=偶数）；而B如果选择走偶数路径的话，A只要跟在他后面走，就相当于转移到了A是大且奇的状态。故 A必胜。

所以，只要存在一条奇数路径的话，A就必胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;
const int N= 1e5 + 5;
int n, a[N];

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    int len1 = 1, len2 = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] <= a[i-1])  break;
        len1 ++;
    }
    for (int i = n-1; i >= 1; i--) {
        if (a[i+1] >= a[i])  break;
        len2 ++;
    }
    if (len1 & 1 || len2 & 1)   puts ("Alice");
    else    puts ("Bob");
}

//存在一条奇数路径即可

A - Yet Another Remainder

费马小定理

确实有循环节，但是我找到的规律比较浅显（没有发现固定的规律），没法抽象出本质的规律，所以陷入了操作不出来的困境。我是根据每个质数去找出他的模的系数，然而实际上，根据费马小定理，只需要进行一些简单的变换（主要是我这都不知道），就能发现循环节是p-1，从而直接找到答案。

以下为简要证明：

费马小定理：a^p^ ≡ a (mod p)

推论：a^p-1^ ≡ 1 (mod p)

此时按位表示每一个数，则有：

a[i] * 10^x+p-1^, a[i+1] * 10^x+p-2^, …, a[j] * 10^x^

对于每一位同时除以 10^x^，有

a[i] * 10^p-1^, a[i+1] * 10^p-2^, …, a[j]

又因为 10^p-1^ ≡ 1 (mod p)

所以，对于两端有性质：**(ai * 10^p-1^ + aj) % p = (ai + aj) * 10^p-1^ % p**

**由此得出循环节就是 p-1 **

故 对于 <= 100 的n, 第 n行就是答案，对于>100的n只需要去第 p-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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int a[N][N], pw[N]; //pw[]:预处理10的次方
int n, p, m;
long long ans;

void pre () {
    pw[0] = 1;
    for (int i = 1; i <= 100; i++) {
        pw[i] = (pw[i-1] * 10) % p;
    }
}

void solve () {
    scanf ("%d", &n);
    for (int i = 1; i <= min (100, n); i++) {
        for (int j = 1; j <= i; j++)    scanf ("%d", &a[i][j]);
    }

    //直接去第n行找
    if (n <= 100) {
        scanf ("%d", &m);
        while (m --) {
            scanf ("%d", &p);
            pre ();
            ans = 0;
            for (int i = 1; i <= n; i++) {
                ans = (ans * 10 % p + a[n][i]) % p;
            }
            printf ("%lld\n", ans);
        }
    }
    else {
        scanf ("%d", &m);
        while (m --) {
            scanf ("%d", &p);
            pre ();
            ans = 0;
            for (int i = 1; i < p; i++) {
                ans = (ans + a[p-1][i] * pw[(n-i) % (p-1)]) % p;
            }
            printf ("%lld\n", ans);
        }
    }

}

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


//循环节是p-1,只要找对应的

F - Infinity Tree

由[p+k(y−1)+1, p+ky]这个生产规律得知，第 i 轮的节点总数是 (k+1)^i^，所以对于给定x, y，可以先跳到大致轮次 cur，当前点 - 上一轮结束的点 = 当前产生的点。然后找当前点的父亲。注意，因为每次产生k个点，有 1/k=0, 2/k=0, …, k/k=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
#include <bits/stdc++.h>
#define int long long

using namespace std;
int k, u, v, cur;

int find (int x) {
    while (cur >= x)    cur /= (k + 1); //i轮结束结点个数是（k+1)^i
    x -= cur; //X-上一次轮结束的结点=当前产生的结点
    int y = x / k; //父亲
    if (x % k == 0)     y --;  //k/k = 1, 特判
    return y + 1; //从1开始生产
}

void solve () {
    cin >> k >> u >> v;
    cur = 1;
    while (cur*1.0 < max (u, v)*1.0/(k+1))  cur *= (k + 1); //跳到大致轮次

    while (u != v) {
        if (u > v)  u = find (u); //往大了先找
        else    v = find (v);
    }
    cout << u << endl;
}

signed main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}


//k, u, v: 现有的每个点产生k个儿子,LCA(u, v)=?

B - Non-decreasing Array

dp

每次操作为了使得最终方差尽可能大，我们要贪心的消去尽可能多的“过渡数”——来自大睿老师

所以对于一次操作，可以删去中间的一个数，然后把后面的变成相邻的（也就等价于再删去一个数）

即 每次操作等价于删去两个数，那么删什么数咋删呢，可以考虑dp

看到了一个比较巧妙的表示方法：f[i][j]:1~i,删了j个数

枚举能删最多多少个数，以及在此限定条件下删连续的多少个，表示出 [l,r]，即 此区间内的全删掉，那么新增的贡献就是两端点的方差。

dp太妙了orz

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

using namespace std;
const int N = 105;
int n, a[N], f[N][N]; //f[i][j]:1~i,删了j个数

signed main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int r = 1; r <= n; r++) {
        for (int cnt = 0; cnt <= r - 2; cnt++) { //最多能删多少个,两端不能删
            for (int len = 0; len <= cnt; len++) { //删连续的多少个
                int l = r - len - 1; //[l+1, r-1]
                f[r][cnt] = max (f[r][cnt], f[l][cnt-len] + (a[r] - a[l]) * (a[r] - a[l])); //[l,r]之间全删掉
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if ((i + 1) * 2 >= n)   cout <<  (a[n] - a[1]) * (a[n] - a[1]) << endl;
        else        cout << f[n][i*2] << endl;
    }
}
//等价于删去两个数

L - Quadruple

容斥+dp

题意：问区间内出现的 “ICPC”个数　

分析：用前缀和。[L, R] 内出现的 ICPC 个数就是 ICPC[R] - ICPC[L-1]

但是这只记录了结尾，也就是说，在L那里可能会有ICPC延伸出去了，即 在L之前出现

具体而言，对于L处的串，可能会出现 I+CPC，IC+PC，ICP+C这种出界的情况

所以答案为： ICPC[l,r] -(I[1,l-1] * CPC[l,r] + IC[1,l-1] * PC[l,r] + ICP[1,l-1] * C[l,r])，就是ICPC容斥掉不在此区间内的那些

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
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 5;
int n, m, L[N], R[N];
long long a, b, M, x; //记得ll
string s;

template<class T>
T qpow(T a, long long b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct ll {
    static int norm(int x){
        if(x<M) x+=M;
        if(x>=M) x-=M;
        return x;
    }
    int x;
    ll(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    ll operator-() const {
        return ll(norm(M - x));
    }
    ll inv() const {
        return qpow(*this, M - 2);
    }
    ll &operator*=(const ll &rhs) {
        x = 1LL *x * rhs.x % M;
        return *this;
    }
    ll &operator+=(const ll &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    ll &operator-=(const ll &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    ll &operator/=(const ll &rhs) {
        return *this *= rhs.inv();
    }
    friend ll operator*(const ll &lhs, const ll &rhs) {
        ll res = lhs;
        res *= rhs;
        return res;
    }
    friend ll operator+(const ll &lhs, const ll &rhs) {
        ll res = lhs;
        res += rhs;
        return res;
    }
    friend ll operator-(const ll &lhs, const ll &rhs) {
        ll res = lhs;
        res -= rhs;
        return res;
    }
    friend ll operator/(const ll &lhs, const ll &rhs) {
        ll res = lhs;
        res /= rhs;
        return res;
    }
    friend std::ostream &operator<<(std::ostream &os, const ll &a) {
        return os << a.val();
    }
};

ll I[N], C[N], P[N], IC[N], CP[N], PC[N], ICP[N], CPC[N], ICPC[N];

void pre () {
    for (int i = 1; i <= n; i++) {
        //前缀和别忘了
        I[i] = I[i-1], C[i] = C[i-1], P[i] = P[i-1];
        IC[i] = IC[i-1], CP[i] = CP[i-1], PC[i] = PC[i-1];
        ICP[i] = ICP[i-1], CPC[i] = CPC[i-1], ICPC[i] = ICPC[i-1];

        if (s[i] == 'I')    I[i] += 1;
        else if (s[i] == 'P')    P[i] += 1, CP[i] += C[i-1], ICP[i] += IC[i-1];
        else {
            C[i] += 1, IC[i] += I[i-1], PC[i] += P[i-1];
            CPC[i] += CP[i-1], ICPC[i] += ICP[i-1];
        }
    }
}

ll query (int l, int r) {
    if (l > r)  swap (l, r);
    ll sC, sPC, sCPC, sICPC;
    sC = C[r] - C[l-1];
    sPC = (PC[r] - PC[l-1]) - (C[r] - C[l-1]) * (P[l-1] - P[0]);
    sCPC = (CPC[r] - CPC[l-1]) - (CP[l-1] - CP[0]) * sC - (C[l-1] - C[0]) * sPC;
    sICPC = (ICPC[r] - ICPC[l-1]) - (I[l-1] - I[0]) * sCPC - (IC[l-1] - IC[0]) * sPC - (ICP[l-1] - ICP[0]) * sC;
    return sICPC;
}

int main() {
    cin >> n >> m >> s >> x >> a >> b >> M;
    s = ' ' + s;
    pre ();
    for (int i = 1; i <= m; i++)    x = (a * x + b) % M, L[i] = x % n + 1;
    for (int i = 1; i <= m; i++)    x = (a * x + b) % M, R[i] = x % n + 1;

    ll ans = 0;
    for (int i = 1; i <= m; i++)    ans += query (L[i], R[i]);
    cout << ans << endl;
}

//ans = ICPC[l,r]-(I[1,l-1]*CPC[l,r] + IC[1,l-1]*PC[l,r] + ICP[1,l-1]*C[l,r]);

G Good Permutation

K Black and White Painting