本Markdown编辑器使用[StackEdit][6]修改而来，用它写博客，将会带来全新的体验哦：
A(chy) csuoj 1828 模拟。
D(chy) csuoj1831 矩阵快速幂。 n<=10.所以状态数 x <= 100.复杂度是n^6logT。 A[i][j]表示上一次的状态j对当前状态i的贡献。将两人在同一点的状态对任意状态的贡献标记为0。 x*1的矩阵B[i][0]表示 状态i的初始数量。 这样A^(T-1)*B可以算出第T-1次时各状态对应的次数。 枚举得到第T次时相遇的状态数。
F(chy) csuoj 1833 DP。dp(i,0)表示前i个不选第i个的max。dp(i,1)表示前i个选第i个的max。
G(ly) csuoj 1834 判断欧拉回路/通路 加并查集。 用并查集计算连通块的数量，大于1输出no; 在只有一个连通块的条件下，如果度为奇数的点的个数等于0 or 2，输出yes,否则输出no。
H(cj) csuoj1835 先考虑不加任何优化的dp方法:dp[i][j]表示A[1..i]转化为B[1..j]最小代价,可由dp[i-1][j-1],dp[i-1][j],dp[i][j-1]转移过来,分别对应替换、删除、插入 n^2的时空复杂度,不可接受 回头看条件k<=100,同时插入、删除操作每次花费>=1,再考虑到替换操作是不会改变s和t的长度差的,而结果要两者长度一样。所以如果A[1..i]转化为B[1..j],A[i]选择提替换成B[j],同时i和j距离大于k的话,意味着这次操作后,还要至少有k次的插入和删除操作才会把两者长度变成一样 综上所述,对于A中的每一个i,跟他关联的j只有[i-k,i+k] 最后滚动数组压缩空间
J(ly) csuoj 1837 对每棵树，先找到其重心（可能有两个），然后树hash，将hash值存入map; 最后处理出结果即可。 树hash不同于普通的同构树hash，因为有双向的边权值，所以要求hash值时，要注入边权值后计算。
K(ly) csuoj 1838 1.O(n)扫一遍，找出每个单位区域内的最高水位high[i]。 2.O(n)从左往右扫，用单调栈（栈底最大）记录递减序列，计算出left数组，left[i]表示第i面墙和第i+1面墙中间放水泵，从第i面墙左边能流过多少单位水。 3.同2，从右往左扫，计算出right数组。 4.在第i面墙和第i+1面墙之间放水泵，能流出的水的面积就是high[i]+left[i]+right[i+1]； 求出最大的即可。 样例数据： 墙： 3 4 2 3 5 2 1 4 3 2 high: 3 4 4 4 4 4 4 3 2 left: 0 0 2 2 0 2 5 0 0 0 right: 0 0 3 1 0 4 3 0 0 0 结果： 3 7 7 6 8 9 9 3 2 L(chy) 一维转二维。 建立坐标系：纵轴表示时间，横轴表示位置。原点表示0时刻在起点。 每个trap对应横坐标[s1,s2]上的无穷多个间隔为b长度为a的矩形。 从原点出发向每个矩形的左上角和右下角引射线。 所引射线中不通过任意矩形且斜率最大的即为所求。 当对第i个矩形的左上角所引射线的斜率大于对第i+1个矩形右上角所引射线的斜率，此时是斜率的上限，也即速度下限。 枚举速度并验证即可。