T1 Kakuro

有界费用流，或者模拟 +inf 的普通费用流。

#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <limits> #include <queue> #define LOG(FMT...) // fprintf(stderr, FMT) using namespace std; typedef long long ll; struct Num { ll d, infs; Num(ll d = 0, ll infs = 0) : d(d), infs(infs) {} bool operator<(const Num& x) const { if (infs != x.infs) return infs < x.infs; return d < x.d; } Num operator+(const Num& x) const { return Num(d + x.d, infs + x.infs); } Num operator*(ll x) const { return Num(d * x, infs * x); } friend Num operator*(ll x, const Num& y) { return y * x; } Num& operator+=(const Num& x) { d += x.d; infs += x.infs; return *this; } }; struct Edge { int v, w; Num c; Edge *next, *rev; }; const int N = 32, V = N * N, T = V - 1, S = V - 2; const Num INF = Num(0, 1); int n, m, nCnt; int typ[N][N]; int a[N][N][2]; int fromRow[N][N]; Num cst[N][N][2]; bool inq[V]; Edge* pth[V]; Num dist[V]; Edge* g[V]; Edge* addEdge(int u, int v, int w, const Num& c); void link(int u, int v, int w, const Num& c); Num mcf(); bool spth(); int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &typ[i][j]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { if ((typ[i][j] & 1) || typ[i][j] == 4) scanf("%d", &a[i][j][0]); if (typ[i][j] & 2) scanf("%d", &a[i][j][1]); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { int x; if ((typ[i][j] & 1) || typ[i][j] == 4) { scanf("%d", &x); if (x == -1) cst[i][j][0] = INF; else cst[i][j][0] = x; } if (typ[i][j] & 2) { scanf("%d", &x); if (x == -1) cst[i][j][1] = INF; else cst[i][j][1] = x; } } Num curCost = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { if (typ[i][j] & 2) { ++nCnt; int cnt = 0, orij = j; for (++j; typ[i][j] == 4; ++j) { fromRow[i][j] = nCnt; ++cnt; } int used = abs(a[i][orij][1] - cnt); curCost += used * cst[i][orij][1]; if (a[i][orij][1] > cnt) link(S, nCnt, used, cst[i][orij][1] * -1); link(S, nCnt, numeric_limits<int>::max(), cst[i][orij][1]); --j; } } for (int j = 1; j <= m; ++j) for (int i = 1; i <= n; ++i) if (typ[i][j] & 1) { ++nCnt; int cnt = 0, orii = i; for (++i; typ[i][j] == 4; ++i) { int used = abs(a[i][j][0] - 1); curCost += used * cst[i][j][0]; ++cnt; link(fromRow[i][j], nCnt, used, cst[i][j][0] * -1); link(fromRow[i][j], nCnt, numeric_limits<int>::max(), cst[i][j][0]); } int used = abs(a[orii][j][0] - cnt); curCost += used * cst[orii][j][0]; if (a[orii][j][0] > cnt) link(nCnt, T, used, cst[orii][j][0] * -1); link(nCnt, T, numeric_limits<int>::max(), cst[orii][j][0]); --i; } LOG("%lld %lld\n", curCost.d, curCost.infs); curCost += mcf(); LOG("%lld %lld\n", curCost.d, curCost.infs); if (curCost.infs) puts("-1"); else printf("%lld\n", curCost.d); return 0; } Num mcf() { Num cost = 0; while (spth()) { LOG("%lld %lld\n", dist[T].d, dist[T].infs); if (!(dist[T] < 0)) break; int flow = numeric_limits<int>::max(); int u = T; while (u != S) { flow = min(flow, pth[u]->rev->w); u = pth[u]->v; } cost += dist[T] * flow; u = T; while (u != S) { pth[u]->w += flow; pth[u]->rev->w -= flow; u = pth[u]->v; } } return cost; } bool spth() { queue<int> q; memset(pth, 0, sizeof(pth)); memset(inq, 0, sizeof(inq)); inq[S] = true; dist[S] = 0; q.push(S); while (!q.empty()) { int u = q.front(); q.pop(); LOG("BFS %d %lld %lld\n", u, dist[u].d, dist[u].infs); inq[u] = false; for (Edge* p = g[u]; p; p = p->next) if (p->w && p->v != S && (!pth[p->v] || dist[u] + p->c < dist[p->v])) { dist[p->v] = dist[u] + p->c; pth[p->v] = p->rev; if (!inq[p->v]) { q.push(p->v); inq[p->v] = true; } } } return pth[T]; } void link(int u, int v, int w, const Num& c) { LOG("LINK %d %d %d %lld + %lldINF\n", u, v, w, c.d, c.infs); Edge *p = addEdge(u, v, w, c), *q = addEdge(v, u, 0, c * -1); p->rev = q; q->rev = p; } Edge* addEdge(int u, int v, int w, const Num& c) { static Edge pool[V * V * 4]; static Edge* p = pool; p->v = v; p->w = w; p->c = c; p->next = g[u]; g[u] = p; return p++; }

T2 Cross sum

可以看成二分图上环的约束，找一颗 DFS 树，随机化。

#include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <set> #define LOG(FMT...) // fprintf(stderr, FMT) using namespace std; typedef long long ll; struct Edge { int v; ll w; bool vis, tree; Edge *next, *rev; }; const int N = 210, M = N * N; int t, n, m; bool gg; int typ[N][N], rowu[N][N], colu[N][N]; int coli[M], rowi[M]; bool vis[M]; ll wt[M]; ll ans[N][N]; Edge* g[M]; Edge pool[M * 2]; Edge* ptop = pool; set<ll> hsh; ll rnd(); Edge* addEdge(int u, int v); void link(int u, int v); void dfs(int u); void dfs2(int u); int main() { srand(time(NULL)); // freopen("test.in", "r", stdin); scanf("%d", &t); while (t--) { ptop = pool; gg = false; hsh.clear(); memset(g, 0, sizeof(g)); memset(vis, 0, sizeof(vis)); scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &typ[i][j]); int vc = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { if (typ[i][j] & 1) { scanf("%lld", &wt[++vc]); coli[vc] = j; rowi[vc] = 0; for (int k = i + 1; typ[k][j] == 4; ++k) colu[k][j] = vc; } if (typ[i][j] & 2) { scanf("%lld", &wt[++vc]); rowi[vc] = i; for (int k = j + 1; typ[i][k] == 4; ++k) rowu[i][k] = vc; } } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (typ[i][j] == 4) link(rowu[i][j], colu[i][j]); for (int i = 1; i <= vc; ++i) if (!vis[i]) { dfs(i); dfs2(i); if (wt[i]) { gg = true; LOG("FAIL %d %lld\n", i, wt[i]); } } if (gg) { printf("-1\n"); continue; } for (int i = 1; i <= vc; ++i) if (rowi[i]) for (Edge* p = g[i]; p; p = p->next) ans[rowi[i]][coli[p->v]] = p->w; for (int i = 1; i <= n; ++i) { bool flag = false; for (int j = 1; j <= m; ++j) if (typ[i][j] == 4) { if (!flag) printf("%lld", ans[i][j]); else printf(" %lld", ans[i][j]); flag = true; } if (flag) printf("\n"); } } return 0; } void dfs2(int u) { for (Edge* p = g[u]; p; p = p->next) if (p->tree) { p->tree = p->rev->tree = false; dfs2(p->v); p->w = p->rev->w = wt[p->v]; if (hsh.count(p->w) || p->w == 0) { LOG("CRASH AT (%d, %d), %lld\n", u, p->v, p->w); gg = true; } hsh.insert(p->w); wt[u] ^= p->w; } } void dfs(int u) { vis[u] = true; for (Edge* p = g[u]; p; p = p->next) if (!p->vis) if (vis[p->v]) { p->vis = p->rev->vis = true; p->w = p->rev->w = rnd(); LOG("CHOOSE %d %d %lld\n", u, p->v, p->w); wt[u] ^= p->w; wt[p->v] ^= p->w; hsh.insert(p->w); } else { p->vis = p->rev->vis = true; p->tree = p->rev->tree = true; dfs(p->v); } } Edge* addEdge(int u, int v) { Edge* p = ptop; ++ptop; p->v = v; p->vis = false; p->tree = false; p->next = g[u]; g[u] = p; return p; } void link(int u, int v) { Edge *p = addEdge(u, v), *q = addEdge(v, u); p->rev = q; q->rev = p; LOG("%d(%lld) LINK %d(%lld)\n", u, wt[u], v, wt[v]); } ll rnd() { return rand() | ((ll)rand() << 16) | ((ll)rand() << 28); }

T3 Kreuzsummen

经过分类讨论的体力活，候选集合必然在 $0\sim 2$ 个区间以内，于是问题规约为三维数点。$\Theta (n{\log }^{2}n)$

#include <cassert> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <cctype> #include <algorithm> #include <tuple> #include <random> #include <bitset> #include <chrono> #include <queue> #include <functional> #include <set> #include <map> #include <vector> #include <iostream> #include <limits> #include <numeric> #ifdef LBT #define LOG(FMT...) fprintf(stderr, FMT) #else #define LOG(FMT...) #endif using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> Range; typedef vector<Range> Ranges; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define L first #define R second const int N = 100010; int n, m, k, cnt; int fw[N]; int res[N * 4]; int lowBit(int x) { return x & -x; } struct C2D { vector<tuple<int, int, int>> modi[N]; int r, c; void ins(int x, int y1, int y2, int v) { for (; x <= r; x += lowBit(x)) { modi[x].emplace_back(0, y1, v); modi[x].emplace_back(0, y2 + 1, -v); } } void qry(int x1, int x2, int y) { ++cnt; for (; x2; x2 -= lowBit(x2)) modi[x2].emplace_back(1, y, cnt); --x1; for (; x1; x1 -= lowBit(x1)) modi[x1].emplace_back(-1, y, cnt); } void run() { for (int i = 1; i <= r; ++i) { for (const auto& tup : modi[i]) { int typ, x, k; tie(typ, k, x) = tup; if (typ == 0) { for (; k <= c; k += lowBit(k)) fw[k] += x; } else for (; k; k -= lowBit(k)) res[x] += typ * fw[k]; } for (const auto& tup : modi[i]) { int typ, x, k; tie(typ, k, x) = tup; if (typ == 0) for (; k <= c; k += lowBit(k)) fw[k] = 0; } } } } r, c; vector<tuple<int, int, int, int>> md[N]; Ranges cand(int l, ll s) { if (l == 1) { if (s <= k) return {Range(s, s)}; return {}; } if (k < l) return {}; s -= l * (ll)(l + 1) / 2; if (s < 0 || s > (k - l) * (ll)l) return {}; if (k == l) return {Range(1, k)}; if (s == (k - l) * (ll)l) return {Range(k - l + 1, k)}; if (s == 0) return {Range(1, l)}; if (l == 2) { s += 3; int my = max((int)s - k, 1); if (s % 2 == 0) { if (my <= s / 2 - 1) return {Range(my, s / 2 - 1), Range(s / 2 + 1, s - my)}; return {}; } return {Range(my, s - my)}; } if (k - l == 1) return {Range(1, k - s - 1), Range(k - s + 1, k)}; int pos = s / (k - l); if (pos == 0) { if (s % (k - l) == 1) return {Range(1, l - 1), Range(l + 1, l + 1)}; return {Range(1, l + s % (k - l))}; } if (pos == l - 1) { if (s % (k - l) == k - l - 1) return {Range(k - l, k - l), Range(k - l + 2, k)}; return {Range(1 + (s % (k - l)), k)}; } return {Range(1, k)}; } int main() { #ifdef LBT freopen("test.in", "r", stdin); int nol_cl = clock(); #endif int tt; scanf("%d%d%d%d", &n, &m, &k, &tt); while (tt--) { int t, x, y1, y2; ll s; scanf("%d%d%d%d%lld", &t, &x, &y1, &y2, &s); for (const Range& rg : cand(y2 - y1 + 1, s)) { md[rg.L - 1].emplace_back(t, -x, y1, y2); md[rg.R].emplace_back(t, x, y1, y2); } } r.r = n; r.c = m; c.r = m; c.c = n; for (int i = k; i >= 0; --i) for (const auto& tup : md[i]) { int t, x, y1, y2; tie(t, x, y1, y2) = tup; if (t == 0) { if (x > 0) { r.ins(x, y1, y2, 1); c.qry(y1, y2, x); } else { r.ins(-x, y1, y2, -1); c.qry(y1, y2, -x); } } else { if (x > 0) { c.ins(x, y1, y2, 1); r.qry(y1, y2, x); } else { c.ins(-x, y1, y2, -1); r.qry(y1, y2, -x); } } } r.run(); c.run(); ll ans = 0, cur = 0; cnt = 0; for (int i = k; i >= 0; --i) { for (const auto &tup : md[i]) { int t, x, y1, y2; tie(t, x, y1, y2) = tup; if (x > 0) cur += res[++cnt]; else cur -= res[++cnt]; } ans += cur; } printf("%lld\n", ans); #ifdef LBT LOG("Time: %dms\n", int ((clock() -nol_cl) / (double)CLOCKS_PER_SEC * 1000)); #endif return 0; }