[C++知识库]第46届ICPC 东亚洲区域赛(澳门)(正式赛) A C F K

A：思维
任意找一条路，如果正着走上坡的次数比下坡多，那么反着走就符合条件了

#pragma GCC optmize(2)
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 100;
int a[N][N];
int n;
bool st[N][N];
int mid = 0;
vector<int>g;

void solve() {
	cin >> n;
	g.clear();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i % 2 == 1) {
			for (int j = 1; j <= n; j++) {
				g.push_back(a[i][j]);
			}
		} else {
			for (int j = n; j >= 1; j--) {
				g.push_back(a[i][j]);
			}
		}
	}
	int up = 0, down = 0;
	for (int i = 1; i < g.size(); i++) {
		if (g[i] > g[i - 1])
			up++;
		else
			down++;
	}
	if (up > down)
		reverse(g.begin(), g.end());
	for (int i = 0; i < g.size(); i++) {
		if (i == g.size() - 1) {
			cout << g[i];
		} else {
			cout << g[i] << " ";
		}
	}
	cout<<endl;

}

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

C:计算几何
想要跑出去，那么剩余的发射器必然在一个半圆中。
所以就用双指针算法来维护一个半圆，这个半圆范围内的发射器都要删除

#pragma GCC optmize(2)
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e6 + 10;
const long double pi = acosl(-1);
long double a[N];


void solve() {
	int n;
	cin >> n;
	int re = n;
	int x, y;
	for (int i = 1; i <= n; i++) {
		cin >> x >> y;
		a[i] = atan2l(1.0 * y, 1.0 * x);//反正切
	}
	sort(a + 1, a + 1 + n);//角度排序
	for (int i = 1; i <= n; i++) {
		a[i + n] = a[i] + 2 * pi;//加了360度,相当于复制
	}
	for (int i = 1, j = 1; i <= n; i++) {
		while (j <= 2 * n && a[j] - a[i] < pi)
			j++;
		re = min(re, j - i - 1);
	}
	cout << re << endl;
}

signed main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

F:(签到)
。。。就很怪的一题，我都不知道为什么能对
用优先队列模拟一下就好了

#pragma GCC optmize(2)
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int n;
const int N = 5e5 + 10;
struct node {
	int val, id;
	bool operator < (const node w)const {
		return val < w.val;
	}
	bool operator > (const node w)const {
		return val > w.val;
	}
} a[N];
priority_queue<node, vector<node>, less<node>>q;
int ans[N];

void solve() {
	cin >> n;
	int all = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].val;
		a[i].id = i;
		all += a[i].val;
		q.push(a[i]);
	}
	if (all > n * (n - 2)) {
		cout << "Recurrent" << endl;
		return;
	}

	int add = 0;
	int ok = 0;
	for (int i = 1; i <=  n; i++) {
		//cout << q.top().val + add << endl;
		if (q.top().val + add < (n - 1)) {
			ok = 1;
			while (q.size()) {
				ans[q.top().id] = q.top().val + add;
				q.pop();
			}
			break;
		} else {
			auto u = q.top();
			q.pop();
			u.val -= n  ;
			add++;
			q.push(u);
		}
	}
	if (!ok) {
		cout << "Recurrent";
		return;
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i];
		if (i != n)
			cout << " ";
	}


}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
}

K
可以按权值从小到大加边，直到出现环
也可以二分限制，大于这个限制的边都不能用
输出边属实是这道题的难点了

#pragma GCC optmize(2)
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n, m;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
vector<PII>g[N];

bool st[N], mark[N];
int way[N];
int aim = 0;
int ok = 0, okp = 0;
int cnt = 0;
void dfs(int u, int fa, int limit) {
	st[u] = mark[u] = true;
	for (auto i : g[u]) {
		if (i.first == fa || i.second > limit)
			continue;

		if (mark[i.first]) {
			ok = 1, okp = i.first;
			mark[u] = 0;
			cnt = 0;
			way[++cnt] = i.second;
			return;
		}
		dfs(i.first, u, limit);
		if (ok) {
			mark[u] = 0;
			if (okp != 0) {
				way[++cnt] = i.second;
			}
			if (okp == u)
				okp = 0;
			return;
		}

	}
	mark[u] = 0;
}

bool check(int limit) {
	ok = 0;
	for (int i = 1; i <= n; i++)
		st[i] = false;
	for (int i = 1; i <= n; i++) {
		if (!st[i]) {
			dfs(i, -1, limit);
			if (ok)
				return true;
		}
	}
	return false;
}



void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		g[i].clear();
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back({v, i});
		g[v].push_back({u, i});
	}
	int ok = 0;
	int l = 0, r = m + 1;
	while (l < r) {
		int mid = l + ((r - l) >> 1);
		if (check(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}

	if (l == m + 1) {
		cout << "-1" << endl;
		return;
	} else {
		sort(way + 1, way + 1 + cnt);
		for (int i = 1; i <= cnt; i++) {
			cout << way[i];
			if (i != cnt)
				cout << " ";
		}

		cout << endl;
	}

}

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