【解题报告】CSP-S 2020
考完自闭了，怎么能这么菜......
$\text{julian}$
考虑分成公元前，$1582.10.4$ 及以前，$1582.10.15$ 以后三种情况。
暴力模拟即可。
//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;
}
出题人很有精神！
$\text{zoo}$
随便分位考虑一下，求有哪些饲料存在，然后暴力每一位判断。如果该位可以放，就 $\times 2$ 。注意 $n=0,k=64$ 的时候 $2^{64}$ 会炸 $\text{unsigned long long}$，谢谢出题人送我退役。
//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;
}曾经，不开 $\text{long long}$ 见祖宗；今天，开了 $\text{unsigned long long}$ 我还是见祖宗了。
$\text{call}$
怎么考场上这题都写不出......
根据部分分极强的提示 我们不难发现函数调用关系是一个 $\text{DAG}$。又每一个加法实际上是独立的，只需要乘一下后面的所有乘法操作即可。
考虑建出 $\text{DAG}$，正反各做一遍 $\text{toposort}$（令被调用的函数向调用他的函数的边为正）。
先通过反图求出经过每一个点的乘法操作，然后通过正图更新每一个加法操作即可。
可以把初始的 $a$ 看做 $n$ 个加法标记，或许会稍微简单一些。
//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;
}$\text{snakes}$
考虑如果一条蛇选择结束，需要满足什么条件。
如果他吃掉最后一名之后，没有变成最后一名，那么他一定选择吃。称这样是必吃状态。
由于整个序列是递增的，如果他吃了最后一名而没有掉到最后一名，会使得序列的 $\min$ 增大，$\max$ 减小。那么新的第一名如果选择吃，那一定会落到原先第一名更后面。
那就让新的第一名去选择是否结束，反正我吃了不会比他先死。
如果他吃掉最后一名之后，变成了最后一名，那么找到距离他最近的必吃状态，我吃不吃只和与这个必吃状态的 距离 的 奇偶性 相关。
设我在 $p$，最近的必吃状态位置是 $s$。
首先显然的是 $s$ 处必定会吃，那考虑 $s$ 到 $p$ 之间的蛇，他们一定不是必吃状态，那一定有：这些蛇选择吃之后的新状态的体力值单调。
也就是说，如果 $s$ 吃，他一定吃的是 $s+1$。$s+1$ 知道自己会被吃，那么他就选择不吃最小的；$s+1$ 不吃，就会选择结束，那么 $s+2$ 就知道自己就算变成最后，也不会死，那么他一定选择吃......
也就是，如果 $p-s$ 是奇数，他就会结束游戏，否则一定会吃掉最小的，而接下来新的第一名就一定会直接结束游戏。
然后拿队列模拟一下，和 $\text{NOIP2016}$ 蚯蚓一样维护一个双端队列，每次从原队列和新队列取 $\max$ 和 $\min$ 更新即可。
只要遇上一个非必吃状态，就 $\mathcal{O(n)}$ 模拟找到下一个必吃状态，返回答案即可。
//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;
}