題解之前

今天是三體的題目背景，比什么美好的每一天好理解多了。

水滴

難得的NOIP模擬題，滑窗解決。
也可以二分區間長度，再進行統計。

我的\(nlogn\)算法

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<ctime>
#define FN "drop"

const int maxn=2e5+5;
int dan[maxn];
int cnt[maxn];
int need[maxn];
int n,k,R;

bool check(int len) {
	memset(cnt,0,sizeof cnt);
	int res=R;
	for(int i=1;i<=len;i++) {
		cnt[dan[i]]++;
		if(cnt[dan[i]]==need[dan[i]]) --res;
		if(!res) return true;
	}
	for(int l=2,r=len+1;r<=n;l++,r++) {
		--cnt[dan[l-1]];
		if(cnt[dan[l-1]]==need[dan[l-1]]-1) ++res;
		++cnt[dan[r]];
		if(cnt[dan[r]]==need[dan[r]]) --res;
		if(!res) return true;
	}
	return false;
}

int main() {
	freopen(FN".in","r",stdin);
	freopen(FN".out","w",stdout);
	int T;scanf("%d",&T);
	while(T--) {
		memset(need,0,sizeof need);
		memset(dan,0,sizeof dan);
		scanf("%d%d%d",&n,&k,&R);
		for(int i=1;i<=n;i++) scanf("%d",dan+i);
		for(int i=1;i<=R;i++) {
			int c,num;scanf("%d%d",&c,&num);
			need[c]=num;
		}
		int l=0,r=n+1,ans=-1;
		while(l<r) {
			int mid=l+r>>1;
			if(check(mid)) {
				ans=mid;
				r=mid;
			}
			else l=mid+1;
		}
		if(!~ans) printf("DESTROY ALL\n");
		else  printf("%d\n",ans);
	}
	return 0;
}

std的O(n)算法

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 200000;
int D[MAXN + 5], ned[MAXN + 5];
int tot[MAXN + 5], nw[MAXN + 5];
void solve() {
	int N, K, R;
	scanf("%d%d%d", &N, &K, &R);
	for(int i=0;i<K;i++)
		ned[i] = tot[i] = 0;
	for(int i=1;i<=N;i++) {
		scanf("%d", &D[i]);
		tot[D[i]]++;
	}
	for(int i=1;i<=R;i++) {
		int B, Q;
		scanf("%d%d", &B, &Q);
		ned[B] = Q;
	}
	for(int i=0;i<K;i++)
		if( tot[i] < ned[i] ) {
			puts("DESTROY ALL");
			return ;
		}
	int ans = N, re = R, le = 1, ri = 0;
	while( le <= N ) {
		while( ri + 1 <= N && re ) {
			nw[D[++ri]]++;
			if( nw[D[ri]] == ned[D[ri]] )
				re--;
		}
		if( !re ) ans = min(ans, ri-le+1);
		if( nw[D[le]] == ned[D[le]] ) re++;
		nw[D[le++]]--;
	}
	printf("%d\n", ans);
}
int main() {
	freopen("drop.in", "r", stdin);
	freopen("drop.out", "w", stdout);
	int T;
	scanf("%d", &T);
	for(int i=1;i<=T;i++)
		solve();
}

“神“

2-SAT裸題？

一眼看出來2-SAT，邊都連好了，寫不來算法。

太菜了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 5000;
struct edge{
	int to;
	edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v) {
	edge *p = (++ecnt);
	p->to = v, p->nxt = adj[u], adj[u] = p;
}
void init() {
	ecnt = &edges[0];
	for(int i=0;i<=MAXN;i++)
		adj[i] = NULL;
}
bool vis[MAXN + 5];
void dfs(int x) {
	vis[x] = true;
	for(edge *p=adj[x];p!=NULL;p=p->nxt)
		if( !vis[p->to] ) dfs(p->to);
}
void solve() {
	init(); int N, M;
	scanf("%d%d", &N, &M);
	for(int i=1;i<=M;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		if( u < 0 )
			u = (-u-1)<<1|1;
		else u = (u-1)<<1;
		if( v < 0 )
			v = (-v-1)<<1|1;
		else v = (v-1)<<1;
		addedge(u, v^1);
		addedge(v, u^1);
	}
	int ans = 3;
	for(int i=0;i<N;i++) {
		bool f1 = false, f2 = false, f3 = false;
		for(int j=0;j<(N<<1);j++)
			vis[j] = false;
		dfs(i<<1);
		f1 = vis[i<<1|1];
		for(int j=0;j<(N<<1);j++)
			vis[j] = false;
		dfs(i<<1|1);
		f2 = vis[i<<1];
		for(int j=0;j<N;j++)
			f3 = f3 || vis[j<<1];
		if( f1 && f2 ) ans = min(ans, 0);
		else if( f2 ) ans = min(ans, 1);
		else if( f3 ) {
			if( f1 ) ans = min(ans, 1);
			else ans = min(ans, 2);
		}
	}
	if( ans == 3 ) puts("No Way");
	else printf("%d\n", ans);
}
int main() {
	freopen("god.in", "r", stdin);
	freopen("god.out", "w", stdout);
	int T;
	scanf("%d", &T);
	for(int i=1;i<=T;i++)
		solve();
}

執劍人

貪心+數據結構。

只會貪心，于是只有60分。

用后綴和來選出槍斃名單。
用棧存從一邊開始的槍斃名單，線段樹從另外一邊開始操作。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = (1<<30);
const int MAXN = 500000;
struct query{
	int ri, ind;
	query(int _r, int _i):ri(_r), ind(_i){}
};
vector<query>qry[MAXN + 5];
char str[MAXN + 5];
int stk[MAXN + 5], ans[MAXN + 5], top;
struct node{
	int mss, sum;
	int le, ri;
}tree[4*MAXN + 5];
void PushUp(int x) {
	tree[x].mss = min(tree[x<<1|1].mss, tree[x<<1].mss + tree[x<<1|1].sum);
	tree[x].sum = tree[x<<1].sum + tree[x<<1|1].sum;
}
void Build(int x, int l, int r) {
	tree[x].le = l, tree[x].ri = r;
	if( l == r ) {
		tree[x].mss = tree[x].sum = 0;
		return ;
	}
	int mid = (l + r) >> 1;
	Build(x<<1, l, mid);
	Build(x<<1|1, mid+1, r);
	PushUp(x);
}
void Modify(int x, int pos, int key) {
	if( pos > tree[x].ri || pos < tree[x].le )
		return ;
	if( tree[x].le == tree[x].ri ) {
		tree[x].sum = tree[x].mss = key;
		return ;
	}
	Modify(x<<1, pos, key);
	Modify(x<<1|1, pos, key);
	PushUp(x);
}
node Query(int x, int pos) {
	if( tree[x].ri <= pos )
		return tree[x];
	int mid = (tree[x].le + tree[x].ri) >> 1;
	if( pos <= mid )
		return Query(x<<1, pos);
	else {
		node ret = Query(x<<1|1, pos);
		ret.mss = min(ret.mss, ret.sum + tree[x<<1].mss);
		ret.sum = ret.sum + tree[x<<1].sum;
		return ret;
	}
}
inline int Read() {
	char ch = getchar(); int x = 0, f = 1;
	while( (ch > '9' || ch < '0') && ch != '-' ) ch = getchar();
	if( ch == '-' ) f = -1, ch = getchar();
	while( '0' <= ch && ch <= '9' )
		x = 10*x + ch-'0', ch = getchar();
	return x * f;
}
int main() {
	freopen("sworder.in", "r", stdin);
	freopen("sworder.out", "w", stdout);
	int N, Q;
	scanf("%d%s%d", &N, str+1, &Q);
	for(int i=1;i<=Q;i++) {
		int l, r;
		l = Read(), r = Read();
		qry[l].push_back(query(r, i));
	}
	Build(1, 1, N); top = N+1;
	for(int i=N;i>=1;i--) {
		if( str[i] == 'C' )
			stk[--top] = i;
		else {
			if( top != N+1 ) {
				Modify(1, stk[top], -1);
				stk[top++] = 0;
			}
			Modify(1, i, 1);
		}
		for(int j=0;j<qry[i].size();j++) {
			int p = upper_bound(stk+top, stk+N+1, qry[i][j].ri) - stk;
			ans[qry[i][j].ind] = (p-top) - min(0, Query(1, qry[i][j].ri).mss);
		}
	}
	for(int i=1;i<=Q;i++)
		printf("%d\n", ans[i]);
}

于是今天愉快地拿到了大眾分數。