CodeForces – 1089A Alice the Fan
题意：两个人打BO5的比赛。在一场比赛中，如果A得到k分，B得分小于等于k-2，则比赛结束，A赢，否则继续比赛，直到两人分数差距大于等于2。前4局比赛k=25，第5局为15。现在已知两人每局的得分之和(X:Y)，求A能够拿到的最好的大比分（即A如果能赢的话，要赢得最多，否则让A输的最少）。数据范围200
题解：dp是比较明显的。f[i][j][l][r]代表A拿到i分，B拿到j分，目前大比分为l:r是否可行，转移:f[i+k][j+t][l+1][r]=f[i][j][l][r] t<=k-2(这是A拿到k分时B的分数小于等于k-2)
f[i+t][j+t-2][l+1][r]=f[i][j][l][r] k<t<=X(A拿到k分以上，两人非常胶着，最后A赢了)
另一个方程同理，把A换成B就行。
需要注意的问题是3:0比赛就结束了，有一些不合法状态，我的做法是只枚举合法状态。
HYSBZ – 1937 Mst 最小生成树
题意：中文
这个题其实现在也没太懂。我们知道，如果一条非树边(u,v)如果不是最小生成树上的边，那么对于树上路径u->v上的所有边的边权都应该小于(u,v)的边权。我们设边权修改为d，则：
w树-d树<= w非树+d非树 移项:
d树+d非树>=w树-w非树 把w换一下变成C
即为: d树+d非树>=C
一开始我想转化成线性规划做网络流。。但是失败了。。
在KM算法中，我们需要满足对每条边a-b，l(a)+l(b)>=v(a,b)，然后不断调整l(a),l(b)，最终得到完美匹配，这个和这道题非常相似，所以可以直接跑二分图最大匹配，费用流即可。
CodeForces – 1089K King Kog’s Reception
题意：有一个公主想见国王，但是想见国王的人很多，所以得排队。一开始队列里没人，现在有q个操作。
+ t d操作：一个骑士在时间t进入队列开始排队，他需要和国王见面d分钟
-i操作：第i号骑士取消排队
? t操作：如果公主在时间t进入队列，那么她需要等待多久才可以见到国王？
题解：这一看就是一道线段树，我们先考虑询问。公主的等待时间只跟[1,t-1]之间加入的骑士有关。那么我们维护的东西就很显然了：
mx[l,r]: [l,r]之间所有骑士的见面结束的时间
sum[l,r]：[l,r]之间所有骑士的d之和
那么 mx[l,r]=max(mx[l,mid]+sum[mid+1,r],mx[mid+1,r])
询问时需要注意，不能按原来的套路询问，因为mx[l,t]和mx[t+1,r]这两个区间的合并需要讨论。由于每次询问都是从1开始，我们一直每次向左询问就行。
Hidden Message CodeChef – CLHMSG
题意：给出一个编码方式：a为1，b为10，c为11（即为数字编号的二进制表示），例如code编码为111111100101。而111111100101对应的字符串不唯一，gcya，acacde等都可以编码为111111100101。
现在给出一段编码S和一段字符串t，求t在S对应的所有字符串中出现了多少次。
题解：这个问题可以拆分成两个子问题：
- t对应的编码T在S中出现了多少次？
- 如果固定了T在S中出现的位置，那么S有多少种解码方案？
问题1可以用kmp或者哈希来解，不说了。问题2用dp：
设f[i]为S的前i个字符对应的字符串数量，g[i]为S中[i,n]这些字符对应的字符数量。
f[i]=∑f[i-t] t为26个字母所对应的编码长度，并且满足[i-t+1,i]这一段编码符合要求，g[i]同理，这里很简单不细说了
如果固定了[l,r]这段字符解码为t的话，可行方案就是f[l-1]*g[r+1]，统计答案即可。
The table CodeForces – 226D
题意：给出一个矩阵，矩阵的元素都是整数，并且在[-100,100]以内。有两种操作：将矩阵中一行元素全部替换成其相反数，或者将一列元素全部换为相反数。矩阵最大100*100。求一种操作方案，使得矩阵中每行每列数的和都是正数。
题解：考虑翻转一行或者一列对矩阵整体的影响。如果某一行或某一列的和为负，我翻转了它，那么整个矩阵的元素的和最少增加2。因为矩阵和最低为-10000，所以翻转几次之后就完成了。最多翻转10000次。。
Gift Pack Gym – 100889G
题意：求x^y+y&z+z^x的最大值。其中x∈[l,r] y<=a z<=b 数据范围1e18
题解：数位dp。设f[t][i][j][x][y]为前t位，其中x的第t位是否需要满足大于l,小于r y的第t位是否需要满足小于a z的第t位是否需要满足小于b
这个其实和数位dp是一样的，比如a的第t位为1 而你在第t位为y赋值为0，那么后面你就可以随便放了，怎么放都不会超过a。