2023年7月30日发(作者：)

POI2004

未完整解决的有：

kag 算法不如标程

zga,mis 不会

题号

gra

核心算法

模型转化+sg函数

具体细节

S1:若a[n]=m-1，则只能移动最后一枚棋子，Ans=1。

S2:若谁移动后所有棋子都在[-2]，则胜。故可转化模型：两个空格之间作为楼梯，m-2与m-1间作为地面，连续棋子数B作为石子数，则成为经典问题（见论文）。

结论：该游戏Sg函数为奇数格棋子数的Xor和S。

优化：对于转化后连续的奇数个0等价于1个0，连续偶数个0等价于2个0。

可行策略：

奇数楼梯i：S xor b[i]

偶数楼梯i：b[i-1]

S1：询问（(1,1,1,1),(1……0……1)），确定哪些数字未出现过。16次。

S2：根据可能数字集大小K别处理。

K={a} Ans=aaaa。

K={a,b,c,d} 询问类似((0,1,1,1),(0,1,1,1))以确定某个位置是不是某个数字。

K={a,b,c} 枚举，若发现某数字x无法匹配到某位置，那么先匹配另外两个，则剩下的两个位置均为x。

K={a,b} 两种情况：abbb与aabb。若某次匹配成功，则剩下的都是另一个数字，否则枚举C(4,2)来确定a即可。

需要次数最多的为aabb，2*4+C(4,2)=14次。

P1:F[i]表示以i为根的子树以及i连向其祖先的边均已被覆盖，所需的最少路径数。

转移：将i的儿子两两配对，拿出一个连向i的祖先。

F[i]=∑F[j]-Si/2+ord(si为偶且i<>1)

Ans1=F[root]

{j为i的儿子,Si为i的儿子数目}

P2:二分枚举答案Ans2，G[i]表示以i为根的子树中所有路径长度不超过Ans2时连向i祖先的路经的最小长度，Ans2可行当且仅当G[root]存在且G[root]<=Ans2。

求G[i]前我们先求出所有G[j]并将它们从小到大排序，然后二分枚举G[i]=G[j]+1，若剩下的G[j]头尾配对均不超过Ans2则G[i]可行。

细节：Si为偶数时可添加G[k+1]=0方便处理。

初始所有点为白色，对于点i，若e[i]为白色则将其染成与c[i]不同的颜色。

证明：若点i确定为白色，e[i]染白色也只能提供一个黑点，故e[i]染黑色不会差；若所有指向i得点均为黑pin 枚举

szn 贪心+树形DP+二分枚举

szp 贪心+拓扑排序 色，则i只能是白色。

使用拓扑排序实现，一开始将无入度的点入队，最后剩下的环从任意处切开即可。

zaw 最短路+枚举+集合划分优化

基本算法：枚举走的第一条边(1,i)，以i为起点求到1的最短路即可。

优化：基本算法实质是把i作为起点集合，其余与1相邻的点作为终点集合，求两个集合间的最短路。实际上我们只需要满足任意两个与1相邻的点i,j至少有两次(分别作起点终点)划分不在同一个集合中即可，故我们可以

for p := 0 to log(n) do

for i := 1 to n do

if i 与 1相邻 then

if i的第p和二进制为1 then i∈集合1

else i∈集合2

求最短路（集合1 to 集合2）

求最短路（集合2 to 集合1）

最短路使用SPFA或Dj+heap皆可。

设T={a,b……c,d,e}（由小到大）

当前，将d与e移过去，有两种选择：

S1={e,a}{a}{d,a}{a}=e+a+d+a

S2={a,b}{b}{d,e}{a}=b+b+e+a

若S1<=S2，则移e（d的移动取决于c）否则将d,e一

起移过去，证明如下：

因为S1>S2，故第一步移e，那么第二步必然移动c,d：

S3={e,a}{a}{a,b}{b}{c,d}{a}=e+a+b+b+d+a，

S2’=S2+{a,c}{a}=b+b+e+a+c+a

S2’-S3=c-d<=0，故先移d,e更优。

将除0，1外所有点标0，利用SPFA更新不合法节点直到所有点均满足给定条件，设此时标号为F[i]。然后标1再做一次，设此时标号为G[i]。

对于i，若F[i]=G[i]，则该点标号确定为F[i]，否则该点标号不确定，证明如下：

1. 每一步中每个点至多更新两次。以第一步为例，第一次更新必然是1 to not 1，这只会使得1的个数减少，那么其余点的更新也只能是变小，故每个点至多1 to 1/2 to 0共两次更新。

2. F[i]=i可取的最大值。G[i]=i可取的最小值。

由1的证明可类似证得。故可由F[i]与G[i]确定i的标号范围。

给一棵树的每个节点标上一个正整数，使得任两个标号均为x的节点间的路径上存在至少一个标号大于x的节点，并使得最大标号X最小。

若解决上述问题，那么该题只需每次询问当前子树中标号最大的点，再根据答案可以将宝藏确定在一个最大标mos 贪心

bra 迭代

jas 模型转化+贪心+位运算 号小1的子树中，故X-1次询问即可找到宝藏。

定义F[i]以I为根的子树中可能溢出的标号集合：

{x|x∈T(i)，no y∈Path(x to I) and c[y]>c[x]}

贪心：自底向上，每个点选择可以标的最小的标号，使得不与任意子树中溢出集合的标号相同，且不小于任意存在于两棵子树的溢出集合的标号。

证明：

1. 对于子树i，将其溢出集合看做二进制数，那么F[i]越小则子树i的答案更小。

2. 对于子树i，在其所有子树j的F值已确定时，i选择最小可行标号可以使F[i]尽量小。

3. 对于j∈子树i，j不选择最小可行标号，无法使得F[i]变小。

运用位运算可以优化到O(n)。

prz 搜索 or 状态压缩动态规划

状态压缩动态规划可以解决，但需要很多很多优化才能到达很一般的效果，譬如按T排序，利用搜索求出决策，将决策排序，最优性剪枝，预处理优化常数等等。

不同搜索策略效果也会有极大的差异，比较容易想的是按T从大到小排序，每次选出尽量多的人让他们一起过桥。这个方法也要很多优化，譬如二分枚举答案，最优性剪枝，Hash判重，特殊处理MaxT等等。

Dp的缺陷在于枚举了所有的状态而无法中途剪枝，DFS的缺陷在于搜索重复量极大，而且最优性剪枝只有在最后几步才能发挥作用。最简洁而且优秀的算法如下：

对于每个人，枚举将他加入现有的未满的一批人，或新增一批人，加上最优化剪枝全部数据闪解。

这也给这类划分集合的搜索题目提供了一种新思路。

结论1：出度最多的人x必然可以获胜。

证明：若x不能获胜，则必然存在y使得x无法打败，即y能打败x以及x能直接打败的所有人，那么d(y)至少为d(x)+1，矛盾，故原结论成立。

结论2：若x可获胜，那么x不能直接打败的人y均可获胜。

证明：x比赛时的流程为一棵以x为根的外向树，我们删除y与其父亲间的边，并进行比赛y胜x，那么构成了以y为根的外向树，故y也能获胜。

结论3：若所有能获胜的人x均可直接打败y，那么y无法获胜。

证明：若y能获胜，那么必然存在某个不能获胜的人z使得y可以打败z(间接或直接)，且z能直接打败x，这与结论2矛盾，故y无法获胜。

根据以上结论，我们可以得出算法：

初始将出度最多的人加入可获胜集合，不停的利用结论2扩展可获胜集合，直至不能扩展时即得到答案。具体tur 构造+调整+链 实现时可以将不确定集合挂成链，容易证明

∑每次遍历的链的长度=|可获胜集合|+|E|

故时间复杂度为O(n+m)

zga 概率 对于第i次猜测，设aL

该策略能胜利30700次左右（可惜0分），标准算法中与该方法类似，只不过有个诡异无比的常量数组。

等价于求平面上被最多多边形覆盖的点，利用事件点思想，对于所有平行于x轴的边(x1,x2,y)，将它们按y从小到大扫描，若x1

Ans=max(覆盖某区间的线段条数)

以N为根做DFS，找到第一个子树中包含所有1-W的点K，以K为根做DFS求出每个点到K的距离d[i]。

设需要运送货物的节点为{x1,x2……,xp}

结论1：若dx互不相等，则它们离开K的时间为dxi。

证明：每天，每个货物向K靠近一步，那么它们深度仍然不相等，故离开K之前x不会相遇，所以每个货物都不需要停留，证毕。

若存在dx相等，则按深度从小到大，每个深度保留一个，其余的等待一天（移至下一深度处理）。

容易证明该贪心是可行且最优的。

结论2：货物在离开K前往目的地的路上不会相遇。

证明：类似结论1的证明。

所以我们只需在中选出深度较小的p个，和p个货物离开K的时间反序配对求最大值即可。

因为d∈[0,n)，故使用基数排序时间复杂度为O(n)。

……

设该置换为x个循环的积，第i个循环长度为li，那么K=lcm(l1,l2……lx)，这点由循环性质可得。

结论1：li为素数的正整数次幂。

证明：若li=x*y(x,y为素数的正整数次幂)，那么将li拆成x,y,li-x-y三个循环，lcm(x,y,li-x-y)>=x*y，即不会变差，证毕。

结论2：素数不会超过350。

证明:∑p{p<=350,p∈素数}>=maxn。

用F[i,j]表示用前i个素数的整数次幂做背包可以得到的最大积。

F[i,j]=First max(F[i-1,j-pi^k]*pi^k)。

因为只要求解而不要最优值，故可以另开数组G记录决策，将F[i,j]转为对应ln值以简化计算。

求出F后，用G求出使K最大的{L}，将L从小到大排序，按照样例的方法即可构造出字典序最小的解。

wys 线段树

wsc 贪心+树的遍历

mis

mak

博弈

循环+数论+动态规划 kag 图论+链 结论1：一个图为C图当且仅当它或它的补图不连通，且每个连通块是C图。

证明：第一种操作得到的C图是不联通的，第二种操作得到的C图的补图是不联通的。

结论2：若一个图与它的补图均连通，则不是C图。

证明：由结论1可得。

结论3：一个图与它的补图至少有一个连通。

证明：若原图不连通，则在补图中处于不同连通块的任意两点均有边，显然补图连通。反之类似。

故我们对于一个图，判断它与它的子图的连通性，若有一个不连通，则递归判断每个连通块是否为C图。

优化1：if |V|<=2 then check = true

优化2：对于补图连通性判断，我们将点挂成一条链，扩展i时，我们在链中找与i无边的点，将它们加入队列。

易证：∑每次遍历的链的长度=|连通块|+|E|

优化3：若某次判断中，发现其补图不连通，则递归判断连通块时只需判断其原图连通性。反之类似。

优化4：若某次判断中，发现其补图不连通，则删除连通块之间的边。

时间复杂度为O(nm)，应该仍有优化余地。