A 井字棋

总的情况数是 C(n,3)，n 是空位置的数量
我们只需要统计 n，然后再枚举一下有多少种情况连成 3，就可以得到答案了。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45914277

B 字符串魔法(easy)

答案会是形如 AAAA...AAAABBBB...BBBBAAAAA...AAAABBB...BBB 这样一段序列。此时我们将中间的 BBB...BBBAAA...AAA 使用魔法翻转，即可得到一段字典序不下降的序列。所以我们需要统计每一段 AA...AA 或者 BB..BB 的长度。最后枚举第一段 AAA...AAA 的起点即可。(注意第一段 AAA..AAA 长度为零的情况)
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45914440

C 字符串魔法(hard)

做法1：前缀和预处理

将 A 看作 -1，B 看作 0，那么某一段和为 0 的区间就是 AB 数量相等的子串。我们对子串记录前缀和，并预处理出每一个位置为起点时，离它最远(最靠右)的 AB 数量相等的子串的位置 Q。选择这一串进行字符串魔法变换一定是最优的。
同时预处理出每个位置前面有多少个连续的 A，后面有多少个连续的 B。
枚举魔法变换的起点 C，答案就是起点前面连续 A 的数量 + C 到 Q 的距离 + Q 后面 B 的数量
这三个东西都是上面预处理的，复杂度 O(n) 即可通过本题
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45914892
##做法2：分治
复杂度O(nlogn)
将字符串一分为二，二分为四直到分成长度为 1 的，然后再合并，合并的时候记录字符串前缀，后缀每一个位置 A 减 B 的数量

D 字符串判断

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45914949

E 数论只会 for 循环

整除分块+记忆化搜索
因为有个log2向上取整，而log1=0，所以每一次迭代至少会使得上界n/2。
记忆化搜索+整除分块，记忆化迭代log次，整除分块复杂度根号，最终复杂度为n根号log。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45915105

F 爬塔

首先可以设表示在前层中挑选个物品所获得的最大价值.转移的话是一个01背包。用,从第层中挑选个物品的最大权值和进行转移.而对于的求解可以采用预处理的办法进行.因为不同层之间是相互独立的.
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45915229

G 请问您要来点兔子吗

单纯型法可以秒
std是费用流+最小割。
首先只考虑上界，上界是用“流”来约束的。
考虑一个比较简单的情景，一共有4只，然后每3只最多选1只

先建一个大概这样的图，因为最多选一只，所以从s出发的流量上界为1。
然后想这么一个问题，如果选了第一只，那么这1,2,3只里面我是不能再次进行选择的。那么这点流量，就会在第4只解锁。同理，如果我选择第二只，那么2,3,4只内也不能继续选择，那么这点流量按理应该流入t。，同理3,4如果选中的话也是流入t的。

这个模型的精妙之处其实就是将流量当成“目前还可以选择几只”的资源，然后使用这点流量时会被锁定，然后它将在k只后解锁。
然后对于仅有上界而已，这道题就写完了。
但是不行，本题对于“下界”也有约束条件。这个下界，我们使用“割”进行约束

什么是“割”呢…生动形象的来说，图中这就是一个“割”。如果你把图论中的边和点看成是用绳子连接在一起的某种物品的话，我们切断一些绳子，使得这个物品彻底的分成两部分，第一部分中包含一个叫s的东西而第二部分包含一个叫t的东西，那么你这一剪子就叫“割”。
定理：通过任意割去重后的流量为最大流。（就是俗称的最小割=最大流，实际上最不最小无所谓，流量总和一定是最大流）
这个模型中的最大流一定是等于R的，但是这不代表流量木有用。
换句话说在红色的“割”中，通过这些割边的流量总和也是R。
例如现在还是4只，我要求你3只内最多选2只，但是至少选1只。

那么在建模的时候S到第1只还是2(R)的上限。只不过，注意到我下方的inf边变为了cap:1，为什么呢
因为红色框圈中的边和蓝色框圈中的边是一个“割”，那么通过他们的流量就为定值 2（R）。
只要限制了红色框中的边流经的最大流量为1，那么蓝色部分的流量就至少为2-1=1(L)。也就达到了约束，“3只内至少选中1只”这个条件。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45915361

H 赌神

正着做很难考虑，倒着做贪心即可
如果是奇数就 -1，如果是偶数就 /2
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45915460

I 会拐弯的眼睛

复杂度 O(nm)
bfs 的过程中同时记录方向，在方向改变时才入队，并且 step++，step 指的是拐弯次数
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45915563

J 全排列

原题转换为，求 A 字符串的编号，再求 B 的字符串编号，然后求差值。
我们需要解决的问题就变为：求某一个字符串 S 的编号
S 编号其实就是字典序比 S 小的字符串数量（当然要满足每一种字母的数量都相同）
那么我们可以再次转换问题为：已知每一种字母的数量，求能构造出多少个字符串，满足字典序比 S 小
现在我们用递归的方法来构造一个新字符串 Q。递归到第 i 层，代表我们已经处理到了字符串的第 i 个位置。我们枚举第 i 位放哪个字符，如果Q[i]>S[i]，这一位字典序大了，后面无论怎么排列，Q 的字典序都会大，方案数是 0。如果 Q[i] == S[i]，这一位字典序一样，继续进行下一层递归。如果 Q[i] < S[i]，这一位字典序小，所以后面无论怎么排列，字符串 Q 的字典序都会小，方案数为剩余字母的全排列方案数（用简单的排列组合就能算出）。
复杂度 O(26n)
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45916046