WHUWC 2025游记&题面

__Tao__ · 2025-01-20 21:21:18 · 生活·游记

WHUWC 2025游记&题面

THUWC打的太烫，不在你谷发了。

Day 0

三分钟报道，然后在校园里面乱逛三个小时（很大，走了两万步也只看了一小部分）。主园区很漂亮，有挺多值得看的民国时期建筑，可惜没有樱花。

Day 1

10：30才正式开始，睡了个懒觉。

通知的是 “NOI&ACM” 赛制，令人摸不到头脑，考前得知原来是 IOI （严格）。

双 Windows 环境，13:00-16:00，神秘。

吃完拉面很困，进场开题。

读了15minT1依然没看懂，叙述的相当不清楚。

题面中的三对词：0和1，教学楼和草地，校徽上的黑色和白色交替出现，我始终没有建立起他们的对应关系，也没有样例解释和大样例。

T2计算几何。跳。

T3尝试倒着贪心合并连续段，线段树维护，写半天假了。T4设 O(n^2) dp 状态失败。感觉这两个都是典题，但是我不会。

此时仅剩 40min，有点红温。

T1终于有了样例1的解释，想了几个做法都被“H”形卡掉，关键时刻灵光一现过了。（我都不敢相信，这个之后再说）飞速打暴力，T2的没有调出来。

最终 100+0+40+30=170 ，混了个 1=。

讲座主要介绍了网安，人工智能和【数据删除】班，反复提及某知名校友。

颁奖。官网表示这与强基招生无关。

简要题意（回忆）

原题面经过包装很复杂，如果你找到了原题请在评论区留言。

T1我尽可能还原原题面（非常长而令人迷惑，大概是达不到这个境界），其他给形式化题意。

T1

你要根据校徽种草。

最初你有一块地，接下来把它通过复制扩大到原来的 n\times n ，如果校徽这一块是白色就复制。对于 s_{i,j}=0 ，把这块地盖上教学楼。问复制 k 次后包含多少块草地。

输入：n\times n 的矩阵 s，只包含0和1，保证白色部分四联通。

原题：AGC003F

T2

给定二维平面上的 n\le 100 个不同整点 i:(x_i,y_i) ，满足任意三点不共线。首先作1\gets 2,1\gets 3,2\gets 3 （数字指点的编号）的有向线段，接下来枚举 i>3 ，对于每个 j<i ，若 j\gets i 和之前任意一条作过的线段都无交（不包括端点），就作这条线段。

问有多少个点编号的置换（共 n! 个），使得 \forall i>3 都有恰好三条有向线段以 i 作为起点。

T3

给定一个长度为 n\le 10^5 的序列 a ，你需要将序列划分为 k 个非空连续段，每一段的价值为段内所有数的极差 （\max-\min）。对于所有 k\in [1,n] ，最大化价值和。

T4

给定数轴上 n\le 2.5\times 10^5 个带权闭区间 (l_i,r_i,w_i) ，两个区间有边当且仅当它们有交。

你需要选择一些区间，在形成的图没有环的前提下最大化权值之和。