over 1 year ago

NOIP滚粗...
NOI滚粗...
WC滚粗...

今年还有ZJOI CTSC APIO.. 以及..NOI 感觉压力好大啊..

以下是滚粗狗的自我修养。



  • SRM 600 div1 hard LotsOfLines

假设原来已经有了一些直线,新加入一条直线之后新产生的区域个数等于[这条直线与之前直线产生的交点个数 + 1]

可以按照a的大小一条一条加入直线, 只有 c < a 的直线才会产生交点, 由于b, d不同,所以c = a的直线与y = ax + b不会产生交点。

y = ax + b可能与多条直线交于同一点,应该去掉这种情况.. 把x表示成最简分数.. 即只计算gcd(d - b, a - c) = 1的解。

d - b 的取值范围是[-b, B - b - 1], a - c的取值范围是[1, a]。

预处理出每个范围内解的个数,然后枚举a, b进行统计即可。


  • SRM 601 div1 hard WinterAndShopping

假设没有第二条限制,那么每家店的方案互不干扰

有第二天限制的话,就只能dp, f[i][r0][g0][r1][g1]来储存第i天正在营业的店铺的状态。
考虑简化这个状态,因为一天最多只有两家店同时营业,对于同时开始营业的两家店,刚开始,营业天数较长的那家店肯定要满足营业天数较短的那家店的要求, 也就是第一家店的三种颜色的球都不能少于第二家店三种颜色的球,那么就可以直接跳过第二家店的营业时间,方案数用上面的组合数计算就好了。第一家店三种颜色的球数量都减去对应的值。这样我们就只要记录第一家店的状态即可。


  • SRM 602 div1 hard BlackBoxDiv1

好神的题目,找找规律。
先坑着..


  • SRM 603 div1 hard SumOfArrays

无脑分块FFT... 注意块的大小


  • *SRM 608 div1 hard OneDimensionalRobo *

枚举L, 用个线段树/链表维护当前超出限制的位置,然后依次修改直到每个位置都合法


  • SRM 609 div1 hard LotteryTree

假设整个概率区间是一个[0,1]的区间,那么由于每个人的概率要相同,所以最后摆出来的树,叶子节点要能表示出[0, 1/p],[1/p,2/p] ... [(p - 1)/p, 1],参考下图:

每一个点的概率都是能计算出来的,考虑dp, dp[i][j][k]表示能否把i这个子树插进j/k开始的一段。由于第i个点每一个孩子的概率区间都是一样长的, 假设i有g个孩子,就可以把j/k开始的一段分成g小段,每个孩子都可能放到这g段中的一段。算出每个孩子放到每个段是否可行,接下来跑二分图匹配就好了。
处理一些比较trivial的情况,再记忆化,就能秒出啦。

WARNING
要注意treedp递归的时候全局变量被修改的问题


  • SRM 610 div1 hard MiningGoldHard

显然x和y坐标互相独立,可以分开解决。
dp[i][j]表示第i天位置是j的情况下最大收益,这个dp是O(nk)的,发现这个dp是个凸函数且dp转移只有两种,一种是对于周围d的位置取max,第二种是每个位置i, dp[i]加上|i - e|, 这两个操作都不会改变函数的凸性。就可以去维护这个凸函数,记录转折点的坐标,每次操作最多只会增加O(1)个转折点,因此总的复杂度是O(k^2).


  • SRM 611 div1 hard ElephantDrinking

原本以为是费用流什么的,结果是码农dp.
dp[x0][y0][x1][y1]代表一个子矩形的最大收益
有三种情况:

Case 0: 当前矩阵为一长条,如图所示,中间那种情况。


这种情况只要一列一列(一行一行)取出最大的和次大的就行了。

Case 1: 不存在两条x方向象鼻的长度和超过(x1 - x0)或不存在两条y方向象鼻的长度和超过(y1 - y0)
枚举最长的一条象鼻在哪里,把它给取了,然后递归下去做。

Case 2: 存在两条象鼻的长度和超过(x1 - x0)且存在y方向象鼻的长度和超过(y1 - y0)
这种情况只有可能发生在第一步决策的时候,因为后面递归下去的时候,就会把图给切开,不可能发生这种情况了。
枚举四个个方向(加上y方向)最长象鼻的长度,然后递归下去。


  • SRM 612 div1 hard LeftAndRightHandedDiv1

显然最优解是所有L都连续,所有R也连续。
那么只要考虑所有R都连续即可。
如果不是环,那么最终连续的R的起点一定是在所有R中最中间的那个位置,可以用经典的绝对值求和那套理论来证明。
由于是环,就枚举每个位置,假设它是中点,用前缀和计算即可。


  • SRM 682 div1 easy SmilesTheFriendshipUnicorn

吉丽提供了一个挺好的做法,随机一个拓扑序,然后把每条边按照这个拓扑序定向,这样就得到了一个DAG, 求这个DAG的最长链,看看是不是大于等于4. 原图中一条长度为4的链在一次随机的DAG中出现的概率为1/60, 这样随机比方说1000次找到它的概率就几乎是1了。


  • SRM 682 div1 medium SuccessfulMerger

先把所有叶子节点找出来,这些点连出去的边显然不用缩,然后如果环上有些点没有子树,那么就可以把环缩成一个二元环,不然就缩成一个点。


  • SRM 682 div1 hard TheKFactor

这题要用到Minimax定理,这个定理就是,对于一个两个人玩的,有限的零和博弈,存在对于双方来说都最优的混合策略,这个解正好就是这个博弈的纳什均衡。

通过Minimax定理的转化.. 假设对手的策略为a[0..n-1], Bob知道对手策略之后的最大收益,假设为b。 那么:

Minimize $$b$$
S.T.
$$\sum a_i=1$$
$$a_0+\dots+a_i\leq i/n$$
$$a_i\geq 0$$
$$b \geq a_0v_0+\dots+a_iv_i+a_{i+1}v_i+\dots+a_{n-1}v_i$$

用单纯形去算它就好了。

WARNING
初始化的时候,加入一个变量x0, 去最大化-x0, 注意要在最终的simplex的时候始终保持x0 = 0, 不然的到的解就不一定合法了。具体实现可以是这样的

REP(i, 0, m) swap(a[0][i], a[n + 1][i]);
++n;
return -simplex();

  • SRM 613 div1 hard TaroCheckers

一列一列地去dp
假设没有左边的限制,只要记录一下当前已经被填过行数就可以了。
假设没有右边的限制,每一列决策的时候,先不要分配具体放到哪一行,而是到某些行左端限制结束的时候再进行分配,有点类似CF 626F的想法。
把上面两个结合起来,F[i][j][k], 表示当前决策到i行,之前j行的左限制填了,k行的右限制填了的方案数,每次考虑当前列不取/取空白/取左限制/取右限制,乘上组合数转移即可

WARNING
左端限制结束的时候,除了要乘以组合数,还要乘以阶乘!!


  • SRM 545 div1 hard SetAndSet

把数拆开成一位一位处理,对于第i位,A中有一些数的第i位是0,那么这些数必须不能都是同一种颜色的。
那就考虑容斥,每次对于一个位的子集,计算它的答案。
对于多个位计算同时不合法的方案数,若两个位对应的集合有交,那么这两个集合必须染成同种颜色,对于多个集合,如果两个集合有交就连一条边,根据联通块个数去计算答案。
在dfs位子集的时候用并查集维护连通性。

WARNING
如果一个位上所有数都为1,那么这位必定合法, dfs的时候就不将它纳入子集了


  • SRM 614 div1 hard TorusSailing

暴力高斯消元是O(n^6)。
发现转移是有方向性的,可以把所有的元素都用第一行的元素和一个常数来表示
即:

然后对第一行进行高斯消元就好了。O(n^3)

看了眼杜老师的代码..居然迭代可以直接过去...

WARNING
这种东西要想清楚再写,不然系数要挂。


  • SRM 615 div1 hard AlternativePiles

十分简单的一个计数题,一个方案是合法的,当且仅当:

  1. R和G数目相同,且R mod M = 0
  2. 对于任意一个前缀,R的数目不少于G的数目,且R的数目与G的数目之差不超过M

这样就可以dp了,O(NM^2)


  • SRM 616 div1 hard ThreeLLogo

我是写插头dp的,不需要把一行的插头都表示出来,因为最多只有三个logo,所以只要记录一下三个插头的位置就可以了,只有这些位置是1,其余位置都是0.
时间复杂度O(N^5)


  • SRM 617 div1 hard FarStrings

这么simple的题目我还没想出来,哎呀..
这题要求字典序最小的方案,就可以一位一位地去枚举,判断当前的前缀是否能产生符合距离的字符串。
某一个前缀所能产生的最大距离就是后面全部填上一个不存在字符和s的距离, 最小距离就是后面全部填上s对应位置的字符。
这样就能解决了。


  • SRM 618 div1 hard MovingRooksDiv1

此类问题基本上都是贪心的思想。
可以发现每次移动都会使字典序减小,那就从左往右一位一位将Y1去变成Y2。
每次把尽可能大的元素放在左侧。
O(n^2)


  • SRM 683 div1 easy MoveStones

这就是经典的糖果传递,直接排序做就好了


  • SRM 683 div1 medium GCDLCM2

首先发现,合并顺序是没有影响的,因为每一次操作,每个质因子的次数都会原封不动保留下来,只是其中一个都变成了较大的,剩下一个变成了较小的。
最后的终止状态一定是任意两个数都有倍数关系,也就是其中一个数每个质因子都不少于另外一个数的对应质因子。
这样就只要把每个质因子的次数从大到小排序,贪心地乘进每个数里。


  • SRM 683 div1 hard RandomWalkOnGrid

如果直接二项式展开搞矩阵乘法的话,会TLE,要想办法把x和y给拆开。
直接做是拆不开的,xy是不独立的。
考虑把坐标轴旋转45°, 令a = (x + y) / 2, b = (x - y) / 2

因为a和b是互相独立的,所以求出a^k的期望和, b^k的期望和,就可以直接乘起来了

矩阵乘法的时候,这样写取模的次数会少一些:

 REP(i, 0, n) 
        REP(j, 0, n) {
            LL tmp = 0;
            REP(k, 0, n) {
                tmp = tmp + 1LL * A[i][k] * B[k][j];
                if (tmp > 8e18) tmp %= mo;
            }
            C[i][j] = tmp % mo;
        }     

  • SRM 619 div1 hard SimilarSequencesAnother

假设已经填了i个字符了,那么需要记录的是,f[i][i], f[i - 1][i], f[i - 2][i], f[i][i - 1], f[i][i - 2], 以及两个串第i个位置和第i-1个位置分别填了什么,这样就能转移到i + 1了。
为什么呢,因为要使得两个串的LCS不超过2,那么类似f[i][i - 3]这样的状态就肯定不会出现在某一步转移里面。
要知道第i个位置和第i - 1个位置填的元素,因为知道具体数值是没意义的,只需要记录这几个元素两两之间是否相同,可以用最小表示来压这个状态。


  • SRM 620 div1 hard PerfectSquare

裸的高斯消元
要注意一个地方,就是方程数和未知数数量是不一样的,因此判断无解和算自由元的时候是要分开来的。


  • SRM 620 div1 medium CandidatesSelection

首先将初始的序列顺序也加入score当中。
将序列中任意两个元素之间的位置关系分开来考虑,对于一对元素< i, j > 能使得i排在j之前的排序方案,一定存在一个x, 使得score[i][x] < score[j][x], 且对于x之前的关键字y有 score[i][y] = score[j][y], x之后的关键字则可以任意选择。

这样就可以把二元组< i, j >分成两个集合,在第一个集合中的二元组是已经存在一个x,使得score[i][x] < score[j][x], 且对于x之前的关键字y有 score[i][y] = score[j][y],这个集合是"已满足"的集合

第二个集合中的二元组是到目前为止score[i][y] = score[j][y]的二元组, 这个集合是"未满足"的集合。

每一轮可以贪心地选择,每次选择一个关键字,使得所有未满足集合中的二元组继续合法,即仍保持score[i][y] = score[j][y], 或 score[i][y] < score[j][y], 从而将这个二元组加入满足的集合。

这样一直做下去,直到所有元素都加入满足的集合,或者不存在一个关键字能让所有未满足集合的元素保持合法。

WARNING
可以用把关键字压位。 不过要注意开long long


  • SRM 621 div1 hard StringsNightmareAgain

这题可以用SAM来做
在SAM的每个节点上记录这个节点最左边出现的位置和最右边出现的位置
然后根据每个节点所代表的子串的长度区间和这个节点左右出现的位置来更新答案


  • SRM 622 div1 hard FibonacciXor

SRM 622 简要题解

话说回来, 当时还是太naive,当时不会数位dp, 硬是yy了一个"部分记忆化"出来。


  • SRM 623 div1 hard AliceAndFriends

暴力大分类讨论,情况如下:

枚举Alice取到了什么卡片,然后扫描线处理


  • SRM 624 div1 hard TreeColoring

和HNOI2015的一道题一模一样。
树链剖分。

把后面那个带有LCA的式子拆开来,就变成i的每个祖先子树中蓝点的个数乘以这个点与其父亲的距离的和。
树链剖分维护即可。


  • SRM 625 div1 hard Seatfriends

这题和ZJOI2012波浪比较像。
考虑dp[i][j]表示已经放进去i个人,组成了j个块的方案数。
这个dp中只需要考虑环上块的相对顺序,不用管每一块的具体位置。
但是只知道相对顺序,最后是很难算出答案的 --- 因为块之间存在空隙。
考虑把所有的座位都填满, 这样算出来的方案数乘以n就是最终的答案了。
可是k不一定等于n, 那就再假想出n - k个人来,这n - k个人最后填入,不用满足G个联通块的限制。
最后把答案再除以(n - k)!就是可以了。

最后一个加入的人需要特殊处理,因为此时只剩下一个块,且只剩下一个空隙而不是两个。


  • SRM 626 div1 hard ReflectiveRectangle

此类反射的题目,可以考虑把图展开来,把图变成若干个格子组合起来,光线就直接穿过镜子。


只需要统计所有(x, y) 满足 gcd(x, y) = 1, x + y - 2 = Bounces的答案即可。
可以用莫比乌斯函数容斥搞搞。


  • SRM 627 div1 hard LaserTowersDiv1

这个最小割的模型以前从没见到过(too naive)
因为同一个方向的塔(纵向或横向)之间肯定不会有干扰, 所以可以把所有纵向的塔跟S连边,横向的塔跟T连边。中间再连连边,跑一个最小割。
那么中间怎么连边呢.. 对于每个塔,先把它连到它能攻击到的收益最大的地方。对于纵向的塔这么连出了一个图,对于横向的塔也连出了这么一个图。任意一个点在一个方向上最多只能被一个塔攻击到,在对应的图中,这个点连出去的边的权值就是对应的塔能攻击到的最大的权值减去这个点的权值。
怎么把两个方向的图拼起来呢... 把每个点在纵向方向生成的图上对应的点向横向图上对应的点连一条无穷大的边就好了。


  • SRM 628 div1 hard DoraemonPuzzleGame

很有趣的dp题,假设关卡序列已知可以通过一个期望dp来求出最小的期望步数,考虑每一关是选择通过即可(一直挑战直到一星或两星为止) 还是一直刷,直到两星。
由于关卡顺序未知,所以考虑通过排序的方法来找一个决策顺序。
考虑相邻的两个关卡i, j。 i在j的前面。
因为不管i j的顺序如何,争取拿到四颗星的概率都是一样的。
而Doraemon也没有必要去争取两颗星,因为只要通过了,就一定会有两颗星。
如果要争取三颗星的话,显然应该是对于这两关,先刷到通过为止,然后看是否有三颗星,如果没有三颗星的话,就把B较大的那关刷到两颗星。所以应该把B较小的那个放到前面去决策,B较大的到后面去考虑是否需要刷到两颗星。
按照B的大小从小到大排序之后dp即可


  • SRM 629 div1 hard CandyDrawing

暴力的dp式子是,dp[i][j] = d[i - 1][j] + dp[i - 1][j - 1] * i
可以发现dp[n][k]是一个关于n的次数不超过2k的多项式。
于是可以拉格朗日插值来做,复杂度O(k^2)


  • SRM 684 div1 easy CliqueParty

先对数列进行排序
枚举l和r,中间暴力dp计算。


  • SRM 684 div1 medium DivFree

这题的标算是一个容斥
我写的是一个奇怪的dp.. 复杂度大概是O(n * k ^ 0.75)..
以前也没见过这种东西..自己yy的
考虑暴力的dp,f[i][j] 代表前i个数,第i个数填j的方案数。
这个dp的复杂度大致是O(nklogk)的.
可以考虑把第二维的状态按照sqrt(k)分块,小于sqrt(k)的j就保持j不变。
注意到对于大于sqrt(k)的j1和j2,如果k / j1 = k / j2,则f[i][j1] = f[i][j2]
这样的话,就可以把所有大于sqrt(k)的j按照k / j的值分成不超过sqrt(k)类。
转移的时候分两类讨论,枚举因子/倍数即可。
这个做法感觉还是很有意思的!


  • SRM 630 div1 hard NeverAskHerAge

这是一个2—SAT的题目.. 实在是太麻烦了QAQ..
不过这个建图思路很不错.. 对于每个Ai, 拆成(Ai < 2), (Ai < 3) .. (Ai < 100) 这样99对点,
相邻点对之间连边(显然)。
为了方便起见,可以把所有符号都变成 >= 和 <=, 然后两两之间连边。
最后输出方案的时候,先把DAG的边取反,然后拓扑排序。对于每个点,如果它没有被染过色,就把它选上,然后找到它的对立点,把从它的对立点出发能经过的点全部删去..
这样做就可以了。


  • SRM 631 div1 hard TaroTreeRequests

这题就是一个LCT
也没有什么需要注意的细节。


  • SRM 632 div1 hard PatternLock

这题就是一个DP..
dp[i][j]代表当前这列有i个未选,另外列有j个未选的方案数。
转移的时候可以通过矩阵的一些前缀和的性质来优化。
注意边界情况。


  • SRM 633 div1 hard GCDLCM

非常麻烦的一道2-sat题目
构图是精髓.. 把每个质因子给分开,这样一个LCM和GCD限制,就可以拆成若干个质因子上面的限制。
对于一个GCD限制, gcd(A, B) = C 那么对于一个质因子p, 有 min(Ap, Bp) = Cp。
那么如下两句话一定至少有一句是对的
1.Ap = Cp, Bp >= Cp
2.Bp = Cp, Cp >= Cp
LCM同理..
接着判断任意两句话之间是否有矛盾,跑2-sat即可。


  • SRM 634 div1 hard SegmentCutting

把式子写出来,可以发现,如果我们已经知道了这条直线的斜率,那么可以排序之后O(n)扫一遍得到答案。
答案之和n个点的相对顺序有关。那么我们可以找到n^2个临界点,每次交换两个元素,维护一下前缀后缀的和就可以更新答案了。


  • SRM 635 div1 hard ColourHolic

小清新计数题。
发现有两种颜色不超过200个。那么就可以先排列这两种颜色。
g[n] 代表这两种颜色的排列中,存在n对相邻同色的方案数。
现在考虑把剩下两种颜色给插进来,假设这两种颜色为AB。
假设前两种颜色的数量和为m. 那么这样就产生了m +1个间隔。
现在就可以往这m+1个间隔中插入AB串。
有些间隔是一定要填串的(相邻同色),另外一些间隔不一定要填(相邻不同色)
可以发现一个AB串中A和B的数量最多相差1(不然就会出现相邻同色)
这样就可以枚举相邻同色的间隔数,填入AB串的间隔数,以及填入的AB串中AB数目相等的串数量
剩余的信息都可以计算出来,用组合数以及之前处理出来的dp数组计算答案即可。


  • SRM 636 div1 hard Sortish

一道meet in the middle题。
很恶心,卡常数
如果把所有元素都扔到一个set里面去的话,会TLE。
可以把元素分组,每一组开一个set,这样就能卡过去了


  • *SRM 685 div1 hard *

参见UR5 智商锁
先随机1000个点数为12的无向图,然后算出它们的生成树个数,再用mim找出四个数乘起来。
就是用把四张图用边串起来,就好啦。


  • SRM 579 div1 hard RockPaperScissors

假设已经进行了t轮,现在要做出第t+1轮决策。 对于第t+1轮有用的信息是前t轮投出的石头、剪刀、布的数目。
这样我们记录dp[r][p][s][i] 代表已经投出了r个石头,p个布,s个剪刀的情况下,第i个骰子还在袋子里的概率。
p[r][p][s] 代表投出这个状态的概率。 这样就可以转移了。
得到所有dp[r][p][s][i]之后每一轮就贪心地选择收益最大的决策。


  • TCO14 Final hard FrozenStandings

R老师的1100分计数题啊。
好神
先把所有可能的得分排序。第i个人可能的位置两个:l[i], r[i]。
如果不考虑重复的排列,那么总共有2^n种方案。
考虑重复的方案。如果对于一个区间l[i], r[i], 它中间没有选任意一个元素,那么这就被重复计算了一次。
这样就可以dp来容斥了。


  • TCO16 Round2A LCMGCD

这题我是分类讨论的。
第一种情况是,存在一个数等于目标数,那么只要把剩下所有数求一个LCM和GCD看看是不是合法即可。
对于剩下的情况,构造两个数 X, Y, 其中X的2的指数等于目标数,Y的3的指数等于目标数,这样再进行讨论即可。


  • TCO16 Round2A CliqueCuts

这题我是用MIM做的。
首先观察发现,令wi为每个点邻边权值和,那么一个方案的贡献就是这个团中所有点的wi之和减去整张图的边权和。
那么就可以MIM了... 中间要计算一个子集和的东西。
这个可以来做, VFK的论文里管这个叫集合的莫比乌斯变换。


  • SRM 690 div1 easy WolfCardGame

发现只要把N里面没出现过的质因子拿出来,用它的倍数就好了。

把3, 4, 5拿出来之后,发现只有60不能做,那么只要用14个7的倍数和1个1就好了。


  • SRM 690 div1 medium TreeWalker

对于一条长度为k的路径,它的贡献就是
只要dfs两遍就好了。


  • SRM 690 div1 hard WolfHockeyTeamHard

先假设每一列的值递增,那么就变成数有多少种不同的括号序列。
假设第二行的最大值为2*n - 1, 去枚举第一行的最大值。 这样就变成统计有多少个括号序列满足还剩下k个左括号未被匹配,这是个经典问题,组合数算算就好了。
假设有a个左括号,b个右括号,它们组成合法括号序列前缀的方案数为


  • SRM 689 div1 easy ColorfulGarden

先填多的字母,后填少的字母,按照斜线的方向填过去就好了。


  • SRM 689 div1 medium MultiplicationTable3

一个不难的构造..我想了好久。
假设已经有了一张表A,答案为x。可以很容易地通过加入一个变量来得到x+1和2x+1的方案。
这样就把x不断拆分成加一和乘二加一就行了。


  • SRM 689 div1 hard ZeroPointSixThreeSix

一个paper题,发现0.636大概就是 ,这个数正好就是正弦绝对值的期望。
随机一个向量,把点均匀分成两份,找一个这两部分点之间不相交的匹配,发现这个匹配的大小期望就是0.636倍的最大匹配。
那么随机几次就能得到答案了。


  • TCO 2016 Round2B easy TriangleTriples

这题可以考虑容斥
如果a和b没有限制, 只有c有限制,那么这就是一个简单的级数求和。 如果a只有下界的限制,那么可以把c的限制减去这个下界,就变成了一个等价的问题。这样就可以算了


  • TCO 2016 Round2B medium FoxAndGemstone

假设已经知道宝石重量的排列了。那么怎么样的两个bag能判断大小呢。如果对于每一个前缀,其中一个bag的数量都大于等于另一个,那么就一定能判断,反之不行。那么就枚举每个bag作为最大值,跑一个状压dp..看看有多少排列满足。看看总的排列数量是否为16!就行了。


  • SRM 640 hard TwoNumberGroups

暴力的做法是枚举两个数去算代价.. 然而算代价这部分进行了太多无用的运算。
首先枚举小于5w的质数,按照余数分类,把每一对余数相同的数消掉这个因子。
最后再看看剩下来的因子就好了。


  • SRM 641 hard BitToggler

陈老师讲过的题目,把每一段的贡献分开来计算。
对于确定的两个点i, j计算把所有点变成相同的情况下期望步数。
这个可以列出方程高斯消元。


  • SRM 642 hard WheelofFortune

简单的期望dp


  • SRM 690 hard WolfHockeyTeamHard

组合计数题.. 要用到经典的找零钱的那个式子。


  • TCO 2016 Round2C medium

上下界网络流的模型,可以用费用流来做。考虑对于行和列分开来建点。
中间连边,如果一个点在某个矩形内,那么再额外新建两个点代表这个矩形。
因为每个矩形内的rook的数目限制了。 所以是个有下界的网络流。


  • TCO 2016 Round2C hard

约瑟夫问题的变种..考虑用约瑟夫问题的dp方式去做。
直接去做这个dp会发现这个dp的转移是有环的。
因此对于每一层来说,先把环上某个点的dp值算出来再进行转移就好了。

← NOI前的71天 滚粗狗的自我修养之Codeforces练习 →
 
comments powered by Disqus