题解 括号密码

传送门

很好的题

  • ((a&1)?1:0)^(b==1) 打成 (a&1)^(b==1) 挂了10pts
  • 关于括号序:
    对于一个括号序列是否合法/使其合法的最小操作次数:
    令 \('('\) 为 \(+1\),\(')'\) 为 \(-1\),求其前缀和 \(a\) 及前缀和最小值 \(w\)
    则括号序列合法的条件是前缀和不存在负数,且总和为0
    若 \(a>0\),则需引进 \(a/2\) 个 \(’)’\),使得 \(a\) 变为0,每次贪心选择最右边的 \(’(‘\) 修改,\(w\) 不改变
    若 \(a<0\) ,需将这里的 \(’)’\) 移除,贪心选择最左边的 \(’)’\) 修改,\(w\) 会增加 \(|a|\)
    最后加上 \(w/2\) 次区间内部操作,使得前缀和不存在负数

然后这里的区间有重叠和嵌套
重叠的处理较显然,把重叠的区间都切开即可,但非常难码,我写的 \(n^2\) 的
然后嵌套的那些会形成树状结构
我显式地把树建出来了,对于一个根节点区间,要先处理它的所有子节点区间,然后把那些已经合法的区间从根节点区间里删掉
这个删的过程可以用vis数组标记实现,建树可以用栈

Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 2010
#define ll long long
//#define int long long

int n, m;
char s2[N];
int ss[N], l[N], r[N], tot0, tot1;

namespace force{
	int ans=INF;
	void solve() {
		int lim=1<<n;
		// cout<<"tot: "<<tot0<<' '<<tot1<<endl;
		for (int s=0,s2,cnt0,cnt1,sum; s<lim; ++s) {
			s2=s; cnt0=cnt1=0; sum=0;
			if (s2) do {++cnt1; s2&=s2-1;} while (s2);
			cnt0=n-cnt1;
			if (cnt0!=tot0 || cnt1!=tot1) continue;
			// cout<<"s: "<<bitset<6>(s)<<endl;
			// cout<<"cnt: "<<cnt0<<' '<<cnt1<<endl;
			for (int i=1; i<=m; ++i) {
				int left=0;
				for (int j=l[i]; j<=r[i]; ++j) {
					if (!(s&(1<<j))) ++left;
					else {if (--left<0) goto jump;}
				}
				if (left) goto jump;
			}
			for (int i=0; i<n; ++i) if ( ((s&(1<<i))?1:0)^(ss[i+1]) ) ++sum;
			// for (int i=0; i<n; ++i) cout<<(s&(1<<i))<<' '<<ss[i+1]<<endl;
			// assert(!(sum&1));
			// cout<<"live: "<<bitset<8>(s)<<endl;
			// cout<<"sum: "<<sum<<endl;
			ans=min(ans, sum/2);
			jump: ;
		}
		printf("%d\n", ans==INF?-1:ans);
		exit(0);
	}
}

namespace task{
	int tot, top, ans;
	int head[N], size, cnt[N], otherl, otherr, own[N];
	bool vis[N];
	struct edge{int to, next;}e[N<<2];
	inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;}
	struct range{int l, r, id; range(){} range(int a, int b):l(a),r(b){} inline void build(int a, int b){l=a; r=b;}}t[N], tem[N*N], sta[N*N];
	inline bool operator == (range a, range b) {return a.l==b.l&&a.r==b.r;}
	inline bool operator < (range a, range b) {return a.l==b.l?a.r>b.r:a.l<b.l;}
	void dfs(int u) {
		// cout<<"dfs: "<<u<<endl;
		for (int i=tem[u].l; i<=tem[u].r; ++i) vis[i]=0;
		for (int i=head[u],v; ~i; i=e[i].next) {
			v = e[i].to;
			dfs(v);
			own[u]+=own[v];
		}
		int w=0, a=0;
		// cout<<"lr: "<<tem[i].l<<' '<<tem[i].r<<endl;
		for (int j=tem[u].l; j<=tem[u].r; ++j) if (!vis[j]) a+=ss[j], w=min(w, a), vis[j]=1;
		// cout<<"a: "<<a<<endl;
		if (a&1) {puts("-1"); exit(0);}
		if (a>0) {
			ans+=abs(a)/2;
			own[u]+=abs(a)/2;
		}
		else {
			own[u]-=abs(a)/2;
			w+=abs(a);
		}
		// cout<<"w: "<<w<<endl;
		if (w<0) {w=-w; ans+=(w+1)/2;}
	}
	void solve() {
		memset(head, -1, sizeof(head));
		for (int i=1; i<=m; ++i) t[i].build(l[i]+1, r[i]+1);
		sort(t+1, t+m+1);
		for (int i=1; i<=m; ++i) {
			bool any=0;
			// cout<<"t: "<<t[i].l<<' '<<t[i].r<<endl;
			int newl=t[i].l, newr=t[i].r;
			for (int j=1; j<=tot; ++j) {
				// cout<<"tem: "<<tem[j].l<<' '<<tem[j].r<<endl;
				if (tem[j].l<=t[i].l && tem[j].r>=t[i].r) sta[++top]=tem[j];
				else if (t[i].l<=tem[j].l && t[i].r>=tem[j].r) sta[++top]=tem[j];
				else if (tem[j].l<t[i].l && t[i].l<=tem[j].r && tem[j].r<t[i].r) {
					sta[++top].build(tem[j].l, t[i].l-1);
					sta[++top].build(t[i].l, tem[j].r);
					// sta[++top].build(tem[j].r+1, t[i].r);
					any=1;
					newl=max(newl, tem[j].r+1);
				}
				else if (t[i].l<tem[j].l && t[i].r>=tem[j].l && t[i].r<tem[j].r) {
					// sta[++top].build(t[i].l, tem[j].l-1);
					sta[++top].build(tem[j].l, t[i].r);
					sta[++top].build(t[i].r+1, tem[j].r);
					any=1;
					newr=min(newr, tem[j].l-1);
				}
				else sta[++top]=tem[j];
			}
			if (!any) sta[++top]=t[i];
			else if (newl<=newr) sta[++top].build(newl, newr);
			sort(sta+1, sta+top+1);
			top=unique(sta+1, sta+top+1)-sta-1;
			for (int j=1; j<=top; ++j) tem[j]=sta[j];
			tot=top; top=0;
		}
		// cout<<"range: "; for (int i=1; i<=tot; ++i) cout<<tem[i].l<<','<<tem[i].r<<' '; cout<<endl;
		// for (int i=1; i<=tot; ++i) assert(tem[i].l<=tem[i].r);
		for (int i=1; i<=tot; ++i) tem[i].id=i;
		for (int i=1; i<=tot; ++i) for (int j=tem[i].l; j<=tem[i].r; ++j) vis[j]=1;
		for (int i=1; i<=n; ++i) if (!vis[i]) ++(ss[i]?otherr:otherl);
		for (int i=1; i<=n; ++i) ss[i]=ss[i]?-1:1;
		for (int i=1; i<=tot; ++i) if ((tem[i].r-tem[i].l+1)&1) {puts("-1"); exit(0);}
		// cout<<"other: "<<other<<endl;
		for (int i=1; i<=tot; ++i) {
			while (top && sta[top].r<tem[i].l) --top;
			if (!top) sta[++top]=tem[i];
			else add(sta[top].id, tem[i].id), sta[++top]=tem[i], ++cnt[tem[i].id];
		}
		int need=0;
		// cout<<"ss: "; for (int i=1; i<=n; ++i) cout<<ss[i]<<' '; cout<<endl;
		for (int i=1; i<=tot; ++i) if (!cnt[i]) {
			// cout<<"i: "<<i<<endl;
			dfs(i);
			need+=own[i];
		}
		// cout<<"need: "<<need<<endl;
		// cout<<"other: "<<otherl<<' '<<otherr<<endl;
		// cout<<"own: "; for (int i=1; i<=tot; ++i) cout<<own[i]<<' '; cout<<endl;
		if (need>0 && need>otherr) {puts("-1"); exit(0);}
		if (need<0 && -need>otherl) {puts("-1"); exit(0);}
		if (need<0) ans+=-need;
		printf("%d\n", ans);
		exit(0);
	}
}

signed main()
{
	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);

	scanf("%s%d", s2+1, &m);
	n=strlen(s2+1);
	for (int i=1; i<=n; ++i) {
		if (s2[i]=='(') {ss[i]=0; ++tot0;}
		else {ss[i]=1; ++tot1;}
	}
	for (int i=1; i<=m; ++i) scanf("%d", &l[i]);
	for (int i=1; i<=m; ++i) scanf("%d", &r[i]);
	// force::solve();
	task::solve();
	
	return 0;
}
上一篇:[PAT 甲级] 1016 Phone Bills (25 分)


下一篇:Could not load native libraries