TC SRM641~650
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
现将原数用$10^6$以下的质数分解，对于剩下的数，肯定是p个大于$10^6$的质数的乘积。
因为原质因子分解已经给出了一半，所以如果p>1，至少还有p/2个大于$10^6$的质因子。故p只能为1。
Medium
如果两个串都没有H那就返回-1。 如果上下两个串是相等的，则答案为单串中S的个数。
则对于剩下的情况，最优方案中肯定有一种是把某一行全部变H，再用这一行影响另一行。
设f[i]为把上面一行的前i个都变成H的最小步数。
f[i]可从f[i-1]右移得到，也可以通过多个另外一行的H上移得到。所以剩下的就是一个DP了。同理求出g[i]定义变成下一行的前i个，答案为min(f[i] , g[i]) + 1。
SRM644
Easy
枚举最大的价值是多少，剩下的用组合数统计。
Medium
DP，构出$2^6$阶的矩阵来加速转移。
SRM645
Easy
竟然是一道和蔼可亲的贪心题，每次找没搞定的结束位置最靠前的区间，在找一个能覆盖它的结束位置最远的区间来覆盖它即可。
Medium
点$(x,y)$以点$(A,B)$做中心对称，会到$(2A-x,2B-y)$。
点$(x,y)$以点$(A,B)$做中心对称，再以点$(C,D)$做中心对称，会到$(2(C-A)+x,2(D-B)+y)$。
可以看出这里$x,y$的系数只会都是1或者都是-1。所以第一步要看两个点集是否能平移成全等。或者枚举第一步是哪个轴，新产生的点再看是否全等，剩下的就是平移的问题，一共四种情况。
这样的话就可以转化为求一个方程是否有整数解，有三个变量，分别代表使用轴01，使用轴02，使用轴12的次数。轴12的效果显然就是前两个的叠加，这样就只剩两个变量了，可以直接解出是否存在整数解，注意有无解或者秩为1的可能。
SRM646
Easy
排个序，那肯定是连续一段的K个数变成连续的K个数，至于连续的K个数是哪个列出式子就能看出是在求一个中位数。
Medium
离散化是必须的，我是把每个障碍以及周围的八个点都拿了出来，这样路径要么是在这些点之间一步一步移动，要么是沿着x轴的正方向直线走过去直到碰到一个关键节点为止。
SRM 647
Easy
坐标范围比较小，暴力计算出每个坐标高度的上界。
Medium
首先按油量递增的顺序派出，第i个人的油量只能给第i+1个人，所以可以直接计算出最优的情况。就可以DP了。
Hard
如果没有“恰有一条”的限制，就是一个普通的最小割。所有从S到T的路径，求出割边后路径上的点所属的集合必然是SSTTTTS….SSTTTTT这样。中间经历了奇数次转换。而加上限制之后，只允许有一次转换，即SSSTTTT。其实就是禁止了”TS”的出现，即如果有一条$u$到$v$代价为$w$的边，还需要加一条从$v$到$u$代价为无穷大的边，表示割掉这条边的代价为正无穷，从而禁止了”TS”的出现。
SRM648
Easy
直接构造不是非常好想，DP简单粗暴。
Medium
非常有趣的题，首先枚举最大值取了多少个，一个要点是取最多的物品和最少的物品数量不会超过30，所以最大值取的数量应该是在${N \over K} \pm 50$左右。
枚举了之后再去二分第K小值是哪个物品，用不大于这个物品价值的有多少个去check，这个求法也很简单，枚举这个物品取了多少个，再解出物品价值的范围。求出不大于这个价值有多少个后，再去计算等于这个价值有多少个。就可以判断出第K小是否在这个区间里面。
Hard
求N个点构成的无向图其中有K个桥的有多少种，K个桥意味着整个图构成K+1个双联通分量再用这K个桥构成一棵树。
SRM649
Easy
枚举任意两个相同字母的位置，子序列会重复当且仅当两个字符两边的字符数量不小于n-K-1。
Medium
每一位单独考虑，第k位的取值只影响前几位相同但第k位不同的数之间的大小关系。所以可以直接计算出每一位是取0好还是取1好，将最大值累计到答案。
SRM650
Easy
考虑每一个间隙能让重复数量最少的方案数量，累乘起来。
Medium
一个很自然的想法是枚举删去哪三条边然后判断剩下的图是不是一棵满二叉树，但那样肯定是要爆炸的。明显原图中是桥的边是不能被删的，找出所有不是桥的边，只要从它们中选三条边再判断即可。由于图的直径很小且只有三条非树边，非桥边的数量不会超过过60。
Written with StackEdit.