GXOI/GZOI2019部分题解
D1T1:与或和
对每位处理，问题变成所有内部不包含0/1的矩阵的个数，单调栈维护即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 using namespace std; 6 7 const int N=1010,mod=1e9+7; 8 int top,sum,sm,n,mx,a[N][N],b[N][N],st[N],sz[N],l[N][N]; 9 10 int work(int w,int op){ 11 rep(i,1,n) rep(j,1,n) 12 if((a[i][j]&(1<<w))) b[i][j]=op; else b[i][j]=op^1; 13 rep(i,1,n){ 14 l[i][n]=b[i][n]; 15 for(int j=n-1; j; j--) 16 if(!b[i][j]) l[i][j]=0; else l[i][j]=l[i][j+1]+1; 17 } 18 int tmp=0; 19 rep(j,1,n){ 20 top=0,sum=0; 21 rep(i,1,n){ 22 int now=0; 23 while (top && st[top]>=l[i][j]) 24 sum-=st[top]*sz[top],now+=sz[top],top--; 25 st[++top]=l[i][j]; sz[top]=now+1; 26 sum+=st[top]*sz[top]; tmp=(tmp+sum)%mod; 27 } 28 } 29 return tmp; 30 } 31 32 int main(){ 33 freopen("andorsum.in","r",stdin); 34 freopen("andorsum.out","w",stdout); 35 scanf("%d",&n); 36 rep(i,1,n) rep(j,1,n) scanf("%d",&a[i][j]),mx=max(mx,a[i][j]); 37 rep(i,1,n) rep(j,1,n) sm=(sm+1ll*i*j)%mod; 38 int ans1=0,ans2=0; 39 rep(w,0,32){ 40 if ((1ll<<w)>mx) break; 41 int t=(1ll<<w)%mod; 42 ans1=(ans1+1ll*t*work(w,1)%mod)%mod; 43 ans2=(ans2+1ll*t*(sm-work(w,0)+mod)%mod)%mod; 44 } 45 printf("%d %d ",ans1,ans2); 46 return 0; 47 }
D1T3:特技飞行
被观察到的特技次数是固定的，先曼哈顿转切比雪夫然后KDT统计即可。
然后发现，若所有特技全部选择对向交换，一定是符合要求的，于是得到了两个极值中的一个。
接下来要让对向交换的次数尽量小，也就是给两个排列，让第一个经过最小的交换次数变成第二个。
找出置换环，答案就是n-置换环数。
1 #include<set> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 typedef long long ll; 7 using namespace std; 8 9 const int N=500010; 10 const double eps=1e-10,inf=1e13; 11 ll A,B,C; 12 int n,T,tot,st,ed,x,y,rr,y0[N],y1[N],id[N],vis[N],b[N],cov[N]; 13 set<pair<int,int> >S; 14 set<pair<int,int> >::iterator it; 15 16 struct P{ double v[2],mn[2],mx[2]; int ls,rs; }v[N],t; 17 bool cmpx(const P &a,const P &b){ return a.v[0]<b.v[0]; } 18 bool cmpy(const P &a,const P &b){ return a.v[1]<b.v[1]; } 19 bool cmp(int a,int b){ return y1[a]<y1[b]; } 20 21 double Abs(double x){ return x<0 ? -x : x; } 22 23 void upd(int x){ 24 rep(i,0,1){ 25 v[x].mn[i]=min(v[x].v[i],min(v[v[x].ls].mn[i],v[v[x].rs].mn[i])); 26 v[x].mx[i]=max(v[x].v[i],max(v[v[x].ls].mx[i],v[v[x].rs].mx[i])); 27 } 28 } 29 30 int build(int L,int R,int k){ 31 if (L>R) return 0; 32 int mid=(L+R)>>1,x=mid; 33 nth_element(v+L,v+mid,v+R+1,k?cmpy:cmpx); 34 v[x].ls=build(L,mid-1,k^1); v[x].rs=build(mid+1,R,k^1); 35 upd(x); return x; 36 } 37 38 void mdf(int x){ 39 if (!x || b[x] || t.v[0]+rr<v[x].mn[0] || t.v[0]-rr>v[x].mx[0] || t.v[1]+rr<v[x].mn[1] || t.v[1]-rr>v[x].mx[1]) return; 40 double s=0; 41 rep(i,0,1) s=max(s,max(Abs(t.v[i]-v[x].mn[i]),Abs(t.v[i]-v[x].mx[i]))); 42 if (s-eps<rr){ b[x]=1; return; } 43 if (!cov[x] && max(Abs(v[x].v[0]-t.v[0]),Abs(v[x].v[1]-t.v[1]))-eps<rr) cov[x]=1; 44 mdf(v[x].ls); mdf(v[x].rs); 45 } 46 47 int dfs(int x){ 48 if (b[x]) cov[x]=cov[v[x].ls]=cov[v[x].rs]=b[v[x].ls]=b[v[x].rs]=1; 49 int res=cov[x]; 50 if (v[x].ls) res+=dfs(v[x].ls); 51 if (v[x].rs) res+=dfs(v[x].rs); 52 return res; 53 } 54 55 int main(){ 56 freopen("aerobatics.in","r",stdin); 57 freopen("aerobatics.out","w",stdout); 58 v[0].mn[0]=v[0].mn[1]=inf; v[0].mx[0]=v[0].mx[1]=-inf; 59 scanf("%d%lld%lld%lld%d%d",&n,&A,&B,&C,&st,&ed); 60 rep(i,1,n) scanf("%d",&y0[i]); 61 rep(i,1,n) scanf("%d",&y1[i]); 62 for (int i=n; i; i--){ 63 for (it=S.begin(); it!=S.end() && (it->first<y1[i]); it++){ 64 int j=it->second; 65 double t=(double)(y0[j]-y0[i])/(y1[i]-y1[j]); 66 double x=(t*ed+st)/(t+1),y=(t*y1[j]+y0[j])/(t+1); 67 v[++tot].v[0]=x+y; v[tot].v[1]=x-y; 68 } 69 S.insert(pair<int,int>(y1[i],i)); 70 } 71 int rt=build(1,tot,0); 72 for (scanf("%d",&T); T--; ) 73 scanf("%d%d%d",&x,&y,&rr),t.v[0]=x+y,t.v[1]=x-y,mdf(rt); 74 ll ans=dfs(rt)*C,ans1=ans+tot*A,ans2=ans+tot*A; 75 rep(i,1,n) id[i]=i; 76 sort(id+1,id+n+1,cmp); 77 ll x=n; 78 rep(i,1,n) if (!vis[i]){ 79 x--; 80 for (int j=i; !vis[j]; j=id[j]) vis[j]=1; 81 } 82 ans2+=(tot-x)*(B-A); 83 printf("%lld %lld ",min(ans1,ans2),max(ans1,ans2)); 84 return 0; 85 }