感谢一堆大佬把题带给我做。。。。。这题还是有点质量的，wzc大佬风采不减当年啊。
总结
- 我不带文件过了，结果带了文件，没有编译过，失去了100分。
- 我以为DisjointSet的getRoot操作第二次和直接引用的耗时一样，事实证明我zz了
- 第二题注意数组开两倍，因为末端点和首端点混在一起离散化的，我调试数据的时候崩溃了一次，查了半天:(
- 第三题有点难搞，但是因为这个题给的Hint比较的明显，我好边界调了半天。
动物园
题意
定义高兴值为一条路径上所经过节点的最小值，求整个图所有点的高兴值之和。
题目分析
这道题是一道很经典的最大瓶颈生成树的问题，数据范围你是无法直接枚举两个端点的，于是考虑统计每条边使用的次数，然后进行对答案的更新。
一开始写的是Prim，但是发现后面没有用Kruskal方便，就换成了Kruskal。 用了一个\(r[i]\)表示序号，防止顺序被直接改变。#includeusing namespace std;#define forn(i, n) for(int i = 1; i <= (int)(n); i++)#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)typedef long long qword;const int inf = 0x7fffffff;const int maxn = 1e5 + 10;const int maxm = maxn * 10;int a[maxn], fa[maxn];int val[maxm], r[maxm], v[maxm], t[maxm];int cnt[maxm];bool cmp(int x, int y) {return val[x] > val[y];}int getRoot(int x) {return x == fa[x] ? x : fa[x] = getRoot(fa[x]);}#define OKint main() {#ifdef OK freopen("zoo.in","r",stdin); freopen("zoo.out","w",stdout);#endif // OK int n, m; qword ans = 0; cin >> n >> m; forn(i, n) cin >> a[i], fa[i] = i; int x, y; forn(i, m) { cin >> x >> y; val[i] = min(a[x], a[y]); v[i] = x; t[i] = y; r[i] = i; cnt[i] = 1; } sort(r + 1, r + m + 1, cmp); forn(i, m) { int k = r[i]; int vv = getRoot(v[k]), tt = getRoot(t[k]); if (getRoot(v[k]) != getRoot(t[k])) { ans += 1ll * val[k] * cnt[vv] * cnt[tt]; cnt[tt] += cnt[vv]; fa[vv] = fa[tt]; } } cout << ans * 2 << endl; return 0;}
线段计数
题目分析
这道题相对于经典的线段计数问题，只是多了一个实时的添加和删除，直接套一个树状数组或者线段树就可以解决。
然后因为这个数据有点点大，于是你再套一个离散化的板子，就很简单了。然而我因为没有去重，wa了一发（实测不去重可以A3个点）
#include#include #include #include #include using namespace std;const int maxn = 500010*2;int C[2][maxn];struct Opt { int opt, x, y; void Clear() { opt = x = y = 0; }}a[maxn];int b[maxn], cnt;int c[maxn], t;void Add(int opt, int x, int v, int n) {for(;x<=n*2;x+=x&-x) C[opt][x]+=v;}int Query(int opt, int x) {int res=0;for(;x;x-=x&-x) res+=C[opt][x];return res;}int query(int x, int y) {return Query(1,y) - Query(0,x-1);}void add(int x, int y, int n) { Add(0, x, 1, n); Add(1, y, 1, n);}void del(int x, int y, int n) { Add(0, x, -1, n);Add(1, y, -1, n);}#define rep(i,s,t) for(int i=(int)(s);i<=(int)(t);++i)#define forn(i) rep(i,1,n)inline void work() { int cnt = 0; int t = 0; int n; cin >> n; forn(i) { cin >> a[i].opt >> a[i].x; if(a[i].opt == 0) { c[++t] = i; b[++cnt] = a[i].x; b[++cnt] = a[i].x + t; a[i].y = a[i].x + t; } } sort(b + 1, b + 1 + cnt); cnt = unique(b + 1, b + 1 + cnt) - b - 1; forn(i) { if(!a[i].opt) { int x = lower_bound(b + 1, b + 1 + cnt, a[i].x) - b; int y = lower_bound(b + 1, b + 1 + cnt, a[i].y) - b; cout << query(x, y) << endl; add(x,y,n); } else { int x = lower_bound(b + 1, b + 1 + cnt, a[c[a[i].x]].x) - b; int y = lower_bound(b + 1, b + 1 + cnt, a[c[a[i].x]].y) - b; del(x,y,n); } }}inline void Init() { memset(C[1], 0, sizeof(C[1])); memset(C[0], 0, sizeof(C[0]));}#define OKint main() {#ifdef OK freopen("segment.in","r",stdin); freopen("segment.out","w",stdout);#endif // OK int T; ios::sync_with_stdio(0); cin >> T; rep(i,1,T) { cout << "Case #" << i << ":" << endl; Init(); work(); } return 0;}
填数
题目分析
易知， 至少会有一行/列是空的。
我们不妨假设完全空的是一个行。我们把这行以外的元素随意填，只需满足每行的所有元素的积为−1.然后用这行来“收尾”。
显然，这一行有且恰有一种方案来填充，以满足每列的所有元素积为\(−1\)的条件。于是，我们只需计算除这行外，每行有多少方案，使得这行的元素积为\(−1\)，然后把这些结果乘起来即可。于是问题被转化为了1维上的问题。 显然，答案只与『还需要填的格子数目』和『已经填上的格子里的数的积』有关。不妨设需要填\(s\)个格子，我们暴力枚举\(k\)，表示其中\(k\)个格子填了\(−1\)（当然必须满足所有数的乘积为\(−1\)），则填法数目显然是\(\binom{s}{k}\)，其和即为答案。时间复杂度\(O(nm)\)代码太多特判，就不写上来了。