时间戳

首页 > 技术文章 > 2018北京冬令营测试

2018北京冬令营测试

xiao-ju-ruo-xjr 2018-01-28 21:14 原文

2018北京冬令营测试

题面戳我！

Problem A 题解

我们发现“所有数加起来等于线索上的权值”这个东西可以用流量平衡来解决，所以可以跑上下界费用流。

建图就是，把上下线索放左边，左右线索放右边，源点向所有上下线索连一个上下界均为对应权值的边，同理左右线索向汇点连一个上下界均为对应权值的边；对于空格就是把左边的一个节点和右边的一个节点连起来，上下界均为这个空格的初始权值。

然后考虑调整，以上建的每条边都可以调整流量（正向表示权值加，反向表示权值减），注意反向要限制流量为对应初始权值减 \(1\)，这样来保证最终都是正整数。如果代价为 \(-1\)，可以直接不建调整的边。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 1810
#define maxm 14420
#define LL long long
#define oo 2147483647
#define ool (1ll << 60)

struct Edge {
	int from, to, flow, cost;
	Edge() {}
	Edge(int _1, int _2, int _3, int _4): from(_1), to(_2), flow(_3), cost(_4) {}
};
struct ZKW {
	int n, m, s, t, head[maxn], nxt[maxm];
	LL cost, ans;
	Edge es[maxm];
	LL d[maxn];
	int Q[maxn], hd, tl;
	bool inq[maxn];
	bool vis[maxn];
	
	void init() {
		m = 0; memset(head, -1, sizeof(head));
		return ;
	}
	void setn(int _) {
		n = _;
		return ;
	}
	
	void AddEdge(int a, int b, int c, int d) {
		es[m] = Edge(a, b, c, d); nxt[m] = head[a]; head[a] = m++;
		es[m] = Edge(b, a, 0, -d); nxt[m] = head[b]; head[b] = m++;
		return ;
	}
	
	int Nxt(int x) { return (x + 1) % maxn; }
	bool BFS() {
		rep(i, 1, n) d[i] = ool;
		d[t] = 0;
		hd = tl = 1; Q[tl = Nxt(tl)] = t; inq[t] = 1;
		while(hd != tl) {
			int u = Q[hd = Nxt(hd)]; inq[u] = 0;
			for(int i = head[u]; i != -1; i = nxt[i]) {
				Edge& e = es[i^1];
				if(e.flow && d[e.from] > d[u] + e.cost) {
					d[e.from] = d[u] + e.cost;
					if(!inq[e.from]) inq[e.from] = 1, Q[tl = Nxt(tl)] = e.from;
				}
			}
		}
		if(d[s] == ool) return 0;
		cost = d[s];
		return 1;
	}
	
	int DFS(int u, int a) {
		if(u == t || !a) return ans += cost * a, a;
		if(vis[u]) return 0;
		vis[u] = 1;
		int flow = 0, f;
		for(int i = head[u]; i != -1; i = nxt[i]) {
			Edge& e = es[i];
			if(d[e.to] == d[u] - e.cost && (f = DFS(e.to, min(a, e.flow)))) {
				flow += f; a -= f;
				e.flow -= f; es[i^1].flow += f;
				if(!a) return flow;
			}
		}
		return flow;
	}
	
	int MaxFlow(int _s, int _t) {
		s = _s; t = _t;
		int flow = 0, f;
		while(BFS())
			do {
				rep(i, 1, n) vis[i] = 0;
				f = DFS(s, oo);
				flow += f;
			} while(f);
		return flow;
	}
} sol;

#define maxr 35

struct Grid {
	int tp, v1, v2, c1, c2;
} gs[maxr][maxr];

int CntP, ind[maxn];
struct Point {
	int id;
	Point(): id(0)  {}
	int p() { return id ? id : id = ++CntP; }
} ud[maxr][maxr], lr[maxr][maxr], S, T, SS, TT;

int main() {
	freopen("kakuro.in", "r", stdin);
	freopen("kakuro.out", "w", stdout);
	
	int n = read(), m = read();
	rep(i, 1, n) rep(j, 1, m) gs[i][j].tp = read();
	rep(i, 1, n) rep(j, 1, m) {
		if(gs[i][j].tp == 1 || gs[i][j].tp == 3) gs[i][j].v1 = read();
		if(gs[i][j].tp == 2 || gs[i][j].tp == 3) gs[i][j].v2 = read();
		if(gs[i][j].tp == 4) gs[i][j].v1 = read();
	}
	rep(i, 1, n) rep(j, 1, m) {
		if(gs[i][j].tp == 1 || gs[i][j].tp == 3) gs[i][j].c1 = read();
		if(gs[i][j].tp == 2 || gs[i][j].tp == 3) gs[i][j].c2 = read();
		if(gs[i][j].tp == 4) gs[i][j].c1 = read();
	}
	
	sol.init();
	rep(i, 1, n) rep(j, 1, m) {
		if(gs[i][j].tp == 1 || gs[i][j].tp == 3) {
			ind[S.p()] -= gs[i][j].v1;
			ind[ud[i][j].p()] += gs[i][j].v1;
			if(gs[i][j].c1 >= 0) {
				sol.AddEdge(S.p(), ud[i][j].p(), oo, gs[i][j].c1);
				sol.AddEdge(ud[i][j].p(), S.p(), gs[i][j].v1 - 1, gs[i][j].c1);
			}
		}
		if(gs[i][j].tp == 2 || gs[i][j].tp == 3) {
			ind[lr[i][j].p()] -= gs[i][j].v2;
			ind[T.p()] += gs[i][j].v2;
			if(gs[i][j].c2 >= 0)  {
				sol.AddEdge(lr[i][j].p(), T.p(), oo, gs[i][j].c2);
				sol.AddEdge(T.p(), lr[i][j].p(), gs[i][j].v2 - 1, gs[i][j].c2);
			}
		}
		if(gs[i][j].tp == 4) {
			int x1 = i, y1 = j, x2 = i, y2 = j;
			while(gs[x1][y1].tp == 4) x1--; // ud
			while(gs[x2][y2].tp == 4) y2--; // lr
			ind[ud[x1][y1].p()] -= gs[i][j].v1;
			ind[lr[x2][y2].p()] += gs[i][j].v1;
			if(gs[i][j].c1 >= 0) {
				sol.AddEdge(ud[x1][y1].p(), lr[x2][y2].p(), oo, gs[i][j].c1);
				sol.AddEdge(lr[x2][y2].p(), ud[x1][y1].p(), gs[i][j].v1 - 1, gs[i][j].c1);
			}
		}
	}
	sol.AddEdge(T.p(), S.p(), oo, 0);
	int sum = 0;
	rep(i, 1, CntP) {
		if(ind[i] > 0) sol.AddEdge(SS.p(), i, ind[i], 0), sum += ind[i];
		if(ind[i] < 0) sol.AddEdge(i, TT.p(), -ind[i], 0);
	}
	sol.setn(CntP);
	
	int flow = sol.MaxFlow(SS.p(), TT.p());
	if(flow < sum) return puts("-1"), 0;
	printf("%lld\n", sol.ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

Problem B 题解

我们将线索看成点，空格就是连接恰好两个点的无向边。把这个图建出来，随便选一棵生成树，非树边就随机一下权值，树边权值就可以确定了（可通过非树边的权值和点权从深往浅递推）。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
#define LL long long

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxr 210
#define maxn 80010
#define maxm 160010

LL get_rand() {
	LL x = 0;
	rep(i, 0, 11) x = x << 5 | (rand() & (1 << 5) - 1);
	return x;
}

int r, c;
struct Grid {
	int tp; LL v1, v2;
} gs[maxr][maxr];

int CntP, eid[maxr][maxr];
LL val[maxn];
struct Point {
	int id;
	Point(): id(0) {}
	int p() { return id ? id : id = ++CntP; }
} ud[maxr][maxr], lr[maxr][maxr];

int M, m, head[maxn], nxt[maxm], to[maxm], id[maxm];
void AddEdge(int a, int b, int i) {
	to[++m] = b; id[m] = i; nxt[m] = head[a]; head[a] = m;
	swap(a, b);
	to[++m] = b; id[m] = i; nxt[m] = head[a]; head[a] = m;
	return ;
}

short vis[maxn], OK;
LL Ans[maxn];
void dfs(int u, int fa) {
	vis[u] = 2;
	for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
		if(vis[to[e]] == 2) {
			Ans[id[e]] = get_rand();
			val[u] ^= Ans[id[e]]; val[to[e]] ^= Ans[id[e]];
		}
		else if(!vis[to[e]]) {
			dfs(to[e], u); Ans[id[e]] = val[to[e]];
			val[u] ^= Ans[id[e]]; val[to[e]] ^= Ans[id[e]];
			if(val[to[e]]) OK = 0;
		}
	}
	if(!fa && val[u]) OK = 0;
	vis[u] = 1;
	return ;
}

map <LL, bool> has;
void work() {
	rep(i, 1, r) rep(j, 1, c) ud[i][j].id = lr[i][j].id = 0;
	r = read(); c = read();
	rep(i, 1, r) rep(j, 1, c) gs[i][j].tp = read();
	rep(i, 1, r) rep(j, 1, c) {
		if(gs[i][j].tp == 1 || gs[i][j].tp == 3) gs[i][j].v1 = read();
		if(gs[i][j].tp == 2 || gs[i][j].tp == 3) gs[i][j].v2 = read();
	}
	CntP = M = m = 0; memset(head, 0, sizeof(head));
	rep(i, 1, r) rep(j, 1, c) if(gs[i][j].tp == 4) {
		int x1 = i, y1 = j, x2 = i, y2 = j;
		while(gs[x1][y1].tp == 4) x1--; // ud
		while(gs[x2][y2].tp == 4) y2--; // lr
		val[ud[x1][y1].p()] = gs[x1][y1].v1;
		val[lr[x2][y2].p()] = gs[x2][y2].v2;
		AddEdge(ud[x1][y1].p(), lr[x2][y2].p(), eid[i][j] = ++M);
	}
	memset(vis, 0, sizeof(vis)); OK = 1;
	rep(i, 1, CntP) if(!vis[i]) {
		dfs(i, 0);
		if(!OK) return (void)puts("-1");
	}
	has.clear();
	rep(i, 1, M) {
		if(!Ans[i] || has.count(Ans[i])) return (void)puts("-1");
		has[Ans[i]] = 1;
	}
	rep(i, 1, r) {
		int lst = 0;
		rep(j, 1, c) if(gs[i][j].tp == 4) lst = max(lst, j);
		rep(j, 1, c) if(gs[i][j].tp == 4) printf("%lld%c", Ans[eid[i][j]], j < lst ? ' ' : '\n');
	}
	return ;
}

int main() {
	freopen("cross.in", "r", stdin);
	freopen("cross.out", "w", stdout);
	
	int T = read();
	
	while(T--) work();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

Problem C 题解

这个每条信息的候选数都是一段连续的区间最多去掉一个数字【需要分情况讨论，当 \(len \le 2\)（\(len\) 表示线索限制的区间长度）时候选数字是单点】。于是我们可以用一个扫描线从上往下扫描这个网格，遇到一个纵向的线索的开头就加入数据结构，结尾就从数据结构删除，然后对于一个横向的线索相当于区间查询信息。我们开一个线段树套线段树，外层位置内层值域，维护左右端点的总和（如果候选数字是贴着 \(k\) 的区间就存左端点，是贴着 \(1\) 的区间就存右断电）、删除的单点，以及如果候选数字是单点就维护一下这个单点信息。

具体实现我也不会，就是不知道如何求出删掉哪个值，感觉这种分类讨论题非常恶心

推荐阅读