2017-Sp82-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，发现有人过E，yzc丢了个做法给cjb，获得认同，cjb上机获得wa。sub读了J，丢了个式子给yzc，yzc上机'''J1y17'''。yzc感觉做法是错的，然后改了改，'''E1y21'''。sub给cjb讲了L的做法，cjb上机wa了两发，sub给yzc丢了B的做法，yzc上机'''B1y42'''。cjb想了一个C的性质，sub丢了个做法给yzc，yzc上机wa了。接下来各自陷入了思考，cjb做L，yzc搞C，sub搞F。cjb终于想到了做法，上机'''L3y98'''，yzc和cjb感觉开大数组就能过C了，又交了几发，还是wa。sub上机写F，wa了一发后找到了问题，'''F2y137'''。cjb发现一队过了I，读了读发现是sb题，让yzc上机，'''I1y166'''。cjb提出了C比较合理的bfs，yzc改了之后终于'''C5y175'''。接下来三个人合力搞A、D、H，cjb提出了一个式子，sub表示自己能够容斥，'''H1y240'''。最后三个人乱搞，cjb负责瞎逼逼，怂恿瞎交，结果'''A1y289'''。
== 总结 ==
=== chenjb ===
罚时像sb，只能靠题数，灵机一动想到H的式子真是太爽了，前期还是谨慎点啊，签到题贡献了3发罚时，有个签到题还一直想不到做法......以后要努力尽早进入状态。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * D：
  * 题意： 两个长度为n的排列，每一次从第一个排列或第二个排列的左侧拿出一个数放进新序列的右侧，问新序列的种类数。n<=2000
  * 题解：考虑dp，f[i][j]表示第一个排列前i位，第二个前j位的方案数，显然这个状态直接转移的话存在重复的情况。观察发现，重复情况一定出现在第一个排列的前i个和第二个排列的前j个有公共后缀的情况下，且每种后缀都会导致重复，于是得到转移方程f[i][j]=f[i-1][j]+f[i][j-1]-sigma(g[k]*f[i-k][j-k])，其中g[k]表示长度为2k的能够被两个相等的排列组成的序列数。设G[i][j]表示这个序列有2i个数字，且第一个排列的第i个数字在第j个位置，则有G[1][1]=1,G[i][j]=sigma(G[i-1][k])。于是g[k]=sigma(G[k][p])。注意到两个序列所有前缀对的最长公共后缀长度之和最多不超过n^2^，所以直接暴力转移即可。
 * [https://wiki.icpc-camp.org/twsf/ICPCCamp%202016%20Day8%20Makoto%20Soejima%20Contest%204 The Way So Far]
 * [https://wiki.icpc-camp.org/dreadnought/ICPCCamp%202016%20Day%207%20-%20Makoto%20Soejima%20Contest%204 Dreadnought]
 * [http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204 Heynihao]
== 补题 ==
 * ~~D~~ by yzc

流水账

开场各自看题，发现有人过E，yzc丢了个做法给cjb，获得认同，cjb上机获得wa。sub读了J，丢了个式子给yzc，yzc上机J1y17。yzc感觉做法是错的，然后改了改，E1y21。sub给cjb讲了L的做法，cjb上机wa了两发，sub给yzc丢了B的做法，yzc上机B1y42。cjb想了一个C的性质，sub丢了个做法给yzc，yzc上机wa了。接下来各自陷入了思考，cjb做L，yzc搞C，sub搞F。cjb终于想到了做法，上机L3y98，yzc和cjb感觉开大数组就能过C了，又交了几发，还是wa。sub上机写F，wa了一发后找到了问题，F2y137。cjb发现一队过了I，读了读发现是sb题，让yzc上机，I1y166。cjb提出了C比较合理的bfs，yzc改了之后终于C5y175。接下来三个人合力搞A、D、H，cjb提出了一个式子，sub表示自己能够容斥，H1y240。最后三个人乱搞，cjb负责瞎逼逼，怂恿瞎交，结果A1y289。

总结

chenjb

罚时像sb，只能靠题数，灵机一动想到H的式子真是太爽了，前期还是谨慎点啊，签到题贡献了3发罚时，有个签到题还一直想不到做法......以后要努力尽早进入状态。

oipotato

subconscious

题解

• D：
  • 题意： 两个长度为n的排列，每一次从第一个排列或第二个排列的左侧拿出一个数放进新序列的右侧，问新序列的种类数。n<=2000
  • 题解：考虑dp，f[i][j]表示第一个排列前i位，第二个前j位的方案数，显然这个状态直接转移的话存在重复的情况。观察发现，重复情况一定出现在第一个排列的前i个和第二个排列的前j个有公共后缀的情况下，且每种后缀都会导致重复，于是得到转移方程f[i][j]=f[i-1][j]+f[i][j-1]-sigma(g[k]*f[i-k][j-k])，其中g[k]表示长度为2k的能够被两个相等的排列组成的序列数。设G[i][j]表示这个序列有2i个数字，且第一个排列的第i个数字在第j个位置，则有G[1][1]=1,G[i][j]=sigma(G[i-1][k])。于是g[k]=sigma(G[k][p])。注意到两个序列所有前缀对的最长公共后缀长度之和最多不超过n²，所以直接暴力转移即可。
• The Way So Far
• Dreadnought
• Heynihao

补题

• D by yzc

附加文件

• 1.png by chenjb