[NOI.AC]NOI2019省选模拟赛第二场

超、凢脫俗 2022-01-09 07:43 249阅读 0赞

## [ 传送门 ][Link 1] ##

## **Solution** ##

> ### A. ###
> 
> 一共有\\(T\\)组数据
> 
> 每次询问你\\(\[l,r\]\\)中有多少个数能被他的所有数位整除（如果数位中含有\\(0\\)忽略掉）
> 
> 数位dp，咕咕咕

> ### B. ###
> 
> 题面略
> 
> 考虑一个个只有两个元素组成的小区间  
> 可以发现若选择\\(\[l,l+1\]\\)，则必定要选择一个最大的区间包含\\(\[a\[l\],a\[l+1\]\]\\)的区间  
> 每个小区间看成一个点，向它所要求必须要选择的点连边，线段树优化建图  
> 对图进行tarjan缩点，然后拓扑排序即可  
> 全是区间询问，大概要有5棵线段树的样子
> 
> 其实有简单得多的解法。  
> 为了方便，考虑初始情况线段树的第i个叶子的val值是i  
> 从左到右，如果当前数是\\(x\\)，位置为\\(j\\)，且\\(x-1\\)的位置小于当前位置（假设是\\(k\\)），那么\\(\[1,k\]\\)区间加1，\\(x+1\\)同理  
> 每对相邻数字只会被算一次  
> 这样每次就能维护以左边每个点做左端点，当前点做为右端点，中间能有多少个点连续  
> 找到最大的val值为\\(j\\)的左端点，就是以该点做右端点的答案了

> ### C. ###
> 
> 题面略
> 
> 经过一波推导可得：\\(a\_i=x\_\{i+1\}x\_i-c\_1(c\_2-c\_1)\\)  
> 所以分块+矩阵快速幂就完事了  
> 没开ll会re，虽然到最后也不知道到底是哪里没开ll

## **Code ** ##

/* B 2019/3/18 */ #include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int MN=1e5+5; int N,Q,a[MN],b[MN],ls[MN*3],rs[MN*3],tt,root,minb[MN<<2],maxb[MN<<2]; struct edge{int to,nex;}e[MN<<4];int en,hr[MN*3]; inline void ins(int f,int t){e[++en]=(edge){t,hr[f]};hr[f]=en;} inline void build(int &x,int l,int r) { if(l==r){x=l;return;}register int mid=(l+r)>>1; x=++tt;build(ls[x],l,mid);build(rs[x],mid+1,r); ins(x,ls[x]);ins(x,rs[x]); } inline void Build(int x,int l,int r) { if(l==r){minb[x]=maxb[x]=b[l];return;}int mid=(l+r)>>1; Build(x<<1,l,mid);Build(x<<1|1,mid+1,r); minb[x]=min(minb[x<<1],minb[x<<1|1]); maxb[x]=max(maxb[x<<1],maxb[x<<1|1]); } inline int qmi(int x,int l,int r,int a,int b) { if(a==l&&b==r)return minb[x];int mid=(l+r)>>1; if(b<=mid) return qmi(x<<1,l,mid,a,b); else if(a>mid) return qmi(x<<1|1,mid+1,r,a,b); return min(qmi(x<<1,l,mid,a,mid),qmi(x<<1|1,mid+1,r,mid+1,b)); } inline int qma(int x,int l,int r,int a,int b) { if(a==l&&b==r)return maxb[x];int mid=(l+r)>>1; if(b<=mid) return qma(x<<1,l,mid,a,b); else if(a>mid) return qma(x<<1|1,mid+1,r,a,b); return max(qma(x<<1,l,mid,a,mid),qma(x<<1|1,mid+1,r,mid+1,b)); } inline void Insert(int x,int l,int r,int a,int b,int t) { if(l==a&&r==b){ins(t,x);return;} int mid=(l+r)>>1; if(b<=mid) Insert(ls[x],l,mid,a,b,t); else if(a>mid) Insert(rs[x],mid+1,r,a,b,t); else Insert(ls[x],l,mid,a,mid,t),Insert(rs[x],mid+1,r,mid+1,b,t); } int bel[MN*3],Mi[MN*3],Ma[MN*3],dfn[MN*3],low[MN*3],dind,st[MN*3],tp,bl; int getv(int x){if(x>N)return 0;return x;}bool in[MN*3]; inline void rwi(int &x,int y){if(y<x)x=y;} inline void rwa(int &x,int y){if(y>x)x=y;} void tj(int x) { dfn[x]=low[x]=++dind;st[tp++]=x;in[x]=true; register int i; for(i=hr[x];i;i=e[i].nex) { if(!dfn[e[i].to]) tj(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(in[e[i].to])low[x]=min(low[x],low[e[i].to]); } if(low[x]==dfn[x]) { ++bl; for(;st[tp]!=x;in[st[--tp]]=false)bel[st[tp-1]]=bl,rwi(Mi[bl],st[tp-1]),rwa(Ma[bl],getv(st[tp-1])); } } inline void Built(int x,int l,int r) { if(l==r){minb[x]=Mi[bel[l]];maxb[x]=Ma[bel[l]];return;} register int mid=(l+r)>>1; Built(x<<1,l,mid);Built(x<<1|1,mid+1,r); minb[x]=min(minb[x<<1],minb[x<<1|1]); maxb[x]=max(maxb[x<<1],maxb[x<<1|1]); } edge E[MN<<4];int En=0,Hr[MN*3],rd[MN*3]; inline void Ins(int f,int t){++rd[t];E[++En]=(edge){t,Hr[f]};Hr[f]=En;} std::queue<int> q; void jt() { register int i,j,I,J; memset(Hr,0,sizeof Hr); for(i=1;i<=tt;++i) for(j=hr[i];j;j=e[j].nex) if(bel[i]^bel[e[j].to]) Ins(bel[e[j].to],bel[i]); for(i=1;i<=bl;++i) if(!rd[i]) q.push(i); while(!q.empty()) { int u=q.front();q.pop(); for(i=Hr[u];i;i=E[i].nex) { if(Ma[u]) rwa(Ma[E[i].to],Ma[u]); if(Mi[u]<N) rwi(Mi[E[i].to],Mi[u]); if(!--rd[E[i].to]) q.push(E[i].to); } } } int main() { register int i,j; tt=N=read();for(i=1;i<=N;++i)b[a[i]=read()]=i; build(root,1,N-1);Build(1,1,N); for(i=1;i<N;++i) { int l=a[i],r=a[i+1],mi,ma; if(l>r) std::swap(l,r); mi=qmi(1,1,N,l,r);ma=qma(1,1,N,l,r);--ma; if(mi<i) Insert(root,1,N-1,mi,i-1,i); if(ma>i) Insert(root,1,N-1,i+1,ma,i); } memset(Mi,0x3f,sizeof Mi); for(i=1;i<=tt;++i) if(i!=N&&!dfn[i]) tj(i);jt(); memset(minb,0,sizeof minb);memset(maxb,0,sizeof maxb); Built(1,1,N-1);Q=read(); while(Q--) { int l=read(),r=read(),mi,ma;--r; if(l>r){printf("%d %d\n",l,l);continue;} mi=qmi(1,1,N-1,l,r);ma=qma(1,1,N-1,l,r); printf("%d %d\n",mi,ma+1); } return 0; }

/* C 2019/3/18 */ #include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } #define reg register ll N,M,P,Q,_1,_2; std::map<ll,ll> mp; const ll MN=2e5+5; struct matrix { ll a[3][3]; matrix(){memset(a,0,sizeof a);} matrix operator *(const matrix o) { reg int i,j,k;matrix c; for(k=0;k<2;++k)for(i=0;i<2;++i)for(j=0;j<2;++j) (c.a[i][j]+=(1ll*o.a[i][k]*a[k][j])%P)%=P; return c; } }L[MN],R[MN],ep,_; ll ans[MN<<1],dec; ll Cal(ll num) { ll x=(num-1)/M,y=(num-1)%M+1; matrix t; t=L[x]*R[y]; ll xi=(1ll*t.a[0][0]*_1%P+1ll*t.a[0][1]*_2%P)%P; ll xi_=(1ll*t.a[1][0]*_1%P+1ll*t.a[1][1]*_2%P)%P; return (1ll*xi_*xi%P+dec)%P; } ll cal(ll x,ll y) { if(mp.count(1ll*(x-1)*M+y)) return (Cal(mp[1ll*(x-1)*M+y])+P)%P; else return (Cal(1ll*(x-1)*M+y)+P)%P; } signed main() { ll x,y,i,j; N=read(),M=read();Q=read();P=read();_1=read();_2=read(); dec=1ll*_1*((_2-_1+P)%P)%P;dec=1ll*(P-dec)%P; while(Q--) { x=read();y=read(); i=mp.count(x)?mp[x]:x;j=mp.count(y)?mp[y]:y; mp[x]=j;mp[y]=i; } ep.a[0][0]=ep.a[1][1]=1;ep.a[0][1]=ep.a[1][0]=0; _.a[0][1]=_.a[1][0]=_.a[1][1]=1;_.a[0][0]=0; R[0]=ep;for(i=1;i<=M;++i)R[i]=R[i-1]*_; L[0]=ep;for(i=1;i<=N;++i)L[i]=L[i-1]*R[M]; ans[1]=cal(1,1); for(i=1,j=1;i<=N&&j<=M;) { if(i<N)x=cal(i+1,j);else x=P+1; if(j<M)y=cal(i,j+1);else y=P+1; ans[i+j]=min(x,y); if(x<=y) i++;else j++; if(i==N&&j==M)break; } for(i=1;i<N+M;++i) printf("%lld ",ans[i]); }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/noiacnoi2019\_2.html

[Link 1]: http://noi.ac/contest/76