本文主要是介绍紫书训练 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;
}
这篇关于紫书训练 7.16的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
