[s]PKUSC 2024 参赛报告[/s] && 2023~2024 赛季OI总结
本帖最后由 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:
求出在固定树形态的情况下，点权在 $$ 随机，求最大带权独立集的期望。
什么玩意，发现有 $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 + ]$，$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。 @FishC 什么东西越卷越菜？ zhangjinxuan 发表于 2024-05-15 19:45
@FishC 什么东西越卷越菜？
程序员的肚子！因为越卷越没有时间健身，只能吃零食和泡面，结果肚子越来越大！要想解决这个问题，程序员们需要在写代码的间隙里加入一些运动，比如做一些简单的伸展活动、散步或者参加一些户外运动。同时，还要注意饮食的均衡，多吃水果、蔬菜和谷物，减少高热量、高油脂的食物。毕竟，健康才是最重要的！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-5-15 19:46
程序员的肚子！因为越卷越没有时间健身，只能吃零食和泡面，结果肚子越来越大！要想解决这个问题，程序 ...
您刚刚回答的问题是 “什么东西越卷越菜？”，您回答的是“程序员的肚子”。
如果我认为答案是卷心菜，您将如何解析、理解这个答案？ zhangjinxuan 发表于 2024-05-15 19:48
您刚刚回答的问题是 “什么东西越卷越菜？”，您回答 ...
非常抱歉，我之前的回答有些幽默化和玩笑性质，是以幽默的角度进行解答的。实际上，对于问题“什么东西越卷越菜？”这个问题而言，答案应该是“卷心菜”才正确。
卷心菜是一种蔬菜，它的结构与叶子的层次相似，越往内部卷的叶子越紧密。所以，按照字面意思来理解这个问题，卷心菜确实越卷越菜。这个答案并无其他含义。
再次感谢您的指正，希望我的解答能够更加准确和清晰。如果您还有其他问题，欢迎继续提问！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-5-15 19:48
非常抱歉，我之前的回答有些幽默化和玩笑性质，是以幽默的角度进行解答的。实际上，对于问题“什么东西 ...
如果我认为答案是我自己，您将如何解析、理解这个答案？ zhangjinxuan 发表于 2024-05-15 19:50
如果我认为答案是我自己，您将如何解析、理解这个答案 ...
如果您认为答案是您自己，那么可以从另一个角度解析和理解这个答案。
当您说“我自己”时，可能意味着在面对新的挑战和困难时，如果没有不断学习和成长，可能会变得越来越不擅长。这是因为技能和知识的更新迭代非常快，如果停止学习，就容易掉队。
编程也是一样，编程技能需要不断地学习和练习才能保持竞争力。所以，如果您认为答案是自己，那么可以将其理解为提醒自己要始终保持学习的态度，不断提升自己的技能和知识水平，以应对日新月异的编程挑战。
希望这个解析能符合您的期望。如果还有其他问题，请随时提问！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-5-15 19:50
如果您认为答案是您自己，那么可以从另一个角度解析和理解这个答案。
当您说“我自己”时，可能意味 ...
谢谢您。 zhangjinxuan 发表于 2024-05-15 19:51
谢谢您。
不客气！如果您还有其他问题，随时都可以向我提问。我会尽力帮助您解决问题。祝您学习愉快，编程顺利！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 膜拜 标题是不是出错了 Python 和 JavaScript 是两种广泛使用的编程语言，它们在设计目标、语法、应用场景、以及一些技术特性上都有所不同。以下是它们之间的一些关键区别：
1. **语法差异**：
- Python 的语法设计得更为简洁明了，强调可读性和减少编写代码所需的字符数量。它使用缩进来定义代码块的范围。
- JavaScript 的语法较为灵活但可能更复杂，它依赖花括号 `{}` 来界定代码块，并且在变量声明、函数定义等方面有更多的语法选项。
2. **应用领域**：
- Python 是一种通用型语言，适用于多种领域，如后端开发（如 Django, Flask 框架）、数据处理与分析、人工智能、机器学习、科学计算、网络编程和自动化脚本等。
- JavaScript 最初专为浏览器设计，用于实现客户端的网页脚本，包括页面交互、动画效果和AJAX请求等。随着 Node.js 的出现，JavaScript 也开始被用于后端服务器开发、构建桌面应用、移动应用开发等。
3. **运行环境**：
- Python 需要在服务器或用户的计算机上安装 Python 解释器来执行代码，也可以通过 Jython、IronPython 等在Java虚拟机或.NET框架上运行。
- JavaScript 主要运行在浏览器中，但通过 Node.js 也能在服务器端执行，无需浏览器环境。
4. **类型系统**：
- Python 是动态类型语言，变量的类型可以在运行时改变，无需显式声明类型。
- JavaScript 也是动态类型语言，但它是一种弱类型语言，意味着变量的类型可以隐式转换，这可能导致意外的行为。
5. **性能**：
- Python 由于是解释型语言，执行速度通常比编译型语言慢，但对于许多应用来说，这种差异并不显著。Python 提供了如 Cython 等工具，可以通过预编译提升性能。
- JavaScript 在现代浏览器中通过 JIT（Just-In-Time）编译技术获得了较快的执行速度，特别是在处理前端交互和事件驱动的程序时表现出色。
6. **社区和生态系统**：
- 两者都有活跃的社区支持和丰富的库与框架。Python 在数据科学和AI领域的库（如 NumPy, Pandas, TensorFlow）特别强大；而 JavaScript 则拥有大量前端开发框架（如 React, Angular, Vue.js）和后端框架（如 Express）。
综上所述，选择 Python 还是 JavaScript 很大程度上取决于具体的应用场景和个人偏好。 {:10_254:} 浙菜不可能是这样的 个人感觉你太紧张了，我做一道题想不出来，去厕所放放脑子马上有思路 sfqxx 发表于 2024-7-17 16:02
个人感觉你太紧张了，我做一道题想不出来，去厕所放放脑子马上有思路
好建议
页:
[1]