2021-03-20

2018 ACM-ICPC, Asia Beijing Regional

字数统计: 1.9k字 | 阅读时长: 9分

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

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

比赛链接

A - Jin Yong’s Wukong Ranking List

solved by lllllan. 00:26(+1)

题意： 以字符串形式给出一条有向边的两端，要求输出第一次形成环的边。

题解： 数据范围很小，可以一边输入一边在邻接矩阵上标记所有连接的点。

AC代码

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

int n, cnt;
map<string, int> mp;

vector<int> pre[110];
int G[100][100];

int id (char s[]) {
	if (mp[s]) return mp[s];
	return mp[s] = ++cnt;
}

void run () {
	mp.clear();
	memset(G, 0, sizeof G);
	for (int i = 0; i < 100; ++i) pre[i].clear();
	cnt = 0;
	
	int flag = 0;
	for (int i  = 1; i <= n; ++i) {
		char s[100], b[100];
		scanf("%s%s", s, b);
		if (flag) continue;
		int is = id(s), ib = id(b);
		pre[ib].push_back(is); 
		G[is][ib] = 1;
		if (G[ib][is]) {
			flag = 1;
			printf("%s %s\n", s, b);
			continue;
		}
		for (int u : pre[is]) {
			pre[ib].push_back(u);
			G[u][ib] = 1;
		}
	}
	if (!flag) printf("0\n");
}

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

B - Heshen’s Account Book

solved by lllllan. (-)

题意： 要求提取出所有符合要求的数字，并输出每行的符合要求数字的个数。要求如下：

前后不能出现字母
不能有前导零
某行的最后一个字符是数字，下一行的第一个字符也是数字，要将这两个字符串连接起来进行判断【并且计数在出现的第一行上】

题解： 总结要求就是提取出所有仅由数字组成并且没有前导零的字符串。但是，单个字符零，又是符合要求的。 剩下麻烦的是连接下一行的字符串，甚至是多行连接起来的。清楚题意和陷阱以后，就是模拟的细节了。

AC代码

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

char c;
string s;

int deep = 1, add;
int cnt[220];
vector<string> ans;

bool check (string s) {
	if (s.length() == 0) return false;
	if (s.length() == 1 && s[0] == '0') return true;
	if (s[0] == '0') return false;
	for (int i = 0; s[i]; ++i) if (s[i] >= 'a' && s[i] <= 'z') return false;
	return true;
}

bool pos (string s) {
	char c = s[ s.length() - 1 ];
	return (c >= '0' && c <= '9');
}

void gao () {
	if (check(s)) {
		ans.push_back(s);
		cnt[deep]++;
	}
	if (add) deep += add, add = 0;
	s.clear();
}

int maxx = 0, tem = 1;
int main () {

	int enter = 0;
	while (~scanf("%c", &c)) {
		maxx += tem, tem = 0;
		if (c == ' ') {
			enter = 0;
			gao();
		} else if (c == '\n') {
			tem = 1;
			add++;
			if ((s.length() && !pos(s)) || s.length() == 0) {
				deep += add, add = 0;
				s.clear();
				enter = 0;
			} else enter = 1;
		} else {
			if (enter && c >= 'a' && c <= 'z') gao();
			s = s + c;
			enter = 0;
		}

	}

	gao();
	if (ans.empty()) puts("");
	for (int i = 0; i < ans.size(); ++i)
		cout << ans[i] << " \n"[i == ans.size() - 1];
	for (int i = 1; i <= maxx; ++i)
		cout << cnt[i] << endl;
		
	return 0;
}

D - Frog and Portal

Solved by Sstee1XD & Tryna. 3:27(+1)

题意： 从点 $0$ 出发，每次可以往前跳 $1$ 个格子或者两个格子。在这种情况下达到第 $i$ 个格子的方案数为斐波那契额数列的第i项。你现在可以添加至多 $199$ 个传送门，使得跳到第 $a_i$ 个格子时，会马上传送到 $b_i$ ，并且 $a_i$ 要各不相同。现在要你输出一种传送门放置方案，使得跳到第 $200$ 个位置的方案数为 $M(0 \leq M < 2^{32})$ 。

题解： 推出任何一个数都可以由一些斐波那契数组合而成，并且 $M$ 比较小，我们可以预处理一些斐波那契数，然后很容易就能找到 $M$ 的斐波那契数组合。接下来为了让这些数能组合成我们想要的数，要让它从前面过来的方案唯一，最后传送到 $200$ 的前几个就可以了。我们可以隔一个放一个，具体构造看代码。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 2e5 + 10;

ll fib[220] = {0, 1, 1};
ll n;
int sum;
vector<int>v;
void init () {
	for (int i = 2; i <= 50; ++i) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
}

void cal(ll x) {
	while(x) {
		int index = lower_bound(fib, fib + 51, x) - fib;
		if(fib[index] != x) index--;
		if(index == 1) index++;
		v.pb(index);
		sum++;
		x -= fib[index];
	}
}

vector<pii> ans;

void run() {
	cal(n);
	ans.clear();
	ans.push_back({1, 3});
	ans.push_back({2, 2});
	int now = 4;
	for (int i = 0; i < v.size(); ++i) {
		ans.push_back({now, 201 - v[i]});
		if (i == v.size() - 1) ans.push_back({now + 1, now + 1});
		now += 2;
	}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); ++i) {
		printf("%d %d\n", ans[i].fi, ans[i].se);
	}
}

int main () {
	init ();
	while(~scanf("%lld", &n)) {
		if(n == 0) {
			printf("2\n1 1\n2 1\n");
			continue;
		}
		v.clear();
		sum = 0;
        run();
	}
	return 0;
}

I - Palindromes

Solved by Sstee1XD. 1:36(+1)

题意： 求自然数中第 $k(1 \leq len(k) \leq 10^5)$ 大的回文数。

思路： 比较小的数很好想到构造方法。我们打个表，发现有规律，可以进行分类讨论。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int N = 1e5 + 7;
int a[N] ={0, 10, 9, 90};
char s[N];

char k[N];

void run () {
	scanf("%s", k);
	int lenk = strlen(k);
	if (lenk == 1) {
		printf("%d\n", k[0] - '1');
		return;
	}
	if (lenk == 2 && k[0] == '1' && k[1] == '0') {
		puts("9");
		return;
	}
	int len = lenk * 2;
	if (k[0] > '1') len++;
	else if (k[1] > '0') len--;
	if (k[0] == '1') {
		k[0] = 0;
		if (k[1] == '0') {
			k[1] = '9';
			lenk--;
		}
		printf("%s", k + 1);
		for (int i = lenk - 1; i >= 1; --i) {
			printf("%c", k[i]);
		}
		puts("");
		return;
	}
	k[0] -= 1;
	printf("%s", k);
	for (int i = lenk - 2; i >= 0; --i) {
		printf("%c", k[i]);
	}
	puts("");
}

int main () {
	int t = 1;
	scanf("%d", &t);
	while (t--) run();
	return 0;
}

打表代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int N = 1e5 + 7;
int a[N] ={0, 10, 9, 90};
char s[N];

int n, now;

bool dfs(int now, int len) {
	if (now > (len + 1) / 2) return false;
	int ss = 0;
	if (now == 1) ss = 1;
	for (int i = ss; i <= 9; ++i) {
		s[now] = i + '0';
		if (now == (len + 1) / 2) {
			n--;
			if (n) {
				continue;
			}
//			s[now] = i + '0'; 
			return true;
		}
		s[now] = i + '0';
		if (dfs(now + 1, len)) return true;
	}
	return false;
}

void run () {
	printf("%d\n", now);
//	scanf("%d", &n);
	n = now;
	if (n <= 10) {
		printf("%d\n", n - 1);
		return;
	}
    for (int i = 1; i <= 15; ++i) {
    	if (a[i] >= n) {
    		n -= a[i - 1];
//    		printf("%d\n", n);
    		dfs(1, i);
    		for (int j = 1; j <= (i + 1) / 2; ++j) {
    			printf("%c", s[j]);
			}
			if (i % 2 == 0) printf("%c", s[(i + 1) / 2]);
			for (int j = (i + 1) / 2 - 1; j >= 1; --j) {
				printf("%c", s[j]);
			}
			puts("");
			return;
		}
	}
}

int main () {
	for (int i = 4; i <= 15; ++i) {
		a[i] = a[i - 2] / 9 * 10 * 9;
	}
	for (int i = 2; i <= 15; ++i) {
		a[i] += a[i - 1];
	}
	int t = 1;
//	scanf("%d", &t);
//	while (t--) run();
	for (now = 0; now <= 1000; ++now) {
		run();
		puts("\n");
	}
	return 0;
}