【解题报告】CSP-S 2020

Posted on Edited on In

考完自闭了，怎么能这么菜…

julian

考虑分成公元前，1582.10.41582.10.4 及以前，1582.10.151582.10.15 以后三种情况。

暴力模拟即可。

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
117
118
119
120
121
122
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

#define FILE
#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define LL long long
#define pii pair<int, int>
#define lowbit(x) ((x) & (-(x)))
#define pb push_back

const int MAXN = 1;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;

int T, r, to1, to1582, ans;
int day[20] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

template<typename T> inline void read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
    a *= f;
}

void BC(int x) {
    int tot = 1461, y = 4713, m = 1, d = 1;
    y -= x / tot * 4; x %= tot;
    for(int i = y, dd;; --i) {
        dd = (i % 4 == 1 ? 366 : 365);
        if(x >= dd) x -= dd, y = i - 1;
        else break;
    }
    if(y % 4 == 1) day[2]++;
    for(int i = 1; i <= 12; ++i) {
        if(x >= day[i]) m = i + 1, x -= day[i];
        else break;
    }
    if(y % 4 == 1) day[2]--;
    d += x;
    printf("%lld %lld %lld BC\n", d, m, y);
}

void AC1(int x) {
    int y = 1, m = 1, d = 1, tot = 1461;
    y += (x / tot) * 4; x %= tot;
    for(int i = y, dd;; ++i) {
        dd = (i % 4 ? 365 : 366);
        if(x >= dd) x -= dd, y = i + 1;
        else break;
    }
    if(y % 4 == 0) day[2]++;
    for(int i = 1; i <= 12; ++i) {
        if(x >= day[i]) x -= day[i], m = i + 1;
        else break;
    }
    if(y % 4 == 0) day[2]--;
    d += x;
    printf("%lld %lld %lld\n", d, m, y);
}

void AC2(int x) {
    int tot = 146097, y = 1582, m = 10, d = 15;
    y += (x / tot) * 400; x %= tot;
    for(int i = y, dd;; ++i) {
        if((i + 1) % 400 == 0) dd = 366;
        else if((i + 1) % 4 == 0 && (i + 1) % 100 != 0) dd = 366;
        else dd = 365;
        if(x >= dd) x -= dd, y = i + 1;
        else break;
    }
    if(x <= day[10] - 15) {
        d += x;
        printf("%lld %lld %lld\n", d, m, y);
        return;
    }
    x -= day[10] - 14;
    m = 11, d = 1;
    for(int i = 11; i <= 12; ++i) {
        if(x >= day[i]) x -= day[i], m = i + 1;
        else break;
    }
    if(m != 13) {
        d += x;
        printf("%lld %lld %lld\n", d, m, y);
        return;
    }
    y++, m = 1, d = 1;
    if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) day[2]++;
    for(int i = 1; i <= 12; ++i) {
        if(x >= day[i]) x -= day[i], m = i + 1;
        else break;
    }
    if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) day[2]--;
    d += x;
    printf("%lld %lld %lld\n", d, m, y);
}

signed main () {
    for(int i = 4713; i >= 1; --i) {
        if(i % 4 == 1) to1 += 366;
        else to1 += 365;
    }
    to1582 = to1;
    for(int i = 1; i <= 1581; ++i) {
        if(i % 4 == 0) to1582 += 366;
        else to1582 += 365;
    }
    for(int i = 1; i <= 9; ++i) to1582 += day[i];
    to1582 += 4;//1582.10.5(15)
    read(T);
    while(T--) {
        read(r);
        if(r < to1) BC(r);
        else if(r < to1582) AC1(r - to1);
        else AC2(r - to1582);
    }
    return 0;
}

出题人很有精神！

zoo

随便分位考虑一下，求有哪些饲料存在，然后暴力每一位判断。如果该位可以放，就 ×2\times 2 。注意 n=0,k=64n=0,k=64 的时候 2642^{64} 会炸 unsigned long long\text{unsigned long long}，谢谢出题人送我退役。

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
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

#define FILE
//#define int unsigned long long
#define ull unsigned long long
#define debug(x) cout << #x << " = " << x << endl
#define LL long long
#define pii pair<int, int>
#define lowbit(x) ((x) & (-(x)))
#define pb push_back

const int MAXN = 1.1e6 + 10;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;

int n, m, c, k, cnt2 = 0;
ull a[MAXN], ans = 0, p2[70];
int p[MAXN], q[MAXN], lsh[MAXN], Lim;
bool ok[70], use[MAXN];

template<typename T> inline void read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
    a *= f;
}

inline int Getid(int x) {
    return lower_bound(lsh + 1, lsh + Lim + 1, x) - lsh;
}

signed main () {
    read(n); read(m); read(c); read(k);
    p2[0] = 1;
    for(int i = 1; i < k; ++i)
        p2[i] = p2[i - 1] << 1ull;
    for(int i = 1; i <= n; ++i) read(a[i]); 
    for(int i = 1; i <= m; ++i) {
        read(p[i]); read(q[i]);
        lsh[i] = q[i];
    }
    sort(lsh + 1, lsh + m + 1);
    Lim = unique(lsh + 1, lsh + m + 1) - lsh - 1;
    for(int i = 1; i <= m; ++i) q[i] = Getid(q[i]);
    for(int s = 0; s < k; ++s) {
        for(int i = 1; i <= n; ++i) {
            if(a[i] & p2[s]) {
                ok[s] = true;
                break;
            }
        }
    }
    for(int i = 1; i <= m; ++i) 
        if(ok[p[i]]) use[q[i]] = true;
    memset(ok, true, sizeof ok);
    for(int i = 1; i <= m; ++i)
        if(!use[q[i]]) ok[p[i]] = false;
    for(int i = 0; i < k; ++i) 
        if(ok[i]) cnt2++;
    if(n == 0 && cnt2 == 64) return puts("18446744073709551616"), 0;
    if(cnt2) ans = 1;
    for(int i = 1; i <= cnt2; ++i) ans *= 2;
    cout << ans - n << endl;
    return 0;
}

曾经，不开 long long\text{long long} 见祖宗；今天，开了 unsigned long long\text{unsigned long long} 我还是见祖宗了。

call

怎么考场上这题都写不出…

根据部分分极强的提示 我们不难发现函数调用关系是一个 DAG\text{DAG}。又每一个加法实际上是独立的，只需要乘一下后面的所有乘法操作即可。

考虑建出 DAG\text{DAG}，正反各做一遍 toposort\text{toposort}（令被调用的函数向调用他的函数的边为正）。

先通过反图求出经过每一个点的乘法操作，然后通过正图更新每一个加法操作即可。

可以把初始的 aa 看做 nn 个加法标记，或许会稍微简单一些。

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
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define vec vector

const int MAXN = 1e6 + 10;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

struct EDGE {
    int head[MAXN], edgesize;
    int nxt[MAXN << 1], to[MAXN << 1];
    inline void addedge(int x, int y) {
        nxt[++edgesize] = head[x];
        to[edgesize] = y;
        head[x] = edgesize;
    }
} e;

int n, m, q;
int a[MAXN], t[MAXN], p[MAXN], v[MAXN];
int c[MAXN], cnt[MAXN], s[MAXN], dp[MAXN];
int ind[MAXN], top[MAXN], ccnt;
vec<int> g[MAXN], w[MAXN];
queue<int> Q;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    a *= f;
    return 1;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

signed main () {
    read(n);
    for(int i = 1; i <= n; ++i)
        read(a[i]);
    read(m);
    for(int i = 1; i <= m; ++i) {
        read(t[i]);
        if(t[i] == 1) read(p[i]), read(v[i]);
        if(t[i] == 2) read(v[i]);
        if(t[i] == 3) {
            read(c[i]);
            for(int j = 1, x; j <= c[i]; ++j) {
                read(x), g[i].pb(x);
                e.addedge(i, x);
                ind[x]++;
            }
        }
    }
    read(q);
    for(int i = 1; i <= q; ++i) {
        read(s[i]);
        e.addedge(0, s[i]);
        ind[s[i]]++;
    }
    for(int i = 0; i <= m; ++i) if(!ind[i]) Q.push(i);
    while(Q.size()) {
        int x = Q.front(); Q.pop();
        top[++ccnt] = x;
        for(int i = e.head[x], to; i; i = e.nxt[i]) {
            to = e.to[i];
            if(!(--ind[to])) Q.push(to);
        }
    }
    for(int ii = ccnt, x; ii >= 1; --ii) {
        x = top[ii];
        if(t[x] == 2) cnt[x] = v[x];
        else cnt[x] = 1;
        for(int i = e.head[x], to; i; i = e.nxt[i]) {
            to = e.to[i];
            w[x].pb(cnt[x]);
            (cnt[x] *= cnt[to]) %= mod;
        }
    }
    dp[0] = 1;
    for(int ii = 1, x; ii <= ccnt; ++ii) {
        x = top[ii];
        for(int i = e.head[x], pos = 0, to; i; i = e.nxt[i], ++pos) {
            to = e.to[i];
            (dp[to] += dp[x] * w[x][pos] % mod) %= mod;
        }
    }
    for(int i = 1; i <= n; ++i)
        (a[i] *= cnt[0]) %= mod;
    for(int i = 1; i <= m; ++i)
        if(t[i] == 1) (a[p[i]] += v[i] * dp[i] % mod) %= mod;
    for(int i = 1; i <= n; ++i)
        printf("%lld ", a[i]);
    return 0;
}

snakes

考虑如果一条蛇选择结束，需要满足什么条件。

如果他吃掉最后一名之后，没有变成最后一名，那么他一定选择吃。称这样是必吃状态。

由于整个序列是递增的，如果他吃了最后一名而没有掉到最后一名，会使得序列的 min⁡\min 增大，max⁡\max 减小。那么新的第一名如果选择吃，那一定会落到原先第一名更后面。

那就让新的第一名去选择是否结束，反正我吃了不会比他先死。

如果他吃掉最后一名之后，变成了最后一名，那么找到距离他最近的必吃状态，我吃不吃只和与这个必吃状态的 距离 的 奇偶性 相关。

设我在 pp，最近的必吃状态位置是 ss。

首先显然的是 ss 处必定会吃，那考虑 ss 到 pp 之间的蛇，他们一定不是必吃状态，那一定有：这些蛇选择吃之后的新状态的体力值单调。

也就是说，如果 ss 吃，他一定吃的是 s+1s+1。s+1s+1 知道自己会被吃，那么他就选择不吃最小的；s+1s+1 不吃，就会选择结束，那么 s+2s+2 就知道自己就算变成最后，也不会死，那么他一定选择吃…

也就是，如果 p−sp-s 是奇数，他就会结束游戏，否则一定会吃掉最小的，而接下来新的第一名就一定会直接结束游戏。

然后拿队列模拟一下，和 NOIP2016\text{NOIP2016} 蚯蚓一样维护一个双端队列，每次从原队列和新队列取 max⁡\max 和 min⁡\min 更新即可。

只要遇上一个非必吃状态，就 O(n)\mathcal{O(n)} 模拟找到下一个必吃状态，返回答案即可。

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define vec vector

const int MAXN = 1e6 + 10;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

struct NODE {
    int x, y;
    NODE(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    bool operator < (const NODE &b) const {
        return (x < b.x) || (x == b.x && y < b.y);
    }
    bool operator > (const NODE &b) const {
        return b < (*this);
    }
    NODE operator - (const NODE &b) const {
        return NODE(x - b.x, y);
    }
    bool operator == (const NODE &b) const {
        return x == b.x && y == b.y;
    }
    bool operator != (const NODE &b) const {
        return !((*this) == b);
    }
} q[3][MAXN << 1];

int T, n, m;
int l[3], r[3];
int a[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    a *= f;
    return 1;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

NODE GetMax(bool del) {
    NODE res = NODE(-INF, -INF);
    int pos = 0;
    if(l[1] <= r[1] && q[1][r[1]] > res) res = q[1][r[1]], pos = 1;
    if(l[2] <= r[2] && q[2][r[2]] > res) res = q[2][r[2]], pos = 2;
    if(!del) return res;
    assert(pos);
    r[pos]--;
    return res;
}

NODE GetMin(bool del) {
    NODE res = NODE(INF, INF);
    int pos = 0;
    if(l[1] <= r[1] && q[1][l[1]] < res) res = q[1][l[1]], pos = 1;
    if(l[2] <= r[2] && q[2][l[2]] < res) res = q[2][l[2]], pos = 2;
    if(!del) return res;
    assert(pos);
    l[pos]++;
    return res;
}

int GetPos(int siz) {
    int cnt = 1;
    for(int i = siz + 1; i <= n; ++i) {
        if(i == n - 1) return n - 1;
        NODE mx = GetMax(1), mn = GetMin(1);
        NODE New = mx - mn;
        q[2][--l[2]] = New;
        if(GetMin(0) != New) return i;
    }
    return n;
}

int solve() {
    l[1] = n, r[1] = n - 1;
    l[2] = n, r[2] = n - 1;
    for(int i = 1; i <= n; ++i) 
        q[1][++r[1]] = NODE(a[i], i);
    int siz = n, now = 0;
    for(int i = 1; i <= n; ++i) {
        if(i == n - 1) return 1;
        NODE mx = GetMax(1), mn = GetMin(1);
        NODE New = mx - mn;
        q[2][--l[2]] = New;
        if(GetMin(0) == New) {
            int pos = GetPos(i);
            if((pos - i) & 1) return n - (i - 1);
            else return n - (i - 1) - 1;
        }
    }
    return 1;
}

signed main () {
    read(T);
    for(int tt = 1, k; tt <= T; ++tt) {
        if(tt == 1) {
            read(n);
            for(int i = 1; i <= n; ++i)
                read(a[i]);
        } else {
            read(k);
            for(int i = 1, x, y; i <= k; ++i) {
                read(x); read(y);
                a[x] = y;
            }
        }
        printf("%d\n", solve());
    }
    return 0;
}