CVBB ACM Team

题意:水。

题解:摸。

题意:给出一个长度为$n$的$01$字符串，每次操作可以选择两个相邻字符将他们变为相反的字符，问能否不超过$3n$次操作使得所有字符相同。

题解:充要条件是有一种字符出现次数是偶数次，将字符串分为不重叠的数段，每段都以该字符串为开头结尾，然后每段除了最后一个字符串以其它字符为开头都操作一遍就可以全变成另一个字符。否则如果两种字符出现次数都是奇数次，这样操作后一定会只剩一个与其它不同的，此时怎么变都无法变成全一样，因此无解。

题意:给出学校坐标$(s_x,s_y)$，每个学生坐标$(x_i,y_i)$保证不和学校重合，坐标均为整数，每个学生都会走曼哈顿距离去学校，现在求一个坐标（不能是学校），使得尽量多的学生到学校的最短路经过这个点。

题解:因为都是走的曼哈顿距离，所以每个学生最后一步经过的点一定是学校上下左右四个点，统计每个学生能经过哪些点：如果和学校某一个坐标相同则只经过一个方向，否则经过两个方向。然后选择数量最多的那个方向即可。

题意:按顺序进攻每个城池，一共有$n$个城池，一开始有初始兵力$k$，打第$i$个城池要$a_i$兵力，每次攻破一个城池可以获得$b_i$兵力。每个城池可以被占领，每次可以将一个单位的兵力放到当前的城池进行占领，同时每个城池有数个传送门，每个会连接一个之前已经攻破的城池，可以将一个单位的兵力放到传送门连接的城池进行占领，每个城池占领后获得$c_i$分数。现在问打完所有城池最多能获得分数，或判断无法攻破所有城池。$(1 \le n \le 5000, k + \sum\limits_{i = 1}^{n} b_i \le 5000)$

题解:显然考虑每个城池是否要占领只用考虑最靠后的能给这个城池传送兵力的城池即可，然后就设$f_{i,j}$为打到第$i$个城池兵力为$j$时的最高分数，直接按题意dp即可。

题意:对一个数不断施行如下操作，$\begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix}$，直到变成$1$，中途所有经过的数字组成的序列称为$path(x)$，例如$path(15) = [15, 14, 7, 6, 3, 2, 1]$。现在求一个最大的$x$，使得它在$path(1),path(2), \dots ,path(n)$中至少出现$k$次。$(1 \le k \le n \le 10^{18})$

题解:

题意:

题解: