AtCoder Beginner Contest 333

总结

• 人生第一次掉rating
• 全tm是降智操作

A

水题

B

逆天操作
WA了3发
第三发交的时候以为过了，等到切完E发现B怎么还没过（

#include<bits/stdc++.h>

using namespace std;
map<string, int> f;

int main() {
	f["AB"] = f["BC"] = f["CD"] = f["DE"] = f["EA"] = 1;
	f["AC"] = f["BD"] = f["CE"] = f["DA"] = f["EB"] = 2;
	string s1, s2;
	cin >> s1 >> s2;
	if(!f[s1]) swap(s1[0], s1[1]);
	if(!f[s2]) swap(s2[0], s2[1]);
	puts(f[s1] == f[s2] ? "Yes" : "No");
	return 0;
}

C

人家题把上限都告诉你了
然后我\(O(12^3)\) 的枚举不写，写半个小时四进制枚举（

#include<bits/stdc++.h>

using namespace std;

bool check(int x) {
	int a[15], len = 0;
	while(x) a[++ len] = x % 4, x /= 4;
	
	for(int i = len ;i >= 1; -- i) {
		if(!a[i]) return 0;
	}
	for(int i = len; i > 1; -- i) {
		if(a[i] > a[i - 1]) return 0;
	}
	return a[1] == 3;
}

int main() {
	int n, cnt = 0;
	cin >> n;
	for(int i = 0; i < 1 << 24; ++ i) {
		if(check(i)) ++ cnt;
		if(cnt == n) {
			int x = i, len = 0, a[15];
			while(x) a[++ len] = x % 4, x /= 4;
			for(int j = len ;j >= 1; -- j) {
				cout << a[j];
			}
			return 0;
		}
	}
	return 0;
}

D

dfs

#include<bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;

vector<int> H[N];
int fa[N], sz[N];

int dfs(int x) {
	sz[x] = 1;
	for(int y : H[x]) {
		if(y != fa[x]) {
			fa[y] = x;
			sz[x] += dfs(y);
		}
	}
	return sz[x];
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int n;
	cin >> n;
	for(int i = 1; i < n; ++ i) {
		int x, y;
		cin >> x >> y;
		H[x].push_back(y);
		H[y].push_back(x);
	}
	dfs(1);
	int ans = n;
	for(int y : H[1]) ans = min(ans, n - sz[y]);	
	cout << ans;
	return 0;
}

E

贪心，打每个怪用离其最近的药水

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;

int n, op[N], a[N];
bool used[N];

struct Node {
	int p, v;
	bool operator < (const Node &x) const {
		if(v != x.v) return v < x.v;
		else return p > x.p;
	}
};

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	set<Node> se;
	for(int i = 1; i <= n; ++ i) {
		cin >> op[i] >> a[i];
		if(op[i] == 1) se.insert({i, a[i]});
	}
	for(int i = 1; i <= n; ++ i) {
		if(op[i] == 2) {
			auto it = se.lower_bound({i, a[i]});
			auto x = *it;
			if(x.v == a[i]) {
				se.erase(it);
				used[x.p] = 1;
			}
			else return cout << -1, int();
		}
	}
	int cur = 0, ans = 0;
	for(int i = 1; i <= n; ++ i) {
		if(used[i]) ++ cur;
		if(op[i] == 2) -- cur;
		ans = max(ans, cur);
	}
	cout << ans << '\n';
	for(int i = 1; i <= n; ++ i) if(op[i] == 1) cout << used[i] << ' ';
	return 0;
}