现场做出 ABCDE，然后 D 因为犯了傻逼错误被 cha 了…

Reverse a Substring

因为忘了下标从 1 开始 WA 了一发。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
char s[N];
int n;
int main()
{
	scanf("%d%s", &n, s);
	for (int i = 1; i < n; ++i)
		if (s[i] < s[i - 1])
			return printf("YES\n%d %d", i, i + 1), 0;
	printf("NO");
}

Game with Telephone Numbers

两个人的必胜策略，一个是优先拿最靠前的 8，另一个是优先拿最靠前的非 8，模拟一下即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
char s[N];
int n;
vector<int> v[2];
int main()
{
	scanf("%d%s", &n, s);
	for (int i = 0; i < n; ++i)
		v[s[i] == '8'].push_back(i);
	n = (n - 11) / 2;
	if (v[0].size() <= n)
		return printf("YES"), 0;
	if (v[1].size() <= n)
		return printf("NO"), 0;
	printf(v[0][n] > v[1][n] ? "YES" : "NO");
}

Alarm Clocks Everywhere

选择的间隔一定要是所有间隔之差的因子，搞一下就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 9;
ll n, m, x[N];
int main()
{
	scanf("%lld%lld", &n, &m);
	for (ll i = 0; i < n; ++i)
		scanf("%lld", &x[i]);
	ll g = 0;
	for (ll i = 1; i < n; ++i)
		g = __gcd(g, x[i] - x[i - 1]);
	for (ll i = 0, p; i < m; ++i)
	{
		scanf("%lld", &p);
		if (g % p == 0)
			return printf("YES\n%lld %lld", x[0], i + 1), 0;
	}
	printf("NO");
}

Beautiful Array

犯了沙雕错误被 cha 了…

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 9;
ll n, x, ans, a[N];
int main()
{
	scanf("%lld%lld", &n, &x);
	for (ll i = 0, a, pre[3] = {0, 0, 0}; i < n; ++i)
	{
		scanf("%lld", &a);
		ans = max(ans, pre[2] = max(0LL, max(pre[0], max(pre[1], pre[2]))) + a);
		ans = max(ans, pre[1] = max(0LL, max(pre[0], pre[1])) + a * x);
		ans = max(ans, pre[0] = max(0LL, pre[0]) + a);
	}
	printf("%lld", ans);
}

Guess the Root

同余系下做一次拉格朗日插值就能把所有的系数求出来了，然后对同余系内的每个数暴力去判一下就行了。

看了一下正解是用高斯消元求各项系数的，大同小异了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef ll lf;
typedef complex<lf> Coord;
#define X real()
#define Y imag()
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {} //预处理开方，优化乘法
	ll add(ll a, ll b) const { return ((a + b) % M + M) % M; }
	ll mul(ll a, ll b) const
	{
		while (a < 0)
			a += M;
		while (b < 0)
			b += M;
		return a * b % M;
	}
	/*
	ll mul(ll x, ll y) const //无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%m
	{
		ll a = x / SM, b = x % SM;
		ll c = y / SM, d = y % SM;
		ll e = SM * SM - M; //可能为负
		ll f = ((a * d + b * c) % M + a * c / SM * e) % M;
		return add(((a * c % SM + f / SM) * e % M + f % SM * SM) % M, b * d);
	}
	ll mul(ll a, ll b) const //另一个快速乘法版本
	{
		ll r = 0;
		for (a %= M; b; b >>= 1, a = add(a, a))
			if (b & 1)
				r = add(r, a);
		return r;
	}
	*/
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		for (a %= M; b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}
	ll inv(ll a) const
	{
		while (a < 0)
			a += M;
		return pow(a, M - 2);
	} //return pow(a, phi(m) - 1, m);
	/*//模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
	ll inv(ll a) const
	{
		ll x, y, d = gcd(a, m, x, y);
		return d == 1 ? (x + m) % m : -1;
	}
	*/
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
} M(1e6 + 3);
struct Lagrange
{
	vector<lf> ask(vector<Coord> p) const //返回p确定的多项式系数向量
	{
		vector<lf> ret(p.size()), sum(p.size());
		ret[0] = p[0].Y, sum[0] = 1;
		for (int i = 1; i < p.size(); ++i)
		{
			for (int j = p.size() - 1; j >= i; --j)
				p[j].imag(M.mul(p[j].Y - p[j - 1].Y, M.inv(p[j].X - p[j - i].X)));
			for (int j = i; ~j; --j)
			{
				sum[j] = M.add(j ? sum[j - 1] : 0, -M.mul(sum[j], p[i - 1].X));
				ret[j] = M.add(ret[j], M.mul(sum[j], p[i].Y));
			}
		}
		return ret;
	}
};
int main()
{
	vector<Coord> v;
	for (ll i = 0, j; i < 11; ++i)
	{
		printf("? %lld\n", i), fflush(stdout);
		scanf("%lld", &j);
		if (j == 0)
			return printf("! %d", i), 0;
		v.push_back({i, j % M.M});
	}
	vector<ll> ret = Lagrange().ask(v);
	for (ll i = 0; i < M.M; ++i)
	{
		ll sum = 0;
		for (ll j = 0, x = 1; j < ret.size(); ++j, x = M.mul(x, i))
			sum = M.add(sum, M.mul(x, ret[j]));
		if (sum == 0)
			return printf("! %d", i), 0;
	}
	printf("! -1");
}

Delivery Oligopoly

给你一张双连通图，要你去掉尽可能多的边并保持双连通的性质。

随机化+tarjan 实现，正解似乎是 dp。

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
vector<pair<int, int>> ans(N *N), cur, bb(N);
vector<int> g[N], dep, b(N);
int n, m;
int dfs(int u, int fa)
{
	int low = b[u] = dep[u] = fa != N ? dep[fa] + 1 : 0;
	random_shuffle(g[u].begin(), g[u].end());
	for (auto to : g[u])
		if (to != fa)
			if (dep[to] == N)
			{
				cur.emplace_back(u, to);
				low = min(low, dfs(to, u));
				if (b[u] > b[to])
					b[u] = b[to], bb[u] = bb[to];
			}
			else if (b[u] > dep[to])
				b[u] = dep[to], bb[u] = {u, to};
	if (fa != N && low == dep[u])
		low = b[u], cur.push_back(bb[u]);
	return low;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, u, v; i < m; ++i)
		scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u);
	for (auto t = clock() + 1926; clock() < t;)
	{
		cur.clear(), dep.assign(n + 1, N), dfs(rand() % n + 1, N);
		if (ans.size() > cur.size())
			ans = cur;
	}
	printf("%d\n", ans.size());
	for (auto it : ans)
		printf("%d %d\n", it.first, it.second);
}