CF 1381A1 Prefix Flip (Easy Version)

* 分类：思维 * 题意：给定一个01字符串，每次可以选择一个$x$，然后操作。操作方法为把该字符串的$x$前缀全部反转（0变成1, 1变成0），然后翻转（首尾交换）。目标是使该字符串变成另外一个01字符串。要求给出翻转方案。字符串的长度为$n（n \leq 1000）$，操作次数不超过$3n$。 * 思路：很明显是要从后往前满足。考虑第$i$个位置，如果已经一样了就可以不用管，如果不一样那么它将会由第一个位置得到。所以如果第一个位置和当前一样，首先要操作前缀1使得第一个和点前$i$的不一样，然后再操作前缀$i$就可以满足$i$了。

CF 1382D Unmerge

• 分类：dp 背包
• 简要题意： 询问是否可以将原序列分成两个长度相等的序列（相对顺序不变），使得按照归并排序里的merge操作过后，还是原序列。
• 解法： 依次寻找当先序列中的最大数，记录其到结尾的长度，并截断。最后转换成背包问题，判断是否存在一些长度的和恰好为n。

Boundary

分类：计算几何

题目大意：考虑所有经过原点的圆，在所给$n$个点中，找出在同一个圆上最多的点的数量。

思路：一开始因为测试用例，我错以为是以所给的点中选择一个点作为圆心，之后就一直错。其实圆心不局限在所给点中，只要圆经过所给点即可。利用圆周角的思路。先枚举所有的点$A$，然后在每一次枚举中在枚举一遍所有的点$B$，计算圆周角$ABO$的cos值，寻找出众数的数量。在每一次枚举的众数的数量，寻找最大的那一个即可。

在寻找众数的时候，我是利用了sort()来找。同时本题在计算圆周角的时候，需要注意$B$点可能会在$AO$的任意一边，所以要用叉积判断一下，然后利用内接四边形对角互补来处理一下，即把cos值取负。最后，还需要注意共线点的处理，例如(0,1)，(0,2)的答案应该为1。

• AIsing Programming Contest 2020

* CF 658

• AIsing Programming Contest 2020