CVBB ACM Team

A

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

题意:给出学校坐标$(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})$

题解:设$g(x)$是$x$在$path(1),path(2), \dots ,path(n)$中的出现次数，通过递归可以求出任意的$g(x)$。打表可以发现分奇偶后$g(x)$是单调不增的，因此可以二分。但是直接递归会tle，需要更快的方式求出$g(x)$。~~找了一万年规律没找出来。~~看题解后恍然大悟，其实$f(x)$操作可以理解为在二进制下的操作（将最低位的$1$变成$0$，右移一位）。因此可以将$x$写成二进制，如果$x$是奇数，例如$101$，那么$101$会出现在所有$\le n$且形如$101 \dots$的数的$path$中；如果$x$是偶数，例如$100$，那么$100$会出现在所有$\le n$且形如$100 \dots$与$101 \dots$的数的$path$中。问题转变为，已知二进制位最高的几位，在低位任意加数字，求有多少$\le n$的数。只需要枚举二进制下增加的位数，设增加的位数是$k$，则对答案的贡献为$min(2^k, n - x \cdot 2^k + 1)$。

题意:一共有$n$个上课的学生。一共有三门课，每个学生会只上其中的$1-3$门，按照它们上哪些课将它们分为七组，告诉你每组各有多少人。现在要将这$n$个学生分为两组，上某一门课时，第一组学生里面上这门课的要到这一门课的第一教室，第二组学生里面上这门课的要到这一门课的第二教室。现在给出这六个教室的容量，问有没有一种合适的分组方式使得上课时所有教室都不会被挤爆。$(0 \le n \le 3000)$