A – The Cow Gathering
首先，如果没有限制的话，其实从叶子结点来抽是一定有解的，可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边，初步思考可以把每个点都作为最后一个节点，然后来看新的图有没有环，这样是 \(\Theta(n^2)\)。
标签： 字典序
[Fortuna OJ]Jul 8th – Group B 解题报告
今天这几题咋就那么毒瘤呢？
A – String
其实这道题考场上应该能做出来的，是一道很简单的计数问题。在考场上一看到字符串就懵了，不知道为什么我对字符串的字典序有阴影，现在看来就是一道傻逼题。
考虑这样计数：
- 枚举一个\(i\)，考虑前\(i-1\)个字符与\(T\)串相同，然后第\(i\)个字符小于\(T[i]\)，这样可以保证后面怎么放置字母都能满足要求。
- 在枚举了\(i\)的情况下，枚举字符\(ch\)，范围在\([a, T[i])\)，考虑以下两种情况对答案的贡献：
- 如果\(ch = S[i]\)，那么后面需要变动的字符个数为\(k\)个，对答案的贡献：\[ {n – i \choose k} 25^{k} \]
- 如果不等于，那么后面需要变动的字符个数为\(k-1\)个，因为本位占了一个；对答案的贡献：\[ {n – i \choose k – 1} 25^{k – 1} \]
- 贡献之后，如果本位\(T[i] \neq S[i]\)，那么把\(k–\)，代表多固定了一个不同的字符。