2021牛客暑期多校训练营2
比赛链接:https://ac.nowcoder.com/acm/contest/11253
第一场有事没打;第二场暑训正式开始。C,D,F,K,4/12,垫底了,咳。G记录得比较详细,我就不回忆了。
改了两天题:
题意:
给一个序列 ( a ) ,求其所有满足 排序后是等差数列 的子区间的个数。( 1 leq n leq 10^5 ) , ( 1 leq a_i leq 10^9 ) , ( a_i ) 各不相同。
分析:
快速判定子区间 ( left [ l,r ight ) ) 满足条件的方法:若排序后为等差数列,则公差 ( d = gcdleft ( b_{l+1}-b_1 , b_{l+2}-b_{l+1} , ... , b_r-b_{r-1} ight ) ) ;
那么判定条件就可以是 ( maxleft { a_l , ... , a_r ight } - minleft { a_l , ... , a_r ight } = ( r-l ) * gcdleft ( b_{l+1}-b_l , b_{l+2}-b_{l+1} , ... , b_r-b_{r-1} ight ) ) ,而且可以发现 ( maxleft { a_l , ... , a_r ight } - minleft { a_l , ... , a_r ight } ) 一定大于等于 ( ( r-l ) * gcdleft ( b_{l+1}-b_l , b_{l+2}-b_{l+1} , ... , b_r-b_{r-1} ight ) ) ;
所以可以考虑枚举 ( r ) ,再 ( log(n) ) 维护( max ) , ( min ) 和 ( gcd );
上式写成 ( maxleft { a_l , ... , a_r ight } - minleft { a_l , ... , a_r ight } + l * gcd = r * gcd ) ,用线段树来维护 ( maxleft { a_l , ... , a_r ight } - minleft { a_l , ... , a_r ight } + l * gcd ) 的最小值以及是这个最小值的点的个数;( max ) 和 ( min ) 可以结合单调栈维护,进行区间修改;( gcd ) 直接单点修改,但是对于每个 ( l ) ,这个点上存的 ( gcd ) (初值 ( a_{l+1}-a_l) )最多修改 ( log(n) ) 次,所以复杂度是 ( nlog(n) );每个 ( r ) 处找一遍答案,也就是看看最小值和上式右面是否相等,相等的话就把答案加到个数里。
代码如下:
#include<iostream> #define ll long long #define ls (u<<1) #define rs (u<<1|1) #define mid ((l+r)>>1) using namespace std; int const N=1e5+5; ll const INF=1e17; int n,tpmn,tpmx,cnt; ll a[N],qmn[N],qmx[N],g[N],gpos[N],ans; struct Nd{ ll s,tg,cnt,mn; }tr[N<<2]; struct qNd{ ll mn,num; }; ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} ll ab(ll x){return x>0?x:-x;} void pdn(int u) { if(!tr[u].tg)return; ll s=tr[u].tg; tr[u].tg=0; tr[ls].tg+=s; tr[ls].mn+=s; tr[rs].tg+=s; tr[rs].mn+=s; } void upt(int u) { //printf("upt(%d):ls.mn=%lld rs.mn=%lld ",u,tr[ls].mn,tr[rs].mn); if(tr[ls].mn<tr[rs].mn)tr[u].mn=tr[ls].mn,tr[u].cnt=tr[ls].cnt; if(tr[ls].mn==tr[rs].mn)tr[u].mn=tr[ls].mn,tr[u].cnt=tr[ls].cnt+tr[rs].cnt; if(tr[ls].mn>tr[rs].mn)tr[u].mn=tr[rs].mn,tr[u].cnt=tr[rs].cnt; } void init(int u,int l,int r) { tr[u].mn=INF; tr[u].tg=0; tr[u].cnt=r-l+1; if(l==r)return; //printf("u=%d ls=%d rs=%d l=%d r=%d mid=%d ",u,ls,rs,l,r,mid); init(ls,l,mid); init(rs,mid+1,r); } void add(int u,int l,int r,int ql,int qr,ll s) { //printf("add(u=%d l=%d r=%d ql=%d qr=%d s=%lld ",u,l,r,ql,qr,s); if(l>=ql&&r<=qr){tr[u].tg+=s; tr[u].mn+=s; return;} pdn(u); if(mid>=ql)add(ls,l,mid,ql,qr,s); if(mid<qr)add(rs,mid+1,r,ql,qr,s); upt(u); //printf("upt:u=%d l=%d r=%d mn=%d cnt=%d ",u,l,r,tr[u].mn,tr[u].cnt); } qNd qry(int u,int l,int r,int ql,int qr) { //printf("qry:u=%d l=%d r=%d ql=%d qr=%d ",u,l,r,ql,qr); if(l>r||ql>qr)return (qNd){-1,0}; if(l>=ql&&r<=qr)return (qNd){tr[u].mn,tr[u].cnt}; //printf("qry:pdn(%d) ",u); pdn(u); if(mid>=qr)return qry(ls,l,mid,ql,qr); if(mid<ql)return qry(rs,mid+1,r,ql,qr); //upt(u); qNd qls=qry(ls,l,mid,ql,qr),qrs=qry(rs,mid+1,r,ql,qr),ret=qls; if(qls.mn>qrs.mn)ret=qrs; else if(qls.mn==qrs.mn)ret.num+=qrs.num; return ret; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); init(1,1,n); ans=0; cnt=0; tpmn=0; tpmx=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); //printf("i=%d ",i); while(tpmn&&a[qmn[tpmn]]>=a[i])add(1,1,n,qmn[tpmn-1]+1,qmn[tpmn],a[qmn[tpmn]]),tpmn--; add(1,1,n,qmn[tpmn]+1,i,-a[i]); qmn[++tpmn]=i; while(tpmx&&a[qmx[tpmx]]<=a[i])add(1,1,n,qmx[tpmx-1]+1,qmx[tpmx],-a[qmx[tpmx]]),tpmx--; add(1,1,n,qmx[tpmx]+1,i,a[i]); qmx[++tpmx]=i; if(i==1)continue;// g[++cnt]=ab(a[i]-a[i-1]); gpos[cnt]=i-1; add(1,1,n,i-1,i-1,(ll)(i-1)*g[cnt]-INF);//-INF! for(int k=cnt-1;k;k--) if(g[k+1]%g[k]) { ll pre=g[k]; g[k]=gcd(g[k+1],g[k]);// for(int p=gpos[k];p<gpos[k+1];p++)add(1,1,n,p,p,(ll)p*(g[k]-pre)); } //printf("cnt=%d ",cnt); //for(int i=1;i<=cnt;i++)printf("g[%d]=%d ",i,g[i]); printf(" "); int num=0; for(int i=1;i<=cnt;i++) if(g[i]!=g[i-1])g[++num]=g[i],gpos[num]=gpos[i]; cnt=num; //printf("cnt2=%d ",cnt); //for(int i=1;i<=cnt;i++)printf("g[%d]=%d ",i,g[i]); printf(" "); for(int k=1;k<=cnt;k++)//一个,两个数也是 { //printf("gpos[%d]=%d ",k,gpos[k]); qNd t=qry(1,1,n,gpos[k],(k==cnt)?i-1:gpos[k+1]-1); //printf("qry.mn=%lld qry.num=%lld i*g=%lld ",t.mn,t.num,(ll)i*g[k]); if(t.mn==(ll)i*g[k])ans+=t.num; } } printf("%lld ",ans+n); } return 0; }
题意:
给定一个 ( n * m ) 的点阵,每次选两个相邻点连线,不能连出封闭图形,两人轮流操作,不能操作者输。
分析:
不能形成环,所以终态是一棵树,所以可以根据点数的奇偶性判断。
签到题,Y做了,G写了。
#include<bits/stdc++.h> using namespace std; int n,m; int main() { scanf("%d%d",&n,&m); if((n==1||n==3)&&(m==1||m==3)) puts("NO"); else puts("YES"); }