POI2002

orz hhw posted @ 2017年11月22日 23:01 in 做题记录 with tags 解题报告 POI , 132 阅读

T1 火车线路 超级大水题,直接线段树就行了

#include<cstdio>
#include<algorithm>
using namespace std;
int n,s,m,x,y,z,mv[255555],cv[255555];
int ask(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return mv[k];
	int mid=l+r>>1,now=0;
	if(x<=mid)now=max(now,ask(k<<1,l,mid,x,y));
	if(y>mid)now=max(now,ask(k<<1|1,mid+1,r,x,y));
	return now+cv[k];
}
void add(int k,int l,int r,int x,int y,int z){
	if(x<=l&&r<=y){mv[k]+=z,cv[k]+=z;return;}
	int mid=l+r>>1;
	if(x<=mid)add(k<<1,l,mid,x,y,z);
	if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
	mv[k]=max(mv[k<<1],mv[k<<1|1])+cv[k];
}
int main(){
	for(scanf("%d%d%d",&n,&s,&m);m--;){
		scanf("%d%d%d",&x,&y,&z);y--;
		if(ask(1,1,n,x,y)+z<=s)add(1,1,n,x,y,z),puts("T");else puts("N");
	}
}

T2 商务旅行 傻逼题,直接把一道树剖拉下来了,其实直接模拟说不定都能过。。

#include<cstdio>
#include<algorithm>
#define N 33333
using namespace std;
int n,m,i,x,y,tot,sz,ans,a[N],fir[N],zs[N],fa[N],h[N],pos[N],bl[N],la[N<<1],ne[N<<1];bool v[N];
void insert(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
    zs[x]=1;v[x]=1;
    for(int i=fir[x];i;i=ne[i])if(!v[y=la[i]]){
        fa[y]=x;h[y]=h[x]+1;
        dfs(y);zs[x]+=zs[y];
    }
}
void dfs2(int x,int f){
    int now=0;pos[x]=++sz;bl[x]=f;
    for(int i=fir[x];i;i=ne[i])if(zs[y=la[i]]>zs[now]&&h[x]<h[y])now=y;
    if(!now)return;dfs2(now,f);
    for(int i=fir[x];i;i=ne[i])if(h[x]<h[y=la[i]]&&now!=y)dfs2(y,y);
}
void queryin(int x,int y){
    for(;bl[x]!=bl[y];x=fa[bl[x]]){
        if(h[bl[x]]<h[bl[y]])swap(x,y);
		ans+=pos[x]-pos[bl[x]]+1;
    }
    if(pos[x]>pos[y])swap(x,y);ans+=pos[y]-pos[x];
}
int main(){
    for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),insert(x,y),insert(y,x);
    dfs(1);dfs2(1,1);
    for(scanf("%d",&m),a[0]=i=1;i<=m;i++)scanf("%d",&a[i]),queryin(a[i-1],a[i]);
    printf("%d",ans);
}

T3 超级马 如果能到达(1,0)(-1,0)(0,1)(0,-1)四个点就可以到达全图了,只要宽搜一遍这四个点可以到达就可以了,宽搜的范围可以定在[-100,100],这样正好可以卡过去。。

#include<cstdio>
#include<cstring>
int T,n,i,x,y,h,t,a[110],b[110];bool v[222][222];
struct P{int x,y;}q[44444];
int main(){
	for(scanf("%d",&T);T--;){
		for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
		for(memset(v,0,sizeof(v)),h=0,q[t=1]=P{100,100},v[100][100]=1;h^t;){
			x=q[++h].x;y=q[h].y;
			for(i=1;i<=n;i++){
				if(x+a[i]<=200&&x+a[i]>=0&&y+b[i]<=200&&y+b[i]>=0)if(!v[x+a[i]][y+b[i]]){
					v[x+a[i]][y+b[i]]=1;
					q[++t]=P{x+a[i],y+b[i]};
				}
			}
		}
		puts(v[100][99]&&v[100][101]&&v[99][100]&&v[101][100]?"TAK":"NIE");
	}
}

T4 敌对球迷 直接剪下来单调扫一遍就行了

#include<cstdio>
#include<algorithm>
#define N 50500
int i,j,n,a[N];long long sum[N],ans;
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	for(i=n+1;i<=n*2;i++)a[i]=a[i-n],sum[i]=sum[i-1]+a[i];
	for(i=1;i<=2*n;i++){
		for(;(sum[i]-sum[j])*2>sum[n];j++);
		ans=std::max(ans,sum[i]-sum[j]);
	}
	printf("%lld",ans);
}

T5 绝缘体 又一道傻逼题,排序后扫一遍就行啦

#include<cstdio>
#include<algorithm>
int n,i,ans,a[100100];
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i];
	for(std::sort(a+1,a+n+1),i=1;i<=n>>1;i++)ans+=a[n-i+1]-a[i];
	printf("%d",ans);
}

T6 最大的园地 悬线法裸题,但是用单调栈更方便,很明显最优的答案在高度和宽度上一定是单调的,对于每个点先算出它往上最多能到哪里,然后弹栈,再把该点压进栈,每次弹出时统计答案,就能得到最优答案

#include<cstdio>
#include<algorithm>
#define N 2222
using namespace std;
int n,i,j,x,t,ans,q[N],h[N],st[N];
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			scanf("%d",&x);if(x)h[j]=0;else h[j]++;q[t+1]=0;
			for(;st[t]>h[j]&&t;t--)ans=max(ans,(j-q[t])*st[t]);
			if(st[t]!=h[j]){st[++t]=h[j];if(!q[t])q[t]=j;}
		}
		for(;t;t--)ans=max(ans,(n-q[t]+1)*st[t]);
	}
	printf("%d",ans);
}

T7 出圈游戏 一道裸的中国剩余定理,可是直接套模板似乎不太资磁。。

要把所有形如$x^p$的项取出来进行中国剩余定理,然后对剩下的项进行判定,这样才能得到正确的答案

#include<cstdio>
using namespace std;
int n,i,j,u,pp,now,la,a[22],sum,d,x,y,ans;bool v[22];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void exgcd(int a,int b,int&x,int&y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
}
int main(){
	for(scanf("%d",&n),i=sum=1;i<=n;i++)scanf("%d",&a[i]),sum/=gcd(sum,i),sum*=i;
	for(la=i=1;i<=n;i++){
		for(j=1;j<=n;j++)if(a[j]==i)u=j;
		for(now=1,j=la;j!=u;j=j%n+1)if(!v[j])now++;
		d=sum/(n-i+1);exgcd(d,n-i+1,x,y);
		if(now==n-i+1)now=0;
		ans=(ans+d*x*now)%sum;
		v[u]=1;la=u;
	}
	while(ans<=0)ans+=sum;
	printf("%d",ans);
}
#include<cstdio>
using namespace std;
int n,i,j,u,pp,now,la,a[22],b[22],sum,d,x,y,ans,p[]={0,2,3,5,7,11,13,17,19};bool v[22];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void exgcd(int a,int b,int&x,int&y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
}
int main(){
	for(scanf("%d",&n),i=sum=1;i<=n;i++)scanf("%d",&a[i]),sum/=gcd(sum,i),sum*=i;
	for(la=i=1;i<=n;i++){
		for(j=1;j<=n;j++)if(a[j]==i)u=j;
		for(now=1,j=la;j!=u;j=j%n+1)if(!v[j])now++;
		if(now==n-i+1)now=0;
		b[n-i+1]=now;v[u]=1;la=u;
	}
	for(i=1;p[i]<=n;i++){
		for(j=p[i];j*p[i]<=n;j*=p[i]);
		d=sum/j;exgcd(d,j,x,y);
		ans=(ans+d*x*b[j])%sum;
	}
	while(ans<=0)ans+=sum;
	for(i=1;i<=n;i++)if(ans%i!=b[i])return puts("NIE"),0;
	printf("%d",ans);
}

T8 滑雪胜地 这题是求小于等于一个长度的最长路,由于这个长度比较小,可以考虑dp,用$f[i][j]$表示用了$i$的费用是否能走到$j$,然后直接扫一遍就可以得到正确答案了

#include<cstdio>
#define N 1100
#define M 5100
int n,u,m,x,y,s,h,t,tot,i,j,q[N],fir[N],la[M],ne[M],a[N],b[N],c[N];bool v[N<<1][N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
	for(scanf("%d%d%d",&n,&u,&m);m--;)scanf("%d%d",&x,&y),ins(x,y);
	for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(scanf("%d%d",&x,&s),v[0][q[t=1]=x]=1;h^t;)
		for(i=fir[x=q[++h]];i;i=ne[i])if(!v[0][la[i]])v[0][q[++t]=la[i]]=1;
	for(j=1;j<=s;j++){
		for(i=1;i<=m;i++)if(j>=c[i])v[j][b[i]]|=v[j-c[i]][a[i]];
		for(h=t=0,i=1;i<=n;i++)if(v[j][i])q[++t]=i;
		for(;h^t;)for(i=fir[x=q[++h]];i;i=ne[i])if(!v[j][la[i]])v[j][q[++t]=la[i]]=1;
	}
	for(i=s;i;i--)for(j=1;j<=u;j++)if(v[i][j])return printf("%d",s-i),0;
}

T9 协议 统计方案后高精度取对数,但这东西似乎挺难的,可以取出最高位然后把剩下答案的贡献暴力算,但这样精度有点问题,会WA一个点,把参数调小一点就能A了。。

#include<cstdio>
#include<cmath>
#define M 32767
int k,n,m,l,i,w,sum,ans[30],f[110][30];double v,q;
void mul(int *a,int b,int *c){
	for(int i=1;i<=w;i++)c[i]+=a[i]*b,c[i+1]+=c[i]>>15,c[i]&=M;
	if(c[w+1])w++;
}
void add(int *a,int *b){
	for(int i=1;i<=w;i++)b[i]+=a[i],b[i+1]+=b[i]>>15,b[i]&=M;
	if(b[w+1])w++;
}
void del(int *a,int *b){
	for(int i=1;i<=w;i++){
		b[i]-=a[i];
		if(b[i]<0)b[i]+=M,b[i+1]--;
	}
	for(;!b[w];w--);
}
int main(){
	scanf("%d%d%d%d",&k,&n,&m,&l);l--;ans[w=1]=f[1][1]=k;
	for(i=2;i<=m;i++){
		mul(ans,k-1,f[i]);add(f[i],ans);
		if(i>l)del(f[i-l],ans);
	}
	for(i=14;i>=0;i--)if(ans[w]>>i)break;
	for(sum=i+w*15-15,v=1;i>=0;i--,v/=2)if(ans[w]>>i&1)q+=v;
	for(;--w;)for(i=14;i>=0&&v>0.05;i--,v/=2)if(ans[w-1]>>i&1)q+=v;
	printf("%d\n",sum*(n/m)+(int)(log2(q)*(n/m)));
}

T10 滑雪者 求最小可行流,先建出图来,统计出最多要走多少次,再减去最大流的值即可求出最小可行流

#include<cstdio>
#define N 5200
#define M 1001000
#define inf 1e9
int n,m,x,i,u,s,t,now,tot,ans,tmp,du[N],fir[N],cur[N],nb[N],d[N],pre[N],va[M],la[M],ne[M];
void ins(int x,int y,int z){
	la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;
	la[++tot]=x;va[tot]=0;ne[tot]=fir[y];fir[y]=tot;
}
void ISAP(){
	for(i=1;i<=t;i++)cur[i]=fir[i];
	u=s;nb[0]=t;
	while(d[s]<t){
		if(u==t){
			now=inf;
			for(i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
			for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=now,va[cur[i]^1]+=now;
			ans-=now;
		}
		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],tmp=t;i;i=ne[i])if(d[la[i]]<tmp&&va[i])tmp=d[la[i]];
			++nb[d[u]=tmp+1];
			if(u!=s)u=pre[u];
		}
	}
}
int main(){
	for(scanf("%d",&n),tot=1,s=n+1,t=s+1,i=1;i<n;i++)
		for(scanf("%d",&m),du[i]+=m;m--;)scanf("%d",&x),ins(i,x,inf),du[x]--;
	for(i=1;i<n;i++)if(du[i]>0)ins(i,t,du[i]),ans+=du[i];else ins(s,i,-du[i]);
	ISAP();printf("%d",ans);
}

T11 B-Smooth数 直接枚举素数后暴力,求出可行的$[l,r]$区间,每次统计这个区间内的素数个数就可以得到正确答案了,速度还是很快的

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,m,k,i,j,sz,ans,a[N],b[N],p[N];bool v[N];
void dfs(int x,int y){
	int l=(n-1)/x+1,r=(n+m)/x;
	for(int i=y;i<=sz&&p[i]<=r/p[i];i++)dfs(x*p[i],i);
	l=max(l,p[y]);l=min(l,k+1);r=min(r,k+1);
	if(b[l]<a[r])ans+=a[r]-b[l];
}
int main(){
	for(scanf("%d%d%d",&n,&m,&k),p[0]=1e9,b[1]=1,i=2;i<=k;i++){
		b[i]=sz;if(!v[i])p[++sz]=i;a[i]=sz;
		for(j=1;j<=sz&&p[j]*i<=k&&i%p[j-1];j++)v[i*p[j]]=1;
	}a[k+1]=b[k+1]=sz;
	dfs(1,1);printf("%d",ans+(n==1));
}

T12 括号 黈力出的题就是大,考的时候根本不会,直接写了个60的暴力

首先要建出一个括号树,向右走奇数次就是-,偶数次就是+,考虑dp,用$dp[i][j]$表示前$i$个已经归位,最右边的一条链长度为$j$时的方案数

则当(j&1)==(s=='-')时$dp[i][j]=\sum dp[i-1][(j-1)~(i-1)]$,表示在$j$这个位置插入该点的方案数,推导去看题解吧~

#include<cstdio>
#define M 1000000000
int n,i,j,e,v,u,ans,f[2][5010];char s[9];
int main(){
	scanf("%d%s",&n,s);n--;if(s[0]=='-')f[0][0]=1;
	for(e=i=1;i<n;i++,e^=1){
		for(scanf("%s",s),u=s[0]=='+',v=0,j=i;j>=0;j--){
			if(j)v=(v+f[!e][j-1])%M;
			if(u^(j&1))f[e][j]=0;else f[e][j]=v;
		}
	}
	for(i=n;i>=0;i--)ans=(ans+f[!e][i])%M;
	printf("%d",ans);
}