Codeforces Round #709 (Div.1, based on Technocup 2021 Final Round)

比赛链接 / 官方题解链接

A. Basic Diplomacy

比赛时没多想，直接上二分图跑最大流了。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;
const int M = 400005;
const LL INF = 1e14;

namespace FLOW{

	int n, S, T;
	struct Edge{
		int nxt, to;
		LL flow;
	}edge[M<<1];
	int head[N], edgeNum = 1;
	void addEdge(int from, int to, LL flow){
		edge[++edgeNum] = (Edge){head[from], to, flow};
		head[from] = edgeNum;
	}
	inline void ae(int from, int to, LL flow){
		addEdge(from, to, flow);
		addEdge(to, from , 0);
	}

	bool inq[N];
	int dep[N], curArc[N];
	inline bool bfs(){
		for(int i = 1; i <= n; i++)
			dep[i] = 1e9, inq[i] = 0, curArc[i] = head[i];
		queue<int> q;
		q.push(S);
		inq[S] = 1;
		dep[S] = 0;
		while(!q.empty()){
			int cur = q.front(); q.pop();
			inq[cur] = 0;
			for(int i = head[cur]; i; i = edge[i].nxt){
				if(dep[edge[i].to] > dep[cur] + 1 && edge[i].flow){
					dep[edge[i].to] = dep[cur] + 1;
					if(!inq[edge[i].to]){
						q.push(edge[i].to);
						inq[edge[i].to] = 1;
					}
				}
			}
		}
		if(dep[T] != 1e9)	return 1;
		return 0;
	}
	LL dfs(int x, LL minFlow){
		LL flow = 0;
		if(x == T)	return minFlow;
		for(int i = curArc[x]; i; i = edge[i].nxt){
			curArc[x] = i;
			if(dep[edge[i].to] == dep[x] + 1 && edge[i].flow){
				flow = dfs(edge[i].to, min(minFlow, edge[i].flow));
				if(flow){
					edge[i].flow -= flow;
					edge[i^1].flow += flow;
					return flow;
				}
			}
		}
		return 0;
	}
	inline LL Dinic(){
		LL maxFlow = 0, flow = 0;
		while(bfs()){
			while(flow = dfs(S, INF))
				maxFlow += flow;
		}
		return maxFlow;
	}
}

int main(){
	int T; for(read(T); T; T--){
		int n, m; read(n, m);
		FLOW::T = FLOW::n = n + m + 2;
		FLOW::S = n + m + 1;
		for(int i = 1; i <= FLOW::n; i++)	FLOW::head[i] = 0;
		FLOW::edgeNum = 1;

		for(int i = 1; i <= m; i++){
			int k; read(k);
			while(k--){
				int j; read(j);
				FLOW::ae(j, i + n, 1);
			}
			FLOW::ae(i + n, FLOW::T, 1);
		}
		for(int i = 1; i <= n; i++)
			FLOW::ae(FLOW::S, i, (m + 1) / 2);
		LL mxflow = FLOW::Dinic();
		if(mxflow == m){
			puts("YES");
			for(int i = 1; i <= m; i++){
				for(int j = FLOW::head[i+n]; j; j = FLOW::edge[j].nxt){
					int to = FLOW::edge[j].to;
					if(to == FLOW::T)	continue;
					if(FLOW::edge[j^1].flow == 0)	printf("%d ", to);
				}
			}
			puts("");
		}
		else	puts("NO");
	}
	return 0;
}

---

B. Playlist

实现起来有点恶心，用链表来方便删除元素，用类似并查集的思想来查找下一个互质的元素，但是要处理并查集上每个点都以下一个点为父节点而构成环的情况。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }

const int N = 100005;

int n, a[N], nxt[N], to[N];
bool circle[N];
vi inc;
int getto(int x){
	if(circle[x])	return -1;
	circle[x] = true;
	inc.pb(x);
	return to[x] == x ? x : to[x] = getto(to[x]);
}

int main(){
	// freopen("data.in", "r", stdin);
	int T; for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i]);
		for(int i = 1; i <= n; i++){
			nxt[i] = i == n ? 1 : i + 1;
			if(gcd(a[i], a[nxt[i]]) > 1)	to[i] = nxt[i];
			else	to[i] = i;
			circle[i] = false;
		}
		inc.clear();
		int now = 1;
		vi ans;
		vector<bool> del(n+1, false);
		while(1){
			if(del[now])	break;
			now = getto(now);
			if(now == -1)	break;
			for(auto &d : inc)	circle[d] = false;
			inc.clear();
			if(gcd(a[nxt[now]], a[now]) == 1){
				ans.pb(nxt[now]);
				del[nxt[now]] = true;
				nxt[now] = nxt[nxt[now]];
				if(gcd(a[nxt[now]], a[now]) > 1)
					to[now] = nxt[now];
				now = nxt[now];
			}
			else	break;
		}
		printf("%d ", (int)ans.size());
		for(auto &k : ans)	printf("%d ", k);
		puts("");
	}
	return 0;
}

---

C. Skyline Photo

很容易想到一个 $\text{dp}$ 的思路：设 $dp[i]$ 表示前 $i$ 个房子能得到的最大 beauty，那么：

$$dp[i]=\max_{0\leqslant j<i}\left\{dp[j]+b[p_{j+1,i}]\right\}$$

其中 $p_{a,b}=\arg\min\limits_{a\leqslant k\leqslant b} h[k]$. 也就是枚举分割点 $j$，然后把 $j+1\sim i$ 分到一段。

直接按此做是 $O(n^2)$ 的，我们需要优化。设 $t$ 是最后一个 $h[t]<h[i]$ 的位置（单调队列+二分可以处理出来），那么当 $t\leqslant j<i$ 时，$b[p_{j+1,i}]$ 就等于 $b[i]$，换句话说，我们称 $b[i]$ 覆盖了 $[t,i)$ 这个区间；同理，我们可以找到每个位置能覆盖到的区间，然后进行区间覆盖即可。最后，我们只需要维护 $dp+b$ 的区间最大值，所以一个线段树就可以搞定。

复杂度：$O(n\lg n)$.

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 300005;
const LL INF = 1e14;

int n, h[N];
LL b[N], dp[N];
vector<pii> v;

struct segTree{
	int l, r;
	LL dp, dpb, lazyb;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
	tr[id].dp = max(tr[lid].dp, tr[rid].dp);
	tr[id].dpb = max(tr[lid].dpb, tr[rid].dpb);
}
inline void pushdown(int id){
	if(tr[id].l == tr[id].r)	return;
	if(tr[id].lazyb != -INF){
		tr[lid].dpb = tr[lid].dp + tr[id].lazyb;
		tr[lid].lazyb = tr[id].lazyb;
		tr[rid].dpb = tr[rid].dp + tr[id].lazyb;
		tr[rid].lazyb = tr[id].lazyb;
		tr[id].lazyb = -INF;
	}
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].dp = tr[id].dpb = 0;
	tr[id].lazyb = -INF;
	if(l == r){ tr[id].dpb = b[l]; return; }
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
void modify(int id, int l, int r, LL val){
	if(l > r)	return;
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r){
		tr[id].lazyb = val;
		tr[id].dpb = tr[id].dp + val;
		return;
	}
	if(r <= mid)	modify(lid, l, r, val);
	else if(l > mid)	modify(rid, l, r, val);
	else	modify(lid, l, mid, val), modify(rid, mid+1, r, val);
	pushup(id);
}
void add(int id, int pos, LL val){
	pushdown(id);
	if(tr[id].l == tr[id].r){
		tr[id].dpb = tr[id].dpb - tr[id].dp + val;
		tr[id].dp = val;
		return;
	}
	if(pos <= mid)	add(lid, pos, val);
	else	add(rid, pos, val);
	pushup(id);
}
LL querydpb(int id, int l, int r){
	if(l > r)	return -INF;
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r)	return tr[id].dpb;
	if(r <= mid)	return querydpb(lid, l, r);
	else if(l > mid)	return querydpb(rid, l, r);
	else	return max(querydpb(lid, l, mid), querydpb(rid, mid+1, r));	
}

int main(){
	read(n);
	build(1, 0, n);
	for(int i = 1; i <= n; i++)	read(h[i]);
	for(int i = 1; i <= n; i++)	read(b[i]), modify(1, i, i, b[i]);
	for(int i = 1; i <= n; i++){
		dp[i] = -INF;
		while(!v.empty() && h[i] < v.back().second)	v.pop_back();
		v.pb(mp(i, h[i]));
		int l = 0, r = v.size() - 1;
		while(l < r){
			int md = (l + r + 1) >> 1;
			if(v[md].second < h[i])	l = md;
			else	r = md - 1;
		}
		int pos = v[l].second < h[i] ? v[l].first : 0;

		modify(1, pos, i, b[i]);
		dp[i] = max(dp[i], querydpb(1, 0, i-1));
		add(1, i, dp[i]);
	}
	printf("%lld\n", dp[n]);
	return 0;
}