PKUSC2024 & APIO2024 游记

以 PKUSC Day1 作为 Day1。

Day -?

加训练功。

好像不会打模拟赛了，感觉集训完反而不会做题了，模拟赛有不少直接做起来很顺的题反而直接思路发散，没有省选前的注意力。不知道是自己底力不足暴露了还是 Topcoder 做多了正常题不会做了。

Day 1

包车去 XJ，车上在睡觉。

SXYZ 到 XJWY 开车居然不到一个小时，太快了！

上午幽默讲座，XJWY 校长把大家都逗乐了（字面意思）。

试机，题怎么是 PKUWC D2T2，那我光速跑路，打板子启动，先打了个 NTT，结果合并的时候不会打了，再打了个双半群线段树，结果没打完就被同学拉走了（。

中午盒饭貌似有点不尽人意，希望后面 APIO 不要也是这样（无所谓，酱油仙人会出击）。

休息室尝试给 Gold 来些外服引诱（。

尝试奶自己不会过题（伏笔）。

下午，终于启动！

先看题，后面两题居然没有数据结构。

T1，想了一些二分哈希，然后发现我要对中点有换行的那一侧的东西求某个哈希值是否存在，然后搞不出来（事实上也搞不出来啊，怎么可能对 $\mathcal{O}(n^2)$ 的信息快速维护查询啊）。

然后发现换行前后的串一定是一边是 $\verb!AB!$ ，一边是 $\verb!C!$ ，其中 $\verb!C!$ 是 $\verb!A!$ 的反串， $\verb!B!$ 是一个回文串。

然后就一直在想对末尾位置维护 $\verb!B!$ 的信息，结果搞不出来，自闭了，跑路。

有点难受，后面直接开始拼暴力了。

看 B，尝试拼上前三个包，这样就有三位数了！（幽默

正方形是好写的，小的包我直接把所有东西都扣出来然后乱做，然后三角形不会了。

先看 C，想了一个很大的 DP，发现可以记录差值把复杂度降下来，结果一直写不对，愤怒 $11$ 分跑路。

然后搞搞 B 的三角形，发现我至少要算一个执教三角形内某个点右上角的整点数量，本来想皮克定理结果发现很不好算，结果发现这个值域不是二维前缀和吗？？？直接开写。

假了一次，不知道怎么办，然后考虑分讨了一下枚举的边与三角形边的斜率关系，很快就过了。

剩下的时间在 emo 和想办法搞 T1 和 T3 的循环中，然后没搞出来，结束了。

事实上自己打比赛容易做不出来的时候反复横跳，这样如果都搞出来的分会很多，但是没有进展的话就很浪费时间。

$50+50+11=111$ ，全场最抽象得分。

赛后发现都过了 T1，问了一下 pai T1 怎么做，发现这里的 $\verb!B!$ 贪心考虑一定是某个中点的最长回文半径的串。

？？？？？？？

这下不会贪心了，唐完了。

更唐的是，如果枚举中点考虑回文半径暴力一点确实是 $\mathcal{O}(n^2)$ 的，但是这个东西写好一点它能过！！！！！

还好不是 NOI D2T2，据说去年出串串题也是这个样子。

然后 T2 发现 $\mathcal{O}(V^3)$ 也是简单的。

T3，最暴力的暴力可以分析得到一个能过的结果，但是我没写，/oh。

但是知道了维护钦定选根 $i$ 的最大独立集的差值和钦定不选根的最大独立集的差值不超过 $a_i$ ，感觉还是很妙的（好像是 SDOI2022 D2T1，但是我没做过）。

回机房的时候听人说了一下发现 T2 $\mathcal{O}(V^2\mathrm{poly}(n))$ 也是简单的！这下这场发挥完全零蛋了。

属于是这场打的比 NOIP 和 CSP 还要唐，实力停留在省选以前了。

看看 Day2 怎么说。

题和目前自己会的分（可能存在记忆偏差）：

T1

给一个 $2\times n$ 的字符矩阵，每个元素为小写字母。

你可以从矩阵内任意个点出发，每次往右或往下走，然后在任意一个点停下来，把所有经过的位置按顺序写成一个字符串，如果这个字符串是回文的，那么称这次行走的路径为一条回文路径。

求最长回文路径。

总范围： $1\leq n\leq 100000$ 。

Sub1(20): $1\leq n\leq 2000$ 。
Sub2(30): 只使用向右走可以得到最优解。
Sub3(30): 无特殊限制。

解法：

考虑换行前后的字符串，假设上面的部分比下面长，那么我们可以把上面的部分写成 $\verb!AB!$ ，下面的部分写成 $\verb!C!$ ，则有 $\verb!A!$ 是 $\verb!C!$ 互为反串， $\verb!B!$ 为回文串。

考虑所有回文中心相同的 $\verb!B!$ ，有结论：相同回文中心的 $\verb!B!$ ，只需要考虑最长的 $\verb!B!$ 。

考虑 $\verb!B!$ 越长，对下面的部分限制就越小可以分析得到这个结果。

然后就可以二分哈希了。

T2

给一个顶点数为 $n$ 的凸包，求内部有多少整点正方形。

令 $x_i,y_i$ 表示凸包顶点 $i$ 的坐标。

总范围： $1\leq n\leq 8,0\leq x_i,y_i\leq 2000$ 。

Sub1(10): 凸包一定是长方形，边与坐标轴平行。
Sub2(25): 凸包一定是一个直角三角形，左下角为直角定点，直角边与坐标轴平行。
Sub3(15): $x_i,y_i\leq 15$ 。
Sub4(15): $x_i,y_i\leq 300$ 。
Sub5(15): $x_i,y_i\leq 800$ 。
Sub6(20): 无特殊限制。

解法：

考虑特殊图形怎么做。

对于长方形，我们可以枚举正方形的形状（枚举左下角的边），然后这个正方形的外边框在这个长方形内就说明了这个正方形在这个长方形内，可以直接算。

对于三角形，还是枚举形状，考虑分析右上角的边与三角形斜边的斜率关系，这样可以把整个正方形在三角形内的的条件放到右上角边的某个端点在三角形内。

现在只要求三角形的某个点右上角有多少整点，最暴力的方法是二维前缀和。

对于一般做法，发现暴力要枚举某个点的位置很难优化，所以我们还是枚举形状！这样对于某个点的限制就是要求其在凸包内，由于形状确定，所以四个点的限制全部可以平移到一个点上，那么限制就是四个凸包的交内的整点数，半平面交求出凸包后可以使用类欧计算。

T3

给一棵树，每个点的可以分配 $[1,m]$ 内的权值。

求所有分配情况中树的最大权独立集之和。

总限制： $1\leq n\leq 2000,1\leq m\leq 10^8$ 。

Sub1(11): $n,m\leq 8$ 。
Sub2(24): $n,m\leq 20$ 。
Sub3(13): $n,m\leq 500$ 。
Sub4(?): $n\leq 500$ 。
Sub5(?): 无特殊限制。

（可能少了一个 Sub）

考虑暴力，设 $f_{u,x,y}$ 表示 $u$ 子树内钦定选 $u$ 的最大独立集为 $x$ ，钦定不选 $u$ 时的最大独立集为 $y$ ，暴力转移貌似可以分析到 $\mathcal{O}(n^2m^4)$ 。

可以只记录 $x-y$ 的值，这样可能转移会复杂，注意到 $|x-y|\leq m$ ，那么转移复杂度 $\mathcal{O}(nm^2)$ 。

观察到答案是关于 $m$ 的多项式，插值可以做到 $\mathcal{O}(n^4)$ 。

剩下不会了。

Day 2

我去，自动 AC 机，我去，九条可怜！

看吉老师，将一些程序自动化理论，感觉还是挺有意思的（~~以及吉老师自带的毒瘤气场~~）。

中午开睡，下午进场多带了一瓶水。

开 T1，大概想到策略大概就是每次加入一个新点，判断一下需不需要反转这个点，如果需要就把前面的操作重复一遍。

结果一直在想维护整个局面，搞了很久没分，就大概看了一下后面的题。

T2 好像是 DS 维护分段函数题，T3 是抽象随机图最短路，一开始还以为是无向图，以为可以乱搞拿不少分（，看到有向图后直接浇灭信心。

先写了 T2 的 $nq$ 暴力，然后尝试搞一搞 T3，写了个从每个询问点出发 spfa，发现居然把那个 $m\leq n$ 也给过了，很抽象。

然后尝试调调参，比如在 spfa 的时候限定次数，只取排序后前几条边等。但是搞了半天还是只有只选前 $50000$ 条边过了 sub2。

写的时候突然大脑复活想到了 T1 直接维护当前点要不要翻，然后写了个完全没有道理的暴力，然后，然后它过了！！！

这个代码非常没有无厘头：

long long c[50005];
int base=0;
c[1]=2;
for(int i=2;i<=n;i++)
{
	c[i]=0;
	for(auto j:fa[i])// a[fa[i]][0]==i or a[fa[i]][1]==i
	{
		c[i]+=c[j]/2;
	}
	if(c[i]&1) 
	{
		base++;
		for(int j=1;j<=i;j++) c[j]*=2;
	}
}
output(base);//print(2^base)

不仅复杂度是 $\mathcal{O}(n^2)$ 的，而且 $c$ 数组根本存不下这么大的数（得高精），完全没有任何道理的过法。

写 T2，以为这个分段函数线段树不好搞（其实是没有分析出来分段函数的段数是 $\mathcal{O}(\mathrm{sz})$ 的），于是写了个分块。

然后卡了最后一场的常数，没有额外获得一分，怄火离场。

$100+10+30=140$

出场发现 tx 和 lanos 分块都卡过了 $70$ ，/fn。

车上听说 nz 直接线段树维护分段函数做出来就是 $\mathcal{O}(n\log n+q\log^2n)$ ，离线可以少一个 $\log$ 。

回绍兴发现这个东西不是直接扫描线就做完了 /qd。

更加唐完。

总分 $50+50+11+100+10+30=251$ 。

每题都有分，总分上了 $250$ ，潜力之星确定！（

这场 Sub 太多了，记不清了。

T1

给一张 $n+1$ 个节点的 DAG，每个节点有两个出点 $a_{i,0},a_{i,1}$ ，和一个状态 $b_i\in\{0,1\}$ ，且出点编号大于自己的编号。

定义操作 $f(x)$ 为：

若 $x=n+1$ 则退出。
令 $q=b_x$ 。
令 $b_x=\neg b_x$ 。
执行 $f(a_{x,q})$ 。

求在执行多少次（非 $0$ 次） $f(1)$ 后，编号为 $1\sim n$ 节点的 $b_i$ 都与初始时相同。

总范围 $1\leq n\leq 50000$ 。时限 $1.5s$ ，空间 $768\mathrm{MiB}$ 。

解法：

先操作两次 $f(1)$ 。

考虑按照编号从小到大加点，每次加入一个新点时，设目前执行了 $c$ 次 $f(1)$ ，我们判断它的状态是不是和初始一样，如果不一样，我们再执行 $c$ 次 $f(1)$ 就可以在不改变之前点的状态的情况下，把这个点的状态翻回来。

怎么判断当前节点要不要翻？维护一个 $g_i$ 表示已经被加入的节点被执行过几次 $f(i)$ ，显然任何时刻， $g_i$ 都是偶数。

那么对于新加入节点 $x$ 的所有入点，这些入点肯定执行完后会有一半去执行 $f(x)$ ，那么令 $g_x$ 为所有入点的 $g$ 之和除以二，判断 $g_x$ 是奇数还是偶数就可以直到是否需要重复执行一边之前所有操作。重复执行就直接令目前所有的 $g$ 都乘二。

正常做法是直接把所有 $g$ 乘二放到后面未加入的点 $g$ 除以二，写个分数类，分母就是一个二的幂次，分子维护一个高精度数，压位一下就是 $\mathcal{O}\bigg(\dfrac{n^2}{w}\bigg)$ 。

不过数据很水，直接做就过了。

upd: 听说 zyy 自己都把 std 写错了，很难蚌。

T2

给定 $n$ 个正整数区间 $l_i,r_i$ 。

定义 $f(i,x)=x+[l_i\leq x\leq r_i]$ 。

$q$ 次询问，每次给出 $L,R$ ，求 $f(r,f(r-1,f(\ldots,f(l+1,f(l,0)))))$ 。

总范围： $1\leq n,q\leq 10^6$ 。

解法：

可以直接线段树维护分段函数，但是非常没有前途！

考虑扫描线，记 $f_{R,L}$ 表示询问区间 $[L,R]$ 的答案，有转移： $f_{R,L}=f_{R-1,L}+[l_R\leq f_{R-1,L}\leq r_R]$ 。

注意到对于某个 $R$ ， $f_R$ 是单调不降的（考虑对于 $L$ 和 $L-1$ ，分析第一次从 $L-1$ 开始走没有加一在哪里）。那么直接在数据结构上二分，区间加维护即可，可能需要使用树状数组上二分避免卡常（~~喜欢我冰火战士吗~~）。

T3

给定一张 $n$ 个点 $m$ 条边的随机有向图带权图，再给定 $q$ 次随机的询问 $u,v$ ，你需要回答从 $u$ 到 $v$ 的最短路。

解法：

不会，但是据说双向 dij 可以做到 $\mathcal{O}(q\sqrt{n}\log n+m\log m)$ 。

Day 3

在学校，忘了干了啥。

Day 4

去 APIO。

早上就去了，然后下午和晚上随机打摆。

这个国际交流中心环境还是听不错的，晚上还能看旁边奥体中心夜景，就是怎么没有网络 /fn。

试图购买网线连到它给的网线口，失败，太不牛了。

这个餐食配置怎么吊打了 PKUSC，~~是不是钱没给够~~。小卖部也很牛，看上去吊打了 SXYZ。

感觉有点感冒了，不牛。

Day 5

讲课。

上午讲到题目的时候光速开睡，讲完题目又感觉不困了。

感觉用证明期望等于某个值得到一定存在不小于某个值的解还是比较厉害的！

下午听 zky 和 Kubic 在线催眠。

你说的对，但是我们 ss 算法是用来解决……

晚上幽默开幕式，领到了密码条和铁牌一块（参赛证明）。dzd 疯狂爆典，《杭州余姚》

感觉自己有点烧了，而且感冒有点严重，早点睡。

Day 6

烧了一会儿感觉第二天复活了不少。

试机赛迷迷糊糊打了个 NTT，居然打对了，牛。

发了一个很大的食品包，应该中饭能吃饱。

发题。

看 T1，一开始题目理解出现了问题，理解对了之后发现 $m=1$ 直接做， $m\neq 1$ 直接拍个哈希上去也解决了。

结果自己写了一堆抽象错误，比如把两位开反什么的，总之 50 多分钟才过，感觉这个 T1 比赛博乐园简单一万倍啊！

看 T2 T3，一看完配分绷不住了： $5+5+30+60,5+30+65$ ，这我打牛牛啊！

T3 是通信，而且看这个抽象东西感觉过不了多少，猜个 Au 线 $235$ 或 $205$ 。

然后开始写 T2，看了一下可以按照起始时间转移，转移是个二维偏序，但是直接做是 $O(m^2)$ 的，可以获得高达 $5$ 分！

感觉这个部分分配的真的好难受啊！没啥好写的东西啊！

突然大脑抽风以为这个东西可以容斥拆开，我也不知道为什么我会认为一个二维偏序可以依赖容斥去降掉一个维度的，可能是烧坏了。

然后开始写假做法，只过了 $w=0$ ，这个时候才意识的这个东西能容斥个牛牛，假透了。

先吃饭吧，再看看 T3 有啥可写的。

感觉 5 分就上个菊花，35 分上两个菊花，100 分我也不知道咋做，由于这是 T3，所以打算拼上个 5 分就跑路先去 T2。

冷静一下发现这个 T2 可以根号分治，但是是 $\mathcal{O}(n\sqrt{n}\log n)$ 的看上去不太能过，然后发现一个地方可以上分块就是根号内 $\log$ 了！ $10^5$ 这不是随便跑！

速速开写。

然后 WA。

调

WA

调

WA

甚至第一个包 WA on 7。

结束了，打铁。

$100+5+5=110$ 。

出场听到 cyf 10min 就把 T3 过了？

然后一问发现 T3 是乱搞题，只要写的东西看上去很对就能过？

？？？？？

讲题环节：

“这个题不是我出的，跟我没啥关系，我只是刚好会所以上来讲”

甚至英文题解。

发现 T2 正解是决策单调性，而且可以做到一个 $\log$ 。

感觉这个一个 $\log$ 的做法还是很牛的！那你为啥开 $10^5$ 啊！这下成根号乱跑题了。

T3 发现标算一坨，结果直接拍个 crt 上去做完了，吊打标算一条街，还有不少基于随机打乱的乱搞菊花也过了，感觉输完了。

一问漏雨小猴 cyf 阿克了，边哥 puppy zhh 205，cjn 没测出来，剩下的全部没过 T2 yyz，而且没人开 T3。

晚上流了不少鼻血。感觉是休息不够导致的。

Day 7

最后一天！

MoonBit 还是挺厉害的，但是讲课语速也太快了！完全没听懂在说什么。

试了一下 Demo，感觉这个效率确实不错，不过貌似文档读的很奇怪。

下午 hlt 讲课，讲到一半发现怎么被 SXYZ 课内讲的真包含了！那直接 run。

run 的时候又流鼻血了，~~那干脆把 sjy 的也翘掉得了~~。

颁奖。

Cu 115,Ag 200,Au 240。

有点离谱，不过 T3 没法 Au。

AK 了 50 多个，太抽象了。

打铁了，不过也好，不用上去丢人了。

出乎意料地爆了一些冷，~~xqw 115 报出来掌声雷动。~~

ZJ 省队有俩打铁，震撼。

Kubic 唱歌好听 /se，铁玩家唱歌不牛。

回去请同学喝蜜雪。

Day 8

回 SXYZ。

评价就是开头的那张图。

题目没啥好说的，别人都骂过了，那我就不骂了，攒攒 rp。

获得了人生中的第一块铁牌！

本文作者：World Creater

本文链接：http://worldcreaterwc.github.io/PKUSCAPIO2024/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

最后更新：2024-12-19, 03:18:27

By World Creater.

随机文章回味旧文

PKUSC2024 & APIO2024 游记

PN 筛学习笔记

联合省选/ZJOI2024 游记

博客信息

文章数目

13