|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2024-6-1 11:54 编辑
前言
上一次 PKUWC 只要少一分我都不可能写这篇游记，只能说运气。
这一次，唯一不同的是去的人变少了，初一初二只有 5 个人，初三 9 人，高中 5 人，竞争的压力似乎变大了。
而且这也是我这一整个赛季最后的比赛，珍惜这一赛季的 OI，好好总结。
Before Contest
期中一考完就去集训了，时间非常紧张。
集训考试，分数的波动非常之大，6 场考试的方差能达到一万三。
但也只能说有效果，在 15 人中可以得到前 7。
在期间一直在学习，学了一下一些可持久化的数据结构，还有高斯消元……希望能用到。
内心还是非常的紧张和害怕，毕竟如果这一场考不好的话，那这个赛季就基本了，成就进度会落后其他 6 个大佬许多。
……加油吧，给自己定一个小目标，280，初二的大佬说要 350，%%%。
5/11 日，晚上还要打 ABC，摆摆摆，根本就不想打。
Goto Hangzhou on Day 0
从江北机场 T3，9 点起飞，终点站萧山机场 T3，第三次坐飞机（也许是第一次印象最深刻的时候）。
下了飞机，去坐杭州地铁 Line2 Line7，感觉杭州地铁和 CRT 的差不多，车车没重庆江跳线快，乘客信息显示屏、车门的话比重庆的帅一点，仅此而已。
午餐吃的是重庆麻辣烫，异地他乡的家乡情，还算不错，就是少了麻辣。
在酒店，疯狂复习了一些字符串、平衡树算法，希望可以用上。
简单回顾了 PKUWC，考的东西基本都是串串、人类智慧、分讨、数据结构什么的。
串串和分讨还好，至少可以抠不少的分，其他就不好说。
平衡树？感觉很少，毕竟可以用值域线段树代替。
晚上体验了神奇的浙菜，感觉很神奇，因为我吃到的 6 盘菜里面，4 盘都有酸味，有不少的醋，尤其是西湖醋鱼（这个其实还好）。
甚至吃到的虾都是感冒药味道的。在这里想问一下本地人，浙菜真的是这种特色吗……
10:00 睡觉。
Day 1
酒店早餐十分丰盛，吃的最饱的一次。
去测试环境，电脑居然是笔记本，屏幕特小，只能说不是台式电脑买不起，而是笔记本更有性价比。
题目是 WC 的题目，就不做了，在本地写了一车板子，有逆元、质数筛、KMP、FHQ-Treap、（可持久化）线段树、快读快写……
写了 50 分钟感觉没意思，走了走了。
中午午休简单睡了一会儿，12:40，所有人起身，走出报告厅，走向考场。在路上，大家仍然在讨论得分、奖项、甚至猜想 20 分钟后可以看到的题目。
12:55 分，坐在电脑前。
这也许就是我这一赛季最后的比赛了。考得好？考不好？无从得知。
但不论是考好还是考寄，也都希望可以稳定发挥，不管结果如何，先把当下的事情做好。
想着想着就快开始了，深呼吸一口气，数着倒计时。
56……57……58……59……00！
比赛开始，再做了一次深呼吸，点开了三道题目。
T1 就三个 Sub，签到预定？
给定 $2\times n$ 的字符串网格，定义路径串为从这个网格任意点开始往下走或者往右走到任意点结束的网格路径上的字符按行走顺序拼接成的字符串，求出最长的路径串，并且他是回文串。
看了一下，毫不犹豫打出了在题目读错情况下的正解，提交上去全 WA。
硬控 40 分钟后找到了问题所在，因为从任意点开始。
从任意点开始的话，那么 $n\le1000$ 的话就得用动态规划，$dp_{x_1,y_1,x_2,y_2}$ 表示这个串以 $(x_1,y_1)$ 开始，以 $(x_2,y_2)$ 结束的路径是否存在回文路径串，转移比较简单。
第二个 Sub2 的话 Manacher 秒了，但是不会，就用字符串哈希+二分。
有一个大体的正解思路就是从 Sub2 开始，然后开始跳到第二行或者第一行，继续二分？假了吧，不敢写，毕竟已经过去 100 分钟了。
T2 唐诗计算几何……
求二维格点凸包内部，格点正方形的个数。
凸包点数 $\le 8$，坐标 $\le2000$，
Sub 很多，不像是签到。有一个 Sub 是保证凸包是坐标矩形，另一个是坐标直角三角形，剩下就是针对于坐标的数据范围。
一眼不好做，想做 Sub1，$\sum_{i=1}^{\max(x)} \sum_{j=1}^{\max(y)} \min(i,j)-1$，错了。
硬控 20 分钟逐渐开始崩溃，吃块巧克力压压惊。
通过研究样例得到，正方形可以是斜的？？！
这下彻底寄，因为我不会……
开始研究坐标小的时候的性质，一个想法就是求出在凸包内所有格点，然后枚举乱搞。
唯一问题就是怎么求出在凸包内所有格点。
一个想法就是枚举一个点，让他与凸包的点连接，再判断是否与凸包线段有交？？？
线段交还是不会，暴力解函数？写了一下，不仅精度爆炸，还假了，尤其是在线段上的点，题目要求这个点也要算。
彻底击溃心理防线，必须完全放弃这道题，只剩下了 60 分钟。
T3:
求出在固定树形态的情况下，点权在 $[1,m]$ 随机，求最大带权独立集的期望。
什么玩意，发现有 $O(2^n m)$ 的分，但是在状压 DP 的过程中，最大带权独立集非常难以维护。
暴力写完后，想了 40 分钟也没想出什么。
16:55 了。
50+0+11。
心理防线完全崩溃，此时想要跳进西湖喂鱼。
越考越烂是我完全没有想到的。
哎…………
遗憾离场，Day 2 能考多少就多少吧，最好高点。
与其他人交流了一下，T1 结果就是我想的假思路，还有原？
啊？？？？
T2 他们说对于上凸壳下凸壳分类讨论，然后暴力算出斜率，对于在这条线段上/下的打一个标记。
啊？？？？
T3 大家都没有思路。
啊？？？？
去吃晚饭的路上，听一首《安河桥》安慰自己。
讓我再看你一遍 從南到北
像是被五環路 蒙住的雙眼
請你再講一遍 關於那天
抱著盒子的姑娘 和擦汗的男人
……
晚上非常悲痛，但是必须振作。
Day 2
早上的讲座讲的是 自动 AC 机，套路和 WC 差不多，都是讲的是怎么教会机器写程序，感觉很有意思。
用来思考人类是如何思考的确实是一个很不错的问题，毕竟目标是为了让机器思考。
这一天的考试只能说压力山大，因为只有得到 120 分，才有机会 Ag，200 分才能达到我的目标。
决定更换策略，三道题目都先看一遍，因为这场比赛大概率没有签，然后对自己有思路的 Sub 开冲。
考前去厕所洗了一把脸。
56……57……58……
度秒如年，紧张感布满了全身……
59……00！
点开三道题。
T1：
一个 DAG，$2\sim n-1$ 的每个点的出度为 $2$，每个点有一个 $0/1$ 的点权，定义一次操作如下：
- 令 $p=1$，目前在 $1$ 号点。
- 若 $p$ 号点的点权为 $1$，走这个点出度中编号较小的点，否则走编号较大的点。
- 对 $p$ 号点的点权取反，然后将 $p$ 设置为目前点的编号。
求出最小地正整数操作次数使得所有点的点权与初始状态一样。
T2：
分段函数 $f_i(x) = x + [x\in[l_i,r_i]]$，$q$ 次询问求 $f_l(f_{l+1}(\dots f_{r}(0)))$ 的值。
T3：
随机有向图上 $q$ 次询问两点最短路。
三个题目的暴力都非常好写，但是只有 35，100 分钟写完。
T2 有一个分块的做法？求出每一个 $\sqrt{n}$ 等分点到下一个 $\sqrt{n}$ 等分点的所有值的函数。
在查询的时候就很简单，整块散块分别求一下？？？
硬控了 60 分钟，发现预处理的时间复杂度就假了……$O(n\times \sqrt{n}^2)$ 跑得不如暴力。
看 T1，有一个 $2\sim n-1$ 每个点入度为 $1$ 的性质，猜想是 $2^n$，T 了。
写了 30 分钟的分段打表，WA 了。
其实很容易就能举出反例……
不知道当时怎么想的。
转身思考，想要求一下从 $1\sim n$ 的路径总数。
显然是可以通过这个 Sub 的。
但是 T 了……
氧？WA 了。
发现高精度写炸了，$0+1=0$ 都能给我求出来？？？
看一看时间，非常糟糕，剩余 15 分钟。
反复地输出调试，硬是找不到问题。
汗珠从额头流下，手指在键盘上略微颤抖地敲打着。
最后 2 分钟了…… $0+1=0$。
最后 1 分钟了…… $16+1=71$。
最后 30 秒了……
20+10+5
不必挣扎了。
赛季最后一场比赛。
草草地结束。
那个人曾站起来过。
却如此抑郁。
为什么越来越菜？
也许本身就是一株卷心菜。
See you again……
T1 他们说只要模拟 2^n 次操作即可，分叉的时候分半放置即可。
T2 他们说平衡树维护答案……
T3 他们说 spfa 可以得到 15……
晚上启动了心理疏导，后面听说自己是倒数第三。
After Contest
比赛确实非常烂，总结了一下确实是自己学的东西过少了。
学习的模式其实一早就有点问题，基础都没怎么扎实，尤其是高中数学，就来卷 NOI 级的东西。
甚至 CSP-S 考的也很炸。
回顾一下我在这个赛季参加的所有比赛：
2023 CSP-J/S
2023 NOIP
2024 PKUWC
2024 PKUSC
比赛确实很丰富，在这些比赛确乎收获了不少经验。
打 AT 的时光，打模拟赛的时光，多么快乐。
或者说，在论坛的一个赛季，也是多么的有意思。
这一赛季也就这样结束了，集训的时光也就结束了，以一个较为消极的事情结尾。
或者说，初一也就到此为止了，踏入的是初二，迎来的是更大的环境、更快乐的生活、更加竞争的时候。
愿各位学生、OIer 都能保持学习的激情、保持对生活的热爱，去追寻那属于自己的光芒。
下个赛季再见，CSP，NOIP，PK/THU。FishC。 |
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-5-15 19:43:31
置顶卡
千斤顶
显身卡
楼主
发表于 2024-5-15 19:46:34
发表于 2024-5-16 13:04:41
