2017-Sp248-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
出门各自看题，yzc跟着签到做了E，'''E1y24'''。cjb和sub丢了D给yzc，'''D1y52'''。sub上机写B，'''B1y76'''。yzc开出了K，上机wa了后对拍，'''K2y124'''。cjb上机写A，'''A1y137'''。sub上机写H，'''H3y166'''。之后cjb上机写sub丢来的G，和yzc确认做法后'''G3y200'''。最后sub开出了I丢给yzc，'''I1y224'''。
=== chenjb ===
I的破局技巧源于树型dp最基本的按dfs序转成序列dp，这个要记住，不能遗忘。
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：字符串完全相同、下标和相同、各串内某字母出现次数<2，某种类字母数量不同，判完这些一点有解。之后用两个set维护ab和ba，从头开始扫，每次对于一个不同的位置，用最早的ab去换最晚的ba，或者最早ba换最晚ab，不断重复推进即可。

 * B：对于每个环可以求出一个同余方程，crt合并判定是否有解即可。

 * C：

 * D：每次对于一个包含x个数>1的块，二分找到最早的一刀切下去，数量增加1，重复直到k块即可。

 * E：f[i]表示前i个的答案，从i-2或者i-3转移。

 * F：

 * G：连边(x,y,w)的时候，(x,w)和(y,w)连边2w，然后(x,w1)和(x,w2)连边，用map维护后扫描连边，跑最短路后/2即可。

 * H：扫描线。

 * I：按dfs序从后往前dp，i不取的话从i+size[i]转移，取的话从i+1转移，用bitset优化。

 * J：

 * K：如果能同时吃掉，一定不会选择先吃单个，对于一个数字i，他面临了两个蛋糕都是这个数字的情况，有两种决策，那么下一次再遇到两个相同数字的时候，两个数字的位置的差是确定的，所以从前往后dp，f[i]表示i这个数字遇到了同时出现在上下两层，往后的最小值，转移的时候取两种决策下位置的差值，在后面第一次出现的数字转移过来即可。

流水账

出门各自看题，yzc跟着签到做了E，E1y24。cjb和sub丢了D给yzc，D1y52。sub上机写B，B1y76。yzc开出了K，上机wa了后对拍，K2y124。cjb上机写A，A1y137。sub上机写H，H3y166。之后cjb上机写sub丢来的G，和yzc确认做法后G3y200。最后sub开出了I丢给yzc，I1y224。

chenjb

I的破局技巧源于树型dp最基本的按dfs序转成序列dp，这个要记住，不能遗忘。

oipotato

subconscious

题解

• A：字符串完全相同、下标和相同、各串内某字母出现次数<2，某种类字母数量不同，判完这些一点有解。之后用两个set维护ab和ba，从头开始扫，每次对于一个不同的位置，用最早的ab去换最晚的ba，或者最早ba换最晚ab，不断重复推进即可。
• B：对于每个环可以求出一个同余方程，crt合并判定是否有解即可。
• C：
• D：每次对于一个包含x个数>1的块，二分找到最早的一刀切下去，数量增加1，重复直到k块即可。
• E：f[i]表示前i个的答案，从i-2或者i-3转移。
• F：
• G：连边(x,y,w)的时候，(x,w)和(y,w)连边2w，然后(x,w1)和(x,w2)连边，用map维护后扫描连边，跑最短路后/2即可。
• H：扫描线。
• I：按dfs序从后往前dp，i不取的话从i+size[i]转移，取的话从i+1转移，用bitset优化。
• J：
• K：如果能同时吃掉，一定不会选择先吃单个，对于一个数字i，他面临了两个蛋糕都是这个数字的情况，有两种决策，那么下一次再遇到两个相同数字的时候，两个数字的位置的差是确定的，所以从前往后dp，f[i]表示i这个数字遇到了同时出现在上下两层，往后的最小值，转移的时候取两种决策下位置的差值，在后面第一次出现的数字转移过来即可。

附加文件

• 1.png by chenjb