很好的题
-
((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;
}