写在前面
- 只记录模拟赛 Div1 的题。专题授课的题实在是太多了。
- 能找到原题的都标了。
- 如你所见，作者实力有限，所以很多 T3 都没有写（所以神犇们可以不用看了）。以后可能会考虑补。
- 有问题的可以写在评论区或者私信。
Day1 模拟赛
A.最小生成树
原题：Spanning Tree Game。
Tip：注意原题与这题的数据范围的差别。
题意
给一张 \(n\) 个点，\(m\) 条边的无向图，每条边有两个可能的权值 \(a_i,b_i\)，你需要对所有 \(k\in [0,m]\) 求出，当恰好有 \(k\) 条边的权值是 \(a_i\)，\(m-k\) 条边的权值是 \(b_i\) 时，该图的最小生成树的边权和的最大值是多少。
数据范围：\(n\le 9,n-1\le m\le 100,a_i,b_i\le 10^8\)，保证图连通且无自环，不保证没有重边。
题解
考虑 Kruskal 的流程。
将每条边拆成两条边 \((x,y,a)\) 和 \((x,y,b)\)，我们称他们互为对应边。
然后把这 \(2m\) 条边按照边权升序排序。
依次考虑每条边 \((x,y,w)\)。
- 他的对应边还没有出现过，那么这条边选不选都可以（不选的话就代表这条边选了另一个边权），选的话如果此时 \(x,y\) 不连通就把 MST 的边权和加上 \(w\)。
- 他的对应边出现过了，那么如果 \(x,y\) 不连通这条边就一定要选，并把 MST 的边权和加上 \(w\)，否则这条边选不选都不影响 MST。
所以设 \(f_{i,j,S}\) 表示考虑了前 \(i\) 条边，图的连通性的状态是 \(S\)，有 \(j\) 条边边权选了 \(a\)。
转移的决策就是在第一种情况中选还是不选（注意第二种情况是不会对 \(j\) 这一维产生影响的，因为贡献在第一种情况里已经算过了），所以为了维护 \(j\) 这一维还需要记录每条边的 \(w\) 原来是 \(a\) 还是 \(b\)。
我们可以哈希并查集数组来记录这个 \(S\)。
合法 \(S\) 的数量为 \(Bell(n)\le 21147\)，所以复杂度是 \(O(m^2Bell(n))\)，但是远远跑不满。
code
[code]#include#define PII pair#define fi first#define se second#define LL long long#define ULL unsigned long long using namespace std;const int N=15,M=105,p=13331;inline int read(){ int w=1,s=0; char c=getchar(); for(;c'9';w*=(c=='-')?-1:1,c=getchar()); for(;c>='0'&&c |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
