2017-Sp113-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
流水账没什么好写的，题目比较简单，但是还是没能写完。靠着新科技，撸过了B、I、J，但是多校一如既往地坑读入格式和多组数据，要注意一些描述上的细节(mdzz shi哥怎么也坑人啊)，C的几何dp题之前见过，sub上机一发就过了。A、E、F没什么好说的sb题。感觉这个D还是挺棒的，似乎shi哥的题解里写的是n^3^，实际上是个n^2^，有一维一一对应的。最后cjb和yzc讨论了20min，yzc上机10min就过了D。G和H早早就开出来了，但是一直没去写，H要套高精度，感觉十分垃圾，三个人纷纷表示丢了丢了。
== 总结 ==
一度以为自己能ak，结果根本写不完...感觉板子题炸了还是要相信一波板子啊，排除法找代码问题还行啊。觉得最妙可能是D题，自己怎么把自己的n^2^做法叉了啊还好最后抓紧过了。这套题感觉适合刚组队的时候做做，多校真的是时代的变迁啊...我猜13年的时候带花树、必经点树和BM都算是高新科技？板子好板子好.jpg 自己写是不可能的，这辈子都不可能的。
=== chenjb ===

=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：暴力拆式子矩阵乘法。

 * B：带花树跑出最大匹配p，然后枚举每条边，把两个点删掉再跑匹配c，如果c<p-1就GG。

 * C：f[i][j]代表逆时针点i到点j都没有被割，别的都割完了的最小代价，转移即可。

 * D：f[i][j]表示前i个位置，有j个加号未被填上的方案数，注意此时前i个数字中恰有j个数字没用到，转移即可，O(n^2^)。

 * E：模拟

 * F：按题意，哈希找下lcp。

 * G：数位和不会超过200，所以可以数位dp搞一搞，写个函数算出[L,R]里面各个数位和的个数。有了这个东西，你可以随便f[i][j]表示前i个位置，第i个位置数字和是j的方案数，dp一下就知道合法序列个数。然后逐位二分就能求出答案序列。注意本题的麻烦地方在于到处都可能爆long long，经典操作就是>m的时候=m就好，另外某个式子比较大小的时候可以double一下，long long是不太行的，或许__int128可以，hdu似乎没有???

 * H：f[c][i]表示c这个字母在扩展i次之后的长度，这个可以很方便dp出来，然后针对一个(n,k)的问题，可以通过枚举字符串每个字母来得到扩展出来恰好包含第k个字符的那个字母，递归做(n-1,k')的问题即可，需要大整数。

 * I：必经点树板子题，注意有点到不了答案为0。

 * J：b的每个步伐的系数是这个长度在a当中有多少种方案，得到递推式，然后套一个n^2^log(k)的板子求第k项即可，矩阵快速幂似乎会被卡掉。

流水账

流水账没什么好写的，题目比较简单，但是还是没能写完。靠着新科技，撸过了B、I、J，但是多校一如既往地坑读入格式和多组数据，要注意一些描述上的细节(mdzz shi哥怎么也坑人啊)，C的几何dp题之前见过，sub上机一发就过了。A、E、F没什么好说的sb题。感觉这个D还是挺棒的，似乎shi哥的题解里写的是n³，实际上是个n²，有一维一一对应的。最后cjb和yzc讨论了20min，yzc上机10min就过了D。G和H早早就开出来了，但是一直没去写，H要套高精度，感觉十分垃圾，三个人纷纷表示丢了丢了。

总结

一度以为自己能ak，结果根本写不完...感觉板子题炸了还是要相信一波板子啊，排除法找代码问题还行啊。觉得最妙可能是D题，自己怎么把自己的n²做法叉了啊还好最后抓紧过了。这套题感觉适合刚组队的时候做做，多校真的是时代的变迁啊...我猜13年的时候带花树、必经点树和BM都算是高新科技？板子好板子好.jpg 自己写是不可能的，这辈子都不可能的。

chenjb

oipotato

subconscious

题解

• A：暴力拆式子矩阵乘法。
• B：带花树跑出最大匹配p，然后枚举每条边，把两个点删掉再跑匹配c，如果c
• C：f[i][j]代表逆时针点i到点j都没有被割，别的都割完了的最小代价，转移即可。
• D：f[i][j]表示前i个位置，有j个加号未被填上的方案数，注意此时前i个数字中恰有j个数字没用到，转移即可，O(n²)。
• E：模拟
• F：按题意，哈希找下lcp。
• G：数位和不会超过200，所以可以数位dp搞一搞，写个函数算出[L,R]里面各个数位和的个数。有了这个东西，你可以随便f[i][j]表示前i个位置，第i个位置数字和是j的方案数，dp一下就知道合法序列个数。然后逐位二分就能求出答案序列。注意本题的麻烦地方在于到处都可能爆long long，经典操作就是>m的时候=m就好，另外某个式子比较大小的时候可以double一下，long long是不太行的，或许__int128可以，hdu似乎没有???
• H：f[c][i]表示c这个字母在扩展i次之后的长度，这个可以很方便dp出来，然后针对一个(n,k)的问题，可以通过枚举字符串每个字母来得到扩展出来恰好包含第k个字符的那个字母，递归做(n-1,k')的问题即可，需要大整数。
• I：必经点树板子题，注意有点到不了答案为0。
• J：b的每个步伐的系数是这个长度在a当中有多少种方案，得到递推式，然后套一个n²log(k)的板子求第k项即可，矩阵快速幂似乎会被卡掉。