2021-02-25

2013-2014 Northwestern European Regional Contest (NWERC 2013)

字数统计: 2.7k字 | 阅读时长: 13分

solved	A	B	C	D	E	F	G	H	I	J
7 / 10	O	O	O	Ø	·	O	O	·	·	Ø

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

REPLY：RE说明数组可能越界了，扩大数组之后还是RE，就要怀疑自己的算法了。

比赛链接

A - Absurdistan Roads

solved by lllllan. 01:52(+)

题意： 给定一个矩阵，表示所有城市之间的最短距离。要求选择 $n$ 条路来连接所有城市，使得任意两个城市之间距离最小。

题解： 一开始都读不懂题意，如果是最小生成树，应该是 $n-1$ 条边才对，可题目偏偏是 $n$ 条边。所以题意应该这么理解【虽然给出的矩阵，是每两个城市之间的最短距离，但要求从里面选出最优的n条路，使得任意两个城市之间的距离最小】

先最小生成树求出前 $n-1$ 条边。
用floyd求出选出的边的条件下，所有城市间的最短距离。
对比原先的矩阵，选择一条距离变长但是最小的边即可。【否则随便输出前面最小生成树上任意一条边】

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
const int inf = 0x3f3f3f3f;

int n, m, cas;
int G[maxn][maxn];
int ans[maxn][maxn];

int s[maxn];
int find (int x) { return s[x] == x ? x : s[x] = find(s[x]); }
void un (int a, int b) { s[find(a)] = find(b); }

struct edge { int u, v, w; } e[maxn * maxn], pre;
int cmp (edge a, edge b) { return a.w < b.w; }
void print(edge e) { printf("%d %d %d\n", e.u, e.v, e.w); }

void kruskal () {
	sort(e + 1, e + m + 1, cmp);
	for (int i = 1; i <= n; ++i) s[i] = i;
	for (int i = 1; i <= m; ++i) {
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int a = find(u), b = find(v);
		if (a == b) continue;
		print(e[i]);
		pre = e[i];
		un(a, b);
		ans[u][v] = ans[v][u] = w;
	}
}

void floyd () {
	for(int k = 1; k <= n; ++k)
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= n; ++j)
		if(ans[i][j] > ans[i][k] + ans[k][j])
			ans[i][j] = ans[i][k] + ans[k][j];
}

void run () {
	if (cas++) printf("\n");
	
	memset(ans, inf, sizeof ans);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j){
			scanf("%d", G[i] + j);
			if (i == 1 && j == 1) m = 0;
			if (j > i) e[++m] = {i, j, G[i][j]};
		}
	kruskal();
	floyd();
	edge tem = {0, 0, inf};
	for (int i = 1; i <= m; ++i) {
		int u = e[i].u, v = e[i].v, w = e[i].w;
		if (ans[u][v] > G[u][v] && w < tem.w) tem = e[i];
	}
	if (tem.w == inf) tem = pre;
	print(tem);
}

int main () {
	while (~scanf("%d", &n)) run();
	return 0;
}

B - Battle for Silver

solved by lllllan. 01:01(+)

题意： 无向图，有点权。要求选择一些点【任意两个点之间都有直接连接的边、权值和尽可能大、边不能交叉】

题解： 咋一看好像很难，但是题意的两个条件限制了很多东西。

选择的点中，任意两个点都要有直接的边连接。
选择的点集，不能有相互交叉的边。

所以结论是，一个图中，最多只能选择四个点。为什么？你画一个五边形套在五角星上，是满足了第一个条件，但是里面的边交叉了。四个点是能保证边不交叉的最大点数。直到这个本质之后，爆搜即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500;

int n, m, ans;
int G[maxn][maxn];

int w[maxn];
int que[4];

int check (int idx, int dep) {
	for (int i = 0; i < dep; ++i)
		if (!G[idx][que[i]]) return 0;
	return 1;
}

void dfs (int u, int dep, int sum) {
	ans = max(ans, sum);
	if (dep == 4) return;
	for (int i = u + 1; i <= n; ++i) {
		if (check(i, dep)) {
			que[dep] = i;
			dfs(i, dep + 1, sum + w[i]);
		}
	}
}

void run () {
	ans = 0; memset(G, 0, sizeof G);
	for (int i = 1; i <= n; ++i) scanf("%d", w + i);
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		G[u][v] = G[v][u] = 1;
	}
	dfs (0, 0, 0);
	printf("%d\n", ans);
}

int main () {
	while (~scanf("%d%d", &n, &m)) run();
	return 0;
}

C - Card Trick

solved by SeTee1XD. 02:34(+)

D - Diagrams & Tableaux

solved by Tryna.(-)

题意： 给出很多方格，我们可以从 $1$ ~ $n$ 中选取任意一个数字填入方格中。问满足这样的情况的方案数有多少种：右边的方格中的数字要大于等于当前的方格中的数字；下面的方格中的数字要严格大于当前方格中的数字。

题解： 刚开始考虑了排列组合，发现数不清情况数量，然后往搜索方向去思考了，dfs只能过UVAL上的那题，因为那题时间给了3s，这题时间只有1s，所以不能考虑dfs。那我们考虑状压dp。因为每一列的数字都是递增的，所以我们将这一列的状态用一个二进制数来表示，所以一列最多有 $2^7$ 个状态。整体的转移思路就是从第一列枚举到最后一列，因为题目给的是行，所以我们还需要将每列求出来。我们假设 $dp[i][j]$ 为第 $i$ 行，二进制数为 $j$ 的方案数量。我们先预处理初始状态，就是先处理第一列，当这个二进制数 $i$ 中 $1$ 的个数为第一列的数量时， $dp[1][i] = 1$ 。然后就是状态的转移，从第一列枚举到最后一列， $j$ 是当前列的二进制数， $k$ 是下一列的二进制数，如果满足

$j$ 中 $1$ 的数量等于当前列
$k$ 中 $1$ 的数量等于下一列
$j$ 拆分成当前列数数量的十进制数， $k$ 也拆分成当前列数数量的十进制数， $k$ 拆分的每一位的结果要大于等于对应 $j$ 拆分的结果。这一步就满足了右边方格中的数字要大于等于当前方格中的数字。举个例子，比如 $j = 5, k = 3$ ，拆分的结果为 $1, 4 和 1, 2$ ，所以是满足的，但如果 $j = 3, k = 5$ 就不满足了。

那么就可以转移到下一列中 $dp[i + 1][k] += dp[i][j]$ ，最后所有的状态都会转移到最后一列上，所以答案就是最后一列所有状态的和。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-10
const int maxn = 10;
int k, l[maxn], n, r[maxn], mp[maxn][maxn], dp[maxn][200], ans;
int cmd1[maxn], cmd2[maxn];
int lowbit(int x){
    return x&-x;
}
int bitcount(int x){      // 计算x的二进制数中有多少个1
    int ans = 0;
    for (; x; x -= lowbit(x))++ans;
    return ans;
}
bool check(int x, int y) {
	int cnt1 = 0, cnt2 = 0;
	for(int i = 0; i < n; i++) {
		if(x>>i&1)
			cmd1[++cnt1] = (1 << i);
		if(y>>i&1)
			cmd2[++cnt2] = (1 << i);
	}
	for(int i = 1; i <= cnt2; i++) {
		if(cmd1[i] > cmd2[i]) return false;
	}
	return true;
}
void solve() {
	while(~scanf("%d", &k)) {
		for(int i = 1; i <= 7; i++) {
			r[i] = 0;
			for(int j = 1; j <= 7; j++)
				mp[i][j] = 0;
		}
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= k; i++) {
			scanf("%d", &l[i]);
			for(int j = 1; j <= l[i]; j++)
				mp[i][j] = 1;
		}
		scanf("%d", &n);
		for(int i = 1; i <= l[1]; i++) {
			int f = 0;
			for(int j = 1; j <= k; j++) {
				if(mp[j][i] == 0) {
					f = 1;
					r[i] = j - 1;
					break;
				}
			}
			if(f == 0) r[i] = k;
		}
		int len = 1 << n;
		for(int i = 1; i < len; i++) {
			if(bitcount(i) == r[1]) dp[1][i]++;
		}
		for(int i = 1; i <= l[1]; i++) {
			for(int j = 1; j < len; j++) {
				if(bitcount(j) != r[i])
					continue;
				for(int k = 1; k < len; k++) {
					if(bitcount(k) == r[i + 1] && check(j, k)) 
						dp[i + 1][k] += dp[i][j];
				}
			}
		}
		int ans = 0;
		for(int i = 1; i < len; i++)
			ans += dp[l[1]][i];
		printf("%d\n", ans);
	}
}
int main() {
	solve();
	return 0;
}

F - First Date

solved by SeTee1XD. 01:34(+)

G - Grachten

solved by lllllan. 00:25(+)

AC代码

#include<bits/stdc++.h>
using namespace std;

int gcd (int a, int b) { return b ? gcd(b, a % b) : a; } 
int a, b, c;

int main () {
	while (~scanf("%d%d%d", &a, &b, &c))
		printf("%d/%d\n", a * b / gcd(a * b, c - b), (c - b) / gcd(a * b, c - b));
}

J - Jingle Balls

solved by SeTee1XD & lllllan.(-)

题意： 一棵二叉树上有一些球，用最少的移动次数，使这棵树平衡。

一个节点下的两个子树的球数差不超过1。
只能将球移动到别的叶子节点上，不可添加不可删除。

题解： 转好一下玩法，题目要求我们把球移动到别的叶子节点上，是一种转移操作。我们可以换成，手握一定数量的球，把他们分配到一些叶子节点上。在满足使树平衡的条件下，尽可能多地将球放在一些原本就有球的叶子节点上。

从根节点开始DFS。
偶数个球，则平均分给两个子树。奇数个球，则要讨论一下怎么分配能获得更小的转移次数。
某个子树上的叶子节点数量都不够放球的话，则是不可能完成题目要求。
DFS到叶子节点的话，事先记录过这里本就是放球的位置，则不用管。否则最终答案+1。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

struct tree {
	int l, r, sum, ball; 
} node[N << 2];

char s[N * 10];
int idx, t;

void build(int id) {
	node[id].ball = node[id].sum = 0;
    if (s[idx + 1] == ')') {
        node[id].ball = 0;
		node[id].sum = 1;
		idx += 2;
		return;
	}
	if (s[idx + 1] == 'B') {
		node[id].ball = 1;
		node[id].sum = 1;
		idx += 3;
		return;
	}

	idx++;
	node[id].l = ++t;
	build(t);
	node[id].r = ++t;
	build(t);
	node[id].ball = node[node[id].l].ball + node[node[id].r].ball;
	node[id].sum = node[node[id].l].sum + node[node[id].r].sum;
	idx++;
}

int get (int id, int res) {
//	printf("id: %d ball:%d sum:%d   res:%d\n", id, node[id].ball, node[id].sum, res);
	if (res == 0) return 0;
	if (node[id].sum < res) return N;
	if (res == 1) return node[id].ball < 1;
	if (res % 2) {
		int a = get(node[id].l, res >> 1) + get(node[id].r, res - (res >> 1));
		int b = get(node[id].l, res - (res >> 1)) + get(node[id].r, res >> 1);
		return min(a, b);
	}
	return get(node[id].l, res >> 1) + get(node[id].r, res >> 1);
}

void solve() {
	idx = 0, t = 1;
	node[1].ball = node[1].sum = 0;
	build(1);

	int ans = get(1, node[1].ball);
	if (ans >= N) printf("impossible\n");
	else printf("%d\n", ans);
}

int main() {
    while (~scanf("%s", s)) solve();
	return 0;
}