A

算法标签: 模拟

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

	string res;
	if (n % 2) {
		int mid = n / 2;
		for (int i = 0; i < mid; ++i) res += '-';
		res += '=';
		for (int i = mid + 1; i < n; ++i) res += '-';
	}
	else {
		int mid = n / 2;
		for (int i = 0; i < mid - 1; ++i) res += '-';
		res += "==";
		for (int i = mid + 1; i < n; ++i) res += '-';
	}

	cout << res << "\n";
	return 0;
}

---

B

算法标签: 哈希, 模拟

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int N = 7;

map<int, int> mp;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	for (int i = 0; i < N; ++i) {
		int val;
		cin >> val;
		if (mp.count(val)) mp[val]++;
		else mp.insert({val, 1});
	}

	if (mp.size() < 2) {
		cout << "No" << "\n";
		return 0;
	}

	for (auto [val1, cnt1] : mp) {
		for (auto [val2, cnt2] : mp) {
			if (val1 == val2) continue;
			if (cnt1 >= 3 && cnt2 >= 2) {
				cout << "Yes" << "\n";
				return 0;
			}
		}
	}

	cout << "No" << "\n";
	return 0;
}

---

C

算法标签: 哈希, 模拟

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int N = 3e5 + 10;

int n, w[N];
map<int, int> mp;
map<int, int> idx_map;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		if (mp.count(w[i])) mp[w[i]]++;
		else {
			mp.insert({w[i], 1});
			idx_map[w[i]] = i;
		}
	}

	int res = 0;
	for (auto [val, k] : mp) {
		if (k == 1 && val > res) {
			res = val;
		}
	}

	if (idx_map.count(res) == 0) res = -1;
	else res = idx_map[res];

	cout << res << "\n";

	return 0;
}

---

D

算法标签: 哈希, 模拟

思路

$N$的范围是$10^5$, 等价于偏移终点位置, 风的偏移方向和人的方向是相反的
固定高桥君的位置, 改变起始产生烟雾的位置

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

int n, r, c;
string s;
map<PII, int> mp;

int get(char c) {
	if (c == 'S') return 0;
	if (c == 'W') return 1;
	if (c == 'N') return 2;
	return 3;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> r >> c >> s;
	s = ' ' + s;
	mp[{0, 0}] = 1;

	int x = 0, y = 0;
	for (int i = 1; i <= n; ++i) {
		int op = get(s[i]);
		op += 2;
		op %= 4;
		x += dx[op], y += dy[op];
		mp[{x, y}] = 1;
		cout << mp[{r + x, c + y}];
	}

	cout << "\n";
	return 0;
}

---

E

算法标签: 博弈论, 二分图, 交互题

思路

注意到, 没有奇环等价于是二分图, 轮流连边不能破坏二分图的性质
对二分图进行染色, 之间有一些边, 只能点对$(i,j)$分别是白色和黑色, 假设白色点的数量是$a$, 黑色点的数量是$b$, 那么能够加的边的数量是$a\times b-(n-1)$, 如果是奇数必胜, 否则必败

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

typedef pair<int, int> PII;
const int N = 110;

int n, w[N][N];
int color[N];
set<PII> s;

void dfs(int u, int fa) {
	for (int v = 1; v <= n; ++v) {
		if (w[u][v] && v != fa) {
			color[v] = color[u] ^ 1;
			dfs(v, u);
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		w[u][v] = w[v][u] = 1;
	}

	dfs(1, -1);

	// 统计可用的边
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (!w[i][j] && color[i] != color[j]) s.insert({i, j});
		}
	}

	if (s.size() % 2) puts("First");
	else puts("Second");
	
	fflush(stdout);
	
	while (true) {
		if (s.size() % 2) {
			auto [u, v] = *s.begin();
			s.erase(s.begin());
			printf("%d %d\n", u, v);
			fflush(stdout);
		}
		else {
			int u, v;
			scanf("%d%d", &u, &v);
			if (u == -1 && v == -1) return 0;
			s.erase({u, v});
		}
	}
	return 0;
}

---

F

算法标签: 字符串哈希, 回文串

思路

对于一个回文串来说, $a=b$, 因此如果想将当前串补为最短回文串, 就需要找到最长的回文后缀, 因为$a$越长$b$越长, 需要补的长度就越小, 注意到原始字符串长度为$5\times 10^5$, 枚举后缀后要迅速判断是否是回文串, 也就不能扫描, 只能用常数做法, 判断正着读是否等于倒着读, 快速判断两个字符串是否是相等的, 使用哈希

判断后缀是否是回文串, 求每个前缀的哈希值, 再翻转, 然后再计算一遍哈希值

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 5e5 + 10, MOD = 998244353;

int n;
string str;
int pre[N], suff[N];

int main() {
	cin >> str;
	int n = str.size();
	str = " " + str;

	for (int i = n; i >= 1; --i) {
		suff[i] = ((LL) 26 * suff[i + 1] + (str[i] - 'A')) % MOD;
	}

	reverse(str.begin() + 1, str.end());

	int base = 1;
	for (int i = 1; i <= n; ++i) {
		pre[i] = ((LL) pre[i - 1] + (LL) base * (str[i] - 'A') % MOD) % MOD;
		base = (LL) 26ll * base % MOD;
	}

	reverse(pre + 1, pre + n + 1);
	reverse(str.begin() + 1, str.end());

	for (int i = 1; i <= n; ++i) {
		if (pre[i] == suff[i]) {
			for (int k = 1; k <= n; ++k) cout << str[k];
			for (int k = i - 1; k >= 1; --k) cout << str[k];
			cout << "\n";
			break;
		}
	}

	return 0;
}

---

G

算法标签: 博弈论, 二分图

注意到这个图是不一定连通的, 白色点数量和黑色点数量在博弈过程中可以进行更改, 添加边的数量的奇偶性也会更改, 与图的形态没有关系