ABC355 A ~ D

A

可能写麻烦了，但是至少它对了。

#include <bits/stdc++.h>
#define gt getchar
#define pt putchar

typedef long long ll;
const int MAXN = 2e5 + 5;
const int mod = 998244353;

ll read() {
	ll x = 0, f = 1;char ch = gt();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = gt();}
	while (ch >= '0' && ch <= '9') {x *= 10;x += ch - '0';ch = gt();}
	return x * f;
}

ll a[5];

int main() {
	a[read()] = a[read()] = 1;
	ll res = 0;
	for (int i = 1; i <= 3; i++) {
		if(a[i] == 0) {
			if(res == 0) res = i;
			else {
				std::cout << -1;
				return 0;
			}
		}
	}
	std::cout << res;
	return 0;
}

B

\(f_i\) 表示 \(i\) 在 \(a\) 中是否出现过。

搞到一起之后排序，判断即可。

#include <bits/stdc++.h>
#define gt getchar
#define pt putchar

typedef long long ll;
const int MAXN = 2e5 + 5;
const int mod = 998244353;

ll read() {
	ll x = 0, f = 1;char ch = gt();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = gt();}
	while (ch >= '0' && ch <= '9') {x *= 10;x += ch - '0';ch = gt();}
	return x * f;
}

ll a[MAXN], b[MAXN], c[MAXN];
bool f[MAXN];

int main() {
	ll n = read(), m = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		c[i] = a[i];
		f[a[i]] = true;
	}
	for (int i = 1; i <= m; i++) {
		b[i] = read();
		c[i + n] = b[i];
	}
	ll len = n + m;
	std::sort(c + 1, c + len + 1);
	for (int i = 1; i < len; i++) {
		if(f[c[i]] && f[c[i + 1]]) {
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

C

\(hang_i\) 表示第 \(i\) 行被涂的格子的个数。

\(lie_i\) 表示第 \(i\) 列被涂的格子的个数。

\(xie1,xie2\) 表示两条对角线上被涂的格子的个数。

行和列都好处理，对角线可以通过 \(O(n)\) 预处理。

#include <bits/stdc++.h>
#define gt getchar
#define pt putchar

typedef long long ll;
const int MAXN = 4e6 + 5;
const int mod = 998244353;

ll read() {
	ll x = 0, f = 1;char ch = gt();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = gt();}
	while (ch >= '0' && ch <= '9') {x *= 10;x += ch - '0';ch = gt();}
	return x * f;
}

ll hang[MAXN], lie[MAXN];
ll dui1, dui2;
bool f[MAXN], g[MAXN];
//f左上-右下对角线经过的数值
//g右上-坐下对角线经过的数值

int main() {
	ll n = read(), t = read();
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		f[(i - 1) * n + i] = true;
		g[i * n - i + 1] = true;
		//预处理
	}
	for (int i = 1; i <= t; i++) {
		ll a = read();
		if(ans) continue;
		ll nowhang;
		if(a % n == 0) nowhang = a / n;
		else nowhang = a / n + 1;
		ll nowlie;
		if(a % n != 0) nowlie = a % n;
		else nowlie = n;
		//当前这个数在第几行、第几列
		hang[nowhang]++;
		if(hang[nowhang] == n) {
			ans = i;
			continue;
		}
		lie[nowlie]++;
		if(lie[nowlie] == n) {
			ans = i;
			continue;
		}
		//边改变当前行的数值边判断
		if(f[a]) {
			dui1++;
			if(dui1 == n) {
				ans = i;
				continue;
			}
		}
		if(g[a]) {
			dui2++;
			if(dui2 == n) {
				ans = i;
				continue;
			}
		}
		//对角线
	}
	std::cout << (ans == 0 ? -1 : ans);
	return 0;
}

D

按照左端点排序，左端点相同就按照右端点排序。

枚举 \(1\sim n\)，二分找到 \(i\) 后面的区间第一个 \(j\) 满足 \(l_j > r_i\)，也就是这两个区间没有重合，把答案增加 \(j - 1 - i\)。

不用考虑 \(i\) 前面的区间，因为在考虑位置 \(<i\) 的线段的时候已经考虑过了。

警钟长鸣，不要忘记删 std::cerr 调试语句！

#include <bits/stdc++.h>
#define gt getchar
#define pt putchar

typedef long long ll;
const int MAXN = 5e5 + 5;
const int mod = 998244353;

ll read() {
	ll x = 0, f = 1;char ch = gt();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = gt();}
	while (ch >= '0' && ch <= '9') {x *= 10;x += ch - '0';ch = gt();}
	return x * f;
}

ll n;
std::pair<ll, ll> a[MAXN];
ll c[MAXN];

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i].first = read();
		a[i].second = read();
	}
	std::sort(a + 1, a + n + 1);
	ll res = 0;
	for (int i = 1; i <= n; i++) c[i] = a[i].first;//为了方便二分，用 c 储存排序后的 l[i]
	for (int i = 1; i < n; i++) {
		ll p = std::upper_bound(c + i + 1, c + n + 1, a[i].second) - c;
		res += p - 1 - i;
	}
	std::cout << res << '\n';
	return 0;
}