B题:Crazy Binary String
把0看成-1,前缀和,pos[ 0+n ] = 0
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+3; int a[maxn]; int pos[maxn<<1]; string s; int main(){ ios::sync_with_stdio(false); int n; cin>>n>>s; for(int i=0; i<n; i++){ if(s[i]=='0') a[i] = a[i-1] -1; else a[i] = a[i-1] + 1; } for(int i=0; i<=2*n; i++){ pos[i] = -1; } pos[ 0+n ] = 0; //注意这个不是简单的0 而是 0+n int ans=0; for(int i=0; i<n; i++){ if(pos[ n+a[i] ]!=-1) ans = max(ans, i-pos[ n+a[i] ]); else{ pos[ n+a[i] ] = i; } } cout<<ans<<" "; int zero=0; for(int i=0; i<n; i++){ zero += s[i]=='0'; } cout<<( min(zero,n-zero)<<1 )<<endl; }
H题: Magic Line
排序 ,找 n/2点 和 n/2+1点
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn=20000; const int M=900000009; struct Point{ int x,y; }po[maxn]; bool cmp(Point a,Point b){ if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } int main(){ int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&po[i].x,&po[i].y); } sort(po+1,po+1+n,cmp); if(po[n/2].x!=po[n/2+1].x) printf("%d %d %d %d ",po[n/2].x,M,po[n/2+1],-M); else printf("%d %d %d %d ",po[n/2].x-1,po[n/2+1].y+M,po[n/2].x+1,po[n/2].y-M); } }
G题:Removing Stones
参考自https://www.cnblogs.com/hua-dong/p/11251800.html
启发式分治,类似题:https://www.cnblogs.com/-Zzz-/p/11525299.html
题意:给定N,表示N堆石子,每堆石子数为a[],问多少个区间,可以满足“石子总和若为偶数,那么可以两两取来自不同堆的石子,直到取完; 如果为奇数,那么排除其中一个,然后可以两两取来自不同堆的石子,直到取完”。
思路:结论是,如果一个区间的区间和大于等于区间最大值的两倍,则这个区间合法。 考虑分治,我们首先找到区间最大值(为了不重复统计,多个最大值时,统一取最左边的,这个可以ST表示实现),然后考虑跨越这个位置的合法区间个数。枚举一端,另外一段二分即可,选择端时要用到启发式,选择更短的那一段,防止最差情况不断发生。
由于分治的性质,我们每次的复杂度要倾向于小的那边,即是一个启发式合并的逆过程,所以启发式分治复杂度是O(NlogN)的,加上二分,这个做法的复杂度是O(Nlog^2N)。
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5+3; int a[maxn]; int st[maxn][20]; int lg[maxn]; int n; long long suf[maxn],pre[maxn],ans; void init_log(){ lg[0] = -1; for(int i=1; i<maxn; i++) lg[i] = lg[i>>1]+1; } void init_ST() //关于最值的pos的st表 (多个最大值时,统一取最左边的,这个可以ST表示实现) { for(int i=1; i<=n; i++) st[i][0]=i; for(int i=1; (1<<i)<=n; i++){ for(int j=1; j+(1<<i)-1<=n; j++){ st[j][i] = a[ st[j][i-1] ] >= a[ st[j+(1<<(i-1))][i-1] ]? st[j][i-1]:st[j+(1<<(i-1))][i-1]; } } } int RMQ(int L,int R){ //返回最大值的pos if(L>=R) return 0; int k=lg[R-L+1]; int pos=( a[ st[L][k] ]>=a[ st[R-(1<<k)+1][k] ]? st[L][k]:st[R-(1<<k)+1][k] ); return pos; } void solve(int L,int R){ if(L>=R) return; int Mid = RMQ(L,R); if(R-Mid > Mid-L){ //启发式分治 for(int i=L; i<=Mid; i++){ int pos = lower_bound( pre+Mid,pre+R+1,pre[i-1]+2LL*a[Mid] )-pre; ans += R-pos+1; } } else{ for(int i=Mid; i<=R; i++){ int pos = lower_bound( suf+1+n-Mid,suf+1+n-L+1,suf[n-i]+2LL*a[Mid] )-suf; ans += n-L+1-pos+1; } } solve(L,Mid-1); solve(Mid+1,R); } int main(){ int T; init_log(); scanf("%d",&T); while(T--){ scanf("%d",&n); ans = 0; for(int i=1; i<=n; i++){ scanf("%d",a+i); pre[i] = pre[i-1] + a[i]; } for(int i=1; i<=n; i++){ suf[i] = suf[i-1] + a[n-i+1]; } init_ST(); solve(1,n); printf("%lld ", ans); } }