2020-team12-038

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(standings.PNG, 1000px)]]
[[Image(codeforces.com_gym_101981_my.png, 1000px)]]




== 问题 ==

ctcE题签到出了失误
我们需要一个人去学“凸优化”

== 题解 == 

A: 签到，特判几种情况以后，先手第一步只要把状态分成两堆一样的就必胜了。

B: 疑似凸优化，全队技能点不足，待补。

C: 待补

D: 三分套三分套三分，注意每往下一层三分都需要重置一遍下一层的L，R。

E: 考虑能否将两个串涂成类似的“基本模型”。看成一段一段连续的0和1，先对于起始串和终止串，找到这些连续01，每找到一个串长度大于等于K，就把它前面K的倍数的部分全都涂成上一个颜色，然后比较起始终止状态是否相同即可.

F: 魔幻题，待补

G: 签到，找规律计数即可。

H: 一开始以为是数位DP……事实上考虑一个串如果0，1，2出现超过一半以上次数，则只能留这一个数；否则答案可能是0和1.对于奇数长度的串（偶串已经肯定可以消完了），考虑每一个0，如果它的两侧的串都是偶数长度且都满足1和2的数量不超过一半，那么就一定可以消到留下这个0为止。扫一遍维护1比非1，2比非2多多少，我们对于每个加入的奇数位置的、右边可消除完的0记录加入它这两个数量，对左边的位置，一减就知道这个0到这里有多少了。用树状数组维护即可。

I: 网络流模板题。

J: 签到。

K  事实上好像是50000次随机都可以过，赛场上我们先写一个每个叶子节点合并到树的bfs在随机到五万次稳健地过了。

L  szbnb 首先不是x和y的字符都可以抽象成z. 然后，令dp[i][j][b1=0/1][b2=0/1][b3=0/1]表示填i个X或Y，j个z，钦定从第i个开始要填b1(x0y1),前面有没有出现x和以及y.
   令bi表示第i个x或y，c[i]表示第i个数之后本来有多少个z.
   四种转移：
   ①枚举第i个位置后，第i-1个位置要剩余多少个z。多的需要移掉且b[i]如果不是枚举的b1也要移去，Min(dp[i][j+shengxia][b1][b2][b3],dp[i-1][j][b1][b2][b3] + （b[i]!=b1+1）+ c[i]-shengxia)
   ②如果有至少一个z，下一个可以转移到不同的b1，Min(dp[i][j+shengxia(shengxia>0][b1^1][b2|(b1==1)][b3|(b1==0)],dp[i-1][j][b1][b2][b3] + （b[i]!=b1+1）+ c[i]-shengxia)
   ③如果一个z都没有，必须要转移一个z过来，其他类似上面，Min(dp[i][j+1][b1][b2][b3],dp[i-1][j][b1][b2][b3]+(b[i]!=b1+1)),Min(dp[i][j+1][b1^1][b2|(b1==1)][b3|(b1==0)+b[i]!=b1+1)

M  回文树+KMP的板子题，ctc这方面的技能点有待继续点。

[/wiki/2020-team12 返回]

问题

ctcE题签到出了失误

我们需要一个人去学“凸优化”

题解

A: 签到，特判几种情况以后，先手第一步只要把状态分成两堆一样的就必胜了。

B: 疑似凸优化，全队技能点不足，待补。

C: 待补

D: 三分套三分套三分，注意每往下一层三分都需要重置一遍下一层的L，R。

E: 考虑能否将两个串涂成类似的“基本模型”。看成一段一段连续的0和1，先对于起始串和终止串，找到这些连续01，每找到一个串长度大于等于K，就把它前面K的倍数的部分全都涂成上一个颜色，然后比较起始终止状态是否相同即可.

F: 魔幻题，待补

G: 签到，找规律计数即可。

H: 一开始以为是数位DP……事实上考虑一个串如果0，1，2出现超过一半以上次数，则只能留这一个数；否则答案可能是0和1.对于奇数长度的串（偶串已经肯定可以消完了），考虑每一个0，如果它的两侧的串都是偶数长度且都满足1和2的数量不超过一半，那么就一定可以消到留下这个0为止。扫一遍维护1比非1，2比非2多多少，我们对于每个加入的奇数位置的、右边可消除完的0记录加入它这两个数量，对左边的位置，一减就知道这个0到这里有多少了。用树状数组维护即可。

I: 网络流模板题。

J: 签到。

K 事实上好像是50000次随机都可以过，赛场上我们先写一个每个叶子节点合并到树的bfs在随机到五万次稳健地过了。

L szbnb 首先不是x和y的字符都可以抽象成z. 然后，令dp[i][j][b1=0/1][b2=0/1][b3=0/1]表示填i个X或Y，j个z，钦定从第i个开始要填b1(x0y1),前面有没有出现x和以及y.

令bi表示第i个x或y，c[i]表示第i个数之后本来有多少个z.

四种转移：

①枚举第i个位置后，第i-1个位置要剩余多少个z。多的需要移掉且b[i]如果不是枚举的b1也要移去，Min(dp[i][j+shengxia][b1][b2][b3],dp[i-1][j][b1][b2][b3] + （b[i]!=b1+1）+ c[i]-shengxia)

②如果有至少一个z，下一个可以转移到不同的b1，Min(dp[i][j+shengxia(shengxia>0][b1^1][b2|(b1==1)][b3|(b1==0)],dp[i-1][j][b1][b2][b3] + （b[i]!=b1+1）+ c[i]-shengxia)

③如果一个z都没有，必须要转移一个z过来，其他类似上面，Min(dp[i][j+1][b1][b2][b3],dp[i-1][j][b1][b2][b3]+(b[i]!=b1+1)),Min(dp[i][j+1][b1^1][b2|(b1==1)][b3|(b1==0)+b[i]!=b1+1)

M 回文树+KMP的板子题，ctc这方面的技能点有待继续点。

附加文件