csp-s模拟测试112 & csp-s模拟测试113

考前两天模拟。

Day1直接炸飞，T1浪费的时间太长，对拍+调试了一个多小时但复杂度还不能过，最后5分钟想出来了解决方案但是已经打不出来了。T2读入出了事故RE0。T3打了假贪心。

Day2心态几乎也是爆炸。T1做了一个小时，也没法对拍。T2调试了一个小时后发现算法伪了，瞬间崩溃。犹豫了一会去打T3，一看T3不好打，暴力也难，又回过头考虑T2，试图基环树dp。终于最后发现在环上贪心就行了不用dp，然后T2过了对拍就只剩不到20分钟了。T3 dfs难打，想骗分，最后也没骗到。

D1T1：

　　首先一个贪心思路：每次给三种颜色的气球排序，从最多的气球出$2$个，次多的出$1$个装饰一张桌子，最终特判$(1,1,1)$。暴力来是$O(N)$的。考虑优化(其实随便构造的)。先取三种气球数量$min$值，即用$(1,1,1)$装饰，把剩下两色气球充分利用(具体需要大力讨论，比较麻烦)，最后使得只剩为$(1,1,0)$或$(x,0,0)$的情况(前者无贡献)，用最后的$x$与$min$个$(1,1,1)$再凑$(1,2,0)$的情况，这样构造了最优解。复杂度$O(1)$。

D1T2：

　　有向图判环。实际考点：换行符linux下'\n'，windows下'\r\n'。其实读入时判getchar()!=' '就可以了。

D1T3：

　　考虑每一个分部的贡献。设一个任务由$cnt$个分部接管，对于每个分部，从自己到总部共$cnt-1$次，从其他部到自己共$cnt-1$次，所以一个任务的总贡献为$(cnt-1)*\sum (dis[0][i]+dis[1][i])$，那么问题转化为：集合权值为总和$\times$大小，划分集合，使得集合权值和最小。对$dis[0][i]+dis[1][i]$从小到大排序，那么选一段连续区间一定最优。就有$dp：f[i][j]$表示第i个集合划分到了$j$处的最小费用。转移：$f[i][j]=f[i-1][k]+(j-k-1)*sum(k+1,j),k<j$。是$O(N^3)$的。但是考虑每一个集合前有一个系数，这个系数越大，后面的值应小一些才优。所以最终的集合划分一定是：$(dis[0]+dis[1])$越小的一段越长。我们已经排序，所以越靠前的集合越长。所以从上一层转移，上界$k$*段数应小于$j$，这样转移一层是$\sum \limits_{i=1}^N \frac{N}{i}$的，是$N \ln N$，总复杂度$O(N^2 \ln N)$。

D2T1：

　　面积一定，越圆的东西一定周长越小（应该是个事实吧）。正六边形是面积一定时最优的。任意一种方案都可以调整为六边形。先找到能围住$N$的最小正六边形，二分边长检验$3N*(N+1)+1>=N$，当然手解不等式应该可以$O(1)$。然后缩小正六边形，墙缩小一，容积缩小$len+1$（第一次缩），$len$（再缩），然后卡住$N$就行。$O(\log N)$。

D2T2：

　　对每一个商品向它的$f[i]$连边，边权为$d[f[i]]-c[i]$，如果为负就不连（稳亏不赚）。变成几个联通块，是基环树或树。对于树上的点，他自己的数量一定是全部被最大边的一头购买最优（它的贡献只能通过被弹出来实现）。而且对于树上的点，一定可以按拓扑序，所以不用考虑顺序。对于环上的点，由于购买一件物品时先检验本品是否为空所以我们先不买断，都留一个。最后考虑一下，如果没有树边，环上的点最终一定剩下一个不被弹出，但有树边的话还可以弹出。那么在环上枚举最后（将）被弹出的点，每一种方案的贡献为换上点贡献之和-这个点的贡献+（如果这个点连了树边）这个点被树上点弹出的最大贡献。枚举复杂度是边数$O(N)$的。

D2T3：

　　暴力做法：枚举子串$p$，$dfs$不断消去子串，直到最后为空。这样用$string$比$char[]$方便，但我并不太会$string$。趁此机会学了一下。

　　正解是$dp$。同样枚举$p$串，然后区间$dp$判断。$f[i][j]$表示$s$串$[i,j]$区间能否匹配p，匹配定义为：能消完，或者消到最后剩下$p$的前缀。转移分为两种：添一个字符，添一整$p$串。仅第一种是不全的，因为无法处理$p$串插入在中间的情况，所以还要整串转移一下。总复杂度$O(N^4)$？（我并没有记忆化所以较慢，但其实很难到上界）。

　　此外调试时注意到了三目运算符$:$的两边必须是严格相同类型的，左$void()$，右边也必须是，有时候不一样了编译不报错但会RE非常难受。

巴特西