T1
懒得写。
T2
同。
T3
我们发现直接做是不太好做的。
我们考虑 \(n = 2\) 的做法，很自然地将所有数取出来放进一个数组 sort 一下然后看相邻且不属于一个序列的数。
于是推广，我们就将原问题转化成了这么一个问题：求一个数组的一个子串满足对于每一个序列（即，原题中的班级），该子串中含有至少一个来自该序列的数，且字串的极差最小。
这个问题是很经典的，我们直接双指针做就行了。
#include <bits/stdc++.h>
#define llong long long
#define N 1005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}pair<int, int> a[N*N];
int cnt[N], ccnt;
int n, m, ans = 1e9+7;int main(){read(n, m);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)read(a[(i-1)*m+j].first), a[(i-1)*m+j].second = i;sort(a+1, a+n*m+1);for(int i = 1, j = 1; j <= n*m; ++j){if(cnt[a[j].second] == 0) ++ccnt;++cnt[a[j].second];while(ccnt == n){ans = min(ans, a[j].first-a[i].first);if(cnt[a[i].second] == 1) --ccnt;--cnt[a[i].second], ++i;}}printf("%d", ans);return 0;
}T4
很容易想到把两种团队分开处理。
然后我们用 \(w = 1\) 的团队把 \(w = 0\) 的团队割成若干段，我们需要对于每一个段找到第一个大小不大于 \(b\) 的 \(w = 0\) 的团队。由于团队间的相对顺序不会改变，我们直接使用线段树二分来做这件事。然后如果在段内没有找到符合条件的团队，我们就处理段尾的 \(w = 1\) 的团队。我们可以用堆来维护这些 \(w = 1\) 的团队。
摊还分析一下可得时间复杂度为 \(\mathrm{O}(\log n)\)。
#include <bits/stdc++.h>
#define llong long long
#define N 200005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}constexpr llong inf = (llong)1e18+3;
typedef pair<int, llong> Node;int n, q;
int vis[N];llong val[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)inline void pushup(int x){val[x] = min(val[ls(x)],val[rs(x)]);return;
}
inline void addtag(int x, llong k){val[x] = k;return;
}inline void modify(int pos, llong k, int x = 1, int l = 1, int r = q){if(l == r) return addtag(x, k);if(pos <= mid) modify(pos, k, ls(x), l, mid );else modify(pos, k, rs(x), mid+1, r);pushup(x);return;
}
inline Node query(int L, int R, llong k, int x = 1, int l = 1, int r = q){if(val[x] > k || L > R) return {1e9+7, 0};if(l == r) return {l, val[x]};if(R <= mid) return query(L, R, k, ls(x), l, mid );if(L > mid) return query(L, R, k, rs(x), mid+1, r);if(val[ls(x)] <= k) return query(L, R, k, ls(x), l, mid );else return query(L, R, k, rs(x), mid+1, r);
}priority_queue<Node, vector<Node>, greater<Node> > pq;
vector<Node> ans;int main(){read(q);for(int i = 1; i <= (q<<2); ++i) val[i] = inf;for(int t = 1; t <= q; ++t){int op; llong x, y;read(op);if(op == 1){read(x, y), ++n;if(y == 0) modify(n, x);else pq.emplace(n, x);}if(op == 2){read(x);vis[x] = true;modify(x, inf);}if(op == 3){read(x);int now = 1;while(x && pq.size()){Node res = query(now, pq.top().first, x);while(res.first < 1e9){x -= res.second;modify(res.first, inf);now = res.first+1;ans.push_back(res);if(!x) goto output;res = query(now, pq.top().first, x);}res = pq.top(); pq.pop();if(vis[res.first]){now = res.first+1;continue;}if(x >= res.second){x -= res.second;ans.push_back(res);if(!x) goto output;}else{ans.emplace_back(res.first, x);pq.emplace(res.first, res.second-x);x = 0;goto output;}}if(x){Node res = query(now, n, x);while(res.first < 1e9){x -= res.second;modify(res.first, inf);now = res.first+1;ans.push_back(res);if(!x) goto output;res = query(now, n, x);}}output: printf("%d\n", ans.size());for(auto i : ans) printf("%d %lld\n", i.first, i.second);ans.clear();}}return 0;
}T5
记得还是普及组小朋友的时候做过一道题，是这题的 Subtask1 且不用输出方案。
那么当 \(c = 1\) 时，对于这 \(2n\) 个点间的 \(2n-1\) 条线段，一条线段被经过的次数即为两边的厂矿数量之差。
扩展到 \(c \in \mathbb N^+\)，设两边厂矿数量差为 \(k\)，则该线段被经过的次数为 \(\lceil \frac{k}{c} \rceil\)。于是我们做完了第一小问。
对于第二小问，我们考虑上结论在题目中的实际意义，于是很容易得出具体的构造方案，详见代码。
其实是可以做到 \(\mathrm O(n \log n)\) 的，但是我懒就写的 \(\mathrm O(n^2)\)。
#include <bits/stdc++.h>
#define llong long long
#define N 1005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, c;
int a[N], b[N];
int tmp1[N<<1], tmp2[N<<1], typ[N<<1];
llong ans;int main(){read(n, c);for(int i = 1; i <= n; ++i) read(a[i]), tmp1[ i ] = a[i];for(int i = 1; i <= n; ++i) read(b[i]), tmp1[i+n] = b[i];sort(tmp1+1, tmp1+n*2+1);for(int i = 1; i <= n; ++i){++tmp2[a[i] = lower_bound(tmp1+1, tmp1+n*2+1, a[i])-tmp1], typ[a[i]] = 1;--tmp2[b[i] = lower_bound(tmp1+1, tmp1+n*2+1, b[i])-tmp1], typ[b[i]] = 2;}for(int i = 1; i <= n*2; ++i) tmp2[i] += tmp2[i-1];for(int i = 1; i <= n*2; ++i)ans += (tmp1[i+1]-tmp1[i])*((abs(tmp2[i])+c-1)/c);printf("%lld\n", ans);for(int i = 1; i <= n*2; ++i){if(tmp2[i] > 0){int j = i;while(tmp2[j]) ++j;for(int k = i; k <= j; ++k){if(typ[k] == 1 && tmp2[ k ] <= c) printf("%d ", tmp1[k]);if(typ[k] == 2 && tmp2[k-1] <= c) printf("%d ", tmp1[k]);}for(int k = i; k <= j; ++k)tmp2[k] = max(tmp2[k]-c, 0);}if(tmp2[i] < 0){int j = i;while(tmp2[j]) ++j;for(int k = j; k >= i; --k){if(typ[k] == 1 && tmp2[k-1] >= -c) printf("%d ", tmp1[k]);if(typ[k] == 2 && tmp2[ k ] >= -c) printf("%d ", tmp1[k]);}for(int k = i; k <= j; ++k)tmp2[k] = min(tmp2[k]+c, 0);}}return 0;
}