题解本人赛后口胡。赛场的爆零人写的题解，有错请各位大佬们指出。
A. 儒略日
这题是大型模拟题。
介绍两种写法：一种代码量致死（赛 场 自 闭），一种是非常好写的。
写法 1
我在赛场的思路：预处理三种情况（闰年，平年，鬼畜 1582 年）在该年第 x 天对应的月日，然后只需快速找到适当的年就可以了，在 1582 年前每 4 年一个循环；1582 年以后 400 年一个循环，400 年中又嵌套着一个 100 年，100 年中又前套着 4 循环。每一个循环的天数相同，可以用整除 O(1) 快速跳。
时间复杂度
O(T)。
奉上赛场丑陋的代码。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL x;
LL k = 1573, r = 1461, r1 = 1460, d2, d4, d3, d5, d6;
const int N = 405;
int D[3][N], M[3][N];
int inline get(int x, int t) {
if (t && x == 2) return 29;
if (x == 4 || x == 6 || x == 9 || x == 11) return 30;
if (x == 2) return 28;
return 31;
}
int main() {
d4 = 365 * 400 + 97; d5 = 100 * 365 + 25, d6 = 100 * 365 + 24;
for (int i = 0; i <= 1; i++) {
int t = 365 + i;
int d = 0, m = 1;
for (int j = 0; j < t; j++ ){
if (d == get(m, i)) {
m ++, d = 1;
} else {
d++;
}
D[i][j] = d, M[i][j] = m;
}
}
int d = 0, m = 1;
for (int j = 0; j < 365 - 10; j++ ){
if (m == 10 && d == 4) {
d = 15;
} else if (d == get(m, 0)) {
m ++, d = 1;
} else {
d++;
}
D[2][j] = d, M[2][j] = m;
}
d2 = 366 + 365 * 2 - 10; d3 = 17 * 365 + 4;
int T; scanf("%d", &T);
while (T--) {
scanf("%lld", &x);
LL a = min(k, x / r);
LL d = 1, m = 1, y = -4713;
y += a * 4; x -= r * a;
if (y >= 0) y ++;
if (y == 1580 && x >= d2) {
y = 1583; x -= d2;
if (y == 1583 && x >= d3) x -= d3, y = 1600;
if (y == 1583) {
if (x >= 365) {
x -= 365, y++;
}
a = x / r;
y += a * 4; x -= r * a;
int k = (y % 100 || (y % 400 == 0)) ? 366 : 365;
if (x >= k) {
x -= k, y ++;
if (x >= 365) x -= 365, y++;
if (x >= 365) x -= 365, y++;
}
int t = (y % 400 == 0 || (y % 4 == 0 && y % 100));
printf("%d %d %lld\n", D[t][x], M[t][x], y);
continue;
}
a = x / d4;
y += 400 * a; x -= a * d4;
if (x >= d5) {
x -= d5, y += 100;
if (x >= d6) x -= d6, y += 100;
if (x >= d6) x -= d6, y += 100;
}
if (y % 400 != 0) {
if (x >= r1) x -= r1, y += 4;
}
a = x / r;
y += a * 4; x -= r * a;
int k = (y % 100 || (y % 400 == 0)) ? 366 : 365;
if (x >= k) {
x -= k, y ++;
if (x >= 365) x -= 365, y++;
if (x >= 365) x -= 365, y++;
}
int t = (y % 400 == 0 || (y % 4 == 0 && y % 100));
printf("%d %d %lld\n", D[t][x], M[t][x], y);
} else {
if (x >= 366) {
x -= 366, y ++;
if (y == 0) y++;
if (x >= 365) x -= 365, y++;
if (x >= 365) x -= 365, y++;
}
int t;
if (y < 0) t = (y % 4 == -1);
else t = y % 4 == 0;
if (y == 1582) {
printf("%d %d %lld\n", D[2][x], M[2][x], y);
} else {
if (y < 0) printf("%d %d %lld BC\n", D[t][x], M[t][x], -y);
else printf("%d %d %lld\n", D[t][x], M[t][x], y);
}
}
}
return 0;
}
写法 2
xtq 鸽鸽教了我一个超好写的方法，tql！
具体是通过观察样例 2 发现，到 1582 年 <A=3000000 天，而之后都是 400 年共 97 闰年的循环（共 T=365×400+97=146097）这个天数的循环。那么暴力预处理出来 G=A+T=3000000+146097=3146097 这么多天的答案，对于任意 r，若 r≤A，直接输出，若 r>M，答案月日就等同于 A+(r−A)mod，年份就是这个天数的年份 + \lfloor (r - A) / T \rfloor。
非 常 好 写。
时间复杂度
复杂度 O(G + T)，每个询问还是 O(1)。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 3146100;
int A = 3000000, T = 146097, G = A + T;
int D[N], M[N], Y[N];
int days[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int inline isLeap(int y) {
if (y <= 1582) return y > 0 ? (y % 4 == 0) : (y % 4 == -1);
else return y % 400 == 0 || (y % 4 == 0 && y % 100);
}
int inline getDays(int x, int y) {
if (y && x == 2) return 29;
else return days[x];
}
void init() {
int d = 1, m = 1, y = -4713;
for (int i = 0; i <= G; i++) {
D[i] = d, M[i] = m, Y[i] = y;
if (d == 4 && m == 10 && y == 1582) {
d = 15;
} else if (d == getDays(m, isLeap(y))) {
d = 1;
if (m == 12) {
m = 1, y ++;
if (y == 0) y++;
} else m++;
} else d++;
}
}
void inline out(int d, int m, int y) {
if (y < 0) printf("%d %d %d BC\n", d, m, -y);
else printf("%d %d %d\n", d, m, y);
}
int main() {
init();
int Q; scanf("%d", &Q);
while (Q--) {
LL r; scanf("%lld", &r);
if (r <= A) out(D[r], M[r], Y[r]);
else {
int a = A + ((r - A) % T);
out(D[a], M[a], Y[a] + (r - A) / T * 400);
}
}
return 0;
}
B. 动物园
由于这题保证 a_i, q_i 各自互不相同，所以会好写一些。
把所有 a_i 所覆盖的所有位搞出来，这只需要一个按位或，设 w_i 表示所有 a 中有没有第 i 位为 1 的。
考虑什么情况才不能选择一位，对于一个要求 p, q，若 w[p] = \text{false}，就意味着第 p 位肯定不能选（由于 q 互不相同，不会其他的 p 会使原来买了 q 了）。
设能选的位数是 k，答案就是 2 ^ k - n，即所有满足的（组合计数算出） - 目前已经有的。
若 k = 64，则式子直接算会爆 \text{unsigned long long} 需要特判。
时间复杂度
O(n)。
P.S. 如果不保证各不相同（我赛场就是这样眼瞎），只需要把 q 离散化，记录覆盖了哪些 q，把 a 去重即可，再扫一遍限制，复杂度只带排序的 O(n \log n)。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000005;
typedef unsigned long long ULL;
int n, m, c, K;
bool f[64];
ULL a[N];
int main() {
scanf("%d%d%d%d", &n, &m, &c, &K);
ULL sum = 0;
for (int i = 1; i <= n; i++) {
ULL x; scanf("%llu", &x); sum |= x;
}
int c = K;
for (int i = 1, p, q; i <= m; i++) {
scanf("%d%d", &p, &q);
if (!(sum >> p & 1) && !f[p]) f[p] = true, c--;
}
if (c == 64) {
if (n == 0) puts("18446744073709551616");
else printf("%llu\n", (~0ull) - (n - 1));
} else printf("%llu\n", (1ull << c) - n);
}
C. 函数调用
事实上，你可以把整个问题作如下转化：
- 对于每个 a_i，可以看作新增了一个在最开始的 P = i, V = a_i 的 1 操作。
- 对于函数操作序列，可以看作新增一个 3 操作 m + 1，他的顺序就是 f。
如果对于每个 3 操作，让 j 向所有他调用的所有函数 g 顺序连一条有向边，由于题中不会调用自身的限制，这个图即变成一个有向无环图。
那么问题就变得统一了起来，即从 m + 1 开始遍历，每次按边的顺序 dfs，经过的 1, 2 操作做一遍操作，求最终的数组。
如果把 dfs 经过的所有点顺序打成一个序列，我们发现乘法实际上是把之前的加法整体乘一个数。
每经过一个加法来说，设其后经过的乘法数值乘积是 s，他的贡献就是让 a_P 加上了 V \times s。 也可以理解为添加了执行了 s 次这个操作的贡献。
我们执行一遍逆拓扑序，把调用每个点走到的所有乘法操作乘积 \text{mul} 找出来。
我们设 cnt_i 为第 i 个点所在操作需要执行多少次，我们只需要把这个东西算出来就可以了。
初始令 cnt_{m + 1} = 1，然后我们尝试递推到每一个点。
然后我们执行一遍拓扑排序，对于每个点 u，维护一个值初始为 s = cnt_u ，我们反向遍历他的每个指向点 v：
- 让 cnt_v 加上 s
- 让 s 为 s \times mul_v
你可以理解为每次遍历到 u 这个点就是需要执行 cnt_u 次的时候，我们考虑把这个点删掉，那么对于他的每个指向点 v，只需要加上其后指向边的乘积次，贡献加上，那么各个指向点就各自独立了。由于拓扑排序，因此每个点 u 被遍历时，能够让 cnt 变化的点都处理完了，所以是对的。
时间复杂度
O(n + m + Q + \sum C_j) （线性）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 100005, P = 998244353;
int n, a[N], m, T[N], B[N], V[N], Q, f[N];
int mul[N], q[N], in[N], deg[N], cnt[N];
vector<int> g[N], e[N];
int inline power(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (LL)res * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return res;
}
void inline topo1() {
int hh = 0, tt = -1;
for (int i = 1; i <= m; i++) if (!deg[i]) q[++tt] = i;
while (hh <= tt) {
int u = q[hh++];
for (int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
mul[v] = (LL)mul[v] * mul[u] % P;
if (--deg[v] == 0) q[++tt] = v;
}
}
}
void inline topo2() {
int hh = 0, tt = -1;
for (int i = 1; i <= m; i++) if (!in[i]) q[++tt] = i;
while (hh <= tt) {
int u = q[hh++], s = cnt[u];
for (int i = g[u].size() - 1; ~i; i--) {
int v = g[u][i];
(cnt[v] += s) %= P;
if (--in[v] == 0) q[++tt] = v;
s = (LL)s * mul[v] % P;
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
scanf("%d", &m);
for (int i = 1; i <= m; i++) mul[i] = 1;
for (int i = 1; i <= m; i++) {
scanf("%d", T + i);
if (T[i] == 1) scanf("%d%d", B + i, V + i);
else if (T[i] == 2) scanf("%d", V + i), mul[i] = V[i];
else if (T[i] == 3) {
scanf("%d", V + i);
for (int j = 0, x; j < V[i]; j++) {
scanf("%d", &x);
g[i].push_back(x), e[x].push_back(i);
in[x]++, deg[i]++;
}
}
}
topo1();
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) scanf("%d", f + i);
int s = 1;
for (int i = Q; i; i--) {
if (T[f[i]] != 2) (cnt[f[i]] += s) %= P;
s = (LL)s * mul[f[i]] % P;
}
for (int i = 1; i <= n; i++) a[i] = (LL)a[i] * s % P;
topo2();
for (int i = 1; i <= m; i++)
if (T[i] == 1) a[B[i]] = (a[B[i]] + (LL)V[i] * cnt[i]) % P;
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
return 0;
}
D. 贪吃蛇
假设每条蛇都选择吃，我们把每轮的情况模拟出来，即模拟出：
- mx_i / mn_i 还剩 i 条蛇的轮次（吃之前）时，实力最强 / 最弱的蛇
- d_i 第 i 条蛇被吃掉后，还有几条蛇
由于轮次越前的蛇越有决定权，我们可以考虑从后往前推，最终结果仅有一条蛇，这是这条蛇满意的结果，动态维护一个 ans = 1，然后枚举 i 从 2 到 n （枚举还有几条蛇的时间）：
- 如果 d_{mx_i} \ge ans，那么 mx_i 会在从当前状态到我们目前答案的时间段中被吃掉，所以 mx_i 这轮不会选择吃，即要改变 ans = i。
- 否则，mx_i 会同意吃，所以 ans 不变，因为自己在后续不会死。
由于惨淡的数据范围，要求我们必须做到线性 O(Tn)
后面推的时间是线性的，只需要快速（线性）模拟情况。
把问题抽象出来：
开始我们有 a_1 \le a_2 \le \text{…} < a_n，n 个数，每个数与其下标作为一个二元组参与比较 (a_i, i)，把这些二元组加入集合。
- 执行 n - 1 轮，每次从集合中找出并弹出最大和最小的两个数 （设这两个数下标为 mx, mn），然后把 (a_{mx} - a_{mn}, mx) 加入集合。
如果要线性，必须满足加入的这个东西满足一些单调性，如 NOIP 2016 蚯蚓的那题。
我们设第 i 轮最大最小的数值分别是 A_i, B_i，推入集合的数值是 C_i = A_i - B_i。
因为不会推入更大的数进集合，所以满足 A_i \ge A_{i+1}，此时只需满足 B_i \le B_{i+1}，我们就可以发现 C_i 是单调非严格递减的了。但实际并不令我们所想的那样美好，我们需要对 B 的情况进行分类讨论。
Case 1
若需 B_i \le B_{i+1}，需要做到推入的数不小于最小的数，即对于任意的 i 都有 A_i - B_i \ge B_i \Leftrightarrow A_i \ge 2B_i 的话，C_i 是单调非严格递减的。那么我们只需要像蚯蚓那题一样开两个单调数组，b 保存初始的蛇，c 保存推入的蛇，两个蚯蚓都是单调的，极值就在队头队尾。
还有一个小问题，我们只保证数值满足关系，下标能否满足呢？
当 C_i = C_{i+1} 时，当且仅当 A_i = A_{i+1} 且 B_i = B_{i+1}，在这种情况下由于 A_i 的下标是大于 A_{i+1} 的下标，所以产生的 C_i 下标也是递减的。
Case 2
我们找到第一个 A_i - B_i < B_i \Leftrightarrow A_i < 2B_i。
设此时有 n 个元素，然后按顺序最小到大排好是 a 数组（实际上是把两个 Case 分开处理了，现在变成了一个新的问题而且初始就满足）。
此时排序，实际上是一个将 Case 1 中两个单调数组做二路归并排序的过程，是 O(n) 的，并且只会执行一次。
那么 A_i = a_n, B_i = a_1。
这种时候：
- 第 2 轮取出来的最小元素肯定是上次的数即 a_n - a_1，最大值是 a_{n - 1}，产生的 a_{n - 1} - (a_n - a_1) = (a_{n - 1} - a_n) + a_1 \le a_1
- 第 3 轮取出来的最小元素的值（注意这里元素不一定，因为还有下标的限制）一定是 a_{n - 1} - (a_n - a_1)，最大元素一定是 a_{n - 2}，产生的 a_{n - 2} - [a_{n - 1} - (a_n - a_1)] = a_{n - 2} - a_{n - 1} + (a_n - a_1) < a_1
注意这里的轮重新从进入 Case 2 算起，可以理解为我们把问题变成了一个一开始就满足 a_n < 2a_1 的一个问题。
这种时候，通过观察发现后续偶数轮数值都是 \le a_1，奇数轮都是 < a_1。
还是数学归纳法证一下吧：
设 f_i 为第 i 轮推出的数，f_1 = a_n - a_1 < a_1, f_2 = a_{n - 1} - (a_n - a_1) = (a_{n - 1} - a_n) + a_1 \le a_1
对于任意 i \ge 3，有 f_i = a_{n - i + 1} - f_{i - 1} = a_{n - i + 1} - a_{n - i + 2} + f_{i - 2} \le f_{i - 2}，因此每个 i 都有 f_i \le f_{i \bmod 2}
证毕。
这样证明完以后，我们发现产生的数要么马上下一轮作为最小值被咔嚓，要么有跟他同值得倒霉蛋代替他受罚。
那如果此时我们还用 Case 1 的方法还能保持单调吗？发现同值情况仅出现在 = a_1 的情况。如果推入的数 \not= a_1，他下一轮就被取出去，所以可以保证 c 只有一个元素。若有多个 = a_1 的情况，即需要满足当前的 [n - i + 1, n] 这个区间的 a 全 = a_n，才能满足那个偶数轮次取等。b 队列中相同的值，下标大的会先作为最大值然后弹出来，所以 c 中也是满足单调递减的。
时间复杂度
O(Tn)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int N = 1000005, INF = 2e9;
int n, a[N], d[N], mx[N], mn[N], ans;
struct E{
int x, id;
bool operator < (const E &b) const {
if (x != b.x) return x < b.x;
return id < b.id;
}
bool operator == (const E &b) const {
return x == b.x && id == b.id;
}
};
E b[N], c[N], f[N];
int hh, tt, L, R;
E inline getMax() {
E x = (E) { -1, -1 };
if (hh <= tt && x < b[hh]) x = b[hh];
if (L <= R && x < c[L]) x = c[L];
if (hh <= tt && x == b[hh]) hh++;
if (L <= R && x == c[L]) L++;
return x;
}
E inline getMin() {
E x = (E) { INF, INF };
if (hh <= tt && b[tt] < x) x = b[tt];
if (L <= R && c[R] < x) x = c[R];
if (hh <= tt && x == b[tt]) tt--;
if (L <= R && x == c[R]) R--;
return x;
}
void inline merge() {
int len = tt - hh + 1 + R - L + 1;
for (int k = 1, i = hh, j = L; k <= len; k++) {
if (j > R || (i <= tt && c[j] < b[i])) f[k] = b[i++];
else f[k] = c[j++];
}
L = 0, R = -1;
hh = 1, tt = len;
for (int i = 1; i <= len; i++) b[i] = f[i];
}
void inline solve() {
hh = 0, tt = -1, L = 0, R = -1;
memset(d, 0, sizeof d);
ans = 1;
for (int i = n; i; i--) b[++tt] = (E) { a[i], i };
bool ok = false;
for (int i = n; i >= 2; i--) {
E A = getMax(), B = getMin();
mx[i] = A.id, mn[i] = B.id;
c[++R] = (E) { A.x - B.x, mx[i] };
if (!ok && A.x < B.x * 2) {
ok = true;
merge();
}
d[mn[i]] = i - 1;
}
for (int i = 2; i <= n; i++)
if (d[mx[i]] >= ans) ans = i;
printf("%d\n", ans);
}
int main() {
int T; scanf("%d", &T); T--;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
solve();
while (T--) {
int k; scanf("%d", &k);
for (int i = 1, x, y; i <= k; i++) {
scanf("%d%d", &x, &y);
a[x] = y;
}
solve();
}
return 0;
}
QAQ
%%%%%%%%
此处省略 10 * 10 ^ 10 ^ 10 个%%%
orz orz orz ......(此处省略1000000000000000000000000000000000000000000000000000000000000000个orz)
粉丝团前来支持！
粉丝团前来支持！
qwq
粉丝团前来支持~
QAQ