SDOI2025集训第一轮

__xzm__ · 2025-03-30 17:24:11 · 个人记录

day1

80+50+0 = 130，总榜 rk8，山东 rk5

T1

显然应该先 2^{r*c} 枚举左上角的 r*c 的矩形，然后不难发现只需要知道前 r 行和前 c 列就能确定整个 n*m 的矩形了。

手推一下发现 a_{x,y}=a_{x-r,y}+a_{x,y-c}-a_{x-r,y-c}，然后再把 a_{x-r,y} 和 a_{x,y-c} 用这个式子拆开，就能得到 a_{x,y}=a_{x\%r,y}+a_{x,y\%c}-a_{x\%r,y\%c}。

看什么时候 a_{x,y} 不合法。发现当且仅当式子右边三项分别为 0,0,1 或 1,1,0 时 a_{x,y} = -1 or 2 不合法，这个可以刻画为 a_{x\%r,y\%c} 与 a_{x\%r,y},a_{x,y\%c} 中至少一个相同。

进一步的，可得 a_{x,y} 与任意的 a_{x+k*r,y} 或任意的 a_{x,y+k*c} 均相等，将这两种记为“行相等”和“列相等”。

也就是说，对于我们枚举的左上角的 rc 的矩形，里面的每个位置要么满足“行相等”，要么满足“列相等”，这个就可以再去 $2^{rc}$ 枚举了。

然后可能会有格子既满足“行相等”又满足“列相等”，容斥抵消计算即可。

进⼀步观察，当⼀个格⼦满⾜“⾏相等”时，该格⼦对于⾏的限制就不复存在，我们仅需考虑该格⼦对于列的限制；同理，当⼀个格⼦满⾜“列相等”时，该格⼦对于列的限制就不复存在，因此仅需考虑该格⼦对于⾏的限制。也就是说，每个格⼦的权值可以放在计算贡献时的统计部分进⾏，仅需考虑每⼀⾏中“列相等”格⼦的数量和每⼀列中“⾏相等”格⼦的数量即可。

然后每行每列贡献的计算可以预处理，这样就能做到 O(3^{rc}*(r+c)) 了。

T2

首先有 d 是质数且 d%20==3 或 d<=10 这个限制，题目又保证数据随机，估测或者打个表看一下就知道有效点对实际上只有大概 n^2/log n 对。

由此容易想到枚举点对 (i,j) 并以 d_{i,j} 作为最后的中位数，考虑如何算答案。

发现存在两个或三个距离相同时就不好算了，可以随便手动定义距离相同时的字典序，这样就设前面的 d 严格小于后面的 d。

这样枚举一遍所有的 k 即可。复杂度 O(n^3/log n)。

然后发现所有 a_i=1 的 sub2 就可以直接bitset优化，O(n^3/log n/w)，这样就一共有 50pts 了。

考虑 bitset 的实质，我们是每 w=64 位压成一个 unsigned long long，然后通过 ull 的位运算来做的。那么这个能不能拓展到非 0/1 任意权值呢？

我们考虑每 B 个位置压成一块。。。

复杂度是 O(n^2/B+)。。。

最优 B 取 logn，。。。

T3

观察“线图”的结构，会发现一个点周围的边进行一次变换之后，会形成一个团。每进行一次变换，这个图会变得更加“紧密”。

显然一个图在做一次线图变换后，连通性大致不会变（即原图中⼀个连通块不会在线图中被分裂成两个连通块）。

因为由若干个团构成，所以 k 阶线图的最⼤独⽴集就等价于 k-1 阶线图的最大匹配（选尽量多的边使得这些边两两无公共点）。

k=2

求 1 阶线图的最大匹配。

注意到线图具有较强的连通性质，那么对于每个连通块，最大匹配实际上就是 \lfloor\frac{点数}{2}\rfloor。而 1 阶线图的点数 = 原图的边数，所以答案 = \sum \lfloor\frac{m}{2}\rfloor，其中 m 是原图中一个连通块的边数。

k=3

求 2 阶线图的最大匹配。

后面基本都同理，懒得写了，看题解吧。

上课

P9342

注意到从连续左/右走转向连续右/左走至多只有 log 次（因为每次调转方向都会翻倍），所以每次二分即可，复杂度 O(mlog^2n)。

P9530

CF1442D

做了。

P6109

day2

90+0+15 = 105，总榜 rk27，山东 rk23

T1

要么认识了所有的 n 个人，要么没有认识所有人。也就是说我最后会认识 i 个人 (i < n)，但是其他人都无法认识了。

设 f_i 表示最终我的社交网络里恰好有 i 个人的概率，那么答案其实就是 f_n。

转移就是 f_i=1-\sum\limits_{j=1}^{i-1}\binom{i-1}{j-1}f_j*(\sum\limits_{c=0}^{k-1}\binom{j-1}{c}p^c(1-p)^{j-c})^{i-j}。

T2

四分树 or KDT。我不会。

T3

CRT 什么玩意的。不会。

上课

qoj7767

P6329

P7215

首先题目要求的就是找一个包含颜色最少的连通块，使得内部出现的颜色和外部的颜色两两不同。

考虑点分治，对于每一次分治出来的重心 x，我们求出仅在 x 子树中的且包含 x 的最小连通块。具体就直接把需要加入的颜色加入队列，直到不需要加为止。这样一定能求出所有的答案，因为如果不包含 x，要么会在上一层的分治重心中算，要么会在下一层儿子那里的分治重心算。

P4183

不妨设 Bessie 从根节点出发，农民从叶子往上走，那么如果农民在 Bessie 到达某个点之前到达了这个点，那这个点的子树就“封锁”了。即要做到“准时到达封锁点”，这个用一个路径长度的不等式表示出来，就可以在根节点确定的时候，做一遍 dfs，数出有多少个封锁点就好了。那这样就有一个 O(n^2) 的做法了。然后把式子形式化地表示一下，树上差分，点分治，做一个“不等式点对的点权统计”，就行了。

day3

55+10+10 = 75，山东 rk18

T1

注意到按照 \frac{c_i}{1-p_i} 从小到大来挑战关卡一定是最优的。所以对于剩下所有的关卡中 \frac{c_i}{1-p_i} 的最小的 i，在他的前驱 d_i 挑战完之后就一定会直接挑战 i。

考虑合并 i 和 d_i，合并之后的 p=p_{d_i}*p_i,c=c_{d_i}+p_{d_i}*c_i。用小根堆+并查集维护即可。

T2

推箱子转为箱子瞬移，然后最大流/费用流消圈。

T3

首先显然 s=\sum a_i\ge 360 时，答案为 0。所以 n\lt 360。

讨论两边的角在上/下/中间，把式子写出来，dp/积分。

上课

P5576

qoj5034

uoj429

P3529

CF932G

day4

60+25+75 = 160，山东 rk9

T1

考虑先按照所有位置的取值都是 1~n 去构造出一个解。然后考虑调整法。先去保证每行不重复，把被 forbidden 的数改为最小的合法的数，然后如果影响了列上的合法性就再去调整列。如此重复。不难发现不合法的位置数量不增，所以最坏做 n^2 轮就会找到一组解。这样的复杂度最劣是 O(n^4) 的。但是随机数据能过。

T2

不会。

T3

因为 p<\frac{1}{2}，所以显然当 b1=2^k 时每次最优一定是选 lowbit(x)，直接记搜即可。

这其实就是 x 是有限小数时。当 x 不是有限小数时，它一定是一个有限小数+循环节组成。考虑 x 是有限小数的做法的过程，实际上可以看作是矩阵乘法，并且可以证明循环小数部分的矩阵的无限次方是收敛的，所以直接求逆即可。

上课

qoj5523

考虑直接状压 dp。设 f_{s,x,y} 表示 x 能否通过 s 点集中的点到达 y，加上转移的复杂度是 O(2^n*n^3)。

考虑固定 x。只用维护 f_{s,y}，算答案的时候枚举两边的状态合并，这样可以做到 O(2^n*n^2)。

我们只维护 f_s，将 y 放到 dp 的状态里，也就是 f_s 的第 i 位代表能否到达 i。复杂度是 O(2^n*n)，就能过了。

agc031e

qoj5419

gym105336H

agc033e

qoj5090

qoj9237

day5

35+28+10=73，山东 rk25

T1

当 m 是奇数时，枚举哪个点是重心，用总方案数减去不合法的即可做到 O(nm)。考虑组合意义+递推可以做到 O(n)。

当 m 是偶数时，容易发现可以作为中心的一定是一条链，中间的点全是 0。如果固定这条链，考虑链上任意一个点 u，设 S 为满足如下条件的点的集合：在链上，编号小于 u，且到 u 的路径上不含有其他小于 u 的点。于是 |S|\le 2，且只需要对 S 做一次容斥即可统计 u 的贡献。这样我们将最小值的贡献拆到了每个点上。上述过程和链的形态没有关系，只需要容斥涉及到的点都是可能的重心即可。用并查集维护，时间复杂度 O(nlogn+m)。

另解：点分治。

T2

T3

上课

qoj4812

首先，有一个 O(n^2) 的 dp，设 f_{i,j} 表示 a 的元素之和为 i 且最后一个元素为 j 的方案数。

注意到，如果 a_1=B，那么 \sum\limits_{k=1}^{m}a_k 会落在 m*B±\frac{m*(m−1)}{2} 中，所以 m=O(\frac{n}{B})。

分类讨论 a_1 的大小。如果 a_1\le B 就暴力 dp，复杂度 O(B^2)。如果 a_1\gt B，直接把 \sum_j (a_j-a1) 记到状态里可以得到一个 O((\frac{n}{B})^4) 的做法，平衡得到 O(n^\frac{8}{5})。

考虑倒着做，每次往前加一个数，这样只需要记长度以及 \sum_j (a_j-a1)，是 O((\frac{n}{B})^3) 的，平衡得到 O(n\sqrt n)。

qoj7677

CF1750G

arc138f

具体看题解吧。

P10145

qoj4893

day6

10+0+0=10，山东 rk29

T1

设 x 表示 123 最多的个数，y 表示 321 最多的个数。显然 x 越大，y 越小，那就直接双指针，考虑如何 check(x,y)。123 一定是选最前面的 x 个 1 和最后面的 x 个 3，321 同理。那这样就变成了一堆区间，中间的 2 的放置就直接排序+贪心放，这样是 O(Tn^2logn) 的。

考虑优化。其实只需要求出 x,y,x+y 的上界就可以直接算答案了，这样的复杂度是 O(n) 的。

T2

T3

上课

qoj4912

考虑这样的构造：有一个指针 p 和一个 26 bit 的内存，初始时 p=0。每次读取 p 指向的内存的值，如果为 0 则 p 回到 0，如果为 1 则 p\leftarrow p+1。移动 p 后将原先 p 指向的内存的值反转。p 第一次移动到 i 恰好需要 2^i 步。每次调用会修改不超过 5 bit 的 p，以及 1 bit 的内存，总共不超过 6 bit。

P10433

qoj8044

竞赛图最小割

题目：给定一张 n 个点的竞赛图 G，所有边的边权都是 1。求 G 中两两点对间的最小割。