reechee's Blog

因为 Timeline 都忘了，所以弄个简要题解吧 20231017-noip-22 NOIP 三道黑 T1 rescue 设 fif_ifi​ 为救出来的概率为多少，得倒着做，转移复杂度 O(n2)\mathcal{O}(n^2)O(n2)。 改改状态，设 fi,jf_{i,j}fi,j​ 为第 iii 天后剩余的总能力为 jjj 时未来救出来的概率时多少，时间复杂度 O(1000n)\mathcal{O}(1000n)O(1000n)。 此外不能用 1−fi1-f_i1−fi​ 表示活着的概率。 T2 dance 将 aia_iai​ 从大到小处理，将影响到的区间都 +1+1+1，将问题转化成了第 xxx 个版本的 [l,r][l,r][l,r] 的最大值是多少，主席树即可。 T3 tree bitset 优化构造 T4 dye 折半搜索 + 容斥 + 高位前缀和 20231018-noip-23 T1 flandre 贪心，答案为排序后的某个后缀 T2 meirin 不是数据结构题而是神仙式子转化，这里空太小我就不写了 T3 sakuya 把期望转化成概率，然后预处理一下后做树形 ...

Timeline 07:50-08:30 先把 A 暴力打了 08:30-09:00 把 B 最低档暴力打了 09:00-09:20 把 C 暴力打了 09:20-09:50 把 D 暴力打了 09:50-10:15 把 A 正解打了 10:15-10:40 B 冲了一点部分分 剩下时间 摆烂。 Result 100+35+10+0=145100+35+10+0=145100+35+10+0=145 Solution T1 超级源点板题。 T2 枚举操作点，在极长子串间计数。 T3 若有 A→BA\rightarrow BA→B 的最短路经过了 U→VU\rightarrow VU→V 的最短路，那么一定是 A→X→Y→BA\rightarrow X\rightarrow Y\rightarrow BA→X→Y→B，其中 X,YX,YX,Y 在 U→VU\rightarrow VU→V 的最短路上。 那么分别对四个点跑一遍 Dijkstra，找出最短路上的边建个图，建出 DAG 后跑个 拓扑排序 + DP 即可。 T4 跑到一个能跑到的最久被抓住的点，然后原地等似，这点用点分治实现。

Timeline 07:40-08:00 看到 A 第一眼就秒了，写暴力 + 正解。 08:00-08:30 B 第一时间没想到什么好的做法，先把暴力打了。 08:30-09:00 想出了个贪心做法，结果测大样例寄了 XwX。 09:00-09:20 先把 C 暴力和 D 最低档分写了。 09:20-09:35 想了一会把 D 另外 10 档分写了。 09:35-10:35 B 居然有重边，把重边删了大样例就过了，算了下时间复杂度能过 剩下时间 摆烂。 Result 100+100+15+20=235100+100+15+20=235100+100+15+20=235 Solution T1 答案只与奇偶性有关，用并查集维护一下就行了。 另外二进制下乘法是 AND⁡\operatorname{AND}AND，加法是 XOR⁡\operatorname{XOR}XOR. T2 贪心的选权值最大点，然后再把其从其它点的权值和中减去，时间复杂度 O(nlog⁡n+n+m)\mathcal{O}(n\log n+n+m)O(nlogn+n+m)。 但这样的话每条边上只会有点权较小的一个点会被统 ...

Timeline 07:40-08:10 通看了一下题目，A 感觉很可做，B 感觉不太可做，C 又是构造，D 不会，先把 A 暴力打了 08:10-09:10 想 A 正解，想到了“正解”，打那个正解 09:10-10:10 写完了，测大样例不对，写对拍，第一组就寄了，发现写的统计的方法不对 10:10-10:45 先把 B,C,D 暴力打了 10:45-11:10 想到了另一种统计方式，这下能过大样例了，但是跑了 1.5s /jk 11:10-11:30 把线段树换成了 ST 表，大样例 0.5s 左右应该稳了 11:30-11:50 GG Result 100+15+25+15=155100+15+25+15=155100+15+25+15=155 Summary 这就是为什么不要摆 大样例错了之后写对拍 比赛结束前 1h 检查一下暴力 Problem T1 给出长度 nnn 的序列 aia_iai​，最小化分成的段的数量，使得每段内第一项为最小值，最后一项为最大值。 n≤3×105,1≤ai≤109n\leq 3\times 10^5,1\leq a_i\leq ...

Timeline 07:40-08:10 通看一遍题目，A 甚至都看不出来是什么算法，后面都没头绪，先把 A 暴力写了。 08:10-08:30 把 B 暴力写了。 08:30-09:30 把 C 链的部分分写了。 09:30-09:40 怎么 D 连最低档暴力都没法写 /jk，开始罚坐。 Result 20+20+0+0=4020+20+0+0=4020+20+0+0=40 C 部分分写挂了，众生平等场。 Problem T1 问长度为 nnn 的排列中分别形成深度为 1∼n1\sim n1∼n 的笛卡尔树的方案数。 1≤n≤9001\leq n\leq 9001≤n≤900 Solution 设 fi,jf_{i,j}fi,j​ 为用 nnn 个数构造深度为 jjj 的笛卡尔树的方案数。 枚举切割点，设左右两边多的一边用了 kkk 个点，少的一边用了 i−k−1i-k-1i−k−1 个点。 fi,j=∑k=i2i−1{2Ci−1k(sumk,j−2fi−k−1,j−1+sumi−k−1,j−1fk,j−1),k≠i−k−1Ci−1k(sumk,j−2fi−k−1,j−1+sumi− ...

Timeline Timeline 08:10-08:20 通看一遍题目，感觉除了 C 都不是很可做的样子， 08:20-08:40 把 A 暴力打了 08:40-08:45 好好好，C 一开始看的时候看错题意了，又变得不太可做了 08:45-09:00 把 C 暴力打了 09:00-09:20 把 B 暴力打了 09:20 D 最小的点居然还有 1e3 /jk GG Summary A 这么简单居然没想出来 /cf 别摆。 对于 n≤1000n\leq 1000n≤1000 的稠密图，跑 Dijkstra 时要用邻接矩阵建图跑最短路。 Problem T1 有一张 nnn 点 mmm 条含权无向边的图，每个点都有一辆出租车，每辆出租车最远可以开的距离为 did_idi​，花费 cic_ici​ 的代价，给定起点和终点，最小化代价，无法到达输出 −1-1−1。 1≤n≤1000,1≤di,ci≤1091\leq n\leq 1000,1\leq d_i,c_i\leq 10^91≤n≤1000,1≤di​,ci​≤109 Solution 从每个点 iii 跑一遍 D ...

Timeline 07:40-08:10 通看题目，好好好，3 道构造是吧，A 又双叒叕是性质题，BCD 还没头绪，先把 A 题 O(n)\mathcal{O}(n)O(n) 卡时暴力打了 08:10-08:45 写了 B D 的暴力 08:45-09:25 C 写了一些莫名其妙的代码，开始罚坐 Result 60+50+0+3060+50+0+3060+50+0+30 Summary 有时间多想想前面的题，别在后面死磕拼包。 Problem T1 给出一个数 aaa，找出另外两个整数 b,cb,cb,c 使得这三个数为勾股数。 1≤a≤1091\leq a\leq 10^91≤a≤109 Solution a≥3a\geq 3a≥3 时绝对有整数解。 先选个好推的式：a2+b2=c2=a2=c2−b2=(c−b)(c+b)a^2+b^2=c^2=a^2=c^2-b^2=(c-b)(c+b)a2+b2=c2=a2=c2−b2=(c−b)(c+b) 设 c−b=1c-b=1c−b=1，则 c+b=a2c+b=a^2c+b=a2，解方程组得： c=a2+12=a2−12+1b=a2−1 ...

Timeline 08:00-08:10 通看一遍题目，A 像性质题，B 6,7 点感觉可以贪（？，剩下的感觉？？？，C 感觉暴力写起来很麻烦，D 无头绪只会暴力，先把 A 暴力写了 08:10-08:40 A 性质没想出来，B 贪想到了一个细节导致代码好难写（也许根本就没法贪） 08:40-09:00 把 C 的部分分和 D 的暴力打上了 09:00-09:30 把 C 的暴力打上了，还顺便把部分分的错找出来了 09:30-09:55 把 B 的暴力打上了，开始罚坐 10:30-11:00 D 写了一个 O(qnmlog⁡m)\mathcal{O}(qnm\log m)O(qnmlogm)的 3,4,5，但是常数巨大（或者算错了）极限数据测了一下会 G （希望是随机） 11:30 D 砍去了 log⁡\loglog，常数大大减小 Result 70+20+20+5070+20+20+5070+20+20+50，B 贪心写炸了 −20-20−20，C 部分分挂了 −20-20−20。 Summary 得加快点写暴力的速度。 先想好怎么写再去写。 Problem T1 TTT ...

Timeline 07:50-08:20 通看了一遍题目，怎么感觉都好难，忘了海伦公式具体是什么然后考场现推近半小时（（（，把 A 题 70 分暴力写了 08:20-09:10 把三题最低档暴力写了 09:20-09:40 把 C 题 4,5,6 写了 09:40-10:10 把 B 题 3,4,5 写了，开始罚坐 Result 30+50+0+4030+50+0+4030+50+0+40 A 题海伦公式爆精度 −40-40−40，C 题两个包各有一个错，第一个包还 nt 了 −60-60−60，输麻了。 Summary 有时间要检查自己暴力有没有写对 坐标系求面积不要用海伦公式，以后用这个： S=∣xAyB−yAxB+xByC−yBxC+xAyC−yAxC∣2S=\frac{|x_Ay_B-y_Ax_B+x_By_C-y_Bx_C+x_Ay_C-y_Ax_C|}{2} S=2∣xA​yB​−yA​xB​+xB​yC​−yB​xC​+xA​yC​−yA​xC​∣​ Problem T1 平面直接坐标系上给定 nnn 个点，问任选三点能组成多少面积为整数的三角形 n≤5000 ...

link T1 摆花 Problem 给出一个整数 nnn 和 mmm 个区间 [li,ri][l_i,r_i][li​,ri​]，要求往长度为 nnn 的序列 aia_iai​ 中填数 x(0≤x≤n−1)x(0\leq x\leq n-1)x(0≤x≤n−1)，其中 xxx 可以重复，求一种方案最大化 mex⁡[ali,ari]\operatorname{mex} [a_{l_i},a_{r_i}]mex[ali​​,ari​​]，输出这个最大值。 100%→n,m≤105,1≤li≤ri≤n100\% \rightarrow n,m\leq 10^5,1\leq l_i\leq r_i\leq n100%→n,m≤105,1≤li​≤ri​≤n 1s/512MB1\text{s}/512\text{MB}1s/512MB Solution 答案为 min⁡(ri−li+1)\min (r_i-l_i+1)min(ri​−li​+1)，因为对于每一个区间来说最优方案肯定是从 000 到 ri−li+1r_i-l_i+1ri​−li​+1。 时间复杂度 O(m)\mathcal{O} ...