专栏文章

2025NOI省选训练

wwangzihan_
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8zh0a
此快照首次捕获于
2025/12/03 08:07
3 个月前
此快照最后确认于
2025/12/03 08:07
3 个月前
查看原文

DAY 1

AT_arc070_d [ARC070F] HonestOrUnkind

询问次数为 2n2n，考虑 O(n)O(n) 找到一个诚实的人，再用 O(n−1)O(n-1) 询问其他人。
  1. 发现如果诚实的人<=<=不诚实的人数量，无解。
  2. 如果询问结果是 NN，则说明这两个人必有一个是撒谎的人。
  3. 如果询问结果为 YY，则两个可能都是真，都是假，或一真一假。
因为现在保证了诚实的人数量大于不诚实的人的数量，所以考虑用一个队列维护现在询问过的人，用队列中最靠后的去询问未被询问的人。如果输出 NN，则删除这两个，否则就加入。这样就保证了队列中的诚实的人数量比不诚实的人的数量多，最后队列中一定会剩下一个诚实的人。所以就做完了。

P11050 [IOI 2024] 消息篡改者（暂无法评测）

太困了没听懂

神秘题目

经典猜数，询问范围，返回 Yes/NoYes/No ，但是交互库有可能返回仅一次错误答案。
1<=x<=1e181<=x<=1e18 询问次数<=70<=70就满分。

部分分一

每次询问两遍，发现不一样后，后面直接二分，可以通过 y<=120y<=120 的数据。

部分分二

每询问 88 次 CheckCheck 一次是否被骗，如果是，后续直接二分，否则继续。
为什么是 88 次呢？我也不知道，可能要通过计算吧？

猜想

询问时取中点可能不是最优，还需要DP。
dp[i][j]=max(dp[x/2][x2/2],dp[x/2][2/x2+y]+1)dp[i][j]=max(dp[x/2][x2/2],dp[x/2][2/x2+y]+1)
x<=213x<=2^13 次方时候可以跑的比方法二快，大了后就g了。

老鼠进洞

题面

一个大小为 xx 的环上有 nn 只老鼠和 mm 个洞，每个洞最多容纳一只老鼠，求 22 个问：所有老鼠都进洞的最小总距离和方案数。
x<=1e9,n<=m<=2e5x<=1e9,n<=m<=2e5

弱化版

先考虑在一个数轴上，然后 DPDP
上面是i代表老鼠，下面是i代表洞

正解

断环为链，费用流

老鼠进洞again

树上，老鼠最多只能走 dd 步，每一个深度为奇数的点上有老鼠，深度为偶数的点上有一个洞。求最多能让多少只老鼠进洞。
类似题面

方法一

反悔贪心+模拟费用流。。。虽然我不会。。。
给每个老鼠和洞排序，先往左匹配，老鼠i进洞j，然后推了个费用流式子。

方法二

DP

打怪

有 nn 只怪物，第 i 只怪物的攻击力为 A[i]A[i]，血量为 H[i]H[i] 现在你需要生产机器人来打败这些怪物，具体地，你可以生产 m(m>0)m(m > 0) 个机器人， 第 j 个机器人的攻击力为 B[j]B[j]，血量为 L[j]L[j]。生产完之后，你可以让机器人和怪物战 斗，战斗规则如下： 每一步，你挑选一个机器人 jj，并选择一个怪物 ii 作为对手，接下来两个人会开启战 斗，战斗一轮一轮进行，每一轮，双方会同时发起攻击，令 H[i]−=B[j]H[i]− = B[j]，同时 L[j]−=A[i]L[j]− = A[i]。如果这一轮结束双方血量仍然 > 0 则继续下一轮。直到有一方血量 ≤0≤ 0 则当前轮结束，血量 ≤0≤ 0 的机器人或怪物出局，血量 >0> 0 的可继续参与后续战 斗。 现在你可以决定机器人的数量 mm、每个机器人的 B[j],L[j]B[j], L[j]，同时决定战斗策略（你 可以任意安排你的机器人和怪物的战斗顺序）。你的目标是不败（即不能出现机器人 全部出局但怪物还有剩余的情况）。平局是可以接受的（即最后一个机器人和怪物同 时出局） 生产机器人的代价为 ∑mj=1(B[j]+L[j])∑m j=1(B[j] + L[j])，你的任务是在保证不败的前提下，让代价 最小。 nn, A[i],H[i]≤105A[i], H[i] ≤ 105

做法

关键性质：不会有两个机器人都用来打超过一个怪物 这样，我们可以枚举这个机器人的攻击力

打怪2

一个 RPGRPG 采用回合战斗，怪物只有一种，但是个数无限多，小 XX 初始攻击力为 11， 防御力为 00. 小 XX 的生命也是足够多。每消灭一次怪物，小 XX 可以得到一个金币，这个金币可 以增加 11 攻击或 11 防御， 回合规则如下：小 XX 攻击一次怪物，然后怪物攻击小 XX，伤害为对方的攻击减去己 方的防御，如果这个值小于零，则不造成伤害。当怪物生命为 00 时，战斗结束。 小 XX 总有一个时候会变得无敌，但是小 XX 想知道在变无敌之前至少承受多少伤害。 怪物攻击力为 nn，生命值为 k，n,k≤1013k，n, k ≤ 1013

做法

贪心策略：一定是先加攻击再加防御
Proof. 假定有一种策略中间存在加了若干次防御后加了攻击，并且这个策略优于整体先加 攻击再加防御的策略，则分为以下三种情况 这若干次攻击没有加到下一个临界点，这将导致这些攻击没有任何作用，显然 成立 这些次攻击保证在加最后一次的时候改变了临界点 设加攻击前被对方攻击的次数为 aa，加攻击后被对方攻击的次数为 bb，加攻击为 mm 次，设这些次防御一次减少伤害的比例为 cc，总共加了防御 mm 次，显然 a>ba > b, 则有 以下情况 B/a>1−m∗cB/a > 1 − m * c 这种情况下说明攻击带来的影响更大，但又可以看出影响大的 放到前面具有更大的优势，减少的伤害相对更多 B/a<1−m∗cB/a < 1 − m*c 这种情况下防御影响的更大，这样将攻击改成防御具有更大的 优势
再使用数论分块，找到何时更改到加防御

打怪3

现在有 nn 种圣物，其中第 ii 个圣物的价格为 cic_i 碎片。你想把这 nn 种圣物全买一遍， 其中有两种购买方式： 花费 cic_i 碎片购买第 ii 种圣物。 花费 xx 碎片进行抽奖，可以等概率随机获得这 nn 种圣物中的一种，如果获得了 已经获得过的圣物，则会还给你 2x2 x 碎片。 现在求最优策略下，得到这 nn 种圣物的最小期望花费。
n≤100,x<=cn ≤ 100,x<=c

solve

先抽再买
证明：首先购买一定是买当前 cic_i 最小的圣物。考虑相邻两次操作，如果先购买再抽 奖，注意到本题的随机规则和决策是无关的，那么我们可以当成，在游戏开始之前， 每次抽的结果就已经确定了 那么分情况讨论：
  1. 如果下一次抽奖抽到的就是 cic_i 最小值，则如果先买再抽，我们就白买了
  2. 如果下一次抽奖抽到的不是 cic_i 最小值，则交换两次操作不影响结果
根据结论就可以 DPDP 了
dp[i][j]dp[i][j] 表示抽了 ii 张卡，cc 之和为 jj 的概率，对 cc 跑01背包。
假设当前已经拥有了 ii 种，已经拥有的 cc 之和为 jj，假设如果选择抽，抽中的下一个圣物是 kk，那如果选择买，也买 kk。比较两个平均值的大小，算期望。

染色

nn 个点的树，每个点染一个 [1,m][1, m] 的颜色，求 mina,b∈[1,n],a≠b,col[a]=col[b](dis(a,b))=kmin_{a,b\in[1,n],a \neq b,col[a]=col[b]}(dis(a,b))=k 的方案数。 n,m≤2×105n, m ≤ 2 × 10^5

练习题

给定一棵 nn 个点的树，接下来有 mm 次操作 每次操作添加一条路径或者删除一条之前添加的路径 定义点到路径的距离为到路径最近的点的距离，定义 f(xf(x) 为 xx 到当前所有路径的距 离的最大值
每次操作之后，你需要回答 mini=1nf(i)min^n_{i=1}f(i)
n,q≤2×105n, q ≤ 2 × 105

性质

两个最远路径的距离的和的一半，但是不好维护。
考虑一个路径集合
  1. 如果这个集合有公共交集，则，f(x)=xf(x) = x 到交集的最短距离，可以直接维护交集 （实现时也可以找到集合中两条交最小的路径，使得两条路径的交恰好是所有路 径的交）
  2. 如果这个集合没有公共交集，则直接维护最远的两条路径的距离，跟直径一样 的合并方式

DAY 2

T1

对于一个字符串 SS，定义 root(S)root(S) 表示 SS 的最小整周期，R(S)=∣S∣/∣root(S)∣R(S) = |S|/ |root(S)| 即最小整 周期出现次数。 定义 S[l,⋅⋅⋅,r]S[l, · · · , r] 表示 S 字符串第 l 个字符到第 r 个字符所构成的子串。 定义 f(S)f(S) 表示 maxl≤rR(S[l,⋅⋅⋅,r])maxl≤r R(S[l, · · · , r])，即 SS 的子串中最大的 RR。 给定一个长度为 n 的字符串 S，你需要找一个最大的子串 S[L,⋅⋅⋅,R]S[L, · · · , R]，使其具有 最大的 RR，若存在多个，输出字典序最小的。 接下来给出 mm 个询问，每次询问给定两个整数 l,r(1≤l≤r≤n)l, r(1 ≤ l ≤ r ≤ n)，你需要输出 f(S[l,⋅⋅⋅,r])f(S[l, · · · , r])。

solve

T2

给定 n×mn × m 的矩阵 AA，你需要构造 n×mn × m 的 0101 矩阵 BB，满足： •∀i∈[1,n],j∈[1,m]• ∀i ∈ [1, n], j ∈ [1, m]，若 Bi,jBi,j 为 11，则 Bi,j−1Bi,j−1, Bi,j+1,Bi−1,j,Bi+1,jBi,j+1, Bi−1,j , Bi+1,j 均为 00。 •∀i∈[1,n],j∈[1,m]• ∀i ∈ [1, n], j ∈ [1, m] 满足 i+ji + j 为奇数，若 Bi,jBi,j 为 11，则 Bi−1,j−1,Bi+1,j+1Bi−1,j−1, Bi+1,j+1 均为 00。 •∀i∈[1,n],j∈[1,m]• ∀i ∈ [1, n], j ∈ [1, m] 满足 i+ji + j 为偶数，若 Bi,jBi,j 为 11，则 Bi−1,j+1,Bi+1,j−1Bi−1,j+1, Bi+1,j−1 均为 00。 对于 i∈/[1,n]i ∈/ [1, n] 或 j∈/[1,m]j ∈/ [1, m]，我们钦定 Bi,j=0。Bi,j = 0。 你需要最大化 ∑Bi,j×Ai,j∑Bi,j × Ai,j。

solve

T3

暑假来了，小 δδ 想要吃冰棒。 小 δδ 知道 nn 家售卖冰棒的商店，它们被依次编号为 00 到 (n−1)(n − 1)。这些商店的老板都十分任性——他们每天售卖的冰棒口味并不相同。小 δδ 只喜欢西瓜味的冰棒，因此他早就做好了调查。小 δδ 的调查结果形如 nn 个有理数序列，其中第 ii 个序列的长度为 lili，且它的第 jj 项记作 pi,jpi,j。为了方便起见，我们给出的值为 pp′i,ji,j，它是 pi,jpi,j 对 998244353998244353 取模的结果，可以说明在本题限制下这不会影响求解的过程。此外，i,ji, j 均从 00 开始标号。小 δδ 的暑假长达 2025!2025! 天。对于商店 ii，在第 tt 天，它售卖西瓜味冰棒的几率为pi,(tmodli)pi,(t mod li)。小 δδ 每天都会前往所有商店购买冰棒，如果其中至少一个商店售卖西瓜味冰棒，小 δδ 就会开心。现在，小 δδ 想要知道：他开心的日子占整个暑假的比例的期望是多少？为了方便你的计算，他只需要你告诉他这个答案对 998244353998244353 取模的结果就好了。

solve

AT_agc039_f [AGC039F] Min Product Sum

∏∏相当不好处理，我们考虑如何转化？ 直接考虑它的组合意义，那么变成了计算两个矩形 (A,B)(A, B) 的数量满足 BB 中的每一个元素都小于 AA 中对应行 // 列最小值的方案数。再转化一下，发现这个条件等价于计算两个矩形 (A,B)(A, B) 的数量满足
  1. BB 中每一行的最大值 ≤A≤ A 中对应行的最小值。
  2. BB 中每一列的最大值 ≤A≤ A 中对应列的最小值。
那么这个东西看起来就比较能 dpdp 了，我们容易想到从小到大扫 值域，那么对于 A,BA, B 一个位置的限定我们希望独立开来。 也就是发现你在一个矩形中又确定行又确定列并不好处理。
所以考虑 dpdp 状态设计成 fk,i,jfk,i,j 表示当前矩形填了 ≤k≤ k 的数，确定了 BB 中 ii 行的最大值，AA 中jj 列的最小值的方案数。转移考虑 k+1k + 1 这些元素填在什么地方，分两步确定一些 BB 中的行的最大值为 k+1k + 1。AA 中对应行已确定列的位置填 ≥k+1≥ k + 1。BB 中对应行未确定列的位置填 ≤k+1≤ k + 1（一定有一个 k+1k + 1）。确定一些 A 中的列的最小值为 k+1k + 1。AA 中对应列已确定行的位置填 ≥k+1≥ k + 1（一定有一个 k+1k + 1）。BB 中对应列未确定行的位置填 ≤k+1≤ k + 1。容易发现这样的 dp 使得每个位置都能取到最严格的限制，于是分两步转移即可（在后面再 加一维）。这样就做完了，时间复杂度 O(Knm(n+m))O(Knm(n + m))。

AT_agc057_e [AGC057E] RowCol/ColRow Sort

第二题我不配

CF908H New Year and Boolean Bridges

CF1916H2 Matrix Rank (Hard Version)

P11983

P11988

QOJ9984

CF1863I

Day 3

T1

对于一个长为 lenlen 的，取值范围为 [1,m][1, m] 的序列 SS，称一个长度为 mm 的，取值范围为[1,m][1, m] 的序列 TT 是好的，当且仅当对于所有 i∈[1,len]i ∈ [1, len]，都满足 TSi=Slen+1−iT_{Si} = S_{len+1-i}。f(S)f(S) 表示有多少个好的序列。给出一个长为 nn 的串 AA，再给出值域 mm，要你求出 AA 的所有非空子串的 ff 之和，即 ∑i=1n∑j=inf(A[i,j])∑^n_{i=1}∑^n_{j=i}f(A[i, j])。对 998244353998244353 取模

T2

solve

T3

solve

太臭了，一共29页的题解，感觉以现在的实力不足以听懂

CF1685E The Ultimate LIS Problem

AT_arc169_e [ARC169E] Avoid Boring Matches

P10219 [省选联考 2024] 虫洞

qoj 7765

P9531 [JOISC 2022] 复兴计划

首先我们可以感性理解一下，一条边 i 能存在的对应 X 是一段区间 [li,ri][li, ri]，如果我们能对于每条边 i 求出对应区间，那么问题就容易解决。
我们把边权按 w 从小到大排序，然后考虑每次加入第 i 条边。如果连接的两个端点不连通，那么直接加入这一条边。
如果连接的两个端点联通了，那么找到环上 ww 最小的边，设其为 jj，那么我们就知道，如果 X>wi+wj2X > wi+wj_2 ，那么我们会选择 ii，否则选择 jj，所以 Rj=wi+wj2R_j =w_i+w_{j2}, Li=wi+wj2+1L_i =w_i+w_j 2 + 1。
然后我们可以 LCTLCT 维护，或者直接 O(n)O(n) 计算。 另外一个更好写的做法是直接并查集维护，可以做到 O(nmα(n))O(nmα(n))。 具体的，每次计算 ii 的时候，让 jj 从 i−1i − 1 到 11 循环，每次用并查集合并 uj,vju_j , v_j 所在连通块， 我们只需要找到连了哪个 jj 之后 ii 的两端联通，然后就可以 breakbreak 掉，每次暴力遍历 jj，遍 历次数可以证明也是 O(nm)O(nm) 的。 我们把问题转化成我们有 mm 条边，对于 ii 定义 f(i)f(i) 表示最大的 xx 使得 ex∼ei−1ex ∼ ei−1 能联通 eiei 的两个端点，如果不存在则 f(i)=1f(i) = 1，那么 ∑i−f(i)∑i − f(i) 最大是多少。
我们把编号看成边权，那么我们每次从 T(i−1)T(i − 1) 变成 T(i)T(i) 的时候，就是添加 eie_i 的时候删除 了 ef(i)e_{f(i)}，如果一开始图被权值为 11 的边联通，那么我们每次相当于加入权值为 ii 的边，删除 权值为 ∑f(i)∑ f(i) 的边，设 A(i)A(i) 为 T(i)T(i) 的边权和，那么我们计算的就是 A(i)−A(i−1)=A(m)−A(1)A(i) − A(i − 1) = A(m) − A(1)，由于 A(m)=O(nm)A(m) = O(nm) 的，所以上面我们总遍历次数也是 O(nm)O(nm) 的。

AT_arc138_f [ARC138F] KD Tree

首先直接枚举操作的分界显然会算重，那么由于一种序列有多种操作方式，一般来说我们就 有两种想法：找到序列能被得到的条件，然后对着条件 dpdp。 只考虑字典序最小的一个解，这样保证不重。 这个题我们采用第二种方法。
我们设计 dpdp 状态，设 fl,r,u,dfl,r,u,d 表示考虑 S=i∣l≤i≤r,u≤pi≤dS = i|l ≤ i ≤ r, u ≤ pi ≤ d 的点集的划分数量。然后现在的问题是我们怎样定义字典序最小。我们考虑计算给点集内点的 xx，yy 坐标排序之后交替合并起来，形如 x1,y1,x2,y2...x1, y1, x2, y2 . . .。然后我们考虑按这个顺序划分，只计算用当前划分能达到且之前划分无法达到的状态，即当前划分作为第一个划分能到达的状态数量。

uoj75

P6816 [PA 2009] Quasi-template

Day 4

T1

有 nn 个人排成一列，每个人有一个能力值 aiai 。 老师将会举行 mm 次考试，第 i 次考试将只有 [li,ri][li , ri ] 内的人参加。 每次考试中，对于 [li,ri][li , ri ] 中的任两个人 x,yx, y , 若 ax>ay×2ax > ay × 2 , 则 xx 会给 yy 带来 ax⊕ayax ⊕ ay 的自卑值, 其中 ⊕⊕ 表示异或。 该次考试产生的自卑值为其中所有人产生的所有自卑值之和。 求每次考试产生的自卑值。

solve

测试点1/2

略

测试点3~5

使用莫队并使用朴素的数据结构来维护。
也许用分块也可以。

测试点6~10

以下视 n,mn,m 同阶。
莫队二次离线。
注意到这种莫队每次移动指针时都要进行一个查询，形如求
∑l≤i≤r,ai>x×2 or ai≤⌊n+12⌋−1ai⊕x\sum_{l\le i\le r,a_i>x\times 2\space or \space a_i\le\lfloor\frac{n+1}2\rfloor-1} a_i\oplus x
注意到 l≤i≤rl\le i\le r 这个限制是可以拆成两个前缀相减的，而拆完之后这个维度的限制是简单的，可以通过离线扫描线的方式去掉这一维限制。剩下的部分就是 O(n)O(n) 个单点修改， O(nn)O(n\sqrt n) 个区间查询，可以使用值域分块平衡复杂度做到总复杂度 O(nn)O(n\sqrt n) 。
注意这里空间限制比较紧，所以不能直接离线，需要对信息进行一定程度的压缩。

T2

给你一个正整数序列 a1,a2,,ana1, a2, , an 。设 S=n+AiS = n + Ai . 有 SS 张卡片。每张卡片上都写有一个整数。卡片上的整数是 a1,a2,⋅⋅⋅an,−1,⋅⋅⋅−1a1, a2, · · · an, −1, · · · − 1 。 其中，有 ∑ai∑ai 张卡片上写着 −1−1 。 NITNIT 现在站在数线上的坐标 00 处。他将执行以下操作 SS 次。 假设 xx 是 NITNIT 的当前坐标。选择并丢弃他手中的一张牌。设 vv 为弃牌上的数字，并 跳转到坐标 x+vx + v 。如果他跳到了坐标 00 ，则获得一枚硬币。 对于每一个 k=1,2,3⋅⋅⋅,nk = 1, 2, 3 · · · , n ，求 NITNIT 的下棋顺序中使得他恰好赚到 kk 枚硬币模数为 998244353998244353 的个数。 您应该计算走棋顺序。也就是说，如果两张牌的数字相同，弃掉其中一张与弃掉另一 张是没有区别的。

solve

首先你可以把相同的 aia_i 看成不同的，最后除以系数即可。
金典恰好转钦定，求出情定恰好 kk 次的方案然后二项式反演回去即可，设其为 anskans_k。
考虑对于每部分出现的是 a1,a2,⋯ama_1,a_2,\cdots a_m，那么有 ∑a\sum a 个 −1-1，那么总方案为 ∏i=1m(∑a+i)\displaystyle\prod_{i=1}^{m} (\sum a+i)，考虑组合意义拆一下，对于每个 aia_i 从同一部分选一个 aja_j，连边，边权为 aj+[j≤i]a_j+[j\le i]，求所有方案边权乘积的和。
那么连边连出来会是一个基环树森林，设形成 kk 个连通块的方案为 fkf_k，那么有 ansi=∑jfjS2(j,i)ans_i=\sum_j f_jS_2(j,i)，S2S_2 为第二类斯特林数。
基环树有环有树，再钦定若干个环，其他点乱连的方案。
观察换上的边 i→j:aj+[j≤i]=(aj+1)−(j>i)i\to j:a_j+[j\le i]=(a_j+1)-(j>i)，考察其组合意义：选取一部分点为 aj+1a_j+1，一部分点取 −1-1，即选取若干条下标上升的链，链头取到 aj+1a_j+1，其余点取到 −1-1，求所有方案的和。
考虑 dp，设 dpi,jdp_{i,j} 表示前 ii 个点构成了 jj 条链的方案和，最终把这些链拼成环，再乘以第一类斯特林数即可。
dpi,j=dpi−1，j−1(ai+1)+dpi−1,j(∑a+i+(−1)×j)dp_{i,j}=dp_{i-1，j-1}(a_i+1)+dp_{i-1,j}(\sum a+i+(-1)\times j)
转移分别代表选链头，环外，链尾，复杂度 O(n2)O(n^2)。

T3

这是一道交互题。 交互库会给出一个 nn 个点 mm 条边的有向无环图，你可以更改 kk 次边（添加/删除），不 需要保证你操作完成后的图还是一个有向无环图。 然后交互库会询问你 qq 次，每次交互库选定一个点 xx，你可以给出一个可重集 SS，交 互库会将 xx 加入 SS ，然后在 SS 中的点上放置棋子（个数是其在 SS 中的出现次数），再让 红磷和白磷开始一轮游戏，并告诉你游戏结果：先手胜利/后手胜利/平局（即会进行无限 久）。 你需要回答交互库。

solve

这道题的 交互库 需要你会 有向有环图的公平博弈游戏。
我问了 GPT/ds 后，它们都给出了一个看起来很对的东西，然后和暴力根本拍不起来...
还好 GPT 给出了一篇论文链接 Extended Sprague-Grundy theory for locally nite games, and applications to random game-trees。
然后模拟论文的式子，就获得了 O(nm)\mathcal{O}(nm) 的一个做法，根据 原题作者的说法，这个是可以优化到 O(mm)\mathcal O(m\sqrt m) 的。

性质 A ∨n≤20\lor n \le 20

发现是一个完全图，又保证了是一个 DAG，考虑此时 SG 函数是两两不同的，每次就枚举一下点，就可以确定 xx 了。

正解

构造大神

设一个棋子局面有三种状态 W(Win)/L(Lose)/D(Draw)
首先发现如果还是 DAG，一定做不了。
考虑利用环的性质，此时用上最特殊的自环，因为如果自环上有棋子，则一定不是 L 态，因为此时先手一定有一个 L 态后继（但可能是 W 态）。
把图分成两个点集 S1,S2S_1, S_2，对于 S1S_1，我们用性质 A 的方法补全成 SG 两两不同的，对于 S2S_2 给每个点连一个自环。
每次询问集合 SS 内只有一个点 ii。
  • 如果 x∈S1x\in S_1：对 S1S_1 的每个点询问就行了。
  • 如果 x∈S2x\in S_2：
    • 如果是 W 态，则先手需要将棋子移到 L 态，则 ii 在 xx 的后继中。
    • 如果是 D 态，此时不管先手怎么移动，都会到 W 态，所以他一定让 xx 在自环上移动。
所以你将 S1S_1 中连成完全 DAG，去掉 S1→S2S_1\to S_2 的边，让 S2S_2 中的点在 S1S_1 的后继集合两两不同，就可以每次询问 S1S_1 中的点获得答案。
理论 n≤qlim+2qlimn\le qlim+2^{qlim}。

Smith Value

根据论文中的理论：
定义 γ(u)\gamma(u) 表示 uu 点上的 exSG， γ(u)∈N∪∞(2N)\gamma (u)\in \mathbb N\cup \infty(2^\mathbb N)
转移就是 ：m=mex{γ(u)∣γ(u)∈N}m=\text{mex}\{\gamma(u)|\gamma(u)\in \mathbb N\} γ(u)={m,∀(u,v)∈E,γ(v)∈N∨(∃(v,w)∈E,γ(w)=m)∞({γ(u)∣γ(u)∈N}),Otherwise\gamma(u)=\begin{cases}m&,\forall (u,v)\in E, {\gamma(v)\in \mathbb N\lor (\exists(v,w)\in E, \gamma(w)=m)}\\\\\infty(\{\gamma(u)|\gamma(u)\in \mathbb N\}) &,\text{Otherwise}\end{cases}
多个独立游戏的 exSG 合并是： {γ(x)⊕γ(y),γ(x),γ(y)∈N∞({v⊕γ(y)∣v∈γ(x)}),γ(x)∉N∧γ(y)∈N∞(∅),γ(x),γ(y)∉N\begin{cases}\gamma(x)\oplus\gamma(y)&, \gamma(x),\gamma(y)\in \mathbb N \\ \infty(\{v\oplus \gamma(y)|v\in \gamma(x)\}) &,\gamma(x)\not\in\mathbb N\land\gamma(y)\in \mathbb N\\\infty(\emptyset)&, \gamma(x),\gamma(y)\not\in \mathbb N\end{cases}
胜负判断：
  • 如果 γ∈N\gamma \in \mathbb N
    • 如果 γ>0\gamma > 0，先手必胜
    • 如果 γ=0\gamma = 0，后手必胜
  • 如果 γ=∞(S)∈∞(2N)\gamma = \infty(S) \in \infty(2^\mathbb N)
    • 如果 0∈S0\in S，先手必胜
    • 如果 0∉S0\not\in S，平局
通过分析 exSG 的性质，也可以得出上面的方法。

CF1270I Xor on Figures

CF526G Spiders Evil Plan

CF1874F Jellyfish and OEIS

CF1874D Jellyfish and Miku

QQJ2064

AT_agc017_f [AGC017F] Zigzag

Day 5

面基滴叉！！！！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...