1 CF1861F
考虑对于每个玩家 \(i\)，枚举其最大值的花色 \(j\)，那么显然要尽可能把花色 \(j\) 的给他，求出每个人最终的牌数 \(x\)，再求出每个人需要拿的牌数 \(c_i\)，那么能给 \(i\) 的个数即 \(\min(b_j,c_i)\)。那么我们只需要最小化 \(y\) 即可。考虑二分答案 \(m\)，如果其他有任意一个 \(a_{i,j}>m\) 显然无解，否则考虑最大流：\(s\) 向花色 \(i\) 连边，流量为 \(b_i\)，花色 \(i\) 向玩家 \(j\) 连边，流量为 \(m-a_{j,i}\)，玩家 \(j\) 向 \(t\) 连边，流量为 \(c_j\)，有解等价于最大流为 \(\sum c_j\)。显然不能跑网络流，考虑将最大流转化为最小割，那么枚举花色的集合使得其与 \(s\) 断开，然后对于每一条没有断开的 \(s\rightarrow i\rightarrow j\rightarrow t\)，只能断后面两条边，对于每个 \(j\) 考虑，其要么分给 \(s\) 要么分给 \(t\)，最小代价即 \(\displaystyle\min(c_j,\sum_{i\rightarrow j}m-a_{j,i})\)，把所有 \(j\) 按照 \(\displaystyle c_j+\sum_{i\rightarrow j}a_{j,i}\) 排序后预处理前缀和不难计算。时间复杂度 \(\mathcal O(nk2^k\log^2 V)\)，其中 \(k=4\)。
2 CF2034H
显然一个数 \(x\) 不能被若干个数表示出来当且仅当这些数的 \(\gcd\) 不整除 \(x\)。那么一个集合 \(S\) 满足条件当且仅当 \(\forall i\in S,\gcd(S)\neq \gcd(S\setminus \{i\})\)。考虑每一种质因数 \(p\)，假设集合中所有数 \(v_{p}(x)\) 构成了 \(a_{1\sim k}\)，那么如果这个数组中有 \(\ge 2\) 个最小值那么 \(p\) 将不会使任何一个 \(i\) 合法。所以只能有一个最小值，此时会让这个最小值合法。显然这种 \(p\) 至少有 \(|S|\) 个，因为 \(2\) 到 \(17\) 所有质数乘起来 \(>10^5\)，那么 \(|S|\le 6\)。考虑暴搜，记 \(\displaystyle x=\prod_{i=1}^{|S|}p_i^{\alpha_i}\)，其中每一个 \(p_i\) 都是有用的，且 \(p_i^{\alpha_i}<p_{i+1}^{\alpha_{i+1}}\)，先假设 \(|S|>2\)，那么必然有 \(p_1^{\alpha_1}\le \sqrt V\)，且后面的乘积 \(\le V\)，枚举 \(p_1^{\alpha_1}\) 然后暴搜即可。记 \(y=p_i^{\alpha_i}\)，\(x\) 合法当且仅当 \(\forall 1\le i\le|S|，f_x>f_{x/y}\)，其中 \(f_i\) 表示 \(a\) 中是 \(i\) 的倍数的数的个数。适当剪枝即可通过。
3 P13694
假设现在已经确定了 \(p\) 的一段前缀，那么这段前缀在每个 \(q\in T\) 中的构成都将会是一段前缀加上一段区间，即 \([1,i]\cup[l,j]\)，其中 \(l\) 就是分割点。那么有一个朴素的 dp 是记 \(f_{i,l,j}\) 表示 \(p\) 在 \(T_1\) 中的构成为 \([1,i]\cup[l,j]\)，每次可以将 \(i\) 加 \(1\) 或者将 \(j\) 加 \(1\)，然后判断在 \(T_{2\sim m}\) 中是否合法即可。但是有个很大的问题就是有可能在加数的过程中 \(T_{2\sim m}\) 的某个排列中满足 \(i=l-1\)，此时就不能分清这是一段前缀还是前缀拼上区间了，而如果是前者则是可以在后面跳着插的，后者则不行。也就是我们要确定 \(T_{1\sim m}\) 所有排列的分割点，对于有多个分割点的情况，我们钦定第一次跳着插的地方为分割点。考虑直接暴搜，也就是先确定 \(p_1\)，对于所有 \(T_{i,1}\neq p_1\) 的 \(i\) 它们的分割点已经确定，然后再确定 \(p_2\)，直到所有分割点都确定为止。注意在确定 \(p_i\) 时也需要满足所有已经确定分割点的 \(T_i\) 的限制，这样可以证明至多有 \(\mathcal O(n^2+nm)\) 种不同的分割点，直接对于每种分割点跑上面的 dp 即可。我写的应该是 \(\mathcal O(n^4m+n^3m^2)\)，不知道怎么过的，但就是过了。