ctt 邮寄

· · 个人记录

Day 0

坐飞机到北京，然后打车到酒店。

到酒店的时候已经快到十二点了，于是外卖了个 KFC 单人餐。天气方面，主要是发现北京室外比较冷，室内应该是由于开了地暖之类的东西，特别热，尤其是酒店里面，必须要脱衣服裤子 才能生存。

下午试机，三个题目是 A+B, 奥林匹克五子棋，元旦激光炮。

感觉 T2 有点难，于是先做 T2 再做 T1 最后把 T3 写了，耗时半小时 AK。

Day 0 得分 100+100+100，应该是 rk1。

试机的时候发现系统是 Linux 但是似乎不是 Ubuntu。显示器不是很大，但是分辨率是 3920 \times 2160，导致所有窗口和字符都特别小。

于是想把分辨率搞低，但是发现找不到设置。这个时候发现 OJ 的 FAQ 里面写了怎么调，第一步是在桌面右键打开设置。

但是我在桌面右键怎么什么也没有发生！！然后又搞了一会，才发现是我的右键好像灵敏度有点低，于是终于把分辨率调到 1920 \times 1080，结果发现画面变得很糊，所以又调回去了。最后的解决方案是把 VSCode 和浏览器比例都调大。

这样搞的一个问题是鼠标滚轮滑动窗口会变得特别慢，懒得管了。

AK 完了之后常规地测了一下 NTT，发现两个 2^{22} 的数组卷起来要 0.55s，交 OJ T 了。2^{21} 的数组大概要 0.25s，交 OJ 跑 0.55s 左右，速度不算特别慢。

晚饭比较好吃，除了饭菜还有一小盒水果和一包酸牛奶。不过饭菜的口味稍微有点不合胃口。

回到酒店。有一位 QQ 叫 whiteqwq 的志愿者加了我的好友，然后把十个人拉了一个群。

由于酒店房间还是非常热，穿的衣服数量+裤子数量=2 还是很热，于是在群里问了一句：有没有同学觉得酒店房间比较热。

发现群里有：房间两个人穿的衣服+裤子数量之和=1 的，非常震撼。同时在群友的指导下，发现把酒店的冷空调关掉之后就会变得凉快，操！！！还有群友说把窗户打开会凉快，但是我们的窗户居然好像打不开。于是点了一杯饮料喝。

然后又不知道过了多久，ningago 大神莅临我们房间，然后在我和 jqh 告诉他“窗户好像打不开”的前提下，轻松地帮我们打开了窗户，这个时候我才发现，是我怕把窗户搞坏了没怎么用力，所以才没有打开,shabby！！1

晚上 1040 睡觉

Day 1

酒店的早餐不失所望地比较难吃。值得一提的是 ningago 和他的室友都忘记定闹钟，七点十几分才起床，所以失去了早餐。

早上的三道题，数据范围可能不准确：

T1

有一个长度为 n 的数组 a，一开始全是 0，同时给定整数 m\le n 和一个长度为 n-m+1 的权值数组 b。接下来做 c 次操作，每次操作以 \frac{b_i}{\sum b} 的概率选中一个 [1,n-m+1] 的整数 i，然后把 a_{i,i+1,\dots,i+m-1} 都加 1。
问 c 次操作后 \sum a_i 的期望。

T2

维护长度为 n 的数组 a 和 b。定义 i,j 匹配当且仅当 b_i=0 且 b_j=1。定义一组匹配是一个匹配的集合，满足所有匹配的二元组中的数互不相同。

在初始时，和每次操作之后，回答以下问题： - 找到**一组**匹配，使得形如 $(i,j),a_i=a_j$ 的匹配数量最大。 - 在满足以上条件的情况下，使得这组匹配的大小最大。 - 输出这组匹配的大小。 $n,m\le 2\times 10^5, 1\le a_i\le n, 0\le b_i\le 1$。

T3

交互题。有一条不与 y 轴平行的未知直线和一个给定的值域 V，满足其不经过 x,y\in [0,V] 的所有整点 (x,y)，且直线与 x=0 和 x=V 的交点纵坐标也在 (0,V) 内。
这条直线把值域内所有点划分为两部分，你需要在 lim 次询问内找到一条直线，满足这条直线划分出的集合与未知直线划分的一致。以 y=kx+b 的形式输出，其中 k,b 用分数形式 \frac{p}{q} 表达，要求 p 在 long long 范围内，q 在 int 范围内。

开局做了十几分钟 T1 发现会一个 n^32^m 的做法，应该能拿 25\sim 45 分。写+调了一个小时左右，没调出来，于是去做 T2。

T2 很快会了 m=0，然后感觉上个线段树二分维护一下就行。写了一个多小时一直没过拍，感觉做法比较伪，于是又在 T1 跟 T3 之间摇摆。最后去上了个厕所，感觉做法可以修，但是要多写 2k 左右，于是就继续写 T2。最后在 12 点过一会的时候过掉了 T2，码长 6660B。

然后调了一下 T1，发现是一个形如 if( s>>b&1 ) 的地方写成了 if( s>>b ) ，改掉之后调了调就过了，同时直接过掉了 n\le 20，有 45 分。

接下来开 T3，感觉特殊性质直接上个 SBT 就做完了，结果发现询问数是假的。然后一顿乱搞，发现始终过不去。最后发现在 SBT 上面倍增跳儿子很对，但是只剩 1min 了没写。

Day 1 得分 45+100+0，但是排名意外地不低。如果过了 T3 性质就到总榜前 10 了。不过反正我没进集训队，没啥好说的。

下午参观清华，印象最深的是走了两个小时把脚走痛了，好似。

然后听讲，感觉这把可以打的分应该至少有 60+100+20，T3 是阴间提。

晚上政委组团开趴，但是由于没睡午觉感觉精神不太好，没去。

Day 2

感觉没啥好写的，还是先记一下题面。

T1

交互题。有一个未知的 n 个点竞赛图，每次询问可以知道两点之间的边的方向。

- 从 $u$ 出发可以到达所有其余结点，并且它到其余点的最短路距离的 $\text{max}$ 最小。

T2

对于两棵 n 个点的有标号树 T_0,T_1，我们称 T_0 偏序 T_1，当且仅当它们满足如下条件：

  • 记 T 是一棵 n 个点的树，V 是它的一个点集，定义 f(V,T) 表示 V 对 T 的导出子图中，度数 \le 1 的点的数量。
  • 条件：\forall S\subset \{1,2\dots,n\}, \exist S\subset T\subset \{1,2,\dots,n\} 使得 f(T,T_0)\le f(S,T_1)。

定义树 T_0,T_1 属于同一个等价类，当且仅当 T_0 偏序 T_1，且 T_1 偏序 T_0。
给定 k 棵 n 个点的树，你需要解决两种问题：
问题 1：对于被所有这 k 棵树偏序的树，计数它们形成的等价类数量。
问题 2：对于偏序所有这 k 棵树的树，计数树的数量。

n\le 5000, k\le 1000, \bmod=998244353

T3

给定一棵 n 个点的随机生成的树。
称长为 n 的排列 P 是它的一个拓扑序，当且仅当对于任意 i=1,2,\dots,n-1，都存在恰好一个 j\gt i 满足 P_i,P_j 之间有连边。
你需要输出这棵树的 k 个拓扑序，满足：同时存在这些拓扑序的树只有给定的树，且 k 最小。
有 T 组数据。
子任务 1：T=10, n=10。
子任务 2：T=100, n=100。

做题体验很阴间，大致是先写了一个看起来像是 n^2 次询问的做法交 T1，结果莫名其妙直接过了。然后打完 T3 的暴力，做了 3h T2，成功 7\rightarrow 17 分，最后给 T3 卡了下常，多了正好 0.99+0.01=1.00 分。

最后是 100+17+62.74。

下午讲题和讲座，比较无聊。

Day 3

T1

有 n 个人，标号为 i 的人实力值为 i，他们排成一个环。
每个人有一个归属的队伍，红队或者蓝队。每相邻两个队伍不同的人会进行比赛，实力值高的获胜。
如果蓝队获胜，蓝队加 1 分。
如果红队获胜，并且这个获胜的人排在蓝队的逆时针方向，红队加 1 分。
最后对于每个 i=-n,-(n-1),\dots,-1,0,1.\dots,n-1,n，询问当红队比蓝队多 k 分时，有多少种可能的圆排列。

3\le n\le 3000, \bmod=998244353

T2

有一段大小为 m 的一维空间，有 n 个有长度的一维物体，第 i 个为 a_i。
对于 i=1,2,\dots,n，依次执行以下操作：

  • 如果还存在一段长度为 a_i 的空间，未放置任何一个物体，则必须选择一个位置（不一定在整点上）把第 i 个物体放入。
  • 否则什么也不做。

问有多少种“放进去的物体的总长度”，依次输出。

T3

交互题。有一棵未知的 n 个点无根树，和一个初始为空的点集 S。
你可以进行一些操作，每次操作可以向 S 中加入或者删除一个点，交互库会返回 S 形成的导出子图中，最大的连通块的大小（点数）。
在 Q=6\times 10^5 次操作内，确定这棵树。

还是很阴间的体验。大致是先想了一下 T3，然后用不到 1h 过掉了。接下来就是打 T1 和 T2 的暴力，打完暴力之后一直想 T1，想了很多种可能的优化方式都不太可行，最后 1h 一直在摆。

于是最后得分是 40+50+100。

下午的讲题，精神不太好没怎么听懂。

讲座更是根本不知道在讲什么，完全没听。

值得一提的是晚饭很幽默，是不怎么好吃的三明治和味道一般的鸡翅和鸡腿，给人一种 THU 闹饥荒的感觉。

后面可能还会更新些东西，不过现在懒得写了。