noip 2018 模拟赛9

$T_1$——policy(3115)

Description:

有一个$n\cdot m$的矩形，现在有$q$次询问，每次询问一个$a\cdot b$的子矩形，若它的最大值mx，权值和为sum，求$min\{mx\cdot a\cdot b-sum\}$。 $n,m\le 1000,A_{i,j}\le 10^9,q\le 10$

Solution:

发现这个就是一个无脑的数据结构题复杂度实在太卡…那么带$\log$的话很容易就挂所以就想到一些线性的做法，比如单调队列这样复杂度就是$\Theta (n^{2}q)$

Code:

#include<bits/stdc++.h> using namespace std; #define REP(i,f,t) for(int i=(f),i##_end_=(t);i<=i##_end_;++i) #define SREP(i,f,t) for(int i=(f),i##_end_=(t);i<i##_end_;++i) #define DREP(i,f,t) for(int i=(f),i##_end_=(t);i>=i##_end_;--i) #define ll long long template<class T>inline bool chkmin(T &x,T y){return x>y?x=y,1:0;} template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;} template<class T>inline void Rd(T &x){ x=0;char c; while((c=getchar())<48); do x=(x<<1)+(x<<3)+(c^48); while((c=getchar())>47); } const int N=1002; #define INF 0x3f3f3f3f3f3f3f3fll int n,m,q; int a,b; int A[N][N],B[N][N],Q[N]; ll sum[N][N]; void solve(){ ll ans=INF; REP(i,1,n){ int l=0,r=0; REP(j,1,m){ while(l<r && Q[l]<=j-b) ++l; while(l<r && A[i][Q[r-1]]<A[i][j]) --r; Q[r++]=j; B[i][j]=A[i][Q[l]]; } } REP(j,b,m){ int l=0,r=0; REP(i,1,n){ while(l<r && Q[l]<=i-a) ++l; while(l<r && B[Q[r-1]][j]<B[i][j]) --r; Q[r++]=i; if(a<=i){ ll x=sum[i][j]-sum[i-a][j]-sum[i][j-b]+sum[i-a][j-b]; ll y=1ll*B[Q[l]][j]*a*b; chkmin(ans,y-x); } } } printf("%lld\n",ans); } int main(){ // freopen("policy.in","r",stdin); // freopen("policy.out","w",stdout); Rd(n),Rd(m); REP(i,1,n) REP(j,1,m)Rd(A[i][j]),sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j]; Rd(q); while(q--)Rd(a),Rd(b),solve(); return 0; }

$T_2$——ricehub(3074)

Description: 在一条$x$轴上，有$n$个米仓，每个米仓的的粮食都是$1$，且知道它们的位置$p_i$，以及坐标范围$L$。问在某个点建一个仓库，在总花费不超过$B$的情况下，求最大的仓库粮食量，一粮食每一单位的运费为$1$。 $n\le 10^6,L\le 10^9,B\le 2\cdot 10^{15}$

Solution:

首先有一个$O(n^3)$的做法因为仓库只对一个区间$[l,r]$的米仓有影响模拟数据发现，它对花费的最优贡献一定是$(p_r-p_l)+(p_{r-1}-p_{l+1})...+(p_{mid+1}-p_{mid-1})$即仓库要建在中位数时最优。那么对于每个左端点$i$，我们可以线性找到它的右端点$j$，再利用前缀和求一个最优花费是否超过$B$即可。

Code:

#include<bits/stdc++.h> using namespace std; #define REP(i,f,t) for(int i=(f),i##_end_=(t);i<=i##_end_;++i) #define SREP(i,f,t) for(int i=(f),i##_end_=(t);i<i##_end_;++i) #define DREP(i,f,t) for(int i=(f),i##_end_=(t);i>=i##_end_;--i) #define ll long long template<class T>inline bool chkmin(T &x,T y){return x>y?x=y,1:0;} template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;} template<class T>inline void Rd(T &x){ x=0;char c; while((c=getchar())<48); do x=(x<<1)+(x<<3)+(c^48); while((c=getchar())>47); } const int N=1e5+2; int n,L; ll B; int p[N]; struct p20{ void solve(){ int ans=0; REP(i,1,n) REP(j,i+1,n) { int l=i,r=j; ll sum=0; while(l<r) sum+=p[r]-p[l],l++,r--; if(sum<=B) chkmax(ans,j-i+1); } printf("%d\n",ans); } }p1; struct p100{ ll sum[N]; bool check(int l,int r){ int mid=(l+r)>>1; ll cost=1ll*p[mid]*(mid-l+1)-(sum[mid]-sum[l-1])+sum[r]-sum[mid]-1ll*p[mid]*(r-mid); return cost<=B; } void solve(){ REP(i,1,n) sum[i]=sum[i-1]+p[i]; int j=1,ans=0; REP(i,1,n){ while(j<=n && check(i,j)) ++j; chkmax(ans,j-i); } printf("%d\n",ans); } }p2; int main(){ // freopen("ricehub.in","r",stdin); // freopen("ricehub.out","w",stdout); Rd(n),Rd(L),Rd(B); REP(i,1,n) Rd(p[i]); // if(n<=100)p1.solve();//O(n^3) // else p2.solve(); return 0; }

$T_3$——war(3117)

Description:

有一个$n$个点，$m$条边的图，每个点都有颜色，颜色种类的范围为$[1,K]$。 现在有$q$个操作，每个操作将点$x$的颜色改为$k$，在每个操作后求不同颜色的最小距离。 $n\le 2\cdot 10^5,m\le 4\cdot 10^5,K\le 10^6,q\le 2\cdot 10^5,w_i\le 10^6$

Solution:

对于这个$n$为$2\cdot 10^5$的图，大概已经没有什么图论算法可以解决问题了而且我们发现答案一定是给定的某一边的边权对于暴力的做法（$\Theta (ml\log mq)$），我们是将边权排序，找最小不同颜色的边而将边排序，我们很容易联想到最小生成树，那么答案是不是一定在最小生成树上呢？我们可以来反证一下若答案是一条非树（最小生成树）边，那么该边的两点颜色不同，且这两点之间一定有树边，且这些树边的边权一定比这条非树边小，且一定会有至少一条不同颜色的点的边。这样，我们可以用线段树来维护树上每个点与它颜色为$c$的儿子的最小距离。但是操作还要修改，就需要用一个全局的$multiset$来维护答案。这样复杂度是$\Theta (n\log n)$。

Code

#include<bits/stdc++.h> using namespace std; #define REP(i,f,t) for(int i=(f),i##_end_=(t);i<=i##_end_;++i) #define SREP(i,f,t) for(int i=(f),i##_end_=(t);i<i##_end_;++i) #define DREP(i,f,t) for(int i=(f),i##_end_=(t);i>=i##_end_;--i) #define ll long long template<class T>inline bool chkmin(T &x,T y){return x>y?x=y,1:0;} template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;} template<class T>inline void Rd(T &x){ x=0;char c; while((c=getchar())<48); do x=(x<<1)+(x<<3)+(c^48); while((c=getchar())>47); } const int N=2e5+2,INF=0x3f3f3f3f; int n,m,K,q; int col[N]; struct node{ int x,y,w,id; bool operator<(const node &_)const{ return w<_.w; } }em[N<<1]; struct p40{ void solve(){ while(q--){ int x,k; Rd(x),Rd(k); col[x]=k; REP(i,1,m){ if(col[em[i].x]==col[em[i].y])continue; printf("%d\n",em[i].w); break; } } } }p1; struct p100{ int fa[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int qwq,head[N]; struct edge{ int to,nxt,w; }E[N<<1]; void addedge(int x,int y,int z){E[qwq]=(edge){y,head[x],z};head[x]=qwq++;} int Fa[N],dis[N]; int res[N]; multiset<int>ans; int tim,rt[N]; int Lson[N*40],Rson[N*40],Mn[N*40]; int cnt,Id[N*40];//叶子 multiset<int>Leaf[N<<1]; void Update(int l,int r,int x,int w,int op,int &p){ if(!p) p=++tim,Mn[p]=INF; if(l==r){ if(!Id[p])Id[p]=++cnt,Leaf[Id[p]].insert(INF); if(op)Leaf[Id[p]].insert(w); else Leaf[Id[p]].erase(Leaf[Id[p]].find(w)); Mn[p]=*Leaf[Id[p]].begin(); return; } int mid=(l+r)>>1; if(x<=mid)Update(l,mid,x,w,op,Lson[p]); else Update(mid+1,r,x,w,op,Rson[p]); chkmin(Mn[p]=Mn[Lson[p]],Mn[Rson[p]]); } int Query(int l,int r,int L,int R,int p){ if(!p || L>R)return INF; if(l==L && r==R) return Mn[p]; int mid=(l+r)>>1; if(R<=mid)return Query(l,mid,L,R,Lson[p]); else if(L>mid)return Query(mid+1,r,L,R,Rson[p]); else return min(Query(l,mid,L,mid,Lson[p]),Query(mid+1,r,mid+1,R,Rson[p])); } void dfs(int x){ for(int i=head[x];~i;i=E[i].nxt){ int y=E[i].to; if(y==Fa[x])continue; Fa[y]=x; Update(1,K,col[y],dis[y]=E[i].w,1,rt[x]); dfs(y); } } void solve(){ REP(i,1,n)fa[i]=i; memset(head,-1,sizeof(head)); int num=0; REP(i,1,m){ int x=em[i].x,y=em[i].y; int fx=find(x),fy=find(y); if(fx!=fy){ fa[fx]=fy; addedge(x,y,em[i].w); addedge(y,x,em[i].w); ++num; } if(num==n-1)break; } Mn[0]=INF; dfs(1); REP(i,1,n) res[i]=min(Query(1,K,1,col[i]-1,rt[i]),Query(1,K,col[i]+1,K,rt[i])),ans.insert(res[i]); while(q--){ int x,k; Rd(x),Rd(k); ans.erase(ans.find(res[x])); res[x]=min(Query(1,K,1,k-1,rt[x]),Query(1,K,k+1,K,rt[x])); ans.insert(res[x]); if(x!=1){ int f=Fa[x]; ans.erase(ans.find(res[f])); Update(1,K,col[x],dis[x],0,rt[f]),Update(1,K,k,dis[x],1,rt[f]); res[f]=min(Query(1,K,1,col[f]-1,rt[f]),Query(1,K,col[f]+1,K,rt[f])); ans.insert(res[f]); } col[x]=k; printf("%d\n",*ans.begin()); } } }p2; int main(){ // freopen("war.in","r",stdin); // freopen("war.out","w",stdout); Rd(n),Rd(m),Rd(K),Rd(q); REP(i,1,m){ int a,b,c; Rd(a),Rd(b),Rd(c); em[i]=(node){a,b,c,i}; } REP(i,1,n) Rd(col[i]); sort(em+1,em+1+m); if(m<=10000 && q<=10000)p1.solve();//O(mlogm+mq) else p2.solve();//O(nlogn) return 0; }