Best Subsequence

贪心。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
set<pair<int, int>> q;
int n, k, a[N], pre[N], nxt[N];
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &a[i]);
		pre[i] = (i - 1 + n) % n;
		nxt[i] = (i + 1) % n;
	}
	for (int i = 0; i < n; ++i)
		q.emplace(a[i] + a[nxt[i]], i);
	while (q.size() > k)
	{
		int x = q.rbegin()->second;
		if (a[x] < a[nxt[x]])
			x = nxt[x];
		q.erase({a[x] + a[nxt[x]], x});
		q.erase({a[pre[x]] + a[x], pre[x]});
		q.emplace(a[pre[x]] + a[nxt[x]], pre[x]);
		nxt[pre[x]] = nxt[x];
		pre[nxt[x]] = pre[x];
	}
	printf("%d", q.rbegin()->first);
}

现场打了个二分+DP+离散化+树状数组前缀最小值

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int N = 2e5 + 9, INF = 2e9 + 9;
int n, k, a[N];
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
} rk;
struct Fenwick : vector<ll>
{
	Fenwick(int n) : vector<ll>(n, 0) {}
	ll ask(int x)
	{
		ll r = 0;
		for (; x; x -= x & -x)
			r = max(r, at(x));
		return r;
	}
	void upd(int x, ll val)
	{
		for (; x < size(); x += x & -x)
			at(x) = max(at(x), val);
	}
};
int ok(int m)
{
	Fenwick t(rk.size() + 9);
	t.upd(rk.ask(a[1]) + 2, 1);
	for (int i = 2; i <= n; ++i)
		if (m - a[i] > 0)
		{
			ll now = t.ask(rk.ask(m - a[i] + 1) - 1 + 2);
			if (now > 0)
			{
				if (m - a[i] >= a[1] && now + 1 >= k)
					return 1;
				t.upd(rk.ask(a[i]) + 2, now + 1);
			}
		}
	return 0;
}
int bs(int b, int e)
{
	if (e - b < 2)
		return e;
	int m = b + (e - b >> 1);
	return ok(m) ? bs(b, m) : bs(m, e);
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]), rk.push_back(a[i]);
	rk.push_back(INF);
	rk.push_back(-INF);
	rk.init();
	rotate(a + 1, min_element(a + 1, a + n + 1), a + n + 1);
	printf("%d", bs(0, INF));
}

Cool Pairs

构造。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 9;
ll n, k, a[N], b[N], c[N];
int main()
{
	scanf("%lld%lld", &n, &k);
	for (ll i = 0, x; i < n; ++i)
	{
		scanf("%lld", &x), --x;
		a[x] = i - n;
		b[x] = n;
	}
	for (ll i = 0, x; k && i < n; ++i)
	{
		scanf("%lld", &x), --x;
		if (k >= x)
		{
			k -= x;
			b[x] = -n;
		}
		else
		{
			copy(a, a + x, c);
			nth_element(c, c + k - 1, c + x);
			b[x] = -c[k - 1] - 1;
			k = 0;
		}
	}
	printf("Yes\n");
	for (ll i = 0; i < n; ++i)
		printf("%lld ", a[i]);
	printf("\n");
	for (ll i = 0; i < n; ++i)
		printf("%lld ", b[i]);
}

Free Edges

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> g[N];
int n, m, vis[N];
void dfs(int u)
{
	vis[u] = 1;
	for (int to : g[u])
		if (!vis[to])
			dfs(to);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, x, y; i < m; ++i)
	{
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; ++i)
		if (!vis[i])
			dfs(i), ++m;
	printf("%d", m - n);
}