2020-11-25

2020 ECNU Campus Online Invitational Contest

字数统计: 1.4k字 | 阅读时长: 6分

solved	A	B	C	D	E	F	G	H	I
4 / 9	O	·	·	·	Ø	Ø	·	·	O

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

比赛链接

A. Amateur Chess Players

solved by Tryna. 0:15(+)

题意：每个人可以每步拿走一个对应颜色的棋子，谁先取完谁输。

题解：比较大小。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
char ch[110];
int main() {
	scanf("%d", &n);
	getchar();
	gets(ch);
	scanf("%d", &m);
	getchar();
	gets(ch);
	if(n > m) puts("Cuber QQ");
	else puts("Quber CC");
	return 0;
}

E. Even Degree

solved by lllllan. (-)

题意： 给定一个无向图，题目保证没有重边，也没有孤立点，并且每一个节点都有偶数条边。要求每次只能从偶点上删除一条边。求最多可以删除多少条边，并按照删除顺序输出每条删除边的编号。

题解： 由于题目保证的所有点都是偶点，所以纸上随便找几个图画一下就知道肯定可以将一个连通图删剩下一条边。然后问题就来到了删边的顺序。

回顾一下最普通的输出欧拉回路的代码：关键在于先递归，后输出。这个代码的正确性我就不加证明了，不理解的可以自己百度。

void euler (int u) {
	for(int v = 1; v <= 50; v++) {
		if(G[u][v]) {
			G[u][v]---, G[v][u]--;
			euler (v);
			printf("%d %d\n", v, u);
		}
	}
}

这题删边的操作也要如此，通过dfs递归，然后记录下一个删边顺序——但是此时会记录下所有的边【实际上只能删除 $m-1$ 条边】，需要我们增加额外的判断，按照一个顺序遍历想要删除的边，每次将两端节点的度数-1，遍历到某条边的两端点均为奇点，说明这条边不可删除，需要反向遍历之前记录下的想要删除的边，如此反复，直到只剩下一条边为止。【表述不清难以理解的的，直接看代码的solve部分】

solve部分的代码即保证了删除的每条边都来自偶点，删边的顺序可以有很多，但是直接按照欧拉回路的路径来删除就会简单很多。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;

int n, m, vis[N];
int u, v, deg[N];
int top, sta[N];
int tot, ans[N];
int cnt, head[N];
struct edge { int u, v, id, next;} e[N << 1];
void add (int u, int v, int id) { e[cnt].u = u, e[cnt].v = v, e[cnt].id = id, e[cnt].next = head[u], head[u] = cnt++;}

void dfs (int u) {
	while (~head[u]) {
		int i = head[u];
		int v = e[i].v, id = e[i].id;
		head[u] = e[i].next;
		if(vis[id]) continue;
		vis[id] = 1, dfs (v);
		sta[++top] = i;
	}
}

void solve () {
	int l = 1, r = top;
	while (l < r) {
		int u = e[sta[l]].u, v = e[sta[l]].v;
		if (deg[u] & 1 && deg[v] & 1) {
			u = e[sta[r]].u, v = e[sta[r]].v;
			ans[++tot] = e[sta[r]].id; r--;
		} else {
			ans[++tot] = e[sta[l]].id; l++;
		}
		deg[u]--, deg[v]--;
	}
}

int main () {
	scanf("%d%d", &n, &m);
	_for (i, 0, n) head[i] = -1;
	_for (i, 1, m) {
		scanf("%d%d", &u, &v);
		deg[u]++, deg[v]++;
		add(u, v, i); add(v, u, i);
	}
	_for (i, 1, n) {
		top = 0;
		dfs(i);
		if (top) solve ();
	}
	printf("%d\n", tot);
	_for (i, 1, tot) 
		printf("%d%c", ans[i], " \n"[i == top]);
	return 0;
}

F. Find / -type f -or -type d

solved by Sstee1XD. (-)

题意： 给你所有文件的子目录，输出结尾为 $.eoj$ 的文件数量。

题解： 前面的 $.eoj$ 文件如果有扩展的话，就是一个文件夹，而非文件，所以我们用字典树就能很好地维护。（看到官方题解是sorting的我人直接没了，字典树调了一万年QAQ）。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int n;
char s[maxn];
int ans;
 
struct Trie{
	struct node {
		int cnt;
		int nx[28];
		void init() {
			memset(nx, -1, sizeof(nx));
			cnt = 0;
		}
	}t[maxn];
	int tot, root;
	int newnode() {
		tot++;
		t[tot].init();
		return tot;
	}
	void init() {
		tot = 0;
		root = newnode();
	}
	void insert(char *s) {
		int now = root;
		int len = strlen(s);
		for (int i = 0; i < len; ++i) {
			int v = s[i] - 'a';
			if (s[i] == '.') v = 26;
			if (s[i] == '/') v = 27, t[now].cnt = -1;
			if (t[now].nx[v] == -1) t[now].nx[v] = newnode();
			now = t[now].nx[v];
		}
        if (len >= 5 && s[len - 1] == 'j' && s[len - 2] == 'o' && s[len - 3] == 'e' && s[len - 4] == '.' && t[now].cnt != -1) t[now].cnt = 1;
	}
	void dfs(int u) {
		if (t[u].cnt != -1) ans += t[u].cnt;
		for (int i = 0; i <= 27; ++i) {
			if (t[u].nx[i] != -1) {
				dfs(t[u].nx[i]);
			}
		}
		
	}
}trie;
int main() {
	scanf("%d", &n);
	trie.init();
	while (n--) {
		scanf("%s", s);
		trie.insert(s);
	}
	trie.dfs(1);
	printf("%d\n", ans);
	return 0;
}

I. Idiotic Suffix Array

solved by Sstee1XD. 0:28(+)

题意： 构造一个长为 $n$ 字符串，使得其第一个字母的字典序最小，并且排序后在第k位上。

题解： 输出对应数量的 $a,b,c$ 即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n, k;
int main() {
	scanf("%d %d", &n, &k);
	putchar('b');
	for (int i = 1; i < k; ++i) {
		putchar('a');
	}
	for (int i = k + 1; i <= n; ++i) putchar('c');
	return 0;
}