A.
先利用一半次数来构造()()()()()()的结构(两个一组，找后面不同的第一个位置reverse)
然后构造((()))()()() (对于每个右括号，找后面第一个左括号)
1 #include<bits/stdc++.h> 2 #define pii pair<int,int> 3 #define mp(a,b) make_pair(a,b) 4 #define maxn 2005 5 using namespace std; 6 int T,n,k; 7 char s[maxn]; 8 vector<pii> Ans; 9 int main() 10 { 11 scanf("%d",&T); 12 while(T--) 13 { 14 scanf("%d%d",&n,&k); 15 scanf("%s",s+1); 16 Ans.clear(); 17 for(int i=1;i<=n;++i) 18 { 19 if(s[i]=='(') 20 { 21 int j=i+1; 22 bool yes=0; 23 for(;j<=n;++j)if(s[j]==')'){yes=1;break;} 24 if(yes) 25 { 26 Ans.push_back(mp(i+1,j)); 27 reverse(s+i+1,s+j+1); 28 } 29 i++; 30 } 31 else 32 { 33 int j=i+1; 34 bool yes=0; 35 for(;j<=n;++j)if(s[j]=='('){yes=1;break;} 36 if(yes) 37 { 38 Ans.push_back(mp(i,j)); 39 reverse(s+i,s+j+1); 40 } 41 i++; 42 } 43 } 44 int cnt=n/2; 45 for(int i=1;i<=n;++i)if(s[i]==')') 46 { 47 if(cnt==k)break; 48 for(int j=i+1;j<=n;++j)if(s[j]=='(') 49 { 50 Ans.push_back(mp(i,j)); 51 reverse(s+i,s+j+1); 52 cnt--; 53 break; 54 } 55 } 56 printf("%d\n",Ans.size()); 57 for(auto x:Ans)printf("%d %d\n",x.first,x.second); 58 } 59 }
B.
离线询问，然后贪心从大到小往里加
每次选的位置是值最大情况下位置最小的
然后这个可以线段树维护
回答询问可以线段树上二分
1 #include<bits/stdc++.h> 2 #define maxn 200005 3 using namespace std; 4 int n,m; 5 int a[maxn]; 6 int maxv[maxn<<2]; 7 vector< pair<int,int> > q[maxn]; 8 void pushup(int rt) 9 { 10 maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]); 11 } 12 void build(int rt,int l,int r) 13 { 14 if(l==r){maxv[rt]=a[l];return;} 15 int mid=(l+r)>>1; 16 build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); 17 pushup(rt); 18 } 19 int update(int rt,int l,int r) 20 { 21 if(l==r) 22 { 23 maxv[rt]=0; 24 return l; 25 } 26 int mid=(l+r)>>1,ans=0; 27 if(maxv[rt<<1]>=maxv[rt<<1|1])ans=update(rt<<1,l,mid); 28 else ans=update(rt<<1|1,mid+1,r); 29 pushup(rt); 30 return ans; 31 } 32 int sz[maxn<<2]; 33 void add(int rt,int l,int r,int pos) 34 { 35 sz[rt]++; 36 if(l==r)return; 37 int mid=(l+r)>>1; 38 if(pos<=mid)add(rt<<1,l,mid,pos); 39 else add(rt<<1|1,mid+1,r,pos); 40 } 41 int query(int rt,int l,int r,int k) 42 { 43 if(l==r)return l; 44 int mid=(l+r)>>1; 45 if(k<=sz[rt<<1])return query(rt<<1,l,mid,k); 46 else return query(rt<<1|1,mid+1,r,k-sz[rt<<1]); 47 } 48 int Ans[maxn]; 49 int main() 50 { 51 scanf("%d",&n); 52 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 53 scanf("%d",&m); 54 for(int i=1;i<=m;++i) 55 { 56 int x,y; 57 scanf("%d%d",&x,&y); 58 q[x].push_back(make_pair(y,i)); 59 } 60 build(1,1,n); 61 for(int i=1;i<=n;++i) 62 { 63 int x=update(1,1,n); 64 add(1,1,n,x); 65 for(auto u:q[i]) 66 { 67 int k=u.first,id=u.second; 68 Ans[id]=a[query(1,1,n,k)]; 69 } 70 } 71 for(int i=1;i<=m;++i)printf("%d\n",Ans[i]); 72 }
C.
二分答案\(T\)
然后找出所有可能的起始点(周围\((2T+1)*(2T+1)\)为'X')
然后check是否可行
1 #include<bits/stdc++.h> 2 #define maxn 1000005 3 using namespace std; 4 int n,m; 5 char str[maxn]; 6 vector<char> a[maxn]; 7 vector<int> c[maxn],sum[maxn]; 8 bool full(int x,int y,int k) 9 { 10 if(x-k<1||y-k<1||x+k>n||y+k>m)return 0; 11 int sx=max(1,x-k),sy=max(1,y-k),tx=min(n,x+k),ty=min(m,y+k); 12 return sum[tx][ty]-sum[tx][sy-1]-sum[sx-1][ty]+sum[sx-1][sy-1]==(tx-sx+1)*(ty-sy+1); 13 } 14 bool check(int k) 15 { 16 for(int i=0;i<=n+1;++i) 17 for(int j=0;j<=m+1;++j)c[i][j]=0; 18 for(int i=1;i<=n;++i) 19 for(int j=1;j<=m;++j) 20 { 21 if(full(i,j,k)) 22 { 23 int sx=i-k,sy=j-k,tx=i+k,ty=j+k; 24 c[tx+1][ty+1]++;c[sx][ty+1]--;c[tx+1][sy]--;c[sx][sy]++; 25 } 26 } 27 for(int i=1;i<=n;++i) 28 for(int j=1;j<=m;++j)c[i][j]+=c[i][j-1]; 29 for(int j=1;j<=m;++j) 30 for(int i=1;i<=n;++i)c[i][j]+=c[i-1][j]; 31 for(int i=1;i<=n;++i) 32 for(int j=1;j<=m;++j) 33 { 34 if(c[i][j]&&a[i][j]=='.')return 0; 35 if(!c[i][j]&&a[i][j]=='X')return 0; 36 } 37 return 1; 38 } 39 int main() 40 { 41 scanf("%d%d",&n,&m); 42 for(int i=0;i<=n+1;++i)a[i].resize(m+2),sum[i].resize(m+2),c[i].resize(m+2); 43 for(int i=1;i<=n;++i) 44 { 45 scanf("%s",str+1); 46 for(int j=1;j<=m;++j)a[i][j]=str[j]; 47 } 48 for(int i=1;i<=n;++i) 49 for(int j=1;j<=m;++j)sum[i][j]=(a[i][j]=='X'); 50 for(int i=1;i<=n;++i) 51 for(int j=1;j<=m;++j)sum[i][j]+=sum[i][j-1]; 52 for(int j=1;j<=m;++j) 53 for(int i=1;i<=n;++i)sum[i][j]+=sum[i-1][j]; 54 int l=0,r=max(n,m),ans=0; 55 while(l<=r) 56 { 57 int mid=(l+r)>>1; 58 if(check(mid))ans=mid,l=mid+1; 59 else r=mid-1; 60 } 61 printf("%d\n",ans); 62 for(int i=1;i<=n;++i) 63 { 64 for(int j=1;j<=m;++j)printf("%c",full(i,j,ans)?'X':'.'); 65 puts(""); 66 } 67 }