CVBB ACM Team

题意:大水题

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

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

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

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

题解:按照不等式建出有向图，如果有环显然无解，因为自己不能小于自己。按照$1$到$n$的顺序遍历每个点，如果这个点能到达的某个点或能到达这个点的某个点已经被访问过了，那么显然这个点不能任意了，否则可以任意。因此先判环，然后建正图和反图，分别dfs即可。注意vis数组对于正图和反图要分别建，比赛的时候合一起就WA了，因为在正图被访问的时候并不能继续访问反图里面能访问的点。

题意:给出一个序列$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$，否则二分的值可以更小。