2017中国大学生程序设计竞赛 - 女生专场

（ACM）数学----矩阵快速幂 （ACM）数学----博弈论

D. Deleting Edges

题意

• 给出带边权无向图（无重边），点0~n-1
• 求满足条件的树的个数
• 条件：0到v的距离等于原图0到v的最短路

题解

• 处理出dis[i]表示0到i的最短路
• 如果对于边(u,v)，dis[u]+(u,v)=dis[v]，那么v可以由u转移过来。
• 求出点i可以由cnt[i]个点转移过来
• 最后的答案是cnt[1] * cnt[2] * ... * cnt[n-1]

H. Happy Necklace（矩阵快速幂）

题意

题解

• 打表之后发现f[n]=f[n-1]+f[n-3]
• 矩阵快速幂
• $$\left[ \begin{matrix} f[n] \\ f[n-1] \\ f[n-2] \\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{matrix} \right] * \left[ \begin{matrix} f[n-1] \\ f[n-2] \\ f[n-3] \\ \end{matrix} \right]$$
• $$\left[ \begin{matrix} f[n] \\ f[n-1] \\ f[n-2] \\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{matrix} \right] ^{(n-4)} * \left[ \begin{matrix} f[4] \\ f[3] \\ f[2] \\ \end{matrix} \right]$$

J. Judicious Strategy（博弈论）

题意

• 给出n个字符串，两人进行博弈
• 规则：初始字符串是空串，每次在开头或者结尾加上一个小写字母，获得的新字符串必须是n个字符串中至少一个串的子串，当前玩家得分加上$score(S)$
• $$score(S)=[(\sum_{i=1}^{|S|}value(S[i])×\max_{i=1}^{|S|}value(S[i])]+occ(S)$$
• $value('a')=1$。以此类推。
• $occ(S)$表示S在n个字符串中出现的次数，多次在同一个字符串中出现计为一次。
• 求最后谁赢，输出两人的得分。

题解

• 比赛的时候不懂怎么用AC自动机求occ(S)，这种类型的博弈也只做过一次，后来就放弃了
• 学习了一下kc大神的做法 在这里 膜kc orz
• 先把所有可能的串处理出来（这部分代码很巧妙）
• 然后对所有串关于长度排个序
• 之后做法就是博弈论从末态推到初态
• 代码和kc一样就不贴了。注意要用c++11编译。