紫书训练 7.16

https://vjudge.net/contest/311524#overview  差分约束+CDQ分治+虚树

密码：996996

差分约束的博客 https://blog.csdn.net/whereisherofrom/article/details/78922648 虚树博客 https://www.cnblogs.com/zwfymqz/p/9175152.html 

虚树还没有学习

A - Layout

差分约数裸题

#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<stack> #include<map> #include<set> #include<cmath> #include<sstream> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=1e5+5; int dist[maxn]; int pushnum[maxn]; bool vis[maxn]; struct edge { int to; int w; }; vector<edge> tt[maxn]; int n,ml,md; bool spfa(int start) { memset(dist,0x3f,sizeof(dist)); memset(vis,false,sizeof(vis)); memset(pushnum,0,sizeof(pushnum)); dist[start]=0; vis[start]=true; pushnum[start]++; queue<int> q; q.push(start); while(!q.empty()) { int p=q.front(); q.pop(); vis[p]=false; for(int i=0; i<(int)tt[p].size(); ++i) { edge tmp=tt[p][i]; if(dist[tmp.to]>dist[p]+tmp.w) { dist[tmp.to]=dist[p]+tmp.w; if(vis[tmp.to]==false) { q.push(tmp.to); vis[tmp.to]=true; pushnum[tmp.to]++; if(pushnum[tmp.to]>n) { return false; } } } } } return true; } int main(){ sc(n),sc(ml),sc(md); int x,y,z; edge tp; rep(i,1,ml){ sc(x),sc(y),sc(z); tp.to=y,tp.w=z; tt[x].pb(tp); } rep(i,1,md){ sc(x),sc(y),sc(z); tp.to=x,tp.w=-z; tt[y].pb(tp); } if(!spfa(1)) cout<<-1<<endl; else if(dist[n] == inf) cout<<-2<<endl; else cout<<dist[n]<<endl; return 0; }

B - World Exhibition

 也是模板题

#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<stack> #include<map> #include<set> #include<cmath> #include<sstream> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=1e5+5; int dist[maxn]; int pushnum[maxn]; bool vis[maxn]; struct edge { int to; int w; }; vector<edge> tt[maxn]; int T,n,xx,yy; bool spfa(int start) { memset(dist,0x3f,sizeof(dist)); memset(vis,false,sizeof(vis)); memset(pushnum,0,sizeof(pushnum)); dist[start]=0; vis[start]=true; pushnum[start]++; queue<int> q; q.push(start); while(!q.empty()) { int p=q.front(); q.pop(); vis[p]=false; for(int i=0; i<(int)tt[p].size(); ++i) { edge tmp=tt[p][i]; if(dist[tmp.to]>dist[p]+tmp.w) { dist[tmp.to]=dist[p]+tmp.w; if(vis[tmp.to]==false) { q.push(tmp.to); vis[tmp.to]=true; pushnum[tmp.to]++; if(pushnum[tmp.to]>n) { return false; } } } } } return true; } int main(){ sc(T); while(T--){ sc(n),sc(xx),sc(yy); rep(i,1,n) tt[i].clear(); int x,y,z; edge tp; rep(i,1,xx){ sc(x),sc(y),sc(z); tp.to=y,tp.w=z; tt[x].pb(tp); } rep(i,1,yy){ sc(x),sc(y),sc(z); tp.to=x,tp.w=-z; tt[y].pb(tp); } if(!spfa(1)) cout<<-1<<endl; else if(dist[n] == inf) cout<<-2<<endl; else cout<<dist[n]<<endl; } return 0; }

D - 陌上花开

解决三维问题，先队一维排序，然后再对一维排序，然后用树状数组解决第三维。

#include<bits/stdc++.h> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=2e5+5; int sum[maxn],tot,ans[maxn/2],n,K; il void add(int p,int k) { while(p<=K) sum[p]+=k,p+=p&-p; } il int ask(int p) { int res=0; while(p) res+=sum[p],p-=p&-p; return res; } struct node { int x,y,z,cnt,ans; } a[maxn/2]; bool cmp(node a,node b) { if(a.x==b.x && b.y==a.y) return a.z<b.z; else if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } bool cmp2(node a,node b) { if(a.y==b.y) return a.z<b.z; else return a.y<b.y; } void CDQ(int l,int r) { if(l==r) { a[l].ans=a[l].cnt-1; return; } int mid=(l+r)>>1; CDQ(l,mid),CDQ(mid+1,r); sort(a+l,a+mid+1,cmp2); sort(a+mid+1,a+r+1,cmp2); int j=l; for(int i=mid+1; i<=r; ++i) { for(; j<=mid && a[j].y<=a[i].y; ++j) { add(a[j].z,a[j].cnt); } a[i].ans+=ask(a[i].z); } for(int i=l; i<j; ++i) add(a[i].z,-a[i].cnt); } int main() { int i,j; SC(n,K); rep(i,1,n) sc(a[i].x),sc(a[i].y),sc(a[i].z); sort(a+1,a+n+1,cmp); for(i=1; i<=n; ++i) if(i!=1 && a[i].x==a[i-1].x && a[i].y==a[i-1].y && a[i].z==a[i-1].z) a[tot].cnt++; else a[++tot]=a[i],a[tot].cnt=1; CDQ(1,tot); rep(i,1,tot) ans[a[i].ans]+=a[i].cnt; rep(i,0,n-1) printf("%d\n",ans[i]); return 0; }

E - Mokia

 太妙了呀，查询拆成4个点，刚学cdq，果然还是不能好好使用。数据里的s都是0，所以初始值就不考虑了，考虑得话加一下就行了。

#include<bits/stdc++.h> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=2e5+5; int sum[maxn*10],ans[maxn],tot; int s,w,op; il void add(int p,int x) { while(p<=w) sum[p]+=x,p+=p&-p; } il int ask(int x){ int res=0; while(x) res+=sum[x],x-=x&-x; return res; } struct node{ int id,x,y,add,pos; }q[maxn<<2],tp[maxn<<2]; bool cmp(node a,node b){ if(a.x==b.x && a.y==b.y) return a.id<b.id; else if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } void cdq(int l,int r){ if(l>=r) return ; int mid=(l+r)>>1; for(int i=l;i<=r;++i){ if(q[i].id<=mid && !q[i].pos) add(q[i].y,q[i].add); else if(q[i].id>mid && q[i].pos) ans[q[i].pos]+=q[i].add*ask(q[i].y); } int l1=l,l2=mid+1; for(int i=l;i<=r;++i){ if(q[i].id<=mid && !q[i].pos) add(q[i].y,-q[i].add); if(q[i].id<=mid) tp[l1++]=q[i]; else tp[l2++]=q[i]; } for(int i=l;i<=r;++i) q[i]=tp[i]; cdq(l,mid),cdq(mid+1,r); return ; } int main() { SC(s,w); int x1,y1,x2,y2,c,cnt=0; while(cin>>op && op!=3){ if(op==1){ SC(x1,y1),sc(c); q[++tot]=node{tot,x1,y1,c,0}; } else if(op==2){ cnt++; SC(x1,y1),SC(x2,y2); q[++tot]=node{tot,x1-1,y1-1,1,cnt}; q[++tot]=node{tot,x2,y2,1,cnt}; q[++tot]=node{tot,x1-1,y2,-1,cnt}; q[++tot]=node{tot,x2,y1-1,-1,cnt}; } } sort(q+1,q+tot+1,cmp); cdq(1,tot); rep(i,1,cnt) printf("%d\n",ans[i]); return 0; }