CVBB ACM Team

题意:大水题

题解:练习英语阅读和手速。

题意:给出$n(n\le100)$个长度为$m(m\le50)$的字符串，求选出任意个任意排序所组成的最长回文串。

题解:数据范围很小，直接两两暴力匹配，然后最中间再放一个没匹配上的回文串（如果有的话）。

题意:店里初始温度为$m$，有个空调每分钟可以升高$1°C$或降低$1°C$或不变，一共有$n$个客人，每个客人会在第$t_i$分钟到达，他要求到达时刻店里温度的范围为$[l_i,r_i]$，问能否让每个客人都满意。

题解:求出每个时刻可能的温度范围，如果和某个客人的要求交集为空，则无法满足，否则可以满足。更新范围时，两个客人间的间隔可以让$L$增加$R$减少对应的时间间隔，客人来时和客人的要求范围取交集。

题意:给出一个序列$a_i$，求序列$b_i$使得$\sum\limits_{i=1}^n b_i(a_i-b_i^2)$的最小值，其中要求$0\le b_i \le a_i$且$\sum\limits_{i=1}^n b_i=k$。

题解:对于某一个$i$，当$b_i$为$x$时，如果令其加$1$，对答案的贡献为$\Delta_i (x):=\left[x(a_i-x^2)\right]-\left[(x-1)(a_i-(x-1)^2)\right]=a_i-3x^2+3x-1,$，可以看到这个二次函数是开口向下而且顶点横坐标在$\frac{1}{2}$，因此在本题定义域中是严格单调递减的。我们可以让所有$b_i$为$0$，然后贪心地看给哪个$b_i$增加$1$的贡献最大就增加哪个。由于$k$太大，因此我们二分每次增加$1$所产生贡献的最小值，对于要验证的值，再套一个二分（或者解方程）算每个$bi$可以加几次，保证总和大于等于$k$，最后如果总和超出$k$，一定可以将多余的增加值等于二分出来的值的$b_i$减少$1$，否则二分的值可以更小。