CVBB ACM Team

题意:有个人赖床，让你帮他模拟一下。

题解:写困了。

题意:给定一个由$123$组成的字符串，求最短的包含$123$的子串。

题解:写的太复杂了，处理出每个位置往左往右的第一个$123$的位置，然后进行组合。

题意:给定一个正$2n$边形，求覆盖这个正多边形的最小正方形。

题解:$n$是偶数的时候很简单，画个图只需要补全就可以。$n$是奇数的时候可以考虑对多边形进行旋转，容易注意到转$\frac{\pi}{n}$后就复原了，这中间的前$\frac{\pi}{2n}$和后$\frac{\pi}{2n}$是对称的，所以只用考虑前$\frac{\pi}{2n}$。又注意到这$\frac{\pi}{2n}$还是对称的，因此最小值是转$\frac{\pi}{4n}$取到，根据图上这个三角形可以算出答案是$\frac{\cos(\frac{\pi}{4n})}{\sin(\frac{\pi}{2n})}$。

题意:数据结构，插入删除第$k$小，空间$28MB$卡平衡树。

题解:写权值线段树。

题意:$n$个点$m$条边的图，有$n_1, n_2, n_3$个$1,2,3$，将他们放到每个点上，要求每条边相连的两个点权值相差$1$，问是否有解，如果有解则输出。$(1 \le n \le 5000, 0 \le m \le 10^5, n_1 + n_2 + n_3 = n)$

题解:$1$和$3$不能有边，因此可以合并为一类，转化为二分图染色+背包判断。因为要输出方案，所以背包dp的时候记录一下转移路径，然后最后再dfs一次为每个点赋值即可。

题意:炉石传说，有$n$个待上场的随从，任意时刻场上的随从数量不能超过$k$，每个随从至多被召唤或消灭一次，每个随从的初始属性为$a_i$，战吼是使其它在场的随从属性增加$b_i$，输出一种方案使得最后场上所有随从属性之和最大。$(1 \le k \le n \le 75)$

题解:贪心地想，最优方案一定是每个随从一定会上场，而且是先铺满场上，然后在一个格子里面不断换随从。那么只需要确定上场顺序即可，转化为费用流匹配问题。源点连$n$个随从，$n$个上场顺序连汇点，然后每个点向对应的上场顺序连边，费用为对最终答案的贡献。所有费用取负跑最小费用最大流即可。输出方案只需要枚举$n$个随从对应的点出边流量即可。

题意:交互题。有$n$个盒子，其中$k$个里面有石头，其它是礼物，石头的重量严格大于礼物。最多询问$50$次，每次询问两个不相交子集盒子的重量和的大小关系，最后需要输出下标最小的礼物编号。$(2 \le n \le 1000, 1 \le k \le \frac{n}{2})$

题解:观察到$k \le \frac{n}{2}$，因此我们随机$30$次第一个盒子和任意一个其它盒子的大小关系，如果一直都是第一个盒子重，那么第一个盒子可以认为就石头了，错误的概率是$\frac{1}{2^{30}}$，可以接受；如果有一个盒子比第一个盒子重，那么第一个盒子就是礼物，直接输出即可。现在我们知道第一个盒子是石头了，那么就可以二分找出最靠左的一个含礼物的区间，然后再二分这个区间找到最靠左的礼物。一共需要操作$30+10+10$正好$50$次。