您的位置: 首页  >  IT文章  >  The 2018 ACM-ICPC Asia Beijing Regional Contest

The 2018 ACM-ICPC Asia Beijing Regional Contest

分类: IT文章 • 2024-01-29 19:06:18

目录

Contest Info

[Practice Link](https://vjudge.net/contest/334680)
Solved A B C D E F G H I J
6/10 O O - O - Ø - O O -
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

A - Jin Yong’s Wukong Ranking List

题意：
给出(n)对有向关系，判断前多少对关系会形成一个环。

思路：
慢慢加入一对关系，跑拓扑排序，出现环就停止。

代码：

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

const int N = 510;
int n;
map<string, int> mp; int tot;
string s[2][N];
int getid(string s) {
	if (mp.count(s)) return mp[s];
	mp[s] = ++tot;
	return mp[s];
}

vector <vector<int>> G;
int d[N];
bool gao(int n) {
	memset(d, 0, sizeof d);
	G.clear(); G.resize(tot + 1);
	for (int i = 1; i <= n; ++i) {
		int u = getid(s[0][i]), v = getid(s[1][i]);
		++d[v];
		G[u].push_back(v);
	}
	int cnt = 0;
	queue <int> que; 
	for (int i = 1; i <= tot; ++i) if (!d[i]) que.push(i);
	while (!que.empty()) {
		int u = que.front(); que.pop();
		++cnt;
		for (auto &v : G[u]) {
			if (--d[v] == 0) {
				que.push(v);
			}
		}
	}
	return cnt != tot;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while (cin >> n) {
		mp.clear(); tot = 0;
		for (int i = 1; i <= n; ++i) {
			cin >> s[0][i] >> s[1][i];
			getid(s[0][i]); getid(s[1][i]);
		}
		bool flag = 0;
		for (int i = 1; i <= n; ++i) {
			if (gao(i)) {
				cout << s[0][i] << " " << s[1][i] << "
";
				flag = 1;
				break;
			}
		}
		if (!flag) cout << 0 << "
";
	}
	return 0;
}

B - Heshen's Account Book

题意：
模拟题。给出若干行文本，包含空格、数字、字母。
找出其中所有连续的自然数，但是如果某一行的结尾是数字，并且下一行的开头也是数字，那么这两行的数字视为连在一起的。

思路：
直接将所有行连在一起再判断。
能直接连就直接连，不能直接连中间加一个空格。
不要分类讨论做，很多Case考虑不到。

代码：

view code
#include <bits/stdc++.h>
using namespace std;
using pSI = pair<string, int>;
#define fi first
#define se second
const int N = 2e5 + 10;
int vis[N], num[N], pos, len;
string s, t;
bool isnum(string &s) {
	int len = s.size();
	if (len == 1) {
		return isdigit(s[0]);
	} 
	if (s[0] == '0') return false;
	for (int i = 0; i < len; ++i)
		if (!isdigit(s[i]))
			return false;
	return true;
}

pSI get() {
	pSI tmp = pSI("", -1);
	while (pos < len && t[pos] == ' ') ++pos;
	while (pos < len && t[pos] != ' ') {
		if (tmp.se == -1) tmp.se = vis[pos];
		tmp.fi += t[pos];
		++pos; 
	}
	return tmp;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	memset(vis, 0, sizeof vis);
	memset(num, 0, sizeof num);
	s = t = "";
	int pre = -1; t = "";
	int n = 0;
	while (getline(cin, s)) {
		++n;
		if (!t.empty() && isdigit(t.end()[-1]) && isdigit(s[0])) {
			t += s;
		} else {
			t += " ";
			t += s;
			++pre;
		}
		int len = t.size();
		for (int i = pre + 1; i < len; ++i) vis[i] = n;
	   	pre = len - 1;	
	} 
	len = t.size();
	pos = 0;
	vector <string> vec;
	while (1) {
		pSI tmp = get();
		if (tmp.se == -1) break;
		if (isnum(tmp.fi)) {
			++num[tmp.se];
			vec.push_back(tmp.fi);
		}
	}
	int sze = vec.size();
	for (int i = 0; i < sze; ++i)
		cout << vec[i] << " 
"[i == sze - 1];
	for (int i = 1; i <= n; ++i)
		cout << num[i] << "
";
	return 0;
}

C - Pythagorean triple

题意：
统计有多少个三元组((a, b, c))使得(a^2 + b^2 = c^2)，并且满足(c leq N)

D - Frog and Portal

题意：
现在有(201)个点，可以加一些传送门，一旦进入这个点就会被传送到另一个点。
现在青蛙在(0)号点，它要到(200)号点，它如果在(p)号点，那么下一步可以去(p + 1)或者(p + 2)号点。
问你如何加传送门，使得它从(0)到(200)的方案数是(m)。

思路：
考虑不加任何传送门方案数是第(201)个斐波那契数。
我们可以考虑任意一个整数都可以被分解为若干个斐波那契数相加。
那么我们从起点的某个地方直接传送到(201 - x)那个点，那么从(x)到(201)的方案数就是第(x)个斐波那契数。
并且控制从(0)走到那个传送门的方案为(1)即可。

代码：

view code
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 110;

ll m;
ll f[N];
int a[N];

int main() {
	f[0] = 1, f[1] = 1;
	for (int i = 2; i <= 50; ++i) {
		f[i] = f[i - 1] + f[i - 2];
	}
	while (scanf("%lld", &m) != EOF) {
		if (m == 0) {
			puts("2
1 1
2 1");
			continue;
		}
		*a = 0;
		for (int i = 50; i >= 1; --i) {
			if (m >= f[i]) {
				a[++*a] = i;
				m -= f[i];
			}
		}
		printf("%d
", *a + 1);
		for (int i = 1; i <= *a; ++i) {
			printf("%d %d
", 2 * i - 1, 200 - a[i]);
		}
		printf("%d %d
", 2 * (*a), 2 * (*a));
	}
	return 0;
}

F - The Kth Largest Value

题意：
给出一个有向图，定义((u, v))是好的二元组当且仅当(u)到(v)至少存在一条可达路径，当然((u, u))是好的。
现在定义二元组((u, v))的权值为(u oplus v)，现在有(q)次询问，询问所有好的二元组中的第(k)大的权值。

思路：
先用(tarjan + topo)求出拓扑序，并且用(bitset)求出(f[u])表示(u)可以到达哪些点。
显然有个思路是二分，然后去找有多少个(u oplus v > mid)，但是这个统计可以放在(Trie)上做，所以就不用二分了。
那么从高位到低位贪心，每次尝试当前位放(0)，那么对于当前位放(1)并且低位任意放的情况都是比当前这个数要大的。
放到字典树上就是统计子树和。
但是我们注意到它的权值是([1, n])连续的，所以不用字典树，它是一棵完全二叉树，并且(DFS)序是确定的就是([1, n])。
那么相当于对于每个点查询一段区间和。可以用手写(bitset)维护(f[u])的前缀和，就可以(O(1))查询一段区间内(1)的个数。
并且注意对于每个(u)来说，在它的字典树上往下走的过程要异或(u)的那一位二进制位。

代码：

view code
#include <bits/stdc++.h>
using namespace std;
#define dbg(x...) do { cout << "

相关推荐