T1
序列
显然每次操作保证 \(a\) 单增是假的，一定可以构造合理的操作顺序无视掉这个限制。每个位置确定划分多少次之后一定均分最优，拿个堆维护把每个东西多分一段的收益，每次选择收益最大的即可。
代码
#include <iostream>
#include <string.h>
#include <queue>
#define int long long
using namespace std;
const int P = 998244353;
int n, m;
int a[100005], b[100005], c[100005];
int cur[100005];
int ans;
priority_queue<pair<int, int> > q;
int calc(int x, int y) {x = c[x];int r = x % y;return (x / y) * (x / y) * (y - r) + (x / y + 1) * (x / y + 1) * r;
}
signed main() {freopen("seq.in", "r", stdin);freopen("seq.out", "w", stdout);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) cin >> b[i];for (int i = 1; i <= n; i++) c[i] = abs(a[i] - b[i]), ans += calc(i, cur[i] = 1) % P, q.push({ calc(i, 1) - calc(i, 2), i }), m -= (a[i] != b[i]);ans %= P;if (m < 0) return cout << "-1\n", 0;while (m) {pair<int, int> p = q.top();q.pop();ans += P - p.first % P;--m;int x = p.second;++cur[x], q.push({ calc(x, cur[x]) - calc(x, cur[x] + 1), x });}cout << ans % P << "\n";return 0;
}
T2
石头剪刀布
线段树板子。
代码
#include <iostream>
#include <string.h>
#include <array>
#include <map>
using namespace std;
int n, q;
string str;
array<int, 3> p[6] = {{ 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 }
};
inline int _p(array<int, 3> x) { return x[0] * 2 + (x[1] > x[2]); }
// 012, rsp
array<int, 3> operator+(array<int, 3> x, array<int, 3> y) { return { y[x[0]], y[x[1]], y[x[2]] }; }
array<int, 3> tmp[6];
int f(int x, int y) { return ((x + 1) % 3 == y) ? x : y; }
struct Segment_Tree {array<int, 3> S[800005][6], tg[800005];void tag(int o, array<int, 3> v) {for (int i = 0; i < 6; i++) tmp[i] = S[o][i];for (int i = 0; i < 6; i++) S[o][i] = tmp[_p(v + p[i])];tg[o] = tg[o] + v;}void pushdown(int o) {if (tg[o] == p[0]) return;tag(o << 1, tg[o]);tag(o << 1 | 1, tg[o]);tg[o] = p[0];}void pushup(int o) { for (int i = 0; i < 6; i++) S[o][i] = S[o << 1][i] + S[o << 1 | 1][i]; }void Build(int o, int l, int r) {tg[o] = p[0];if (l == r) {int x = str[l] - 'A';for (int i = 0; i < 6; i++) S[o][i] = { f(0, p[i][x]), f(1, p[i][x]), f(2, p[i][x]) };return;}int mid = (l + r) >> 1;Build(o << 1, l, mid);Build(o << 1 | 1, mid + 1, r);pushup(o);}void Change(int o, int l, int r, int L, int R, array<int, 3> v) {if (L <= l && r <= R) return tag(o, v);pushdown(o);int mid = (l + r) >> 1;if (L <= mid) Change(o << 1, l, mid, L, R, v);if (R > mid) Change(o << 1 | 1, mid + 1, r, L, R, v);pushup(o);}array<int, 3> Query(int o, int l, int r, int L, int R) {if (L <= l && r <= R) return S[o][0];pushdown(o);int mid = (l + r) >> 1;if (R <= mid) return Query(o << 1, l, mid, L, R);if (L > mid) return Query(o << 1 | 1, mid + 1, r, L, R);return Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R);}
} seg;
int main() {freopen("rps.in", "r", stdin);freopen("rps.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> q;cin >> str; str = ' ' + str;seg.Build(1, 1, n);while (q--) {int op, l, r;char x, y;cin >> op >> l >> r;if (op == 0) {cin >> x >> y; x -= 'A', y -= 'A'; tmp[0] = p[0]; swap(tmp[0][(int)x], tmp[0][(int)y]);seg.Change(1, 1, n, l, r, tmp[0]);} else cin >> x, cout << (char)(seg.Query(1, 1, n, l, r)[x - 'A'] + 'A') << "\n";}return 0;
}
T3
蝴蝶图
设 \(G = (V, E)\) 为 \(L \cap R\) 的导出子图，那么我们考虑从 \(E\) 中的边都不连的时候往里加边。考虑 \(L\) 侧 MST 的变化。当我们加入 \(E\) 中的一些边，显然每次会删掉原来树上的一些边。那么这个时候抛开维护不谈，我们就应该注意到只有原 MST 中的边是有用的。然后再考虑有哪些边无论 \(V\) 中的联通状态如何都是一定在 MST 中的。发现如果将 \(E\) 中的边全连起来，此时还在 \(L\) 中的 MST 中的边无论如何一定在 MST 中。于是我们只需要考虑那些在第一棵 MST 中而不在第二棵 MST 中的边即可。这样的边只有 \(\mathcal{O}(|V|)\) 条，于是可以直接每次枚举贝尔数然后暴力对这些边重跑 MST。总复杂度 \(\mathcal{O}(Bell(|V|)V\alpha(|V|) + m\log m)\)，由于 \(|V|\) 很小，只有 11，因此可以通过。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
int n, m, L, R, ans = inf;
map<int, int> mp[100005];
struct Edge { int u, v, w; } e[200005];
vector<Edge> el, er;
vector<int> cap;
int bel[200005], p[200005];
int dsu[100005], td[100005];
void clear(int x) { for (; x; --x) dsu[x] = x; }
int getf(int x) { return dsu[x] == x ? x : (dsu[x] = getf(dsu[x])); }
int f[100005];
int cur[15];
struct rD {int f[100005], sz[100005];vector<pair<int, int> > s;void init(int x) { for (; x; --x) f[x] = x, sz[x] = 1; }int getf(int x) { return f[x] == x ? x : getf(f[x]); }bool Merge(int x, int y) {x = getf(x), y = getf(y); (sz[x] > sz[y]) ? swap(x, y) : void();return (x == y) ? 0 : (f[x] = y, sz[y] += sz[x], s.emplace_back(x, y), 1);}void Re(int t) {while ((int)s.size() > t) {int x, y; pair<int, int> p = s.back(); s.pop_back(); x = p.first, y = p.second;f[x] = x, sz[y] -= sz[x];}}
} dl, dr;
int rl, rr;
void work(int t) {int tl = dl.s.size(), tr = dr.s.size(), res = 0;for (int i = 1; i <= t; i++) {res += f[cur[i]];for (int j = cur[i]; j; j -= (j & (-j))) {dl.Merge(cap[63 - __builtin_clzll(j & (-j))], cap[63 - __builtin_clzll(cur[i] & (-cur[i]))]);dr.Merge(cap[63 - __builtin_clzll(j & (-j))], cap[63 - __builtin_clzll(cur[i] & (-cur[i]))]);}}if (res >= inf) return dl.Re(tl), dr.Re(tr);for (auto E : el) {int u = E.u, v = E.v;if (dl.getf(u) != dl.getf(v)) dl.Merge(u, v), res += E.w;}for (auto E : er) {int u = E.u, v = E.v;if (dr.getf(u) != dr.getf(v)) dr.Merge(u, v), res += E.w;}dl.Re(tl), dr.Re(tr);ans = min(ans, res);
}
void dfs(int x, int y) {if (x == (int)cap.size()) return work(y);for (int i = 1; i <= y; i++) {cur[i] ^= (1 << x);dfs(x + 1, y);cur[i] ^= (1 << x);}cur[++y] = (1 << x);dfs(x + 1, y);
}
int _f[200005];
signed main() {freopen("butterfly.in", "r", stdin);freopen("butterfly.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m >> L >> R;for (int i = 1; i <= m; i++) {int u, v, ww, x;cin >> u >> v >> ww;if (u == v) continue;if (u > v) swap(u, v);x = mp[u][v];if (!x) mp[u][v] = ww;else mp[u][v] = min(x, ww);}for (int i = 1; i <= L; i++) cin >> m, bel[m] |= 1;for (int i = 1; i <= R; i++) cin >> m, bel[m] |= 2, (bel[m] == 3 ? cap.emplace_back(m) : void());m = 0;for (int i = 1; i <= n; i++) for (auto v : mp[i]) e[++m] = { i, v.first, v.second };sort(e + 1, e + m + 1, [](Edge x, Edge y) { return x.w < y.w; });for (int S = 0; S < (1 << (int)cap.size()); S++) {for (int i = 0; i < (int)cap.size(); i++) p[dsu[cap[i]] = cap[i]] = ((S >> i) & 1);int tmp = __builtin_popcountll(S);for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (bel[u] == 3 && bel[v] == 3 && p[u] && p[v] && getf(u) != getf(v)) dsu[dsu[u]] = v, --tmp, f[S] += e[i].w;}if (tmp != 1) f[S] = inf;}clear(n);for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (bel[u] == 3 && bel[v] == 3 && getf(u) != getf(v)) dsu[dsu[u]] = v;}for (int i = 1; i <= n; i++) td[i] = dsu[i];for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (((bel[u] == 1 && bel[v] == 1) || (bel[u] ^ bel[v]) == 2) && getf(u) != getf(v)) dsu[dsu[u]] = v, _f[i] = 2;}for (int i = 1; i <= n; i++) dsu[i] = td[i];for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (((bel[u] == 2 && bel[v] == 2) || (bel[u] ^ bel[v]) == 1) && getf(u) != getf(v)) dsu[dsu[u]] = v, _f[i] = 2;}clear(n);for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (((bel[u] == 1 && bel[v] == 1) || (bel[u] ^ bel[v]) == 2) && getf(u) != getf(v)) dsu[dsu[u]] = v, _f[i] |= 1;}clear(n);for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (((bel[u] == 2 && bel[v] == 2) || (bel[u] ^ bel[v]) == 1) && getf(u) != getf(v)) dsu[dsu[u]] = v, _f[i] |= 1;}dl.init(n), dr.init(n);int _ = 0;for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v, t;if (bel[u] == 3 && bel[v] == 3) continue;if (_f[i] == 0) continue;else if (_f[i] == 1) (bel[u] == 1 || bel[v] == 1) ? el.emplace_back(e[i]) : er.emplace_back(e[i]);else t = ((bel[u] == 1 || bel[v] == 1) ? dl.Merge(u, v) : dr.Merge(u, v)), _ += t * e[i].w;}sort(el.begin(), el.end(), [](Edge x, Edge y) { return x.w < y.w; });sort(er.begin(), er.end(), [](Edge x, Edge y) { return x.w < y.w; });cur[1] = 1;dfs(1, 1);cout << _ + ans << "\n";return 0;
}
T4
游戏厅
观察数据范围，一眼认出网络流。考虑 \(f_i\) 表示第 \(i\) 个人是否使用 A 机器。那么先建出时间轴，每个时间段上我们限制用 \(A\) 机器的人数。原本的上界是 \(x\)，但是由于 \(n\) 个人的存在，每个位置的上界可能就变了。而对于下界，设这个时间总共有 \(t_i\) 人，那么 \(B\) 机器的个数限制了用 \(A\) 的人数下界是 \(\max\{ 0, t_i - y \}\)。于是对 \(m\) 个人的每个，从 \(t_i\) 向 \(s_i\) 连边，无脑无源汇上下界可行流即可。构造方案是容易的。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, X, Y;
pair<int, int> p[605];
int d[1205], dcnt;
int d1[1205], d2[1205];
int lb[1205], rb[1205];
struct Workable_Flow_with_LRBounds {int n, S, T, c;int head[5005], cur[5005], nxt[100005], to[100005], cst[100005], res[100005], ecnt;int add(int u, int v, int x) {to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = x;to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0;return ecnt - 1;}int in[5005], out[5005];int add(int u, int v, int l, int r) {in[v] += l, out[u] += l;return add(u, v, r - l);}queue<int> q;int dep[5005];bool bfs(int s, int t) {for (int i = 1; i <= n + 2; i++) dep[i] = 0;q.push(s);dep[s] = 1;while (!q.empty()) {int x = q.front();q.pop();for (int i = head[x]; i; i = nxt[i]) {int v = to[i];if (!dep[v] && res[i] > 0) {dep[v] = dep[x] + 1;q.push(v);}}}return (dep[t] > 0);}int dfs(int x, int flow) {if (x == T || !flow) return flow;int ret = 0;for (int i = cur[x]; i && flow; i = nxt[i]) {cur[x] = i;int v = to[i];if (dep[v] == dep[x] + 1 && res[i] > 0) {int tmp = dfs(v, min(flow, res[i]));res[i] -= tmp;res[i ^ 1] += tmp;ret += tmp;flow -= tmp;}}if (!ret) dep[x] = 0;return ret;}int dinic() {int ret = 0;while (bfs(S, T)) {for (int i = 1; i <= T; i++) cur[i] = head[i];ret += dfs(S, inf);}return ret;}void initialize(int nn) {n = nn, ecnt = 1;for (int i = 0; i <= n + 2; i++) in[i] = out[i] = head[i] = 0;}int work() {S = n + 1, T = n + 2;for (int i = 1; i <= n; i++) {if (in[i] < out[i]) add(i, T, out[i] - in[i]);else add(S, i, in[i] - out[i]);}int t = dinic();for (int i = head[S]; i; i = nxt[i]) if (res[i]) return -1;return t;}
} G;
int eid[5005];
int f[5005];
int o[605], ans[605];
int ed[605];
int main() {freopen("round.in", "r", stdin);freopen("round.out", "w", stdout);int tc;cin >> tc;while (tc--) {memset(f, 0, sizeof f);memset(ed, 0, sizeof ed);memset(d1, 0, sizeof d1);memset(d2, 0, sizeof d2);memset(ans, 0, sizeof ans);cin >> n >> m >> X >> Y; dcnt = 0;for (int i = 1; i <= n + m; i++) cin >> p[i].first >> p[i].second, d[++dcnt] = p[i].first, d[++dcnt] = p[i].second, o[i] = i;sort(d + 1, d + dcnt + 1);dcnt = unique(d + 1, d + dcnt + 1) - d - 1;for (int i = 1; i <= n + m; i++) {int l = p[i].first = lower_bound(d + 1, d + dcnt + 1, p[i].first) - d;int r = p[i].second = lower_bound(d + 1, d + dcnt + 1, p[i].second) - d;++d1[l], --d1[r];if (i <= n) ++d2[l], --d2[r];}for (int i = 1; i <= dcnt; i++) d1[i] += d1[i - 1], d2[i] += d2[i - 1];bool no = 0;G.initialize(dcnt);for (int i = 1; i < dcnt; i++) {lb[i] = max(0, d1[i] - d2[i] - Y), rb[i] = X - d2[i];if (lb[i] > rb[i]) {no = 1;break;}G.add(i, i + 1, lb[i], rb[i]);}if (no) {cout << "NO\n";continue;}for (int i = n + 1; i <= n + m; i++) eid[i] = G.add(p[i].second, p[i].first, 0, 1);if (G.work() == -1) {cout << "NO\n";continue;}for (int i = n + 1; i <= n + m; i++) f[i] = G.res[eid[i]];sort(o + 1, o + n + m + 1, [](int x, int y) { return p[x] < p[y]; });for (int i = 1; i <= n + m; i++) {int t = o[i];if (f[t]) {for (int j = X + 1; j <= X + Y; j++) {if (ed[j] <= p[t].first) {ans[t] = j;ed[j] = p[t].second;break;}}} else {for (int j = 1; j <= X; j++) {if (ed[j] <= p[t].first) {ans[t] = j;ed[j] = p[t].second;break;}}}}cout << "YES\n";for (int i = 1; i <= n; i++) cout << ans[i] << " ";cout << "\n";for (int i = n + 1; i <= n + m; i++) cout << ans[i] << " ";cout << "\n";}return 0;
}
贪心一定要构造出最优方案。
T3。
T4。对时间考虑，而不是对人和机器考虑。不会做时考虑思考对象。