A.Available Computation Sequence 虽然串长为$10^5$，但是只有至多100个运算符，就可以转化为经典的DP问题，复杂度$O(n^3)$ B.Board 手工构造出$n=1,2,3,4$的情况，对于大于4的$n$可以通过中间放$n-2$然后四周用$n=3$以及$2 \times 3$的块来补满。 E.Permutation 对于排列$C$的每个置换环都是独立的，所以分配提取出$A$,$B$的对应位置是否可以匹配上。如果能匹配上就能得到一个关于次数的同余式，合并这些同余式即可，需要高精度。 （求教Java怎么写递归的扩展欧几里得算法 = =） G.Stean 体积大家都会算。 表面积是一个曲面积分，好像是找不到对应的原函数的，所以使用自适...

402 枚举最后占领的点，剩下的就是要求把剩下的图分成两部分的最小代价。 显然就是全局最小割，输出方案略有一点麻烦。 413 构造，比较有趣。 一个重点在于在DFS生成树上深度至多相差1的联通子集的导出子图必然是树。 416 猜结论，样例就是一个好例子 417 积分，猜结论。 422 概率DP，推出暴力转移的公式后，可以优化转移至$O(1)$。 428 小的合法方案可以拼成大的合法方案，构造 429 最暴力的DP是四维的$f[i][j][k][l]$表示还剩第i堆到第j堆的石子且第i堆还剩k个第j堆还剩l个，转移显然。 然而要注意到$f[i][j]$这个二位矩阵每行每列只有一个必输态，就能想办法将复杂度降至$O(n^2A)$甚至$O(n^2)$。 432 模拟 433 ...

SRM651 Easy 如果机器人在某一方向有墙挡着，返回-1，因为往那个方向再怎么走都不会死。然后现在考虑某一个方向，如果走x步就会死，那显然步数序列中就不能有x个这个方向。四个方向的x-1加起来答案为n+m-2。 Medium 首先只有6只狐狸……6个格子所形成的联通块样式的数量是非常有限的，可以先把这些样式暴搜出来，然后就差移动了。固定一个格子的坐标后可以发现横纵坐标是独立的，而每个坐标实际上还是一个求绝对值之和最小的问题，取中位数即可。 SRM652 Easy 考虑1所在置换群子群的大小，答案为$[1,n]$的LCM。 Medium 设$f[i][j]$表示Alice在i点并且Bob还有j次机会Alice走到终点的最小花费，初值$f[n-1][j]=0$。则如果i能走...

《社会计算》大作业 生成树 生成树(spanning-tree)是图论里面一个重要的概念。 一个无向图的所有边构成的集合称为这个无向图的边集，一个构成树的边集的子集，就成为这个无向图的生成树。 如果只是要求一棵生成树或者是要求边总权值最小的生成树，有很多经典的算法，比如Prim与Kruscal算法。 然而如果要求一个无向图的生成树数量，就不是一个那么简单的任务了。 Matrix-Tree定理 以下引用自国家集训队2008论文集 Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念： 1、 G的度数矩阵D[G]是一个nn的矩阵，并且满足：当i≠j时,dij=0；当i=j...

一个字符串中的回文子串的种类数是$O(n)$的，$n$为字符串长度。因为每在一个串后面加一个字符最多只可能新加一种回文子串。 例如abab有4种回文子串、aabca也有4种回文子串。 一个非常经典的求出一个串的所有回文子串的方法是利用Manacher算法，求出所有极长回文子串，再将找到的回文子串的hash值存起来，按长度顺序枚举每个串，看这个串去掉两头新产生的串是否存在，存在就可以退出，不存在把新串加入集合。 这样就能得到一个$O(n\log n)$的算法，但需要hash的辅助。 可以看出所有的回文子串可以构成一个树的结构，如果$S = \alpha T\alpha$，$\alpha$为任意一字符，就让$T$成为$S$的父亲。除此之外还需要两个辅助的串，分别是偶数长度回文串与奇...

SRM641 Easy 貌似原点不被包含要更好统计一些。枚举一个点A，再看剩下的点在OA这个向量的哪一侧，这样如果剩下选的两个点都在OA的同一侧，O是不被包含在里面的。 Medium 特判一下答案为0的情况。然后状态之间可以归类为偶数位置上有多少个大于n/2的数字，BFS即可。 SRM642 Easy 时间范围只有$10^5$，巴士只有100个，直接DP可以接受。 Medium 费用流，需要比较精巧的建模简化。 暴力的话就是建个二分图，左边n个点，右边m*time个点，边的数量级是$O({150}^3)$，怎么可能过啊。 经过仔细的简化后，可以成为$O(n+time+m)$个点，$O({150}^2)$条边的网络，费用流就可以轻松跑了…… SRM643 Easy 现将...