NOIP 2021 失恋记

NOIP2021

学了四年多终于第一次参加提高组 NOIP.

Day $-3$

做了一些状压, 属于是无头苍蝇乱飞了.

考前学新东西的是我了, 发现欧拉路没学, 怒补, 晚上因为自己无法发明欧拉路算法破防了, 遂颓.

Day $-2$

感觉什么都没做就已经 Day $-2$ 了啊.

早上贺了欧拉路.

然后补了一些模拟赛的题, 晚上就回家了, 考前颓颓颓.

Day $-1$

今天在家颓颓颓.

颓以外的事情, 发现字符串哈希和 Nim 博弈的板子没做, 怒做, 然后把二gou子新出的题写了.

晚上回到机房, 研究了几个题 (就是看了题解, 连贺都懒得贺了).

Day $0$

早读听说明天可以睡到 $7:10$ , 高兴.

今天早上开了一场 NOIP2020 重现赛, 去年 CSP 爆零后, 一年了都没舍得打, 就等今天打了.

因为早就知道排水系统的鼎鼎大名, 所以我早就计划用 long double 来做了, 然后精度爆了, 调了两个小时参, 失败, 遂写高精.

一个小时后, 发现高精除法非常难写, 心态爆炸, 遂看 T2.

一上来就发现可以线性求出所有后缀和前缀的出现奇数次的字母数量.

T2 一开始想的是固定 $A$ , 然后讨论 $B$ , $C$ , 发现不可做. 倒着考虑, 先枚举 $C$ , 然后把这个 $C$ 可以对应的所有 $AB$ 的首次循环的末尾位置都打上标记. 因为 $AB$ 一定是 $S - C$ 的一个周期, 所以最多只有因数个, 每个 $C$ 的复杂度是 $O(\sqrt n)$ . 这样就可以对每个点记录下它后面可以跟的 $C$ 里面各种奇数字母数量的 $C$ 的个数.

然后从左往右扫描第一个 $AB$ , 对于每个 $AB$ , 相比上一个, 差别是多了一个 $A$ 的情况, 其它都相同, 所以可以用 $26$ 的常数维护这个个数的前缀和, 对每个它后面可以跟的 $C$ 的奇数字母数量计算贡献.

总复杂度 $O(n (\sqrt n + 26))$ . 得了 $84'$ .

这一切只用了不到一个小时.

然后花了十几分钟把换了好几个方案的 T1 改成 unsigned long long, 拿了 $90'$ .

最后还有不到半个小时, 什么都做不了了, 遂颓. 总分 $174'$ , 放到去年能到省一, 但是无缘省队.

Day $1$ : Prepare

达成成就: 在历城二中宿舍睡到 $6:40$ .

起来以后去五楼机房播放 好运来, 一边进食一边查阅爆零血泪史.

从五楼看选手入场感觉十分激动.

进场后, 虽然已经体验过这个傻逼隔板, 但是仍然不是很自在.

试机时写了快读, 对拍, 仍然是拿快读和 scanf 拍. 然后闲得无聊, 又去写 WBLT, 可惜没写完.

$8:20$ 左右发了密码, 但是不让看题, 非常难受. 按说文化课考试发卷子以后, 铃没响, 只要不动笔想怎么看怎么看啊.

Day $1$ : Number

暴力

开题后发现第一题貌似可以骗他一骗, 火速写了一个复杂度玄学的程序, 先找出 $1e5$ 以内含 $7$ 的所有数, 然后枚举每个数的倍数. 最后询问时, 直接往后扫描即可.

定义一个 bitset 如果 $f_i = 0$ 表示 $i$ 是可以报的, $f_i = 1$ 表示 $i$ 不能报. 写的过程中发现这个东西是根据因数的值更新积的值, 换句话说, 如果 $f_i = 1$ 则对于所有正整数 $k$ , $f_{ik} = 1$ .

线性筛

我思考 $f$ 是否算得上是类似积性函数的东西, 所以我写了一个线性筛, 先把本身就有 $7$ 的数赋值, 然后在更新是否是质数的数组时, 将 $f_{iPrime_j} |= f_{i}$ .

但是这样会造成有些位置无法被赋值, 如 $135$ , 在线性筛中, 它是被 $3 \times 45$ 筛掉的, 但是 $f_{45}$ 和 $f_3$ 都不是 $1$ . $f_{135}$ 应当被 $5 \times 27$ 更新.

乱搞

于是我们想到, 既然线性筛是筛素数的, 那么我写一个新的筛法, 让它专门筛不能删除的数不就好了吗.

于是新开一个数组 $No$ , 表示它的倍数需要更新. 每次遇到 $No_i = 1$ , 都枚举 $j \in [1, \lfloor \frac{n}{i} \rfloor]$ , 把 $f_{ij}$ 变成 $1$ , 把 $No_{ij}$ 变成 $0$ .

$No_i = 1$ 的 $i$ 是十进制中自带 $7$ 的数, 线性求出即可.

正确性

这样的正确性是因为如果 $i$ 的倍数的 $f_i$ 都被 $i$ 更新了, 那么 $i$ 的倍数去更新它的倍数的时候, 更新到的一定也都是 $i$ 的倍数, 所以不必用被自己因数更新过的数去更新它的倍数.

这样也能保证所有 $No$ 不是 $0$ 的数的倍数都被更新, 也不会漏下什么.

虽然这样做的复杂度没有那么显然, 而且貌似严格大于线性, 但是实践证明它可以跑得飞快, 场上就没再深究.

首先发现这样的复杂度最多是 $O(n \sqrt n)$ , 因为显然一个数最多被它每个因数更新 $1$ 次, $i$ 的因数数量是 $O(\sqrt i)$ 的.

然后发现一个数 $i$ 被更新的所有次数中, 假设更新它的数是 $j_1$ , $j_2$ ,…, $j_k$ , 我们知道这 $k$ 个 $j$ 两两互质, 因为如果 $j_x$ 是 $j_y$ 的倍数, 那么 $j_y$ 更新倍数后, $j_x$ 就不能更新别人了.

因为 $i$ 的质因数是 $O(\log i)$ 的, 所以容易发现 $k$ 的数量级也应该是 $O(\log i)$ 的, 因为 $i$ 的每个质因数, 最多在一个 $j$ 里面出现.

这样复杂度就是 $O(n\log n)$ , 这个 $\log n$ 的上界还非常松, 所以可以认为它和线性算法是一个水平的. (场上实测它运行的时间是线性筛的 $150\%$ 左右)

回答询问

$f$ 筛出来以后, 回答询问就很简单了, 直接跳 $f_{i + j}$ 直到 $f_{i + j} = 0$ 为止也不是没可能过, 也有很多人把所有 $f_i = 0$ 的 $i$ 存到一个数组里, 用二分查找询问. 但是我就不明白为什么不能直接存答案, 反正都要开 $10^7$ 数量级的空间, 我定义 $Ans_i$ 为 $i$ 后面第一个 $f$ 值为 $0$ 的数即可 $O(1)$ 回答询问.

考场代码大赏

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<bitset> 
using namespace std;
inline unsigned RD() {
  unsigned TmpRD(0);
  char RChr(getchar());
  while ((RChr < '0') || (RChr > '9')) RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD;
}
inline int RDsg() {
  int TmpRD(0), TmpSg(1);
  char RChr(getchar());
  while (((RChr < '0') || (RChr > '9')) && (RChr ^ '-')) RChr = getchar();
  if(RChr == '-') TmpSg = -1, RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD * TmpSg;
}
unsigned n, m, t;
unsigned A, B, C, D, Op;
unsigned Ans[11000005], Cnt(0);
bitset<11000005> No, Need;
signed main() {
  freopen("number.in", "r", stdin);
  freopen("number.out", "w", stdout);
  for (unsigned i(0); i <= 10000001; i += 7) No[i] = 1;
  for (unsigned i(7); i <= 10000001; i += 10) No[i] = 1;
  for (unsigned i(70); i <= 10000001; i += 100) for (unsigned j(0); j < 10; ++j)
    No[i + j] = 1;
  for (unsigned i(700); i <= 10000001; i += 1000) for (unsigned j(0); j < 100; ++j)
    No[i + j] = 1;
  for (unsigned i(7000); i <= 10000001; i += 10000) for (unsigned j(0); j < 1000; ++j)
    No[i + j] = 1;
  for (unsigned i(70000); i <= 10000001; i += 100000) for (unsigned j(0); j < 10000; ++j)
    No[i + j] = 1;
  for (unsigned i(700000); i <= 10000001; i += 1000000) for (unsigned j(0); j < 100000; ++j)
    No[i + j] = 1;
  for (unsigned i(7000000); i < 8000000; ++i) No[i] = 1;
  for (unsigned i(2); i <= 10000001; ++i) if(No[i]) {
    Need[i] = 1;
    for (unsigned j(2); i * j <= 10000001; ++j) Need[i * j] = 1, No[i * j] = 0;
  }
  for (unsigned i(10000001), j(0); i; --i) {
    Ans[i] = j;
    if(!Need[i]) j = i;
  }
  t = RD();
  for (unsigned T(1); T <= t; ++T) {
    n = RD();
    if(Need[n]) {printf("-1\n");continue;}
    printf("%u\n", Ans[n]);
  }
  return 0;
}
/*
5865
*/

评价

整个题做完让人摸不着头脑, 我都不知道写了个什么就过了, 我甚至不知道它的复杂度. 只是三个版本的代码地花了一些时间, 拍完之后已经将近 $1H$ 了.

Day $1$ : Sequence

正解

一眼就是 DP, 数据范围给人一种 “你随便设状态, 但是别想状压” 的感觉. 于是就从一维状态胡到 $4$ 维. 于是 $15min$ 不到就把方程写出来了.

又花了 $15min$ 左右, 根据方程写出代码, 借助样例这里修修那里补补, 然后就过样例了.

测大样例没过, 我觉得这是情理之中, 这么草率的方程能过就有鬼了. 输出 $f$ 数组发现是初值赋得不对, 改过来顺利过大样例.

对拍

如果放在以前, 我可能就去干 T3 了, 但是这极有可能是我最后一次 NOIP 了, 所以还是决定要写对拍.

这个题数据很好造, 所以瞬间造完了, 但是想到暴力就是按部就班爆搜, 于是没了动力, 一边看 T3 一边写爆搜.

把 T3 式子推完以后, 断断续续地写完爆搜一遍过拍.

造了一个极限数据, 在考场代码跑了 $0.6s$ 左右, 稳了.

考场代码大赏

事实上我是写了一篇题解的.

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<bitset> 
using namespace std;
inline unsigned RD() {
  unsigned TmpRD(0);
  char RChr(getchar());
  while ((RChr < '0') || (RChr > '9')) RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD;
}
inline int RDsg() {
  int TmpRD(0), TmpSg(1);
  char RChr(getchar());
  while (((RChr < '0') || (RChr > '9')) && (RChr ^ '-')) RChr = getchar();
  if(RChr == '-') TmpSg = -1, RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD * TmpSg;
}
const unsigned long long Mod(998244353);
unsigned long long Ans(0), C[35][35], a[105][35];
unsigned f[105][35][35][35], Pop[105];
unsigned n, m, t;
unsigned A, B;
unsigned Cnt(0);
signed main() {
  freopen("sequence.in", "r", stdin);
  freopen("sequence.out", "w", stdout);
  n = RD(), m = RD() + 1, t = RD();
  for (unsigned i(1); i <= m; ++i) {
    a[i][0] = 1, a[i][1] = RD();
    for (unsigned j(2); j <= n; ++j)
      a[i][j] = a[i][j - 1] * a[i][1] % Mod;
  }
  for (unsigned i(1); i <= 102; ++i) Pop[i] = Pop[i >> 1] + (i & 1);
  C[0][0] = 1;
  for (unsigned i(1); i <= n; ++i) {
    C[i][0] = 1;
    for (unsigned j(1); j <= n; ++j) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
      if(C[i][j] >= Mod) C[i][j] -= Mod;
    }
  }
  for (unsigned i(0); i <= m; ++i) f[i][0][0][0] = 1;
  for (unsigned i(1); i <= m; ++i) {
    for (unsigned j(1); j <= n; ++j) {
      for (unsigned k(0); k <= t; ++k) {
        for (unsigned jj(0); jj <= j; ++jj) {
          for (unsigned ll(0); ll <= n; ++ll) {
            if((ll + jj) & 1) {
              if(!k) continue;
              f[i][j][k][(ll + jj) >> 1] = ((f[i][j][k][(ll + jj) >> 1] + (f[i - 1][j - jj][k - 1][ll] * C[n - j + jj][jj] % Mod) * a[i][jj]) % Mod);
            } else {
              f[i][j][k][(ll + jj) >> 1] = ((f[i][j][k][(ll + jj) >> 1] + (f[i - 1][j - jj][k][ll] * C[n - j + jj][jj] % Mod) * a[i][jj]) % Mod);
            }
          }
        }
      }
    } 
  }
  for (unsigned i(0); i <= t; ++i) {
    for (unsigned j(0); j <= n; ++j) {
      if(Pop[j] + i <= t) {
        Ans += f[m][n][i][j];
        if(Ans >= Mod) Ans -= Mod;
      }
    }
  }
  printf("%u\n", Ans);
  return 0;
}
/*
5865
*/

评价

这个题更加令人迷惑, 我直到过拍都不知道为什么这样是对的. 而且 $8.1*10^7$ 的复杂度也很恐怖, 我也不知道为什么跑那么快.

这个题写完最终程序大概不到半个小时, 最后写对拍断断续续加上把后两个题读完思考了一会, 过拍时总时间也就过了 $2$ 小时不到.

Day $1$ : Variance

式子

首先看到一个操作会影响一个元素和它相邻的元素, 我之前做过两道题, 它们的性质都类似于使序列前缀和交换, 但是这道题好像和前缀和没有什么关系.

然后我便开始从方差的式子上下功夫, 因为之前做的题只要有方差, 推完之后的式子一般会非常好看.

\begin{aligned} D &= \frac 1n \sum_{i = 1}^{n} (a_i - \bar a)^2\\ &= \frac 1n \sum_{i = 1}^{n} (a_i^2 - 2a_i\bar a + \bar a^2)\\ Dn^2 &= n \sum_{i = 1}^{n} (a_i^2 - 2a_i\bar a + \bar a^2)\\ &= n \sum_{i = 1}^{n} a_i^2 - 2\sum_{i = 1}^{n}a_i\sum_{j = 1}^{n}a_j + (\sum_{i = 1}^{n} a_i)^2\\ &= n \sum_{i = 1}^{n} a_i^2 - (\sum_{i = 1}^{n} a_i)^2\\ \end{aligned}

如果用 $S$ 代替 $\displaystyle{\sum_{i = 1}^n a_i}$ , 式子就变成:

Dn^2 = n \sum_{i = 1}^{n} a_i^2 - S^2\\

我一开始是把每个元素变成一个点 $P_i = (i, a_i)$ , 手玩一般情况, 发现如果对一个元素 $P_i$ 执行操作, 则相当于把线段 $P_{i - 1}P_{i}$ , $P_{i}P_{i + 1}$ 交换位置, 中间的交点就是新的 $P_{i}$ .

这个东西看似毫无头绪, 但是我发现这样就可以保证整个序列永远单调不降. 直觉告诉我, 这个性质绝对有用.

所以单调的序列相比随机序列有什么特殊性呢? 作为 unsigned 玩家, 我可以轻松地用差分数组表示这个序列, 而仔细一看发现每次操作相当于差分数组的邻位交换. 换汤不换药, 这个性质绝对有大用.

有了这个性质, 我们就可以用 $b_i$ 表示 $a_i - a_{i - 1}$ , 特别地, $a_0 = 0$ .

既然是对差分数组进行交换, 那么我们就可以得到 $b_2$ 到 $b_n$ 的任何一个排列, 一共 $(n - 1)!$ 种情况.

如果用 $\displaystyle{\sum_{j = 1}^i b_j}$ 来表示 $a_i$ , 我们就可以 $O(n)$ 对一个数组求方差了.

但是显然这个式子需要更加复杂的化简, 更加绝望的是, 我的草稿纸用满了 (历城二中真是出了名的抠门, 不愧是农村学校, 一张 B5 纸就像打发 NOIP2021, 想当年 NOIP2018 普及组初赛我都用了满满两面 A4), 但是社恐让我无法开口索要, 于是插字缝推出了下面的式子.

\begin{aligned} s_i &= \sum_{j = i}^{n} (n - j + 1)b_j\\ Dn^2 &= n \sum_{i = 1}^{n} a_i^2 - S^2\\ &= n \sum_{i = 1}^{n} (\sum_{j = 1}^i b_j)^2 - S^2\\ &= n \sum_{i = 1}^{n} (\sum_{j = 1}^i b_j)^2 - (\sum_{i = 1}^{n}\sum_{j = 1}^{i} b_j)^2\\ &= n \sum_{i = 1}^{n} (\sum_{j = 1}^i b_j)^2 - (\sum_{i = 1}^{n} (n - i + 1) b_i)^2\\ &= n \sum_{i = 1}^{n}\sum_{j = 1}^i\sum_{k = 1}^i b_jb_k - s_1^2\\ &= n \sum_{i = 1}^{n}\sum_{j = i}^{n} (n - j + 1)b_ib_j + n \sum_{i = 1}^{n}\sum_{j = 1}^{i - 1} (n - i + 1)b_ib_j - s_1^2\\ &= n \sum_{i = 1}^{n}b_i\sum_{j = i}^{n} (n - j + 1)b_j + n \sum_{i = 1}^{n}b_i\sum_{j = i + 1}^{n} (n - j + 1)b_j - s_1^2\\ &= n \sum_{i = 1}^{n}b_is_i + n \sum_{i = 1}^{n}b_is_{i + 1} - s_1^2\\ &= n \sum_{i = 1}^{n}b_i(s_i + s_{i + 1}) - s_1^2\\ \end{aligned}

这样就可以 $O(n)$ 求方差了.

不过在 $Day8$ 也就是 2021.11.27, 我猛然发现完全可以用差分数组直接把 $a$ 求前缀和积出来, 然后直接根据定义求 $Dn^2$ , 所以我考场上这 $1.5H$ 是浪费了的, 而如果节省下这些时间, 我完全可以在 T4 刮到一点分.

就当是行为艺术了吧, 虽然我没有把过程写到代码里进不了迷惑行为.

$O(n!n)$

这个复杂度虽然长得很像中指, 但它的确是个能拿 $12'$ 的复杂度.

许久没有想法, 火速写 $O(n!n)$ 出来, 然后跑了一些数据, 对于每次更新答案输出 $b$ , 发现最后的 $b$ 一定满足先单调不增后单调不降.

$O(2^nn)$

虽然不知道为什么, 但是貌似这个性质可以进行优化, 但是我也不知道如何构造靠谱的两头高的数据, 所以还只能爆搜, 但是复杂度到了 $O(2^nn)$ , 这样就可以拿 $48'$ 了, 这已经很令当时的我满意了.

对拍

有两个爆搜来对拍, 正确性确实可以保证, 而且数据好造, 一分钟就结束了对拍工作.

考场代码大赏

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<bitset> 
using namespace std;
inline unsigned RD() {
  unsigned TmpRD(0);
  char RChr(getchar());
  while ((RChr < '0') || (RChr > '9')) RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD;
}
inline int RDsg() {
  int TmpRD(0), TmpSg(1);
  char RChr(getchar());
  while (((RChr < '0') || (RChr > '9')) && (RChr ^ '-')) RChr = getchar();
  if(RChr == '-') TmpSg = -1, RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD * TmpSg;
}
const unsigned long long Mod(998244353);
unsigned long long Suf[10005], Ans(0x3f3f3f3f3f3f3f3f), Tmp(0);
unsigned a[10005], b[10005], STop(0);
unsigned n, m, t;
unsigned A, B, L(2), R;
unsigned Now(0);
inline void DFS(unsigned Dep) {
//  printf("DFS %u [%u, %u]\n", Dep, L, R);
  if(Dep <= 1) {
    Tmp = 0;
    for (unsigned i(n); i; --i) {
      Suf[i] = Suf[i + 1] + (n - i + 1) * a[i];
      Tmp += a[i] * (Suf[i] + Suf[i + 1]);
    }
    Tmp *= n;
    Tmp -= Suf[1] * Suf[1];
    if(Ans > Tmp) {
      Ans = min(Ans, Tmp);
//      for (unsigned i(2); i <= n; ++i) printf("%u ", a[i]);putchar(0x0A);
    }
    return;
  }
  a[L++] = b[Dep], DFS(Dep - 1), --L;
  a[R--] = b[Dep], DFS(Dep - 1), ++R;
}
signed main() {
  freopen("variance.in", "r", stdin);
  freopen("variance.out", "w", stdout);
  R = n = RD();
  for (unsigned i(1); i <= n; ++i) a[i] = RD();
  for (unsigned i(n); i > 1; --i) a[i] -= a[i - 1];
  memcpy(b, a, sizeof(a));
  sort(b + 2, b + n + 1);
  DFS(n);
  printf("%llu\n", Ans);
  return 0;
}
/*
5
1 2 3 5 8
*/

评价

这个题多少有些不甘, 毕竟花了近 $2H$ .

多次测试发现答案中, 差分数组是趋于对称的, 也就是说, 枚举的 $2^n$ 中情况绝大多数一开始就不优了, 但是我却不知道如何避免, 因为直接贪心从大到小从两头往中间填是和答案略有出入的. 但是如果我用数据点分治, $48'$ 以内严格搜索, $48'$ 以外使用随机化方法, 是有概率摸到 $70'$ 左右的.

Day $1$ : Chess

暴三骗四

小标题用典出处, 请自行 Ctrl + F.

早就看到 T4 是个码农题, 暴力分不多不少, 留了时间把暴力进行一个打. 最后还有 $40+min$ , 当时觉得 $O(nmq)$ 的逻辑还很清晰.

打了 $20min$ 左右吧, 写是写完了, 跑一遍样例过不了, 开始 De, 发现有一些问题, 开始把递归函数进行重构.

默写

只剩 $15min$ 的时候去建文件夹查文件操作去了.

回来还有 $10min$ , 继续重构, 最后 $5min$ 调不动摆烂了.

把函数删了默写终末之诗去了…

考场代码大赏

最后摆烂了, 纯行为艺术了属于是.

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<bitset> 
using namespace std;
inline unsigned RD() {
  unsigned TmpRD(0);
  char RChr(getchar());
  while ((RChr < '0') || (RChr > '9')) RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD;
}
inline int RDsg() {
  int TmpRD(0), TmpSg(1);
  char RChr(getchar());
  while (((RChr < '0') || (RChr > '9')) && (RChr ^ '-')) RChr = getchar();
  if(RChr == '-') TmpSg = -1, RChr = getchar();
  while ((RChr >= '0') && (RChr <= '9'))
    TmpRD = (TmpRD << 3) + (TmpRD << 1) + RChr - '0', RChr = getchar();
  return TmpRD * TmpSg;
}
unsigned long long Ans(0x3f3f3f3f3f3f3f3f), Tmp(0);
unsigned n, m, t;
unsigned Now, Dire;
unsigned A, B, C, E;
unsigned Out;
char IO[200005];
set<unsigned> Set;
struct Node;
struct Edge {
  Node* To;
  char Type;
};
struct Node {
  Edge U, D, L, R;
  unsigned Lev, Col;
}N[200005];
inline void Go (Node* x) {
  if(Set.find(x - N) != Set.end()) return;
  Set.insert(x - N);
  /*
  Wild_Donkey
  The End?
  Once we're called the spirits of the mountains.
  Who are we?
  Father sun, mother moon
  We are the univers
  And the univers said: I love you.
  And the univers said: You are the daylight.
  And the univers said: You are not alone.
  And the univers said: You are the nignt.
  Take a breath now, take another.
  And the game was over.
  Wake up.
  */
}
signed main() {
  freopen("chess.in", "r", stdin);
  freopen("chess.out", "w", stdout);
  Out = RD();
  for (unsigned O(1); O <= Out; ++O) {
    n = RD(), m = RD(), t = RD();
    for (unsigned i(1); i < n; ++i) {
      scanf("%u", IO + 1);
      for (unsigned j(1); j <= m; ++j) {
        N[(i - 1) * m + j].D = (Edge){N + i * m + j, IO[j] - '0'};
        N[i * m + j].U = (Edge){N + (i - 1) * m + j, IO[j] - '0'};
      }
    }
    for (unsigned i(0); i < n; ++i) {
      scanf("%u", IO + 1);
      for (unsigned j(1); j < m; ++j) {
        N[i * m + j].R = (Edge){N + i * m + j + 1, IO[j] - '0'};
        N[i * m + j + 1].L = (Edge){N + i * m + j, IO[j] - '0'};
      }
    }
    for (unsigned i(1); i <= t; ++i) {
      C = RD() + 1, E = RD(), A = RD() - 1, B = RD();
      Node* Cur(N + A * m + B);
      Set.clear(), Go(Cur), Set.insert(Cur - N);
      if(Cur->U.Type) 
        {Dire = 1, Now = Cur->U.Type; if(Cur->U.Type > 1) Go(Cur->U.To); else Set.insert(Cur->U.To - N);}
      if(Cur->D.Type) 
        {Dire = 1, Now = Cur->D.Type; if(Cur->D.Type > 1) Go(Cur->D.To); else Set.insert(Cur->D.To - N);}
      if(Cur->L.Type) 
        {Dire = 2, Now = Cur->L.Type; if(Cur->L.Type > 1) Go(Cur->L.To); else Set.insert(Cur->L.To - N);}
      if(Cur->R.Type) 
        {Dire = 2, Now = Cur->R.Type; if(Cur->R.Type > 1) Go(Cur->R.To); else Set.insert(Cur->R.To - N);}
      printf("%u\n", Set.size());
      Cur->Col = C, Cur->Lev = E; 
    }
  }
  return 0;
}
/*
5
1 2 3 5 8
*/

Day $1$ : After

散伙饭, 当时有将近 $10$ 个人都说要去, 结果最后加上已经退役的Cyc才一共 $3$ 个人, 另一个是去年诅咒我爆零的法王, 三个男的如果加上一条狗就能打 GTA 了吧.

三个人简单交流了一下, 也没有想象中的相拥而泣又或是什么喝酒唱歌, 从此以后应该算是分道扬镳了吧.

Day $2$

回学校, 从久负盛名的 $33$ 班文化课实验班被安排到 $21$ 班复习文化课, 因为我们已经停了两个月课, 所以进度已经被拉开了, 所以需要到进度慢的班级补课.

统计之后发现, 我们这一级的 OIer 除了我留下来以外, 其他人都处于退役或半退役状态了.

图炸了就永远炸了, 再也找不回来了

一共 $9$ 个人被分到了 $9$ 个班学文化课. (不要过于在意好久没更新的存活率和被脑瘫管理员改的备注, 气氛全没了md)

Day $3$

一天下来确实有感受到孤独.

晚上被调到 $34$ 班奥赛班, 因为我计划之后还要停课, 所以需要赶紧把课学完, 补课可以通过渗透, 需求促进生产.

渗透就是学新课发现知识断层就去问别人或是自己查资料, 这样的资源占用不高, 适合进度没有拉开太多的情况.

Day $9$

盘点一下我都落下哪些课:

语文

语文课本和高考有关系吗?

数学

差了导数, 计数原理, 概率三部分的内容.

后两章都是算法竞赛中计数期望概率 DP 的延伸, 记号熟悉后能掌握个大概, 导数作为高中数学两大毒瘤之一还是要重视起来的.

英语

英语课本除了单词表, 剩下的和高考有关系吗?

物理

之前的物理老师讲得过快, 以至于物理到现在还在等别的科目的进度, 做一些压轴题打发时间, 所以一点没落. 应该差一个光学就结束了吧.

化学

回来以后发现差了选修二整本加选修一的半本, 后来有好心人提醒我选修二我学了, 我翻了一下书发现果然有笔记, 但是我什么都不记得了.

生物

不多不少, 我从 $21$ 班听了选修二第一节课, 刚庆幸终于完美接上进度, 然后又到 $34$ 班成功赶上了选修三第一节课.

Day $10$

2021-11-29, 出官方成绩, 此前我在洛谷, 小图灵, 编程兔都是 $248'$ , 别人的成绩像 CSP 一样, 在不同的 OJ 测都很刺激, 唯独我又双叒叕十分稳定, 甚至平淡.

出分后果然是 $248'$ , 有幸和杜爷爷贴贴, 貌似是 RK-18, 感觉省选有点虚, 但不是没有戏, RK-14 是 $252'$ , 问题不大.

此贴完结, 祝好.

NOIP 2021 失恋记

NOIP2021

Day −3-3−3

Day −2-2−2

Day −1-1−1

Day 000

Day 111: Prepare

Day 111: Number

暴力

线性筛

乱搞

正确性

回答询问

考场代码大赏

评价

Day 111: Sequence

正解

对拍

考场代码大赏

评价

Day 111: Variance

式子

O(n!n)O(n!n)O(n!n)

O(2nn)O(2^nn)O(2nn)

对拍

考场代码大赏

评价

Day 111: Chess

暴三骗四

默写

考场代码大赏

Day 111: After

Day 222

Day 333

Day 999

语文

数学

英语

物理

化学

生物

Day 101010

Day $-3$

Day $-2$

Day $-1$

Day $0$

Day $1$ : Prepare

Day $1$ : Number

Day $1$ : Sequence

Day $1$ : Variance

$O(n!n)$

$O(2^nn)$

Day $1$ : Chess

Day $1$ : After

Day $2$

Day $3$

Day $9$

Day $10$