2021-03-14

2021训练联盟热身训练赛第二场

字数统计: 3.1k字 | 阅读时长: 17分

solved	A	B	C	D	E	F	G	H	I	J
10 \ 10	O	O	O	O	O	O	O	O	O	O

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

比赛链接

A - Binarize It

solved by Tryna. 00:03(+)

题意： 求大于等于 $x$ 的最小的二次方的数

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int t, n, cnt;
void solve() {
	scanf("%d", &n);
	cnt++;
	if(cnt != 1) puts("");
	printf("Input value: %d\n", n);
	int sum = 1;
	while(sum < n) {
		sum = sum * 2;
	}
	printf("%d\n", sum);
	
}
int main () {
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}

B - g2g c u l8r

Solved by Sstee1XD. 0:34(+)

题意： 将一些单词替换。

思路： 直接 $map$ 模拟即可。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

#define endl "\n"

map<string, string> mp;
string s;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	getline(cin, s);
	while (t--) {
		getline(cin, s);
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == ' ') {
				mp[s.substr(0, i)] = s.substr(i + 1, s.size() - i - 1);
				break;
			}
		}
	}
	cin >> t;
	getline(cin, s);
	while (t--) {
		getline(cin, s);
		int pre = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == ' ') {
				if (mp.count(s.substr(pre, i - pre))) cout << mp[s.substr(pre, i - pre)] << " ";
				else cout << s.substr(pre, i - pre) << " ";
				pre = i + 1;
			}
		}
		if (mp.count(s.substr(pre, s.size() - pre))) cout << mp[s.substr(pre, s.size() - pre)];
		else cout << s.substr(pre, s.size() - pre);
		cout << endl;
	}
	return 0;
}

C - Tip to be Palindrome

solved by Tryna & llllan. 00:36(+1)

题意： 给出一个花费 $n$ ，每个花费我们需要支付 $20$ %的小费。我们希望最后的总花费是个回文数，所以希望通过增加小费来使这个条件满足

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int t, n, cnt;
bool check(int x) {
	int a[10] = {0};
	while (x) {
		a[ ++a[0] ] = x % 10;
		x /= 10;
	}
	for (int i = 1; i <= a[0]; ++i) {
		if (a[i] != a[ a[0] + 1 - i ]) return 0;
	}
	return 1;
}
void solve() {
	scanf("%d", &n);
	cnt++;
	if(cnt != 1) puts("");
	printf("Input cost: %d\n", n);
	int c = ceil(n * 0.2);
	for(int i = c; i <= 10000; i++) {
		if(check(i + n)) {
			printf("%d %d\n", i, i + n);
			return ;
		}
	}
}
int main () {
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}

D - Soccer Standings

Solved by Sstee1XD & lllllan. 1:00(+)

题意： 给你球队间比分的信息，统计信息，排序后输出。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
const int N = 4e2 + 7;
map<string, int> mp;
int cas;

struct Team {
    string name;
    int p, win, lose, draw, gs, ga;
    bool operator < (const Team &a) {
    	if (p == a.p) {
    		if (gs - ga == a.gs - a.ga) {
    			if (gs == a.gs) {
    				return name < a.name;
				}
				return gs > a.gs;
			}
			return gs - ga > a.gs - a.ga;
		}
		return p > a.p;
	}
}t[N];

void solve() {
	int n, q;
	string s;
	cin >> n >> q;
	mp.clear();
	for (int i = 1; i <= n; ++i) {
		cin >> s;
		mp[s] = i;
		t[i] = {s, 0, 0, 0, 0, 0, 0};
	}
	string a, b;
	int ag, bg;
	for (int i = 1; i <= q; ++i) {
		cin >> a >> ag >> b >> bg;
		t[ mp[a] ].gs += ag;
		t[ mp[a] ].ga += bg;
		t[ mp[b] ].gs += bg;
		t[ mp[b] ].ga += ag;
		if (ag > bg) {
			t[ mp[a] ].win++;
			t[ mp[a] ].p += 3;
			t[ mp[b] ].lose++;
		}
		else if (ag < bg) {
			t[ mp[b] ].win++;
			t[ mp[b] ].p += 3;
			t[ mp[a] ].lose++;
		} else {
			t[ mp[a] ].draw++;
			t[ mp[b] ].draw++;
			t[ mp[a] ].p++;
			t[ mp[b] ].p++;
		}
	}
	sort(t + 1, t + 1 + n);
	cout << "Group " << ++cas << ":" << endl;
	for (int i = 1; i <= n; ++i) {
		cout << t[i].name << " " << t[i].p << " " << t[i].win << " " << t[i].lose << " " << t[i].draw << " " << t[i].gs << " " << t[i].ga << endl;
	}
	cout << endl;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) solve();
	return 0;
}

E - NIH Budget

Solved by Sstee1XD & Tryna. 2:15(+1)

题意： 现有 $d$ 种病，和资金 $B$ ，每种病都有四种治疗方案，花费一定数量的钱救治一定数量的人，每种病至多选择一种治疗方案，问最多能救治多少人。

思路： 多组背包。

AC代码

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

const int N = 1e5 + 7;

int cas, dp[N];
int w[17][5], v[17][5];

inline void chmax(int &a, int b) {
	if (b > a) a = b;
}

inline int rd() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * w;
}

int main () {
	int t = rd();
	while (t--) {
		memset(dp, 0xcf, sizeof(dp));
		dp[0] = 0;
		
		int d = rd();
		int m = rd();
		dp[m] = 0;
		for (int i = 1; i <= d; ++i) {
			for (int j = 1; j <= 4; ++j) {
				v[i][j] = rd();
				w[i][j] = rd();
			}
		}
		for (int i = 1; i <= d; ++i) {
			for (int j = m; j >= 0; --j) {
				for (int k = 1; k <= 4; ++k) {
					if (j >= v[i][k]) {
						chmax(dp[j], dp[j - v[i][k] ] + w[i][k]);
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i <= m; ++i) chmax(ans, dp[i]);
		printf("Budget #%d: Maximum of %d lives saved.\n", ++cas, ans);
		puts("");
	}
	
	return 0;
}

F - Interstellar Love

solved by lllllan. 02:01(+)

题意： 找有多少个至少有两个点的连通块和多少个内部构成环的连通块。

题解： 可以选择并查集记录联通也可以直接搜索。

AC代码

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

int cnt, head[1010];
struct edge { int v, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}; head[u] = cnt;
	e[++cnt] = {u, head[v]}; head[v] = cnt;
}

int n, m, tot;
int vis[1010];
int ans[1010];
int deg[1010];

void dfs (int u, int fa) {
	vis[u] = tot;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa) continue;
		if (vis[v]) {
			ans[tot] = 1;
			continue;
		}
		dfs(v, u);
	}
}

void run () {
	cnt = tot = 0;
	
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) deg[i] = ans[i] = vis[i] = head[i] = 0;
	
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		deg[u] = deg[v] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		if (!vis[i] && deg[i]) {
			++tot;
			dfs(i, 0);
		}
	}
	
	int sum = 0;
	for (int i = 1; i <= tot; ++i) sum += ans[i];
	printf("%d constellations, of which %d need to be fixed. \n", tot, sum);
}

int main () {
	int _; scanf("%d", &_);
	for (int i = 1; i <= _; ++i) {
		if (i > 1) puts("");
		printf("Night sky #%d: ", i);
		run();
	}
	return 0;
}

G - Plate Spinning

solved by Tryna. 03:12(+5)

思路： 根据题意求出关系即可，注意特判 $1$ 的情况

AC代码

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

void run () {
	double a, p;
	scanf("%lf%lf", &a, &p);
	if(a == 1) {
		puts("Chester can do it!");
		return ;
	}
	printf("%s\n", p * 0.2 < a * 0.5 ? "Chester will fail!" : "Chester can do it!");
}

int main () {
	int _; scanf("%d", &_);
	for (int i = 1; i <= _; ++i) {
		if (i > 1) puts("");
		printf("Circus Act %d:\n", i);
		run();
	}
	return 0;
}

H - The Eternal Quest for Caffeine

Solved by Sstee1XD & lllllan. 4:32(+2)

题意： 有 $n$ 层楼，你目前处于 $m$ 层，每一层都有一个售货机，每个售货机有两个信息，拥有的零件和是否有你需要的东西。售货机需要集齐 $1$ ~ $k$ 个零件才能运作。你可以上下移动，并且收集一路的零件用给别的楼层的机器，问你最少需要走几层楼，使得你回到 $m$ 层楼时，能获得你需要的东西。

思路： 状态压缩记录每层楼拥有的零件情况，记录每层楼是否拥有的需要的东西，枚举向上走几层，然后枚举向下走几层，记录达到需要状态时的最小值。

AC代码

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

const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m, k;
bool ok[21];
int sta[21];
int a, b;
char s[3];
int tot;
int cas;

int main () {
	while (~scanf("%d %d %d", &n, &m, &k), n | k | m) {
		tot = (1 << k) - 1;
//		printf("%d\n", tot);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &a);
			sta[i] = 0;
			while (a--) {
				scanf("%d", &b);
				sta[i] |= (1 << (b - 1));
			}
			scanf("%s", s);
			if (s[0] == 'Y') ok[i] = true;
			else ok[i] = false;
		}
		int t = sta[m];
		bool good = ok[m];
		int ans = inf;
		for (int i = m; i >= 1; --i) {
			t |= sta[i];
			good |= ok[i];
//			printf("%d %d\n", t, good);
			int step = (m - i) * 2;
			int to = t;
			bool g = good;
			if (g && to == tot) ans = min(ans, step);
			for (int j = m + 1; j <= n; ++j) {
				to |= sta[j];
				g |= ok[j];
				step += 2;
				if (g && to == tot) {
					ans = min(ans, step);
					break;
				}
			}
		}
		printf("Test case #%d: ", ++cas);
		if (ans < inf) printf("%d\n", ans);
		else puts("Impossible");
		puts("");
	}
	return 0;
}

I - Pegasus Circle Shortcut

solved by Tryna. 04:03(+)

思路： 根据题意求出两个距离比较一下即可

AC代码

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int maxn = 20;
const double pi = acos(-1.0);
int sgn(double x) {
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}
struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
	Point operator - (Point B){
		return Point(x - B.x, y - B.y);
	} 
}c, P[maxn], P1, P2;
struct Line{
	Point p1, p2;
	Line(){}
	Line(Point p1, Point p2):p1(p1),p2(p2){}
};
double Cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}
double Dist(Point a, Point b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double Dist_Point_line(Point p, Line v) {
	return fabs(Cross(p - v.p1, v.p2 - v.p1))/Dist(v.p1, v.p2);
}
int n;
double r;
int main () {
	int cnt = 0;
	while(~scanf("%lf%lf%lf%lf%lf%lf", &c.x, &c.y, &P1.x, &P1.y, &P2.x, &P2.y)) {
		if(c.x == 0 && c.y == 0 && P1.x == 0 && P1.y == 0 && P2.x == 0 && P2.y == 0) 
			break;
		cnt++;
		if(cnt != 1) puts("");
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) scanf("%lf%lf", &P[i].x, &P[i].y);
		double sum1 = Dist(P1, P[1]) + Dist(P2, P[n]);
		for(int i = 2; i <= n; i++) sum1 += Dist(P[i - 1], P[i]);
		r = Dist(c, P1);
		Line L = Line(P1, P2);
		double d = Dist_Point_line(c, L);
		double angle = 2 * acos(d / r);
		double rate = angle / (2 * pi);
		Line l = Line(P1, c);
		double sum2 = rate * 2 * pi * r;
		printf("Case #%d: ", cnt);
		if(sum2 < sum1) puts("Stick to the Circle.");
		else puts("Watch out for squirrels!");
	}
	return 0;
}

J - Lowest Common Ancestor

solved by lllllan & Setee1XD. 04:56(+)

题意： 求完全二叉树上两点的最近公共祖先。

题解： 根据节点编号的规律，某个节点的两个孩子节点的二进制编号，就是在该父节点的二进制编号最后加0或1。也就说说，找两个点的最近公共祖先，只要找到他们的二进制编号下的最长公共前缀即可。——》先把两个十六进制转成二进制找最长公共前缀然后再转回十六进制输出即可。

AC代码

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

char jin61[maxn], jin62[maxn];
char cha[18] = "0123456789abcdef";

vector<int> gao (char a[]) {
	vector<int> ans;
	int len  = strlen(a);
	for (int i = 0; i < len; ++i) {
		int x = (a[i] >= '0' && a[i] <= '9') ? x = a[i] - '0' : x = a[i] - 'a' + 10;
		ans.push_back((x / 8) & 1);
		ans.push_back((x / 4) & 1);
		ans.push_back((x / 2) & 1);
		ans.push_back(x & 1);
	}
	return ans;
}

vector<int> sol (vector<int> a, vector<int> b) {
	int c1 = 0, c2 = 0;
	while (a[c1] == 0) ++c1;
	while (b[c2] == 0) ++c2;
	
	vector<int> ans;
	for (; c1 < a.size() && c2 < b.size(); ++c1, ++c2) {
		if (a[c1] == b[c2]) ans.push_back(a[c1]);
		else return ans;
	}
	return ans;
}

void print (vector<int> a) {
	int tem = 0;
	int k = a.size() % 4;
	for (int i = 0; i < k; ++i) tem = tem * 2 + a[i];
	if (tem) printf("%c", cha[tem]);
	for (int i = k; i < a.size(); i += 4) {
		tem = 0;
		for (int j = i; j < i + 4; ++j) tem = tem * 2 + a[j];
		printf("%c", cha[tem]);
	}
	printf("\n");
}

void run () {
	scanf("%s%s", jin61, jin62);
	vector<int> jin21 = gao(jin61);
	vector<int> jin22 = gao(jin62);
	vector<int> ans = sol(jin21, jin22);
	print(ans);
}

int main () {
	int _; scanf("%d", &_);
	for (int i = 1; i <= _; ++i) {
		if (i > 1) puts("");
		printf("Case #%d: ", i);
		run();
	}
	return 0;
}