妈的，挂完了。
发生肾么事了?发生肾么事了?发生肾么事了?发生肾么事了?发生肾么事了?发生肾么事了?发生肾么事了?发生肾么事了?
挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了挂完了
因为我在这场比赛中超常发挥，把所有我犯过的没犯过的想到的想不到的傻逼错误全犯了一遍，我决定写一篇博客。一方面是发泄心中的火气，一方面也能防止我在今后的比赛中再因为这些容易避免的错误而卡题、吃罚时乃至于调不出题。
先浅浅地对这场比赛进行一个总结：从结果来说，过了 9 题，与第三名仅仅只有罚时差距，这个结果似乎也可以接受。但是从过程上来讲，除了三道打卡题和一道猜想题，我每道题都吃了至少一发罚时，并且绝大多数都是些到了这个水平早就不该再犯的错误，导致在罚时上与我前面的几名拉开了巨大的差距，而且还挂掉了一道树剖模板与 10 题失之交臂，这无疑是我无法接受的。
再说一个无语的事：我为了打印我准备的模板，忙着折腾宿舍楼里的打印机，结果比赛迟到了差不多 10 分钟。也许就是因为这 10 分钟，我没调出来 G；也许就是因为这 10 分钟，急着赶代码的我犯下了无数的低级错误。最让我无语的是：我打印出来的那些个模板，根！本！没！用！上！
即使是我写挂的树剖模板题，我错的也不是树剖的板子（而且我还没打印树剖板子）。所以我打这么多板子干嘛！！！
接下来我开始逐题列举我所犯的错误，警钟敲烂：
首先让我们把镜头给到 C 题，它拉开了我挂分表演的序幕：
观察下方 C 题代码，找出它们的不同
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <iostream>
#include <algorithm>
using i32 = int32_t;
using i64 = int64_t;
#define read std::cin
const int N = 1e6 + 10;
int n;
int arr[N];
int main(void)
{
//Think twice, code once!
std::ios::sync_with_stdio(false);
read >> n;
for (i32 i = 1; i <= n; ++i) read >>arr[i];
i32 res = 0;
for (i32 i = 1; i <= n; ++i, ++res){
if (arr[i +1] == arr[i] +1) {
while (i < n && arr[i +1] == arr[i] +1) ++i;
i += 1;
}
else if (arr[i +1] == arr[i] - 1) {
while (i <n && arr[i +1] == arr[i] - 1) ++i;
i += 1;
}
}
printf("%d\n", res - 1);
return 0;
}
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <iostream>
#include <algorithm>
using i32 = int32_t;
using i64 = int64_t;
#define read std::cin
const int N = 1e6 + 10;
int n;
int arr[N];
int main(void)
{
//Think twice, code once!
std::ios::sync_with_stdio(false);
read >> n;
for (i32 i = 1; i <= n; ++i) read >>arr[i];
i32 res = 0;
for (i32 i = 1; i <= n; ++i, ++res){
if (arr[i +1] == arr[i] +1) {
while (i < n && arr[i +1] == arr[i] +1) ++i;
}
else if (arr[i +1] == arr[i] - 1) {
while (i <n && arr[i +1] == arr[i] - 1) ++i;
}
}
printf("%d\n", res - 1);
return 0;
}
容易发现，我去掉了两个 i += 1;，这是因为我忽略了 for 循环已经帮我把 i 加 1 了。
单纯是写太快又没有细想细看的原因吧。这启示我们在写代码的时候要仔细想象分析算法过程。
然后是匪夷所思的 A 题，犯了一个刚学语法的人常犯的错误，甚至我前几天刚一眼帮我的一个高中同学调出来了一个一样的错误。
观察以下 A 题代码，猜测其最可能错在哪儿了
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <algorithm>
using i32 = int32_t;
using i64 = int64_t;
using pii = std::pair<i32, i32>;
#define read std::cin
const int N = 5e6;
i32 y, n, m;
i32 b[20];
i32 dis[N];
i32 q[N], hh, tt;
int main(void)
{
//Think twice, code once!
std::ios::sync_with_stdio(false);
read >> y >> n >> m;
for (i32 i = 1; i <= m; ++i) {
read >> b[i];
}
std::memset(dis, 0x3f, sizeof dis);
dis[0] = 0;
q[tt++] = 0;
for (i32 i = 1; i <= y; ++i) {
while (hh != tt && i - q[hh] > n) hh += 1;
if (hh != tt) {
dis[i] = std::min(dis[i], dis[q[hh]] + 1);
}
while (hh != tt && dis[i] <= dis[q[tt - 1]]) tt -= 1;
q[tt++] = i;
for (i32 j = 1; j <= m; ++j) {
if (1ll * i * b[j] <= y) {
dis[i * b[j]] = std::min(dis[i * b[j]], dis[i] + 1);
}
}
}
printf("%d\n", dis[y]);
return 0;
}
细心的同学一眼就会发现：const int N = 5e6，并且我声明数组的时候直接使用了 N：i32 dis[N];。因为数组是从 0 开始数的，所以容易发现，若 n = 5e6，那么数组就会越界。
接下来是 F 题。这不是一个低级错误了。我随手写个了 \(\log^2\) 的做法，TLE 了。优化成 \(\log\) 的做法就过了。
I 题是一道矩阵快速幂加速递推，我犯了一个不太经典的低级错误。
请阅读以下两份 I 题代码，找出区别
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <iostream>
#include <algorithm>
using i32 = int32_t;
using i64 = int64_t;
#define read std::cin
i32 mod;
struct Matrix
{
i32 n, m;
std::vector<std::vector<i32>> val;
Matrix(void) {}
Matrix(int x, int y)
{
n = x, m = y;
val.resize(n);
for (i32 i = 0; i <n; ++i) {
val[i].resize(m);
}
}
Matrix(int x, int y, int v)
{
n = x, m = y;
val.resize(n);
for (i32 i = 0; i <n; ++i) {
val[i].resize(m);
for (i32 j = 0; j <m; ++j) {
val[i][j] = (i == j) ? v : 0;
}
}
}
Matrix operator*(const Matrix &o) const
{
Matrix res(n, o.m);
for (i32 i = 0; i < n; ++i)
for (i32 k = 0; k <m; ++k) {
i32 tmp = val[i][k];
for (i32 j = 0; j < o.m; ++j) {
res.val[i][j] = (res.val[i][j] +1ll * tmp * o.val[k][j])% mod;
}
}
return res;
}
};
Matrix qpow(Matrix base, i64 k)
{
Matrix res(base.n, base.m, 1);
while (k){
if (k &1)res = res *base;
base = base *base;
k >>= 1;
}
return res;
}
i32 k;
i64 n;
int main(void)
{
//Think twice, code once!
std::ios::sync_with_stdio(false);
read >> mod >> k >> n;
if (n == 1) {
printf("%d\n", k);
}
else {
Matrix base(2, 2);
base.val[0][0] = 0;
base.val[1][0] = 1;
base.val[0][1] = -1;
base.val[1][1] = k;
Matrix tmp(1, 2);
tmp.val[0][0] = k;
tmp.val[0][1] = (1ll *k *k - 2) % mod;
Matrix res= tmp * qpow(base, k - 1);
printf("%d\n", (res.val[0][1] +mod) % mod);
}
return 0;
}
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <iostream>
#include <algorithm>
using i32 = int32_t;
using i64 = int64_t;
#define read std::cin
i32 mod;
struct Matrix
{
i32 n, m;
std::vector<std::vector<i32>> val;
Matrix(void) {}
Matrix(int x, int y)
{
n = x, m = y;
val.resize(n);
for (i32 i = 0; i <n; ++i) {
val[i].resize(m);
}
}
Matrix(int x, int y, int v)
{
n = x, m = y;
val.resize(n);
for (i32 i = 0; i <n; ++i) {
val[i].resize(m);
for (i32 j = 0; j <m; ++j) {
val[i][j] = (i == j) ? v : 0;
}
}
}
Matrix operator*(const Matrix &o) const
{
Matrix res(n, o.m);
for (i32 i = 0; i < n; ++i)
for (i32 k = 0; k <m; ++k) {
i32 tmp = val[i][k];
for (i32 j = 0; j < o.m; ++j) {
res.val[i][j] = (res.val[i][j] +1ll * tmp * o.val[k][j])% mod;
}
}
return res;
}
};
Matrix qpow(Matrix base, i64 k)
{
Matrix res(base.n, base.m, 1);
while (k){
if (k &1)res = res *base;
base = base *base;
k >>= 1;
}
return res;
}
i32 k;
i64 n;
int main(void)
{
//Think twice, code once!
std::ios::sync_with_stdio(false);
read >> mod >> k >> n;
if (n == 1) {
printf("%d\n", k);
}
else {
Matrix base(2, 2);
base.val[0][0] = 0;
base.val[1][0] = 1;
base.val[0][1] = -1;
base.val[1][1] = k;
Matrix tmp(1, 2);
tmp.val[0][0] = k;
tmp.val[0][1] = (1ll *k *k - 2) % mod;
Matrix res= tmp * qpow(base, n - 2);
printf("%d\n", (res.val[0][1] % mod +mod) % mod);
}
return 0;
}
聪明的同学，可能只要看到第一份代码，就发现问题所在了：
\(n\)，如此重要的变量 \(n\)，居然只在一个特判里面使用过。不错，我在快速幂的时候一不小心把 \(n\) 写成了 \(k\)，并且歪打正着地输出了正确的样例答案。
然后就是 L，经典，不能再经典了。草！！！！！
错哪儿了？？？？我问你错哪儿了？？？
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <algorithm>
using i32 = int32_t;
using i64 = int64_t;
#define read std::cin
const int N = 1e6 +10;
i32 n, m;
bool isH[N];
i32 a[N];
i64 res[N];
int main(void)
{
//Think twice, code once!
std::ios::sync_with_stdio(false);
read >>n >>m;
std::memset(res, -1, sizeof res);
for (i32 i = 1; i <= n; ++i) {
read >>a[i];
}
i32 cntH = 0;
for (i32 i = 1; i <= n; ++i) {
isH[i] = 1;
cntH += 1;
while (i < n && a[i] >= a[i +1]) i += 1;
}
i64 rtmp = 0;
for (i32 i = n, d = 1; i >= 1; --i) {
rtmp += d;
if (isH[i]) d += 1;
}
for (i32 i = cntH, pos = 1; i <= n; ++i) {
res[i] = rtmp;
while (pos > 0 && isH[pos]) pos += 1;
rtmp += pos - 1;
pos += 1;
}
for (i32 i = 1; i <= n; ++i) {
printf("%d ", res[i]);
}
puts("");
return 0;
}
如果你编译并且加上 -Wall 参数，编译器应该会告诉你答案。
不错，res 明明是 64 位整形数组，我却用 %d 输出。。。。。
十年 OI 一场空，不开 long long 见祖宗。
D 一发过了，大胆猜想题。因为我罚时吃饱了，胆子很大，随便猜，一发入魂。
接下来是 B，有一定难度的题目。我第一发确实是想错了，没什么好说的。第二发轻松通过。
然后，就是整场比赛最让我意难平的 G。
看了两眼，树上问题，链乘，整体求和。一眼树剖可做，两眼树上差分不太行（其实可行，因为操作满足先祖宗再儿子的顺序）。在看眼数据范围，总点数 \(10^6\)。直接狠狠树剖，此时距离考试结束大概还有 \(50 \min\)。
结果写了 \(20\min\)，调了 \(30 \min\)。连冲 \(11\) 发没调出来，寄了。
赛后不知所以，但是因为听了讲题，发现题目保证了左右儿子编号大于当前点编号，故节点 \(1\) 一定是根，不用找根，随手把找根删了，交一发。
过了。
当时我就蒙了，难道我找根挂了？认真的观察两下，没问题啊？？？莫非数据锅了？？？
然后开始和队友交流，然后各种 assert，最终我队友一语道破天机。
大家可以先看眼代码：
//root 已被声明为全局变量
read >> n;
for (int i = 1; i <= n; ++i) {
read >>a[i];
}
for (int i = 1; i <= n; ++i){
read >>b[i];
}
for (int i = 1; i < n; ++i) {
read >> ls[i] >> rs[i];
fa[ls[i]] = fa[rs[i]] = i;
}
for (int i = 1; i < n; ++i) {
if (fa[i] == 0) root = i;
}
assert(root == 1);// 成功 RE
大家不妨猜猜看是怎么回事？原来，\(n\) 可以为 \(1\)。此时我不会去找根，所以 \(root\) 变成了 \(0\)。
也许真的是退役太久了吧，这次一急，就原形毕露了。队友也没有发挥好，封榜后也都挂题了。于是我们也就和唯一的区域赛名额失之交臂，我也和键盘失之交臂了。
封榜前的强大都是假的，滚榜后的排名才是真的。警钟敲烂，切勿再犯！