国家集训队命题答辩

orz hhw posted @ 2016年2月18日 12:54 in 做题记录 with tags 做题记录 集训队 解题报告 Tsinsen , 1056 阅读

BZOJ炸了,只好来Tsinsen做题咯。。现在做了几道

 

50

采矿 傻逼树剖,线段树维护背包后的答案,m^2背包一次更新操作,并支持链上查最大操作即可,时间复杂度O(nm^2+qm^2lgn+qmlg^2n)

#include<bits/stdc++.h>
#define N 20020
using namespace std;const int X=65536,Y=2147483647;int n,m,A,B,Q,x,y,i,j,C,o,id,tot,ans,b[N*4][52],a[N][52],e[N*4][52],c[52],d[52],fir[N],ne[N],la[N],sz[N],fa[N],hs[N],st[N],ed[N],bl[N],h[N],to[N];
int gi(){A=((A^B)+(B/X)+(B*X))&Y;B=((A^B)+(A/X)+(A*X))&Y;return (A^B)%Q;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
    sz[x]=1;int i,y;for(i=fir[x];i;i=ne[i]){
		fa[y=la[i]]=x,h[y]=h[x]+1,dfs(y),sz[x]+=sz[y];
		if(sz[y]>sz[hs[x]])hs[x]=y;
	}
}
void dfs2(int x,int f){
	st[x]=++id;to[id]=x;bl[x]=f;if(hs[x])dfs2(hs[x],f);
	for(int i=fir[x];i;i=ne[i])if(la[i]!=hs[x])dfs2(la[i],la[i]);ed[x]=id;
}
void ps(int k){
	memset(b[k],0,sizeof b[k]);int i,j;
	for(i=0;i<=m;i++)for(j=0;i+j<=m;j++)b[k][i+j]=max(b[k][i+j],b[k<<1][i]+b[k<<1|1][j]);
	for(i=1;i<=m;i++)e[k][i]=max(e[k<<1][i],e[k<<1|1][i]);
}
void bt(int k,int l,int r){
	int i=1,mid=l+r>>1;if(l==r){for(;i<=m;i++)b[k][i]=e[k][i]=a[to[l]][i];return;}
	bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);ps(k);
}
void cha(int k,int l,int r,int x){
	int i=1,mid=l+r>>1;if(l==r){for(;i<=m;i++)b[k][i]=gi();sort(b[k]+1,b[k]+m+1);for(i=1;i<=m;i++)e[k][i]=b[k][i];return;}
	if(x<=mid)cha(k<<1,l,mid,x);else cha(k<<1|1,mid+1,r,x);ps(k);
}
void get(int k,int l,int r,int x,int y){
	int i=m,j,mid=l+r>>1;
	if(x<=l&&r<=y){for(i=m;i;i--)for(j=i;j;j--)c[i]=max(c[i],b[k][j]+c[i-j]);return;}
	if(x<=mid)get(k<<1,l,mid,x,y);if(y>mid)get(k<<1|1,mid+1,r,x,y);
}
void qu(int k,int l,int r,int x,int y){
	int i=1,mid=l+r>>1;if(x<=l&&r<=y){for(;i<=m;i++)d[i]=max(d[i],e[k][i]);return;}
	if(x<=mid)qu(k<<1,l,mid,x,y);if(y>mid)qu(k<<1|1,mid+1,r,x,y);
}
int main(){
	for(scanf("%d%d%d%d%d",&n,&m,&A,&B,&Q),i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
	for(i=1;i<=n;sort(a[i]+1,a[i]+m+1),i++)for(j=1;j<=m;j++)a[i][j]=gi();
	for(dfs(1),dfs2(1,1),bt(1,1,n),scanf("%d",&C);C--;)
		if(scanf("%d",&o),o){
			scanf("%d%d",&x,&y);memset(c,0,sizeof c);memset(d,0,sizeof d);get(1,1,n,st[x],ed[x]);
			if(x!=y){
				for(x=fa[x];bl[x]!=bl[y];x=fa[bl[x]])qu(1,1,n,st[bl[x]],st[x]);
				qu(1,1,n,st[y],st[x]);
			}
			for(ans=i=0;i<=m;i++)ans=max(ans,c[i]+d[m-i]);printf("%d\n",ans);
		}else scanf("%d",&x),cha(1,1,n,st[x]);
}

复杂的大门 建出分层图跑网络流,答案就是最小割。但是理论上会T的,应该要写Dijkstra,但是我懒得写直接网络流水过了,其实网络流和最短路在分层图上速度差距也不是特别大

#include<bits/stdc++.h>
#define N 20020
#define M 300300
using namespace std;
int n,m,i,x,y,z,s,t,u,w,V,fl,tot,fir[N],cur[N],pre[N],d[N],nb[N],ne[M],la[M],va[M];
void ins(int x,int y,int z){
    la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;
    la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;
}
int main(){
	for(scanf("%d%d",&n,&m),s=2*n+1,t=s+1,tot=i=1;i<=n;i++)scanf("%d",&x),ins(s,i,x),ins(i+n,t,x),fl+=x;
	for(;m--;ins(x,y+n,z))scanf("%d%d%d",&x,&y,&z);
	for(i=1;i<=t;i++)cur[i]=fir[i];
    for(u=s,nb[0]=t;d[s]<t;){
        if(u==t){
            for(V=1e9,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<V)V=va[cur[u=i]];
            for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=V,va[cur[i]^1]+=V;
            fl-=V;
        }
        for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
        if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
            if(0==--nb[d[u]])break;
            for(i=cur[u]=fir[u],w=t;i;i=ne[i])if(d[la[i]]<w&&va[i])w=d[la[i]];
            ++nb[d[u]=w+1];if(u!=s)u=pre[u];
        }
    }
    printf("%d",fl);
}


大楼

连边☆ f[i][j]表示选了i条边,有j个点的度数为奇数的方案数

先不考虑有重复的边,那么f[i][j]=f[i-1][j-2]*c(j,2)+f[i-1][j]*j*(n-j)+f[i-1][j+2]*c(n-j,2)

但题目要求不能有重复的边,考虑第i条边和前面的某一条边重复,那么奇偶性不变,前面有i-1条边可选,每条边又有c(n,2)-i+2种方案,所以f[i][j]减去f[i-2][j]*(i-1)*(c(n,2)-i+2)

#include<bits/stdc++.h>
#define M 10007
#define N 1010
int n,m,i,j,k,x,y,w,o,v,f[N][N],a[N];
int G(int x){return (x*(x-1)/2)%M;}
int pow(int a,int b,int p){for(o=1,a%=p;b;a=a*a%p,b>>=1)if(b&1)o=o*a%p;return o;}
int main(){
	for(scanf("%d%d%d",&n,&m,&k);m--;a[x]^=1,a[y]^=1)scanf("%d%d",&x,&y);for(i=1;i<=n;w+=a[i++]);
	for(f[0][0]=1,i=1;i<=k;i++)for(j=0;j<=n;j++)f[i][j]=(f[i-1][j]*(n-j)%M*j%M+f[i-1][j-2]*G(j)%M+f[i-1][j+2]*G(n-j)%M-f[i-2][j]*(i-1)%M*(G(n)-i+2+M)%M+M)%M;
	for(v=i=1;i<=k;i++)v=v*pow(i,M-2,M)%M;
	printf("%d",f[k][w]*v%M);
}

画圈圈☆ 很明显是插头DP,今天学习了下,基本方法差不多,判断是否在多边形内可以用射线法。下面写一下推插头DP转移方程的基本方法

用括号序列表示联通状态,共m+1个插头,0表示无插头,1表示左括号,2表示右括号

逐格递推,将上插头和左插头变成下插头和右插头,考虑转移

如果左插头为1,上插头为2,那么形成一个回路,在这道题目中可以看成转移到(0,0)。但如果到终点累加到答案中。

如果左插头为2,上插头为1,那么连起来发现转移到(0,0)

如果左插头和上插头同时为0,那么可以转移到(0,0)和(1,2),由于这题要求每个点都要经过,所以只能转移到(1,2)

如果左插头和上插头有一个为0,那么可以转移到(0,x)和(x,0),x为不为0的那个插头状态

如果左插头和上插头相等,转移到(0,0)。那么如果都是插头1,并将右边第一个状态为2的不匹配插头改为1。如果都是插头2,那么往左找第一个状态为1的不匹配插头改为2。

#include<bits/stdc++.h>
#define M 123456791
using namespace std;char s[15];struct Q{int x,y;}q[8888888];int n,m,i,j,h,t,W,S,x,y,z,p,en,ans,a[15],u[15][22],f[2][4444444],v[2][4444444];
int G(int x,int q1,int q2){int k=0,i=m+1;for(;i;i--)k=k*3+(i==x?q1:(i==x+1?q2:a[i]));return k;}
void up(int x,int S,int z){
	x++;int o=x&1;
	if(v[o][S]!=x)v[o][S]=x,f[o][S]=0,q[++t]=Q{x,S};
	f[o][S]=(f[o][S]+z)%M;
}
int main(){
	for(memset(u,1,sizeof(u)),scanf("%d%d",&n,&m),i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=m;j++)if(s[j]=='#')u[j][i]=1;else if(s[j]=='*')u[j][i]=2;else u[j][i]=0;
	for(en=n*m-1;u[en%m+1][en/m+1];en--);
	for(q[f[0][0]=v[0][0]=t=1]=Q{0,0};h<t;){
		W=q[++h].x;S=q[h].y;z=f[W&1][S];x=W%m+1;y=W/m+1;
		if(W%m==0)S*=3;for(i=1,j=S;i<=m+1;i++,j/=3)a[i]=j%3;
		if(u[x][y]){
			for(p=0,i=1;i<x;i++)if(a[i])p^=1;
			if(u[x][y]==1&&!p||u[x][y]==2&&p)up(W,G(x,0,0),z);
		}else if(a[x]==1&&a[x+1]==2&&W==en){ans=(ans+z)%M;}else
		if(a[x]==1&&a[x+1]==2||a[x]==2&&a[x+1]==1)up(W,G(x,0,0),z);else
		if(!a[x]&&!a[x+1]){
			if(!u[x][y+1]&&!u[x+1][y])up(W,G(x,1,2),z);
		}else if(!a[x]){
			if(!u[x+1][y])up(W,G(x,0,a[x+1]),z);
			if(!u[x][y+1])up(W,G(x,a[x+1],0),z);
		}else if(!a[x+1]){
			if(!u[x+1][y])up(W,G(x,0,a[x]),z);
			if(!u[x][y+1])up(W,G(x,a[x],0),z);
		}else if(a[x]==a[x+1]){
			if(a[x]==1)for(j=0,i=x+2;i<=m+1;i++){
				if(a[i]==1)j--;if(a[i]==2)j++;
				if(j>0){a[i]=1;break;}
			}else for(j=0,i=x-1;i;i--){
				if(a[i]==1)j++;if(a[i]==2)j--;
				if(j>0){a[i]=2;break;}
			}
			up(W,G(x,0,0),z);
		}
	}
	printf("%d",ans);
}

单选错位 

刷题计划 如果m比较小,直接堆就可以了;现在m比较大,可以先粗略地把m插进去,剩下大约n个再用堆得到更加精确的答案。

#include<bits/stdc++.h>
#define N 50100
#define sqr(x)((x)*(x))
using namespace std;int n,m,i,rt,x,b[N],l[N],r[N];double L,sum,ans,a[N];
double G(int i){return sqr(a[i]/(b[i]+2)-L)*(b[i]+2)-sqr(a[i]/(b[i]+1)-L)*(b[i]+1);}
int mg(int x,int y){
	if(!x||!y)return x+y;if(G(x)>G(y))swap(x,y);
	r[x]=mg(r[x],y);swap(l[x],r[x]);return x;
}
int main(){
	for(scanf("%d%d%lf",&n,&m,&L),i=1;i<=n;i++)scanf("%lf",&a[i]);
	for(i=1;i<n;i++)a[i]=a[i+1]-a[i],sum+=fabs(a[i]);
	for(i=1;i<n;i++)b[i]=max(min((int)(m/sum*fabs(a[i]))-1,(int)fabs(a[i]/L)-1),0);
	for(i=1;i<n;i++)rt=mg(rt,i),m-=b[i];
	for(;m--&&G(rt)<0;rt=mg(rt,x))b[rt]++,x=rt,rt=mg(l[x],r[x]),l[x]=r[x]=0;
	for(i=1;i<n;i++)ans+=sqr(a[i]/(b[i]+1)-L)*(b[i]+1);
	printf("%.3lf",ans);
}

飞飞侠 傻逼最短路,加一个状态z表示还能飞几次,不用连边,否则MLE

跳跳棋☆ 好神啊。考虑三个棋子间距相等的话,那么只能中间这个棋子向两边动。否则还可以两边棋子向中间动

这很像一颗树,三个棋子间距相等就是树根,两边向中间跳就是向父亲走一步,中间向两边跳就是向儿子走一步

这样就把问题转化为①两种情况是否同根②如果同根,两点在树上距离

直接暴力也是不可以的,但可以考虑一次跳很多很多步,这样走到s1==s2的情况的步数是log级的

然后要求LCA,可以先把两个点移动到相同深度,然后可以二分答案x,判断一下两个点向上走x步是不是一个点

于是总的复杂度变成log^2ans,好题!

#include<bits/stdc++.h>
using namespace std;struct P{int x,y,z;}a,b,A,B;int d1,d2,l,r,mid,w,v,o,p,q;
bool xd(P a,P b){return a.x==b.x&&a.y==b.y&&a.z==b.z;}
void G(P&a){if(a.x>a.y)swap(a.x,a.y);if(a.x>a.z)swap(a.x,a.z);if(a.y>a.z)swap(a.y,a.z);}
int rt(P a,P&b){
	for(v=0,b=a;b.y*2!=b.x+b.z;v+=o,G(b)){
		p=b.y-b.x;q=b.z-b.y;
		if(p<q)o=(q-1)/p,b.x+=p*o,b.y+=p*o;else o=(p-1)/q,b.z-=q*o,b.y-=q*o;
	}
	return v;
}
P up(P a,int x){
	for(;x;x-=o,G(a)){
		p=a.y-a.x;q=a.z-a.y;
		if(p<q)o=min((q-1)/p,x),a.x+=p*o,a.y+=p*o;else o=min((p-1)/q,x),a.z-=q*o,a.y-=q*o;
	}
	return a;
}
bool ok(int x){return xd(up(a,x),up(b,x));}
int main(){
	scanf("%d%d%d%d%d%d",&a.x,&a.y,&a.z,&b.x,&b.y,&b.z);G(a);G(b);
	d1=rt(a,A);d2=rt(b,B);if(!xd(A,B))return puts("NO"),0;
	puts("YES");if(d1>d2)w=d1-d2,a=up(a,w);else w=d2-d1,b=up(b,w);
	for(l=0,r=min(d1,d2);mid=(l+r)/2,l<r;ok(mid)?r=mid:l=mid+1);
	printf("%d",w+2*l);
}

悄悄话 OTZ出题人

Crash的数字表格

Crash的文明世界 x^k=ΣSterling2(k,i)*i!*C(x,i),递推出斯特林数和阶乘,然后用树形DP递推组合数

#include<bits/stdc++.h>
#define M 10007
#define N 50050
using namespace std;int n,k,L,W,A,B,Q,p,i,j,x,y,v,tot,fir[N],ne[N<<1],pw[155],la[N<<1],S[N][155],f[N][155],g[N][155];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
	f[x][0]=1;
	for(int i=fir[x],j,y;i;i=ne[i])if(la[i]!=fa)for(dfs(y=la[i],x),f[x][0]+=f[y][0],j=1;j<=k;j++)f[x][j]=(f[x][j]+f[y][j]+f[y][j-1])%M;
}
void dp(int x,int fa){
	for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa){
		for(g[y=la[i]][0]=n-f[y][0],j=1;j<=k;j++)g[y][j]=((g[x][j-1]+g[x][j]+f[x][j-1]+f[x][j]-2*f[y][j-1]-f[y][j]-f[y][j-2])%M+M)%M;
		dp(y,x);
	}
}
int main(){
	for(scanf("%d%d%d%d%d%d%d",&n,&k,&L,&W,&A,&B,&Q),pw[0]=S[0][0]=i=1;i<=k;pw[i]=pw[i-1]*i%M,i++)for(S[i][i]=j=1;j<i;j++)S[i][j]=(j*S[i-1][j]+S[i-1][j-1])%M;
	for(i=1;i<n;i++)W=(W*A+B)%Q,p=i<L?i:L,x=i-W%p,y=i+1,ins(x,y),ins(y,x);
	for(dfs(1,0),dp(1,0),i=1;i<=n;printf("%d\n",v),i++)for(v=0,j=1;j<=k;j++)v=(v+(int)(1ll*S[k][j]*pw[j]*(f[i][j]+g[i][j])%M))%M;
}

Construct 第一问求出最大和最小的就行了,第二问可以维护一个单调栈,得到单调上升和下降的曼哈顿凸包,就可以统计出面积了

#include<bits/stdc++.h>
#define N 100100
using namespace std;typedef long long LL;int n,i,t;LL ans,yv=-1e9,yi=1e9;
struct P{LL x,y;}p[N],q[N];bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
		scanf("%lld%lld",&p[i].x,&p[i].y);
		yi=min(yi,p[i].y);yv=max(yv,p[i].y);
	}
	for(sort(p+1,p+n+1,cmp),i=1;i<=n;i++){
		if(!t||p[i].y>q[t].y)q[++t]=p[i];
		if(p[i].y==yv)break;
	}
	for(i++;i<=n;q[++t]=p[i++])for(;p[i].y>q[t].y;t--);
	for(i=2;i<=t;i++)ans+=min(q[i-1].y,q[i].y)*(q[i].x-q[i-1].x);
	for(t=0,i=1;i<=n;i++){
		if(!t||p[i].y<=q[t].y)q[++t]=p[i];
		if(p[i].y==yi)break;
	}
	for(i++;i<=n;q[++t]=p[i++])for(;p[i].y<q[t].y;t--);
	for(i=2;i<=t;i++)ans+=max(q[i-1].y,q[i].y)*(q[i-1].x-q[i].x);
	printf("%lld\n%lld",(p[n].x-p[1].x+yv-yi)*2,ans);
}

免费的馅饼 f[i]=max(f[j])(2t[i]+p[i]>=2t[j]+p[j],2t[i]-p[i]>=2t[j]-p[j]),树状数组优化一下就可以了

#include<bits/stdc++.h>
#define N 100100
using namespace std;int n,w,i,x,y,z,cnt,ans,v[N],c[N];
struct P{int x,y,z;}p[N];bool cmp(P a,P b){return a.x<b.x;}
void add(int x,int z){for(;x<cnt;x+=x&-x)c[x]=max(c[x],z);}
int qu(int x){for(w=0;x;x-=x&-x)w=max(w,c[x]);return w;}
int main(){
	for(scanf("%d%d",&w,&n),i=1;i<=n;i++)scanf("%d%d%d",&x,&y,&p[i].z),x*=2,p[i].x=x+y,p[i].y=v[i]=x-y;
	for(sort(p+1,p+n+1,cmp),sort(v+1,v+n+1),cnt=unique(v+1,v+n+1)-v,i=1;i<=n;i++)
		x=lower_bound(v+1,v+cnt,p[i].y)-v,z=qu(x)+p[i].z,add(x,z),ans=max(ans,z);
	printf("%d",ans);
}

圈地计划 黑白染色,黑点源流量商业,汇流量工业;白点源流量工业,汇流量商业;相邻两点间流量c1+c2。跑最大流。 

切割 树形DP,f[i][j][k]表示以i为根,需要联通块大小为j,当前联通块大小为k的最小值,g[i]为min(f[i][j][j])(k1≤j≤k2),暴力n^4转移

#include<bits/stdc++.h>
using namespace std;int n,k1,k2,i,j,k,x,y,tot,fir[52],la[101],ne[101];double sm,v[52],g[52],f[52][52][52];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
	int i,j,k,l,y;g[x]=1e18;
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x);
	for(j=k1;j<=k2;g[x]=min(g[x],f[x][j][j]),j++)for(f[x][j][1]=v[x]/j,i=fir[x];i;i=ne[i])if(la[i]!=fa)for(k=j;k;k--)for(f[x][j][k]+=g[y=la[i]],l=1;l<k;l++)f[x][j][k]=min(f[x][j][k],f[x][j][k-l]+f[y][j][l]);
}
int main(){
	for(scanf("%d%d%d",&n,&k1,&k2),i=1;i<=n;i++)scanf("%lf",&v[i]),sm+=v[i];
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(i=0;i<=n;i++)for(j=1;j<=k2;j++)for(k=0;k<=k2;k++)f[i][j][k]=1e18;
	dfs(1,0);if(g[1]==1e18)g[1]=sm*2;printf("%.2lf",g[1]);
}

Submultiple 可以发现答案就是(Σ(j<=a[i]+1)j^k),对于不同的数据采取不同的方法

对于k=3的情况,对每个数用三次方求和公式求解统计贡献

对Pi≤100000的情况,暴力统计k次方前缀和

对于k较小的情况,用矩阵乘法来做k次方前缀和,当然这个k完全可以做到200000,CF上出过,拉下来就好了

#include<bits/stdc++.h>
#define M 1000000007
using namespace std;typedef long long LL;int n,i;LL x,y,v,k,ans,a[77777],F[111111],pw[44],cc[44],R[44];
LL pow(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
LL get(LL n,LL k){
	int i,j;LL an=0,p=1;if(n<=k+4)return R[n];
    for(i=1;i<k+5;i++)p=p*(n-i)%M;
    for(i=1;i<k+5;i++)an=(an+p*pow(n-i,M-2,M)%M*cc[i])%M;
    return an;
}
int main(){
	for(scanf("%d%lld",&n,&k),ans=i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]++,v=max(v,a[i]);
	if(k==3){
		for(i=1;i<=n;i++)x=a[i]%M,y=(a[i]+1)%M,x=(x*y/2)%M,ans=ans*x%M*x%M;
		return printf("%lld",ans),0;
	}
	if(v<=100001){
		for(i=1;i<=100001;i++)F[i]=(F[i-1]+pow(i,k,M))%M;
		for(i=1;i<=n;i++)ans=ans*F[a[i]]%M;
		return printf("%lld",ans),0;
	}
	for(pw[0]=1,i=1;i<k+5;i++)pw[i]=pw[i-1]*i%M;
    for(i=1;i<k+5;i++)R[i]=(R[i-1]+pow(i,k,M))%M;
    for(i=1;i<k+5;i++){
        cc[i]=pow(pw[i-1]*pw[k+4-i],M-2,M)*R[i]%M;
        if((k+4-i)&1)cc[i]=(M-cc[i])%M;
    }
	for(i=1;i<=n;i++)ans=ans*get(a[i],k)%M;
	printf("%lld",ans);
}

Road☆ 首先贪心地按A和B的顺序先分配边,这样构成了很多个环,目标是把这些环连到一起,可以转化为最小生成树模型,树上的边就是相邻环的代价

#include<bits/stdc++.h>
#define sqr(x)((x)*(x))
#define N 1001000
using namespace std;int n,i,x,y,z,ans,F[N];
struct P{int y,z;}a[N],b[N],c[N];bool cmp(P a,P b){return a.z>b.z;}
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
int main(){
	for(scanf("%d%d%d%d%d%d",&n,&a[1].z,&a[2].z,&x,&y,&z),i=3;i<=n;i++)a[i].z=(a[i-1].z*x+a[i-2].z*y+z)%32767;
	for(scanf("%d%d%d%d%d",&b[1].z,&b[2].z,&x,&y,&z),i=3;i<=n;i++)b[i].z=(b[i-1].z*x+b[i-2].z*y+z)%32767;
	for(i=1;i<=n;i++)F[i]=a[i].y=b[i].y=i;sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
	for(i=1;i<=n;i++)F[gf(b[i].y)]=gf(a[i].y),ans=max(ans,sqr(a[i].z)-sqr(b[i].z));
	for(i=1;i<n;i++)c[i].z=sqr(a[i].z)-sqr(b[i+1].z),c[i].y=i;
	for(sort(c+1,c+n,cmp),i=n-1;i;i--){
		z=c[i].y;x=gf(a[z].y);y=gf(b[z+1].y);
		if(x!=y)ans=max(ans,c[i].z),F[x]=y;
	}
    printf("%d",ans);
}

Mario填格子 

整数的lqp拆分

拆迁队☆ 设d[i]=a[i]-i,则f[i]=max(f[j]+1)(d[i]>=d[j])

dp[i]=min(a[i]+b[i]+dp[j]+(i-j+1)*a[j]+(i-j+1)*(i-j)/2)
设c[i]=i(i+1)/2+dp[i]-a[i]*i-a[i]
则dp[i]=min(c[j]+i*d[j])+b[i]+a[i]+i(i-1)/2
满足①j<i②f[j]+1=f[i]③d[j]<=d[i]
按照f[i]分组,用f[i]=x的组去更新f[i]=x+1的答案,并按照序号排序,解决①②两个限制
考虑j比k更优时,当且仅当c[j]+i*d[j]<c[k]+i*d[k]
(c[j]-c[k])/(d[j]-d[k])<-i(假设d[j]≥d[k])
和上题一样利用CDQ分治解决,分治的时候按d排序解决限制③
维护凸壳,查询时在凸壳上二分,时间复杂度O(nlg^2n)
Tsinsen上不知为何挂了5分。。

信号塔 把每个菱形先转45°变成正方形,从后往前求出当前正方形的交并记录答案,再从前往后把答案推出来即可

#include<bits/stdc++.h>
using namespace std;struct P{int lx,ly,rx,ry;}w,A[100100];vector<P>v[100100];int n,m,i,j,z,x,y,px,py,d[100100];
void get(P b){w.lx=max(w.lx,b.lx);w.ly=max(w.ly,b.ly);w.rx=min(w.rx,b.rx);w.ry=min(w.ry,b.ry);}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&d[i]);
	for(i=1;i<=m;i++)scanf("%d%d%d",&z,&x,&y),v[z].push_back(P{x-y-d[z],x+y-d[z],x-y+d[z],x+y+d[z]});
	for(w.lx=w.ly=-1e8,w.rx=w.ry=1e8,i=n;i;i--){
		w.lx+=d[i];w.ly+=d[i];w.rx-=d[i];w.ry-=d[i];
		for(j=0;j<v[i].size();j++)get(v[i][j]);A[i]=w;
		w.lx-=d[i];w.ly-=d[i];w.rx+=d[i];w.ry+=d[i];
	}
	for(w.lx=w.ly=-1e8,w.rx=w.ry=1e8,i=1;i<=n;i++){
		get(A[i]);px=w.lx;py=w.ly;
		if((px+py)&1)if(w.lx==w.ly)py++;else px++;
		printf("%d %d\n",(px+py)/2,(py-px)/2);
		w.lx=px+d[i]-d[i+1];w.ly=py+d[i]-d[i+1];w.rx=px-d[i]+d[i+1];w.ry=py-d[i]+d[i+1];
	}
}

部落战争

种树

聪聪可可

设计铁路 裸斜率优化

#include<bits/stdc++.h>
#define N 40040
using namespace std;typedef long long LL;
int n,m,i,j,h,t,q[N];LL f[N],g[N],s[N];
struct P{int d,r;}p[N];bool cmp(P a,P b){return a.d>b.d;}
LL gx(LL j,LL k){return f[j]+s[j]-f[k]-s[k];}
LL gy(LL j,LL k){return g[j]-g[k];}
LL gd(LL i,LL j){return f[j]+s[j]-s[i]+(g[i]-g[j])*p[i].d+m;}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d",&p[i].d,&p[i].r);
	for(sort(p+1,p+n+1,cmp),i=n-1;i>=0;i--)s[i]=s[i+1]+p[i+1].d*p[i+1].r,g[i]=g[i+1]+p[i+1].r;
	for(i=1;i<=n+1;q[++t]=i++){
		for(;h<t&&gx(q[h+1],q[h])<gy(q[h+1],q[h])*p[i].d;h++);
		for(f[i]=gd(i,q[h]);h<t&&gx(i,q[t])*gy(q[t],q[t-1])>gx(q[t],q[t-1])*gy(i,q[t]);t--);
	}
	printf("%lld",f[n+1]-m);
}

星际探险 BZOJ上是傻逼最短路

旅游

拉拉队排练 Manacher扫一遍,然后按半径从大到小贪心快速幂就可以了

#include<bits/stdc++.h>
#define N 2000003
#define M 19930726
using namespace std;typedef long long LL;int l,n,i,p,mx,r[N],sum[N];char a[N],s[N];LL k,ans,v;
LL pow(LL a,LL b,LL p){for(v=1;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
int main(){
	for(scanf("%d%lld%s",&n,&k,a),s[l++]='&',s[l++]='#',i=0;i<n;i++)s[l++]=a[i],s[l++]='#';
	for(i=0;i<l;i++){
		for(r[i]=mx>i?min(r[2*p-i],mx-i):1;s[i+r[i]]==s[i-r[i]];r[i]++);
		if(i+r[i]>mx)mx=i+r[i],p=i;
		if(i%2==0)sum[r[i]/2]++;
	}
	for(ans=1,i=n;i;i--)sum[i]+=sum[i+1];
	for(i=n;i&&k;i--)if(sum[i]<=k)k-=sum[i],ans=ans*pow(2*i-1,sum[i],M)%M;else ans=ans*pow(2*i-1,k,M)%M,k=0;
	printf("%lld",ans);
}

男生女生☆ 好题!首先解决第一问,找一个最大的全连边的二分图,不妨建出反图,那么反图的最小割即为答案。

可是还要让男生尽量多,不妨把男生的权值设为100,女生的权值设为99,跑最小割就可以得到男生更多的答案

这样就解决了第一问,假设答案为x个男生,y个女生,用DP解决第二问

f[x][y]表示选择x个男生,y个女生的方案数,不妨看成一个x*y的方格上取数

那么容斥一下,得到f[x][y]=c[x*y][k]-Σf[x'][y']*c[x][x']*c[y][y'](x!=x'||y!=y')

这样时间复杂度是O(网络流+n^4)

#include<bits/stdc++.h>
#define N 2525
#define P 19921228
using namespace std;bool v[52][52];long long f[52][52],c[N][N];
int n,k,m,x,y,s,t,i,j,I,J,u,tot,V,w,fl,fir[N],d[N],pre[N],cur[N],nb[N],ne[N*3],la[N*3],va[N*3];
void ins(int x,int y,int fl){
    la[++tot]=y;ne[tot]=fir[x];va[tot]=fl;fir[x]=tot;
    la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;
}
int main(){
	for(scanf("%d%d%d",&n,&k,&m);m--;)scanf("%d%d",&x,&y),v[x][y]=1;
	for(s=2*n+1,t=s+1,tot=i=1;i<=n;i++)for(j=1;j<=n;j++)if(!v[i][j])ins(i,j+n,1e9);
	for(i=1;i<=n;i++)ins(s,i,100),ins(i+n,t,99);
	for(i=1;i<=t;i++)cur[i]=fir[i];
    for(u=s,nb[0]=t;d[s]<t;){
        if(u==t){
            for(V=1e9,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<V)V=va[cur[u=i]];
            for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=V,va[cur[i]^1]+=V;
            fl+=V;
        }
        for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
        if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
            if(0==--nb[d[u]])break;
            for(i=cur[u]=fir[u],w=t;i;i=ne[i])if(d[la[i]]<w&&va[i])w=d[la[i]];
            ++nb[d[u]=w+1];if(u!=s)u=pre[u];
        }
    }
    x=fl-fl/99*99;y=fl/99-x;x=n-x;y=n-y;
    for(i=0;i<=x*y;i++)for(c[i][0]=1,j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
    for(i=1;i<=x;i++)for(j=1;j<=y;j++)for(f[i][j]=c[i*j][k],I=1;I<=i;I++)for(J=1;J<=j;J++)if(I!=i||J!=j)f[i][j]=(f[i][j]-f[I][J]*c[i][I]%P*c[j][J]%P+P)%P;
	printf("%d %d\n%lld",x,y,f[x][y]);
}

稳定婚姻☆ 暴力二分图是没什么希望的,发现每次不合法的情况一定是在二分图上构成了一个“环”

由此想到可以把每对婚外情当做一条有向边,然后用tarjan判断每一个点所在的联通分量是否大于1,就可以O(n+m)出解了

#include<bits/stdc++.h>
#define N 32001 
using namespace std;char s[9];int n,m,i,j,w,u,o,tot,id,cnt,di,t,c[N][52],fir[N],ne[N],la[N],low[N],dfn[N],st[N],sz[N],bl[N],is[N],to[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int C(char x){return x>='a'&&x<='z'?x-'a':x-'A'+26;}
void G(){for(scanf("%s",s),u=j=0;s[j];u=c[u][o],j++)if(!c[u][o=C(s[j])])c[u][o]=++id;}
void tj(int x){
    low[x]=dfn[x]=++di;is[x]=1;st[++t]=x;int y,i;
    for(i=fir[x];i;i=ne[i])if(!dfn[y=la[i]])tj(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
    if(dfn[x]==low[x])for(cnt++,u=0;u!=x;u=st[t--],bl[u]=cnt,sz[cnt]++,is[u]=0);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)G(),to[u]=i,G(),to[u]=i;
	for(scanf("%d",&m);m--;)G(),w=to[u],G(),ins(w,to[u]); 
	for(i=1;i<=n;i++)if(!dfn[i])tj(i);
	for(i=1;i<=n;i++)puts(sz[bl[i]]>1?"Unsafe":"Safe"); 
}

排队 分块在线统计逆序对

礼物 扩展lucas

happiness 神奇的最小割

cheat 分块,记录s[i][j][k]表示1~i,1~j,在块1~k的答案,每m分一块,总复杂度O(n^2m+qm)

#include<bits/stdc++.h>
using namespace std;
int i,j,k,pa,pb,pc,n,m,O,Q,X1,Y1,X2,Y2,l,r,t,ans,v[255][255],s[255][255][255];long long a[3333],b[3333],c[3333];
int get(int i,int j,int O){return (a[i%pa+1]+b[i%pb+1]+c[i%pc+1]+a[j%pa+1]+b[j%pb+1]+c[j%pc+1])%O+1;}
struct P{int z,x,y;}p[66666];bool cmp(P a,P b){return a.z<b.z;}
int G(int z){
	int u,i,V=0,o;
	for(u=0;u<m;u++)if(p[u*n+1].z>z)break;
	if(p[u*n+1].z>z)u--;if(u==m)u--;
	if(u>=0){
		V=s[X2][Y2][u]+s[X1-1][Y1-1][u]-s[X2][Y1-1][u]-s[X1-1][Y2][u];o=u*n;
		for(i=2;i<=n;i++)if(p[o+i].z<=z&&p[o+i].z!=p[o+1].z)if(X1<=p[o+i].x&&p[o+i].x<=X2&&Y1<=p[o+i].y&&p[o+i].y<=Y2)V++;
	}return V;
}
int main(){
	for(scanf("%d",&pa),i=1;i<=pa;i++)scanf("%lld",&a[i]);
	for(scanf("%d",&pb),i=1;i<=pb;i++)scanf("%lld",&b[i]);
	for(scanf("%d",&pc),i=1;i<=pc;i++)scanf("%lld",&c[i]);
	for(scanf("%d%d%d%d",&n,&m,&O,&Q),i=1;i<=n;i++)for(j=1;j<=m;j++)v[i][j]=get(i,j,O),p[++t]=P{v[i][j],i,j};
	for(sort(p+1,p+t+1,cmp),i=1;i<=n;i++)for(j=1;j<=m;j++)for(k=0;k<m;k++)if(v[i][j]>p[k*n+1].z)s[i][j][k]=s[i-1][j][k]+s[i][j-1][k]-s[i-1][j-1][k];else s[i][j][k]=s[i][j-1][k]+s[i-1][j][k]-s[i-1][j-1][k]+1;
	for(i=1;i<=Q;i++){
		X1=get(i,1,n);Y1=get(i,2,m);X2=get(i,3,n);Y2=get(i,4,m);l=get(i,5,O);r=get(i,6,O);
		if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);if(l>r)swap(l,r);ans^=(G(r)-G(l-1));
	}
	printf("%d",ans);
}

candy 记录多个前缀和,加一加减一减,对于每个询问O(1)回答

#include<bits/stdc++.h>
using namespace std;int pa,pb,pc,n,m,i,j,p,q,x,y,z,a[3030],b[3030],c[3030];
long long ans,v[620][620],s2[620][620],s3[620][620],s4[620][620],s5[620][620];
int G(int i,int j){return a[i%pa+1]+b[i%pb+1]+c[i%pc+1]+a[j%pa+1]+b[j%pb+1]+c[j%pc+1];}
int main(){
	for(scanf("%d",&pa),i=1;i<=pa;i++)scanf("%d",&a[i]);
	for(scanf("%d",&pb),i=1;i<=pb;i++)scanf("%d",&b[i]);
	for(scanf("%d",&pc),i=1;i<=pc;i++)scanf("%d",&c[i]);
	for(scanf("%d%d%d%d",&n,&m,&p,&q),n+=10,m+=10,i=6;i<=n-5;i++)for(j=6;j<=m-5;j++)v[i][j]=G(i-5,j-5)%p+1;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)v[i][j]=v[i][j-1]+v[i][j],s2[i][j]=s2[i][j-1]+v[i][j],s3[i][j]=s3[i-1][j]+s2[i][j],s4[i][j]=s4[i-1][j-1]+s2[i][j],s5[i][j]=s5[i-1][j+1]+s2[i][j];
	for(i=1;i<=q;i++){
		x=G(i,1)%(n-10)+6;y=G(i,2)%(m-10)+6;z=G(i,3)%min(min(x-5,y-5),min(n-5-x+1,m-5-y+1))+1;
		ans^=(s4[x][y+z-1]-s4[x-z][y-1]+s4[x+z-1][y-2]-s4[x-1][y-z-2]+s5[x-1][y-z]-s5[x-z][y-1]+s5[x+z-1][y]-s5[x][y+z-1]-2*(s3[x+z-1][y-1]-s3[x-z][y-1]));
	}
	printf("%lld",ans);
}

等差子序列 正解应该是HASH,我用了一个分治+Cheat的方法。取出一个最大的,然后两边看看能不能找到小的和大的构成等差数列。分治下去。取出一个最小的做同样的事。数据实在太弱特判1组水过了。

最短路☆ 静态仙人掌(杨天树),学习了一下。这个图是分层的,所以可以先最短路求出1号点到每个点的距离,然后处理处每个环,环上其他点向环头连边建立出新树,在新树上求LCA,进行以下讨论:

①两个点在一条链上,直接输出两个点在最短路上的距离差

②LCA后两个点在一个环上,先加上两个点到环上点的距离,再加上环上较短的一段

③LCA后两个点不在一个环上,直接按正常LCA返回距离

#include<bits/stdc++.h>
#define N 10020
using namespace std;bool us[N*4],v[N];int n,m,Q,i,h,t,x,y,z,tot,cnt,id,d[N],H[N],q[N],rd[N],rl[N],bl[N],dfn[N],fir[N],pre[N],F[N][14],ne[N*4],la[N*4],va[N*4];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void gr(int x,int y,int z){
	us[z]=us[z^1]=1;rl[++cnt]+=va[z];
	for(int i=y;i!=x;i=la[pre[i]^1])bl[i]=cnt,us[pre[i]]=us[pre[i]^1]=1,ins(x,i,0),rl[cnt]+=va[pre[i]];
}
void dfs(int x){
	dfn[x]=++id;
	for(int i=fir[x],y;i;i=ne[i])if(i!=(pre[x]^1)&&i<=m*2+1)if(!dfn[y=la[i]])pre[y]=i,rd[y]=rd[x]+va[i],dfs(y);else if(dfn[y]<dfn[x])gr(y,x,i);
}
void dfs2(int x){
	v[x]=1;int i,y;for(i=1;i<=13;i++)F[x][i]=F[F[x][i-1]][i-1];
	for(i=fir[x];i;i=ne[i])if(!us[i]&&la[i]!=F[x][0])F[y=la[i]][0]=x,H[y]=H[x]+1,dfs2(y);	
}
int qu(int x,int y){
	if(H[x]<H[y])swap(x,y);int t=H[x]-H[y],i,o=d[x]+d[y],w=d[x]-d[y];
    for(i=0;i<=13;i++)if(t&(1<<i))x=F[x][i];if(x==y)return w;
    for(i=13;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];t=F[x][0];
    return bl[x]&&bl[x]==bl[y]?o-d[x]-d[y]+min(rl[bl[x]]-abs(rd[x]-rd[y]),abs(rd[x]-rd[y])):o-2*d[t];
}
int main(){
	for(scanf("%d%d%d",&n,&m,&Q),i=tot=1;i<=m;ins(x,y,z),ins(y,x,z),i++)scanf("%d%d%d",&x,&y,&z);
	for(memset(d,63,sizeof(d)),d[q[t=1]=1]=0,v[1]=1;h^t;)for(i=fir[x=q[++h]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[++t]=y]=1;
    for(dfs(1),memset(v,0,sizeof(v)),dfs2(1);Q--;printf("%d\n",qu(x,y)))scanf("%d%d",&x,&y);
}

排斥反应☆ 把问题转化为在p*q矩阵上取若干个元素,任意两个不相邻的方案个数

如果直接2^p是1024,不能接受,把不合法状态去掉后变成123,复杂度O(123^3lgq)

#include<bits/stdc++.h>
#define M 19921107
int p,T,t,i,j,A,B,C,q[124];long long ans,f[124][124],h[124][124],g[124][124];
void dfs(int x,int y){
	if(x==p-1){
		if(!((1<<(x-1))&y)&&y%2==0)q[++t]=y+(1<<x);
		q[++t]=y;
	}else if(!x)dfs(x+1,0),dfs(x+1,1);else{
		if(!((1<<(x-1))&y))dfs(x+1,y+(1<<x));
		dfs(x+1,y);
	}
}
int main(){
	for(scanf("%d%d",&p,&T),dfs(0,0),i=1;i<=t;f[i][i]=1,i++)for(j=1;j<=t;j++)if(!(q[i]&q[j]))g[i][j]++;
	for(T--,i=0;i<=30;i++){
		if(T>>i&1){
			for(memset(h,0,sizeof(h)),A=1;A<=t;A++)for(B=1;B<=t;B++)for(C=1;C<=t;C++)h[A][B]=h[A][B]+f[A][C]*g[C][B];
			for(A=1;A<=t;A++)for(B=1;B<=t;B++)f[A][B]=h[A][B]%M;
		}
		for(memset(h,0,sizeof(h)),A=1;A<=t;A++)for(B=1;B<=t;B++)for(C=1;C<=t;C++)h[A][B]=h[A][B]+g[A][C]*g[C][B];
		for(A=1;A<=t;A++)for(B=1;B<=t;B++)g[A][B]=h[A][B]%M;
	}
	for(i=1;i<=t;i++)for(j=1;j<=t;j++)if(!(q[i]&q[j])||!T)ans=(ans+f[i][j])%M;
	printf("%lld",ans);
}

字符串游戏 f[i][j][k][p]表示i到j是否可以表示第k个字符串的前p个字符,c[i][j]表示i到j是否可以全部删去。

转移f[i][j][k][p]|=(f[j-1][k][p-1]&S[k][p]==s[j])or(f[d][k][p]&c[d+1][j])

#include<bits/stdc++.h>
using namespace std;char s[155],S[33][22];bool f[155][33][22],c[155][155];int l,m,i,j,k,p,u,L[33],g[155]; 
int main(){
	for(scanf("%s%d",s+1,&m),l=strlen(s+1),i=1;i<=m;i++)scanf("%s",S[i]+1),L[i]=strlen(S[i]+1); 
	for(i=l;i;i--){
		for(memset(f,0,sizeof(f)),j=1;j<=m;j++)f[i-1][j][0]=1;
		for(j=i;j<=l;j++){
			for(k=1;k<=m;k++)for(p=1;p<=L[k];p++)f[j][k][p]|=(f[j-1][k][p-1]&S[k][p]==s[j]); 
			for(u=i;u<=j;u++)if(c[u+1][j])for(k=1;k<=m;k++)for(p=1;p<=L[k];p++)f[j][k][p]|=f[u][k][p]; 
		}
		for(j=i;j<=l;j++)for(k=1;k<=m;k++)c[i][j]|=f[j][k][L[k]]; 
	}
	for(i=1;i<=l;i++)for(g[i]=g[i-1]+1,j=1;j<=i;j++)if(c[j][i])g[i]=min(g[i],g[j-1]); 
	printf("%d",g[l]); 
}

股市的预测 HASH大法好!差分后枚举A串长度,用HASH求出前面一段和后面一段最多弄多少,时间复杂度是调和级数*二分HASH的复杂度,即nlg^2n,BZOJ上卡了好几发才过。

#include<bits/stdc++.h>
#define M 1000000007
#define N 111111
using namespace std;typedef long long LL;int n,m,i,j,o,la,a[N];LL ans,O,I[N],sm[N];
inline LL C(const int&l,const int&r){return (sm[r]-sm[l-1]+M)*I[l-1]%M;}
inline bool G(const int&x,const int&y,const int&z){return C(x,x+z-1)==C(y,y+z-1);}
inline int get(const int&x,const int&y){
    int l=1,r=min(n*2+1-y+1,n),mid,A=0;
    for(;l<=r;)if(G(x,y,mid=l+r>>1))l=(A=mid)+1;else r=mid-1;
    return A;
}
int main(){
    for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
    for(n--,i=1;i<=n;i++)a[i]=a[i+1]-a[i],a[n+n+2-i]=a[i];a[n+1]=23333333;
    for(I[0]=O=i=1;i<=2*n+1;i++)O=O*999983%M,sm[i]=(sm[i-1]+1ll*(a[i]+M)*O)%M,I[i]=I[i-1]*496501444%M;
    for(j=1;j+j+m<=n;j++)for(la=0,i=1;i+j+m<=n;i+=j){
        o=min(get(i,i+j+m),j);if(o+la>=j)ans+=o+la-j+1;
        la=min(get(n+n-i-j+3,n*2-i-j-j-m+3),j-1);
    }printf("%lld",ans);
}

数颜色

墨墨的等式 任选一个ai,那么如果x+kai可以凑出来,那么x+(k+w)ai也可以凑出来。于是对于每个x找到最小的满足条件的k就好了,使用最短路即可。

JZPFAR 直接上K-D树(口胡)

tree 直接LCT(口胡)

Crisis(GG) 建出矩阵,然后主席树往下传。。然后矩阵TM不能换,一定要按顺序,爆炸了

黑白染色 不同颜色连1边否则连0边,每个点为起点跑最短路,找到一个点使距离最远的黑点最小。不知为何挂了5分。。

#include<bits/stdc++.h>
using namespace std;char s[44][44];
int n,m,i,j,p,h,t,S,x,y,ans=1e9,tot,fir[1666],d[1666],ne[8888],la[8888],va[8888],c[1666],q[23333333],v[1666];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void I(int x,int y,int z){ins(x,y,z);ins(y,x,z);}
int G(int x,int y){return x*m-m+y;}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)for(scanf("%s",s[i]+1),j=1;j<=m;j++){
		c[G(i,j)]=s[i][j]=='B'?1:0;
		if(i>1)I(G(i,j),G(i-1,j),s[i][j]!=s[i-1][j]);
		if(j>1)I(G(i,j),G(i,j-1),s[i][j]!=s[i][j-1]);
	}
	for(S=1;S<=n*m;S++){
		for(memset(d,63,sizeof(d)),h=d[q[t=1]=S]=0,v[S]=1;h^t;)for(i=fir[x=q[++h]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],v[y]!=S)v[q[++t]=y]=S;
		for(p=0,i=1;i<=n*m;i++)if(c[i])p=max(p,d[i]+1);ans=min(ans,p);
	}
	printf("%d",ans);
}

矩形计算☆ 离线好题啊。。可是没讲

对于出现次数比较多的点,预处理出答案

对于出现次数比较少的点,枚举点对做矩形,这样每次询问相当于询问一个矩形里有多少个矩形

把一维排序后变成三维数点,树状数组解决

设这个出现次数的分界线为p,则时间复杂度为O(n^2m^2/p+Q(nm/p+lg^3n)+(nm/p)lg^3n))

#include<bits/stdc++.h>
#define N 40040
#define M 100100
using namespace std;long long ans[M];
int n,m,i,j,k,w,o,t,x,O,Q,cnt,X1,X2,Y1,Y2,a[202][202],b[N],s[202][202][802],c[202][202][202];
struct U{int x,y;};vector<U>v[N];
struct P{int x1,y1,x2,y2,id;}q[M],p[M*9];bool cmp(P a,P b){return a.x1>b.x1;}
void add(int x,int y,int z){int i,j;for(;x;x-=x&-x)for(i=y;i<201;i+=i&-i)for(j=z;j<201;j+=j&-j)c[x][i][j]++;}
int qu(int x,int y,int z){int i,j,v=0;for(;x<201;x+=x&-x)for(i=y;i;i-=i&-i)for(j=z;j;j-=j&-j)v+=c[x][i][j];return v;}
int main(){
	for(scanf("%d%d",&n,&m),O=40,i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]),b[++w]=a[i][j];
	sort(b+1,b+w+1);cnt=unique(b+1,b+w+1)-b-1;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)v[a[i][j]=lower_bound(b+1,b+cnt+1,a[i][j])-b].push_back(U{i,j});
	for(k=1;k<=cnt;k++)if(v[k].size()>O)
		for(o++,i=1;i<=n;i++)for(j=1;j<=m;j++)s[i][j][o]=s[i-1][j][o]+s[i][j-1][o]-s[i-1][j-1][o]+(a[i][j]==k);
	else{
		for(i=0;i<v[k].size();i++)for(j=0;j<v[k].size();j++){
			X1=v[k][i].x;Y1=v[k][i].y;X2=v[k][j].x;Y2=v[k][j].y;
			p[++t]=P{min(X1,X2),min(Y1,Y2),max(X1,X2),max(Y1,Y2)};
		}
	}
	for(scanf("%d",&Q),i=1;i<=Q;i++){
		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);q[i]=P{X1,Y1,X2,Y2,i};
		for(j=1;j<=o;j++)x=s[X2][Y2][j]+s[X1-1][Y1-1][j]-s[X1-1][Y2][j]-s[X2][Y1-1][j],ans[i]+=1ll*x*x;
	}
	sort(p+1,p+t+1,cmp);sort(q+1,q+Q+1,cmp);
	for(i=j=1;i<=Q;i++){
		for(;p[j].x1>=q[i].x1;j++)add(p[j].y1,p[j].x2,p[j].y2);
		ans[q[i].id]+=qu(q[i].y1,q[i].x2,q[i].y2);
	}
	for(i=1;i<=Q;i++)printf("%lld\n",ans[i]);
}

城市改建☆ 大力树DP,f[i]表示子树直径,h[i]表示子树外直径,那么答案为min(max(f[i],h[i],(f[i]+1)/2+(h[i]+1)/2+1))

但是还要记录方案,那么记录g,g2,g3表示往下伸的第一,第二,第三长长度,u表示往上伸的最长长度

那么第二遍DFS时,h[y]=max(h[x],f[i],g[i]+g[j]+2,g[i]+1+u[x])(i!=j,j!=y,i!=y),u[y]=max(u[x]+1,g[i]+2)(i!=y)用记录的三个值完成转移

#include<bits/stdc++.h>
#define N 300300
using namespace std;
int n,i,A,Y,x,y,tot,fir[N],ne[N<<1],la[N<<1],f[N],g[N],h[N],u[N],f2[N],f1[N],g2[N],g3[N],fa[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int G(int x){return x?max(max(f[x],h[x]),(f[x]+1)/2+(h[x]+1)/2+1):1e9;}
void dfs(int x){
    f1[x]=f2[x]=g2[x]=g3[x]=-1e9;f[x]=g[x]=0;
    for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x]){
        fa[y=la[i]]=x;dfs(y=la[i]),f[x]=max(f[x],max(f[y],g[x]+g[y]+1));
        if(f[y]>f1[x])f2[x]=f1[x],f1[x]=f[y];else f2[x]=max(f2[x],f[y]);
        if(g[y]+1>g[x])g3[x]=g2[x],g2[x]=g[x],g[x]=g[y]+1;else if(g[y]+1>g2[x])g3[x]=g2[x],g2[x]=g[y]+1;else g3[x]=max(g3[x],g[y]+1);
    }
}
void dfs2(int x){
    for(int i=fir[x],y,X,Y;i;i=ne[i])if(la[i]!=fa[x]){
        if(g[x]==g[y=la[i]]+1)X=g2[x],Y=g2[x]+g3[x];else if(g2[x]==g[y]+1)X=g[x],Y=g[x]+g3[x];else X=g[x],Y=g[x]+g2[x];
        h[y]=max(max(f1[x]==f[y]?f2[x]:f1[x],h[x]),max(X+u[x],Y));u[y]=max(X+1,u[x]+1);dfs2(y);
    }
}
int get(int x,int z){
	for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x])if(f[y=la[i]]==z)return get(y,z);
	return x;
}
int cal(int x,int z){
	if(g[x]-(z-g[x])<=1)return x;
	for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa[x])if(g[y=la[i]]+1==g[x])return cal(y,z);
}
int fd(int x,int F){
	memset(fa,0,sizeof(fa));fa[x]=F;dfs(x);
	return cal(get(x,f[x]),f[x]);
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1),dfs2(1),i=2;i<=n;i++)if(G(i)<G(A))A=i;Y=fa[A];
	printf("%d\n%d %d\n",G(A),A,fa[A]);
	printf("%d %d\n",fd(A,Y),fd(Y,A));
}

Calc d=gcd(i,j),i=ad,j=bd,gcd(a,b)=1,(a+b)|abd,gcd(a,b)=1-->gcd(a+b,b)=1,gcd(a+b,a)=1,-->(a+b)|d,d=(a+b)t

只需求a<b gcd(a,b)=1 b(a+b)t<=n,打表也可以找到这个规律。然后枚举b,乱搞。。

Attack K-D树套权值线段树,时间复杂度O(nlgn+mn^0.5lgn)。

#include<bits/stdc++.h>
#define Mx(a,b)(a<b?a=b:a)
#define Mi(a,b)(a>b?a=b:a)
#define N 60600
#define M 23333333
using namespace std;char s[9];
int n,m,i,l,r,O,k,x,y,z,V,id,md,rt,W,X,Y,X1,Y1,X2,Y2,t1,t2,Z[N],T[N],to[N],q1[N],q2[N],L[M],R[M],sz[M];
struct P{int l,r,z,fa,id,d[2],mi[2],mx[2];}p[N];
bool cmp(P a,P b){return a.d[O]<b.d[O]||a.d[O]==b.d[O]&&a.d[O^1]<b.d[O^1];}
void ins(int&k,int l,int r,int x,int z){
    if(!k)k=++id;sz[k]+=z;if(l==r)return;int md=l+r>>1;
    if(x<=md)ins(L[k],l,md,x,z);else ins(R[k],md+1,r,x,z);
}
void tou(int k,int rt){
    ins(T[rt],1,W,p[k].z,1);
    if(p[k].l)tou(p[k].l,rt);if(p[k].r)tou(p[k].r,rt);
}
int bt(int l,int r,int o,int fa){
    O=o;int k=l+r>>1,i;nth_element(p+l,p+k,p+r+1,cmp);
    for(i=0;i<2;i++)p[k].mi[i]=p[k].mx[i]=p[k].d[i];to[p[k].id]=k;p[k].fa=fa;
    if(l<k)for(p[k].l=bt(l,k-1,o^1,k),i=0;i<2;i++)Mi(p[k].mi[i],p[p[k].l].mi[i]),Mx(p[k].mx[i],p[p[k].l].mx[i]);
    if(k<r)for(p[k].r=bt(k+1,r,o^1,k),i=0;i<2;i++)Mi(p[k].mi[i],p[p[k].r].mi[i]),Mx(p[k].mx[i],p[p[k].r].mx[i]);
    return tou(k,k),k;
}
void qu(int k){
    if(X1>p[k].mx[0]||X2<p[k].mi[0]||Y1>p[k].mx[1]||Y2<p[k].mi[1])return;
    if(X1<=p[k].mi[0]&&p[k].mx[0]<=X2&&Y1<=p[k].mi[1]&&p[k].mx[1]<=Y2){q1[++t1]=T[k];return;}
    if(X1<=p[k].d[0]&&p[k].d[0]<=X2&&Y1<=p[k].d[1]&&p[k].d[1]<=Y2)q2[++t2]=k;
    if(p[k].l)qu(p[k].l);if(p[k].r)qu(p[k].r);
}
int main(){
    for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d%d",&p[i].d[0],&p[i].d[1],&p[i].z),p[i].id=i,Z[i]=p[i].z;
    for(sort(Z+1,Z+n+1),W=unique(Z+1,Z+n+1)-Z-1,i=1;i<=n;i++)p[i].z=lower_bound(Z+1,Z+W+1,p[i].z)-Z;
    for(rt=bt(1,n,0,0);m--;)
        if(scanf("%s",s),s[0]=='S'){
            scanf("%d%d",&x,&y);x++;y++;
            for(X=to[x],z=p[X].z;X;X=p[X].fa)ins(T[X],1,W,z,-1);
            for(Y=to[y];Y;Y=p[Y].fa)ins(T[Y],1,W,z,1);
            for(Y=to[y],z=p[Y].z;Y;Y=p[Y].fa)ins(T[Y],1,W,z,-1);
            for(X=to[x];X;X=p[X].fa)ins(T[X],1,W,z,1);
            swap(p[to[x]].z,p[to[y]].z);
        }else{
            scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&k);t1=t2=0;
            if(X1>X2)swap(X1,X2);if(Y1>Y2)swap(Y1,Y2);qu(rt);
            for(V=0,i=1;i<=t1;i++)V+=sz[q1[i]];if(V+t2<k){puts("It doesn't exist.");continue;}
            for(l=1,r=W;l<r;){
                md=l+r>>1;V=0;
                for(i=1;i<=t1;i++)V+=sz[L[q1[i]]];
                for(i=1;i<=t2;i++)if(p[q2[i]].z<=md&&p[q2[i]].z>=l)V++;
                if(k<=V)for(r=md,i=1;i<=t1;i++)q1[i]=L[q1[i]];
                else for(l=md+1,k-=V,i=1;i<=t1;i++)q1[i]=R[q1[i]];
            }
            printf("%d\n",Z[l]);
        }
}

飞行计划 每个点拉链,把所有和他入边和出边有关的权值作为一个点。上行边有费用,下行边无费用,两点间再连边。但这样横向边有点多。发现太离谱的话还不如先上后下而不走横向边,优化一下可以大大缩小边数,就能通过了。

航班计划 直观的费用流建图可以按时间建分层图,可这样点数NT不能接受。可以把所有M个条件建分层图,把M个条件拆点,两点间连费用的边,如果两个条件间可以互达或者起点可以到左部或者右部可以到终点就连。点数O(m),边数O(m^2)

特技飞行 普及水题。

世博会 坐标转化后两个坐标独立,然后建一颗主席树求出区间和和权值和并在上面二分即可,懒写了个暴力。

JZPLCM☆ 离线好题啊。。可是没讲

对每个数,拆分成pi^ai的形式,对质数的每个幂记录一个状态表示,贡献为pi

每个询问就是询问一段区间有多少种不同的状态,把贡献乘起来,离线后BIT维护

#include<bits/stdc++.h>
#define M 1000000007
using namespace std;typedef long long LL;map<int,int>mp;
int Q,n,i,j,k,t,o,w,x,id,v[2333333],p[33333];bool f[33333];
struct P{int x,y,z,l;}u[2333333],q[111111];LL c[111111],ans[111111];
bool cmp(P a,P b){return a.y<b.y;}
LL pow(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
void add(int x,int z){if(!x)return;for(;x<=n;x+=x&-x)c[x]=c[x]*z%M;}
LL qu(int x){LL v=1;for(;x;x-=x&-x)v=v*c[x]%M;return v;}
int main(){
	for(scanf("%d%d",&n,&Q),i=2;i<33333;i++){
        if(!f[i]){
			p[++t]=i;
			for(j=1;1ll*j*i<=1e9;)j*=i,mp[j]=++id;
		}
        for(j=1;j<=t&&i*p[j]<33333;j++){
            f[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
 	}
 	for(i=1;i<=n;i++){
 		scanf("%d",&x);c[i]=1;
 		for(j=1;p[j]*p[j]<=x;j++)for(w=1;x%p[j]==0;x/=p[j])w*=p[j],u[++o]=P{i,mp[w],p[j],0};
 		if(x>1){
 			if(!mp[x])mp[x]=++id;
			u[++o]=P{i,mp[x],x,0};
		}
	}
	for(i=1;i<=o;i++)u[i].l=v[u[i].y],v[u[i].y]=u[i].x;
	for(i=1;i<=Q;i++)scanf("%d%d",&q[i].x,&q[i].y),q[i].z=i;
	for(sort(q+1,q+Q+1,cmp),i=j=k=1;i<=n;i++){
		for(;u[j].x==i&&j<=o;j++)add(u[j].x,u[j].z),add(u[j].l,pow(u[j].z,M-2,M));
		for(;q[k].y==i&&k<=Q;k++)ans[q[k].z]=qu(i)*pow(qu(q[k].x-1),M-2,M)%M;
	}
	for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
}
Avatar_small
GG 说:
2016年11月01日 20:17

信号塔:
6 1
999995 999996 999997 999998 999999 1000000
6 -1000000 -1000000
您的答案好像越界了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter