CSP-S 2020 题解

发表于

CSP-S 2020 题解

A

读完题第一感觉是不怎么好写。

实际上仔细思考之后可以得到一种实现起来较为简单的做法。

暴力预处理一直到公元后 $1600$ 年的答案，中间吞掉的十天只需要特判一下跳过去即可；

然后对于后面的都需要按照格里高利历进行计算。不难发现每四百年都是相同的，那么只需要预处理四百年的答案即可。

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

typedef long long ll;

template <class T>
inline void rd(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

const int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int SZ1 = 6500 * 366 + 7;
const int SZ2 = 366 * 400 + 7;
const int MOD = 146097, LIM = 2305448;

struct Data {
    ll x, y, z, t; //日月年，是否为公元前
    Data() {}
    Data(ll x, ll y, ll z, ll t) : x(x), y(y), z(z), t(t) {}
    inline void out() {
        if (t) printf("%lld %lld %lld BC\n", x, y, z);
        else printf("%lld %lld %lld\n", x, y, z);
    }
} l1[SZ1], l2[SZ2];

bool chk(int x, int t) { //检查是否是闰年，t表示是否是公元后
    if (!t) return x % 4 == 1;
    if (x <= 1582) return x % 4 == 0;
    if (x % 4 == 0) {
        if (x % 100 == 0) {
            if (x % 400 == 0) return 1;
            else return 0;
        } else return 1;
    } else return 0;
}

void init() {//预处理，这里把两端预处理写在了一起
    int ptr = 0, x = 31, y = 12, z = 4714, t = 0, gg = 0;
    while (1) {
        x++;
        int sz = month[y] + (y == 2 ? chk(z, t) : 0);
        if (x == sz + 1) {
            x = 1;
            y++;
            if (y == 13) {
                y = 1;
                z += (t ? 1 : -1);
                if (!z) z = 1, t = 1;
            }
        }
        if (x == 5 && y == 10 && z == 1582 && t) x = 15;
        if (!gg) l1[ptr++] = Data(x, y, z, t ^ 1);
        else l2[ptr++] = Data(x, y, z, t ^ 1);
        if (x == 31 && y == 12 && z == 1599 && t) ptr = 0, gg = 1;
        if (gg && ptr == MOD) return;
    }
}

int main() {
    init();
    int T; rd(T);
    while (T--) {
        ll n;
        rd(n);
        if (n < LIM) l1[n].out();
        else {
            n -= LIM;
            Data gx = l2[n % MOD];
            gx.z += 400 * (n / MOD);
            gx.out();
        }
    }
    return 0;
}

B

题面里非常重要但是没用黑体标记的一个信息是保证 $q_i$ 互不相同。

做法很简单，求出哪些二进制位可以自由选择即可。

题目的坑点是需要用unsigned long long，并且还需要特判 （1<<64）-0 这种情况。

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

#define fi first
#define se second
#define PII std::pair<int, int>
#define MP std::make_pair
#define pb push_back
#define CL(a, b) memset((a), (b), sizeof (a))
#define rep(i, l, r) for (int (i) = (l); (i) <= (r); (i)++)
#define per(i, l, r) for (int (i) = (r); (i) >= (l); (i)--)
#define PE(u, e) for (int e = head[u]; e; e = edge[e].next)

typedef long long ll;
typedef unsigned long long ull;

void rd(int &x) {
	char c = getchar(), f = 0; x = 0;
	while (!isdigit(c)) f = (c == '-'), c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	x = f ? -x : x;
}

void rd(ll &x) {
	char c = getchar(), f = 0; x = 0;
	while (!isdigit(c)) f = (c == '-'), c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	x = f ? -x : x;
}

void rd(ull &x) {
	char c = getchar(), f = 0; x = 0;
	while (!isdigit(c)) f = (c == '-'), c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	x = f ? -x : x;
}

const int MAXN = 1e6 + 7;

int n, m, c, k;
ull a[MAXN], os, lim;

int main() {
	//freopen("zoo.in", "r", stdin);
	//freopen("zoo.out", "w", stdout);
	rd(n); rd(m); rd(c); rd(k);
	rep(i, 1, n) {
		rd(a[i]); os |= a[i];
	}
	rep(i, 1, m) {
		ll x, y;
		rd(x); rd(y);
		lim |= (1ull << x);
	}
	
	ull ans = 0, cc = 0;
	rep(i, 0, k - 1) {
		if ((lim >> i) & 1ull) {
			if ((os >> i) & 1ull) cc++;
		} else {
			cc++;
		}
	}
    if (cc == 64 && n == 0) {
        printf("18446744073709551616");
        return 0;
    }
    if (cc != 64) ans = (1ull << cc) - n;
    else {
        ans = (1ull << (cc - 1)) - n;
        ans += (1ull << (cc - 1));
    }
	std::cout << ans << std::endl;
	return 0;
}

C

先一次 $dfs$ 求出每个第二类和第三类操作会使得整个序列乘以多少，记为 $coe_i$。

记 $cc_i$ 表示加法操作 $i$ 执行了多少次。

一次加法会被以后的乘法影响，因此先把操作序列离线，倒着处理，这样可以求出在以后的操作会被执行多少次。

现在只差操作内部的没处理了，再一遍拓扑排序即可求出内部的影响。

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

#define fi first
#define se second
#define pb push_back
#define MP std::make_pair
#define PII std::pair<int, int>
#define all(x) (x).begin(), (x).end()
#define CL(a, b) memset(a, b, sizeof a)
#define rep(i, l, r) for (int i = (l); i <= (r); ++ i)
#define per(i, r, l) for (int i = (r); i >= (l); -- i)
#define PE(x, a) for (int x = head[a]; x;x = edge[x].next)

typedef long long ll;

template <class T>
inline void rd(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

#define int long long

const int MAXN = 1e6 + 7;
const int HA = 998244353;

int n, m, k;
int a[MAXN], pos[MAXN], type[MAXN], val[MAXN], deg[MAXN], coe[MAXN], opt[MAXN], cc[MAXN];

struct Edge {
    int t, next;
} edge[MAXN];

int head[MAXN], cnt;

void add(int &x, const int &y) { x += y - HA; x += x >> 31 & HA; }

void Add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}

void init(int u) {
    if (~coe[u]) return;
    coe[u] = 1;
    if (type[u] == 1) return;
    if (type[u] == 2) { coe[u] = val[u]; return; }
    PE(e, u) {
        int v = edge[e].t;
        init(v);
        coe[u] = 1ll * coe[u] * coe[v] % HA;
    }
}

signed main() {
    rd(n);
    rep(i, 1, n) rd(a[i]);
    rd(m);
    rep(i, 1, m) {
        rd(type[i]);
        if (type[i] == 1) rd(pos[i]), rd(val[i]);
        else if (type[i] == 2) rd(val[i]);
        else {
            int num, x; rd(num);
            while (num--) {
                rd(x); Add(i, x); deg[x]++;
            }
        }
    }

    CL(coe, -1);
    rep(i, 1, m) init(i);

    rd(k);
    rep(i, 1, k) rd(opt[i]);

    int v = 1;

    per(i, k, 1) {
        int x = opt[i];
        if (type[x] == 1) add(cc[x], v);
        else if (type[x] == 2) v = 1ll * v * val[x] % HA;
        else {
            add(cc[x], v);
            v = 1ll * v * coe[x] % HA;
        }
    }
    rep(i, 1, n) a[i] = 1ll * a[i] * v % HA;

    std::queue<int> q;
    rep(i, 1, m) if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (type[u] == 1) {add(a[pos[u]], 1ll * val[u] * cc[u] % HA); continue; }
        if (type[u] == 2) continue;
        int c = 1;
        PE(e, u) {
            int to = edge[e].t;
            add(cc[to], 1ll * cc[u] * c % HA);
            if (!--deg[to]) q.push(to);
            c = 1ll * c * coe[to] % HA;
        }
    }
    rep(i, 1, n) printf("%lld ", a[i]);
    puts("");
    return 0;
}

D

每条蛇会在保证自己不被吃掉的前提下进行操作。

对于当前的最大值，如果吃掉之后不是最小值，那么下一个最大值一定比他先被吃，所以可以直接选择吃，然后把锅甩给下一个最大值；

如果一个蛇在吃掉之后最小值之后其不是新的最小值或者只剩下他自己，则称其为安全的。

如果会变成最小值，则需要求出到下一条安全的蛇的距离，按照距离的奇偶性来进行决策。

那么只需要模拟这个过程即可。

直接使用堆可以得到 $70pts$。

新开一个双端队列，将 $max-min$放进队尾，每次取最大值和最小值的时候只需要比较原序列和该队列的头和尾。

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

#define fi first
#define se second
#define pb push_back
#define MP std::make_pair
#define PII std::pair<int, int>
#define all(x) (x).begin(), (x).end()
#define CL(a, b) memset(a, b, sizeof a)
#define rep(i, l, r) for (int i = (l); i <= (r); ++ i)
#define per(i, r, l) for (int i = (r); i >= (l); -- i)
#define PE(x, a) for (int x = head[a]; x;x = edge[x].next)

typedef long long ll;

template <class T>
inline void rd(T &x) {
	char c = getchar(), f = 0; x = 0;
	while (!isdigit(c)) f = (c == '-'), c = getchar();
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
	x = f ? -x : x;
}

const int MAXN = 1e6 + 7;
const PII INF = MP(0x3f3f3f3f, 0x3f3f3f3f);
const PII IND = MP(-0x3f3f3f3f, -0x3f3f3f3f);

int T, a[MAXN], n;
PII q1[MAXN], q2[MAXN];
int l1, l2, r1, r2, len, cur;

PII mx1() { return l1 <= r1 ? q1[l1] : IND; }
PII mx2() { return l2 <= r2 ? q2[l2] : IND; }
PII mn1() { return l1 <= r1 ? q1[r1] : INF; }
PII mn2() { return l2 <= r2 ? q2[r2] : INF; }

void add0() {
	if (~cur) cur ^= 1;
	else cur = 0;
}

bool add1() {
	if (~cur) { len += cur; return 1;}
	len++; return 0;
}

void solve() {
	l1 = 1, r1 = n;
	rep(i, 1, n) q1[i] = MP(a[n - i + 1], n - i + 1);
	l2 = 1, r2 = 0;

	int s = n - 1;
	len = 0, cur = -1;
	while (s--) {
		PII mx, mn;
		if (mx1() > mx2()) mx = mx1(), l1++; 
		else mx = mx2(), l2++;
		if (mn1() < mn2()) mn = mn1(), r1--;
		else mn = mn2(), r2--;
		mx.fi -= mn.fi;
		if (s && mx < std::min(mn1(), mn2())) add0();
		else if (add1()) break;
		q2[++r2] = mx;
	}

	printf("%d\n", n - len);
}

int main() {
	rd(T);
	rd(n);
	rep(i, 1, n) rd(a[i]);
	solve();
	T--;
	while (T--) {
		int k, x; rd(k);
		while (k--) {
			rd(x); rd(a[x]);
		}
		solve();
	}
	return 0;
}