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 }
D2T2:旅行者
方法一：二进制分组，对每个二进制位，将所有编号在这一位为0的关键点放在一边，为1的放在另一边跑最短路。这样任意两点间最短路都一定在某次中被考虑到。O(nlog^2n)
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 7 using namespace std; 8 9 const int N=500010,inf=1e9; 10 int n,m,k,T,u,v,w,ans,cnt,s[N],b[N],dis[N],fr[N],h[N],to[N],nxt[N],val[N]; 11 struct P{ int x,d; }; 12 bool operator <(const P &a,const P &b){ return a.d>b.d; } 13 priority_queue<P>Q; 14 15 void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } 16 17 void dij(){ 18 while (!Q.empty()){ 19 int x=Q.top().x; Q.pop(); 20 if (b[x]) continue; 21 b[x]=1; 22 For(i,x) if (dis[k=to[i]]>dis[x]+val[i]) 23 dis[k]=dis[x]+val[i],fr[k]=fr[x],Q.push((P){k,dis[k]}); 24 } 25 } 26 27 int main(){ 28 freopen("tourist.in","r",stdin); 29 freopen("tourist.out","w",stdout); 30 for (scanf("%d",&T); T--; ){ 31 cnt=0; ans=inf; rep(i,1,n) h[i]=0; 32 scanf("%d%d%d",&n,&m,&k); 33 rep(i,1,m) scanf("%d%d%d",&u,&v,&w),add(u,v,w); 34 rep(i,1,k) scanf("%d",&s[i]); 35 for (int t=1; t<=k; t<<=1){ 36 rep(i,1,n) dis[i]=inf,b[i]=0; 37 while (!Q.empty()) Q.pop(); 38 rep(i,1,k) if (i&t) dis[s[i]]=0,Q.push((P){s[i],0}),fr[s[i]]=s[i]; 39 dij(); 40 rep(i,1,k) if (!(i&t)) ans=min(ans,dis[s[i]]); 41 rep(i,1,n) dis[i]=inf,b[i]=0; 42 while (!Q.empty()) Q.pop(); 43 rep(i,1,k) if (!(i&t)) dis[s[i]]=0,Q.push((P){s[i],0}),fr[s[i]]=s[i]; 44 dij(); 45 rep(i,1,k) if (i&t) ans=min(ans,dis[s[i]]); 46 } 47 printf("%d ",ans); 48 } 49 return 0; 50 }
方法二：对于一条边，它对答案的贡献是a[u]+w+b[v]，其中a是所有关键点到它的最短距离，b是它到所有关键点的最短距离。
注意若a和b来自同一个关键点的时候忽略这条边，显然任意两个关键点之间的最短路上总有一条边不会被忽略。O(nlogn)
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 7 using namespace std; 8 9 const int N=500010,inf=1e9; 10 int n,m,k,T,u,v,w,ans,s[N],b[N]; 11 struct P{ int x,d; }; 12 bool operator <(const P &a,const P &b){ return a.d>b.d; } 13 priority_queue<P>Q; 14 struct E{ int u,v,w; }e[N]; 15 16 struct Gr{ 17 int cnt,dis[N],fr[N],h[N],to[N],nxt[N],val[N]; 18 void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } 19 20 void dij(){ 21 rep(i,1,n) dis[i]=inf,b[i]=0; 22 while (!Q.empty()) Q.pop(); 23 rep(i,1,k) dis[s[i]]=0,Q.push((P){s[i],0}),fr[s[i]]=s[i]; 24 while (!Q.empty()){ 25 int x=Q.top().x; Q.pop(); 26 if (b[x]) continue; 27 b[x]=1; 28 For(i,x) if (dis[k=to[i]]>dis[x]+val[i]) 29 dis[k]=dis[x]+val[i],fr[k]=fr[x],Q.push((P){k,dis[k]}); 30 } 31 } 32 }G1,G2; 33 34 void init(){ 35 G1.cnt=G2.cnt=0; ans=inf; 36 memset(G1.h,0,sizeof(G1.h)); memset(G2.h,0,sizeof(G2.h)); 37 } 38 39 int main(){ 40 freopen("tourist.in","r",stdin); 41 freopen("tourist.out","w",stdout); 42 for (scanf("%d",&T); T--; ){ 43 init(); scanf("%d%d%d",&n,&m,&k); 44 rep(i,1,m) scanf("%d%d%d",&u,&v,&w),G1.add(u,v,w),G2.add(v,u,w),e[i]=(E){u,v,w}; 45 rep(i,1,k) scanf("%d",&s[i]); 46 G1.dij(); G2.dij(); 47 rep(i,1,m) if (G1.fr[e[i].u]!=G2.fr[e[i].v]) ans=min(ans,G1.dis[e[i].u]+e[i].w+G2.dis[e[i].v]); 48 printf("%d ",ans); 49 } 50 return 0; 51 }