初赛

Ros 的初赛考场在宁波市蛟川双语幼儿园，第四考场 $32$ 座位，如果有同学校甚至同考场的见到 Ros 本人但不知道就是 Ros 还请打声招呼。

在进了学校后入考场前，Ros 本来想多打听一下同考场的巨佬们的洛谷 ID …… 然后只问到了 @天机星 巨佬然后被一个人无视后 Ros 太害羞又没问了……出考场的时候也顺便问到了 @Mincraft_fan 巨佬。

显然考场是在小学里面……桌子又小又矮，很难受，教室前面没有钟而 Ros 又没有带表所以更难受……Ros 还问了监考老师能不能把钟搬到教室前面来然后被拒绝了……尬死。

试卷发下来，做完选择题感觉状态很好，然后阅读理解第一题虽然稍微遇到了一点点困难但也没有什么大问题结果从阅读理解第二题开始人就奔溃了……一直奔溃到考试结束。

估分出来是 $68$ 分左右，虽然考虑到因为试卷难度的问题分数线相比于去年的 $71.5$ 会有所下降但是具体下降多少还是个未知数所以这种进了复赛又没有进复赛的感觉真的很难受搞得 Ros 不知道中秋假期要不要再搞复赛好了……

但是知乎上有大佬说这次试卷很简单和去年的不相上下所以 Ros 也不知道怎么办才好。

奶一口，分数线在 $65$ 以下，$60$ 出个头左右。

但是其实也不是没有可能 $70$ 多。

---

好的分析一下这套试卷。

直接说结论：CCF &！……￥&……！（￥）（&（！

好的讲讲这套试卷：

T1 没用过 Linux，不会。

T21 搞心理战，很遗憾 Ros 中招。

阅读理解 T2 重载没看明白，手膜实在麻烦，时间不够，卒。

阅读理解 T3 0xff，0x0f，0x3f 不知道具体是多少数值，完全不可做，卒。

T 35 至今不知道为什么 B 不可以。

程序填空 T3，笛卡尔树啊 Euler 序列啊什么的完全没学过，卒。

---

好的总结一下：

Ros 为了这次初赛训练的几个星期，几个星期晚自修没有认真做作业没有复习甚至还有几天没做作业基本放弃了 whk 在搞初赛结果初赛全是我不用复习就会的东西和我这辈子也复习不到的东西就让我感觉我前段时间的努力都努力了个寂寞还导致 whk 下降要知道月考可就在中秋后那么显然 Ros 的月考也要完蛋就属于是人 lose 了真的是太恶心了 CCF 就不能出一点阳间的东西吗 Ros 回家还被母亲大人骂了一顿明明在解释但是也说不清但是 Ros 确实几乎把所有能拿的分都拿到了但是成绩就是这样子这种试卷就感觉像是你十几年高考从来没有考必修 $2$ 第 $3$ 单元（举个例子）所以所有人都默认不会考所以老师也不教同学们复习高考的时候也没看但是突然就考到了所以看过学过的人就可以比较方便地做出来但是没学过的人想一辈子都想不出来而且之前的复习时间都打水漂就真的特别恶心所以一定会有一些学过的巨佬们能拿很高的分但是像我这种就完全是看运气拿分数 Ros 本来想进复赛和很多巨佬面基但是感觉似乎又很难进所以很 ex 又考虑到对 whk 的影响所以这次甚至有可能会退役而且因为这次考了这种东西那么我明年准备初赛的时候是不是还要把什么点分治树套树启发式合并中国剩余定理啊什么的奇奇怪怪的东西全部复习一遍？？？？？？？

哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊

我还没面到可爱的 Macesuted 怎么能就这样退役啊啊啊啊啊啊啊啊啊啊啊啊啊啊

总之希望能过初赛。

希望这个游记还能继续更新。

复赛

Day -inf

奶一口，分数线在 $65$ 以下，$60$ 出个头左右。

结果分数线 $58.5$ 是我想不到的。

总之是非常惊险地过了初赛。

在复赛之前熬夜肝了 $7$ 天学完了初等数论……希望能考到吧。

又花了好久总算刷完了 NOI 大纲一直到提高组的部分。

然后时间就没了。

感觉光刷板子题可能考到思维题了就不会……但是又在想到时候如果连板题都不会的话那岂不是完全不可写？

总之加油吧！

Day -1

本来是打算在比赛前一天晚上高铁跑到杭州然后住酒店的——去年就是这样。

但是我们的学校要求我们一定当天早上做小客车去。

小客车想想就会很颠簸……感觉等到的时候状态都没了……

但因为是学校安排的也不好反对……也没办法。

希望不要太影响状态吧

Day 0

明天是复赛。

理论上应该是要复习……但是也不清楚要复习什么。

摸了缩点、快读，会看的数论笔记，又复习了其他一点东西。

然后睡觉。

比赛加油！

Day 1

Day 1 很开心：

• 早上应该 7:30 到的车 8:15 才到很开心；
• 路上非常颠簸一点都睡不着很开心；
• 在 XJ 边上的天街吃午饭很开心；
• 吃完午饭还吃了一桶 DQ 很开心；
• 最早进 XJ 很开心；
• 没有面到枫酱很不开心；
• 一眼就在人群中认出了可爱的 Macesuted 还贴贴了很开心；
• Macesuted 非常可爱，抱起来非常舒服，很开心（
• 和 Macesuted 合照，很开心；
• 考场前面屏幕上打着「Rp ++」很开心；
• 一看题目全不会做很开心；
• T2 写了三个半小时很开心；
• T2 等想出可以前缀和优化的时候已经没时间了，止步于 $O(n^3k)$ 很开心
• 只得了一百多分很开心；
• 晚上又吃了大餐很开心；
• 20:00 上车，路上赌了好久又因为高速不知道怎么了不让走只能走省道很开心；
• 在车上和伙伴一起过了程序员节很开心；
• Day 2 00:15 才到家和开心；
• 杭 州 两 日 游很开心。

讲讲考试过程：

14:20

考场提前十分钟公布了解压密码让我们看题。

扫一眼题目发现完全没有一眼就有思路的题，危。

14:30

按部就班开始想 T1

花十分钟打完了代码，样例 #1 就挂，发现假了，完全没有考虑不停廊桥的飞机对后面飞机是完全没有影响的。

又开始重新想。

15:00

暂时放弃 T1。

此时 T1 暴力还没有写，想着万一之后又想到了呢？

看 T2 了。

T2 倒是仔细一看发现是一道 DP，开始写。

用 $f_{i,j}$ 表示区间 $[i,j]$ 内合法的情况数量，之后分别讨论 $\text{(),(S),(A),AB,ASB,(AS),(SA)}$ 的情况。

15:40

T2 DP 写完了，但是样例 #2 没过，输出 $28$。——后来出考场一问有好多人都是这个问题。

检查代码。

16:00

代码检查无误，感觉是自己思路错了但又不知道错在哪里……开始手模。

16:40

模拟了一些答案出来，终于发现：没有去重！

简单的说就是如果遇上 $\text{()()()}$ 的情况会被重复计算很多次。

16:50

重新想出思路，$f_{i,j}$ 仅严格讨论区间 $[i,j]$ 中两端分别为 $(,)$ 且两端为一对括号的情况（不知道有没有表述清楚），再最后统计一个 $last_i$ 表示 $[1,i]$ 中所有的组成情况。

17:10

把新思路写出来了。

样例 #2 输出 $8$，看起来又挂了。

17:20

简单的手模之后发现，如果有类似于 $(()())$ 的情况，它应该被统计在 $f$ 中，但是根据我之前的思路却不会被统计进去。

17:30

出了新的思路，用 $f_{i,j}$ 表示区间 $[i,j]$ 中左右端点严格是同一对括号的情况，$last_{i,j}$ 表示区间 $[i,j]$ 中左右端点严格不是同一对括号的情况（懒得改名了）。

18:00

写完了新的思路。

样例 #2 过了但是样例 #3 还是没过。

想着没时间了，开始写 T1 $nm$ 暴力与 T3 $2^n$ 暴力。

18:20

写完了 T1 与 T3 暴力。

偶然瞟到 T2 还要对 $10^9+7$ 取模。（我之前就奇怪为什么不用取模的，感觉情况总数一定会爆 long long）

在加模数的时候发现代码中把一个 l 打成了 i，改了过来，实在惊险。

然后过了样例 #3。

样例 #4 本地跑跑答案是没错的，但是要跑好久。

时间复杂度 $O(n^3k)$。

贴一下考场代码：

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 510;
const long long MOD = 1e9 + 7;

char s[N];
long long z[N], f[N][N], last[N][N];

int main()
{
	freopen("bracket.in", "r", stdin);
	freopen("bracket.out", "w", stdout);
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i ++)
	{
		scanf(" %c", &s[i]);
		if(s[i] == '(' || s[i] == ')') z[i] ++;
		z[i] += z[i - 1];
	}
	for(int len = 2; len <= n; len ++)
	{
		for(int l = 1; l <= n - len + 1; l ++)
		{
			int r = l + len - 1;
			if(!((s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?'))) continue;
			if(len == 2)
			{
				f[l][r] = 1;// ()
			}
			else
			{
				for(int i = l + 1; i <= min(l + k, r - 3); i ++)
				{
					if(z[i] - z[l] == 0) f[l][r] = (f[l][r] + f[i + 1][r - 1] + last[i + 1][r - 1]) % MOD; // l + 1 to i, (SA)
					else break;
				}
				for(int i = r - 1; i >= max(r - k, l + 3); i --)
				{
					if(z[r - 1] - z[i - 1] == 0) f[l][r] = (f[l][r] + f[l + 1][i - 1] + last[l + 1][i - 1]) % MOD; // i to r - 1 (AS)
					else break;
				}
				f[l][r] = (f[l][r] + f[l + 1][r - 1] + last[l + 1][r - 1]) % MOD;
				if(z[r - 1] - z[l] == 0 && r - l - 1 <= k) f[l][r] = (f[l][r] + 1) % MOD; // (S)
			}
		}
		for(int llast = 1; llast <= n - len + 1; llast ++) // last, ASB & AB
		{
			int rlast = llast + len - 1;
			int r = rlast;
			for(int l = llast; l < rlast; l ++)
			{
				for(int lenk = 0; lenk <= min(k, l - llast - 1); lenk ++)
				{
					if(z[l - 1] - z[l - lenk - 1] == 0) last[llast][rlast] = (last[llast][rlast] + f[l][r] * ((last[llast][l - lenk - 1] + f[llast][l - lenk - 1]) % MOD) % MOD) % MOD;
					else break;
				}
			}
		}
	}
	
	cout << (last[1][n] + f[1][n]) % MOD << endl;
	
	return 0;
}

18:25

突然想到 T2 如果加上前缀和优化与一点点预处理可以做到 $O(n^3)$，但是实在没时间了，着实可惜。

对 T2 的代码加了一点点可能没有什么用的小优化。

T2 止步于 $O(n^3k)$，预计 65pts。

18:30

在检查了读写之后，考试结束。

估分是 $40+65+28+0=132$，都是暴力的分。

T4 根本没想。

感觉分数挺低的……但感觉也没那么可惜……至少我是做到了：不该丢的分没有丢，不该得的分也没得。

出考场的是想到应该再在代码里加一句：// Orz Macesuted AK IOI 的，考试的时候居然没想到，着实可惜。

Day 2

说实话 Day 2 早上 00:15 到家，10:23 起床。

Hydro 上 $55+65+27$，非常正常的分数呢。

CSP 到底有没有一等也不重要了，反正肯定能进 NOIP，肯定进不了省选。

NOIP 去好好地面个基，之后就快乐地退役吧！

总结一下原因

• 首先确实是 whk 缠身，不好抽出时间准备；
• 说实话考场上的时候整个人都是懵逼的……尤其是前一个小时浑浑噩噩，还是阅历不够丰富啊；
• 赛前复习方向不对，复习了一堆根本不考的板子题却没有去刷思维题（尤其是 DP 一道都没有刷过啊啊啊啊啊）；
• 赛场上一看都不会做心态就炸掉了……要调整心态啊！

---

$\operatorname{Rosmarinus}$

$2021.10.24$