题解本人赛后口胡。赛场的爆零人写的题解，有错请各位大佬们指出。
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 \times 400 + 97 = 146097$）这个天数的循环。那么暴力预处理出来 $G = A + T = 3000000 + 146097 = 3146097$ 这么多天的答案，对于任意 $r$，若 $r \le A$，直接输出，若 $r > M$，答案月日就等同于 $A + (r - A) \bmod T$，年份就是这个天数的年份 $+ \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