POI2000

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

T1 迷宫的墙 暴力从后往前判断是否存在相同的即可,相同的话就更新答案

#include<cstdio>
#include<cstring>
#include<map>
#define N 6010
using namespace std;
int n,i,j,ans,w[N],c[N],a[N][3];char s[9];
long long now;map<long long,int>mp;
int main(){
	scanf("%d",&n);w[n]=n;ans=n;
	for(i=1;i<n;i++){
		scanf("%s",s);w[i]=i;
		if(s[0]=='C')c[i]=1;else if(s[0]=='Z')c[i]=2;else c[i]=3;
		for(j=0;j<3;j++)scanf("%d",&a[i][j]);
	}
	for(i=n-1;i;i--){
		now=c[i];
		for(j=0;j<3;j++)a[i][j]=w[a[i][j]],now=now*n+a[i][j]-1;
		if(mp[now])w[i]=mp[now],ans--;else mp[now]=i;
	}
	printf("%d",ans);
}

T2 建造酿酒厂 首先向两边送的分割点肯定是单调的,于是可以$O(n)$转一圈,每次得到这个分割点,然后通过前缀和快速得到答案,为了方便可以把一个环剪成$2*n$的链

#include<cstdio>
#include<algorithm>
#define N 20010
using namespace std;
int n,i,j,x,y,z[N],d[N];
long long f[N],g[N],s[N],now,ans=1e18;
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&z[i],&d[i]),f[i]=f[i-1]+z[i],g[i]=g[i-1]+d[i],s[i]=s[i-1]+z[i]*g[i-1];
	for(i=n+1;i<=n*2;i++)z[i]=z[i-n],d[i]=d[i-n],f[i]=f[i-1]+z[i],g[i]=g[i-1]+d[i],s[i]=s[i-1]+z[i]*g[i-1];
	for(i=j=1;i<=n;i++){
		for(;(g[j-1]-g[i-1])<=(g[n]>>1)&&j<=n*2;j++);
		now=s[j-1]-s[i]+g[i-1]*f[i]-(f[j-1]-f[i])*g[i-1]+(g[i-1]+g[n])*(f[n]-f[j-1])-s[n]+s[j-1]-s[i];
		if(now<ans)ans=now;
	}
	printf("%lld",ans);
}

T3 病毒 AC自动机弄出所有danger节点后判一遍是否有环即可

#include<cstdio>
#define N 33333
int n,i,j,c,x,y,k,h,t,cnt,son[N][2],fail[N],q[N],v[N];
bool dg[N],flag;char s[N];
void dfs(int x){
	if(dg[x]||flag)return;v[x]=1;
	for(int i=0;i<2;i++){
		int y=son[x][i];
		if(v[y]==1){flag=1;return;}
		if(!v[y])dfs(y);
		if(flag)return;
	}
	v[x]=2;
}
int main(){
	for(scanf("%d",&n),cnt=son[0][0]=son[0][1]=1;n--;dg[x]=1){
		scanf("%s",s);x=1;
		for(i=0;s[i];x=son[x][c],i++)if(!son[x][c=s[i]-'0'])son[x][c]=++cnt;
	}
	for(q[t=1]=1;h<t;)
		for(x=q[++h],i=0;i<2;i++){
			y=son[x][i];
			if(!y){son[x][i]=son[fail[x]][i];continue;}
			for(k=fail[x];!son[k][i];k=fail[k]);
			fail[y]=son[k][i];
			dg[y]|=dg[fail[y]];
			q[++t]=y;
		}
	dfs(1);flag?puts("TAK"):puts("NIE");
}

T4 滑雪 就是一个小小的网络流,由于边的流量只有1,可以直接DFS解决。。

#include<cstdio>
#include<cstring>
#define N 10010
#define M 200020
int n,i,j,k,x,tot,ans,fir[N],pre[N],va[M],la[M],ne[M];bool v[N];
void ins(int x,int y){
	la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=1;
	la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;va[tot]=0;
}
bool dfs(int x){
	v[x]=1;if(x==n)return 1;
	for(int i=fir[x];i;i=ne[i])
		if(va[i]&&!v[la[i]]){
			pre[la[i]]=i;
			if(dfs(la[i]))return 1;
		}
	return 0;
}
int main(){
	scanf("%d",&n);tot=1;
	for(i=1;i<n;i++){
		scanf("%d",&k);ins(i,i+n);
		for(j=1;j<=k;j++)scanf("%d",&x),ins(i+n,x);
	}
	for(;dfs(n+1);ans++){
		for(i=n;i!=n+1;i=la[pre[i]^1])va[pre[i]]^=1,va[pre[i]^1]^=1;
		memset(v,0,sizeof(v));
	}printf("%d",ans);
}

T5 条纹 直接暴力求SG函数就可以了

#include<cstdio>
#include<cstring>
int a,b,c,i,j,x,Q,sg[1111],hash[1111];
int main(){
	scanf("%d%d%d",&a,&b,&c);
	for(i=1;i<=1000;i++){
		memset(hash,0,sizeof(hash));
		if(i>=a)for(j=0;j<=i-a;j++)hash[sg[j]^sg[i-a-j]]=1;
		if(i>=b)for(j=0;j<=i-b;j++)hash[sg[j]^sg[i-b-j]]=1;
		if(i>=c)for(j=0;j<=i-c;j++)hash[sg[j]^sg[i-c-j]]=1;
		for(j=0;j<=1000;j++)if(!hash[j]){sg[i]=j;break;}
	}
	for(scanf("%d",&Q);Q--;sg[x]?puts("1"):puts("2"))scanf("%d",&x);
}

T6 担保 只要判断一下是否有大于等于两个长官担保即可

#include<cstdio>
#define N 510
int n,i,k,x,tot,f,g[N],v[N],s[N],fir[N],ne[N*N],la[N*N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int z){
	v[x]=z;s[x]++;
	for(int i=fir[x];i;i=ne[i])if(v[la[i]]!=z)dfs(la[i],z);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%d",&g[i]),k=g[i];k--;)scanf("%d",&x),ins(x,i);
	for(i=1;i<=n;i++)if(!g[i])dfs(i,i);
	for(i=1;i<=n;i++)if(g[i]&&s[i]<2)printf("%d\n",i),f=1;
	if(!f)puts("BRAK");
}

T7 同构 首先如果有偶数环肯定是不合法的,因为这样置换会换到自己爆炸,然后奇数环对答案的贡献是$2^{\frac{cnt-1}{2}}$

奇数环之间的贡献是他们的gcd之和,但暴力求可能会T,可以用计数的思想计出每种个数的数量,然后统计贡献时可以在$nlgn$统计出来

#include<cstdio>
#define N 10010
int n,i,j,x,cnt,ans,tot,w,p,a[N],f[N],to[N];bool v[N];
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]);
	for(i=1;i<=n;i++)if(!v[i]){
		for(v[x=i]=1,cnt=1;!v[to[x]];v[x=to[x]]=1)cnt++;
		if(cnt%2==0)return puts("0"),0;
		p+=cnt-1;a[cnt]++;
	}
	for(i=n;i>=1;i--){
        for(tot=a[i],j=i+i;j<=n;j+=i)tot+=a[j],f[i]+=f[j];
        f[i]=tot*tot-f[i];p+=(f[i]-a[i])*i;
    }
    for(p>>=1,ans=1,w=2;p;w=w*w%1000,p>>=1)if(p&1)ans=ans*w%1000;
    printf("%d",ans);
}

T8请不要提交!

T9 代码 递推后再递归找答案就行了

#include<cstdio>
int i,j,n,k,ln,f[21];char s[21];
void dfs(int l,int r,int k){
    int i;for(i=l;i<=r;i++)if(f[i-l]*f[r-i]<=k)k-=f[i-l]*f[r-i];else break;
    s[ln++]=i+'a'-1;if(i>l)dfs(l,i-1,k/f[r-i]);if(i<r)dfs(i+1,r,k%f[r-i]);
}
int main(){
	scanf("%d%d",&n,&k);n--;
	for(f[0]=i=1;i<=k;i++)for(j=0;j<i;j++)f[i]+=f[j]*f[i-j-1];
	dfs(1,k,n);printf("%s",s);
}

T10 气垫船 首先找出出现次数最多的数,然后判断一下是否在一边没有数,有的话n++,然后判断一下出现次数最多的数*2是否小于等于n即可

#include<cstdio>
int T,n,p,s,i,a[1001000];bool f1,f2;char ch;
void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
	for(read(T);T--;){
		read(n);p=f1=f2=0;s=1;
		for(i=1;i<=n;i++){
			read(a[i]);
			if(a[i]==p)s++;else s--;
			if(!s)s++,p=a[i];
		}
		for(s=0,i=1;i<=n;i++)if(a[i]>p)f1=1;else if(a[i]<p)f2=1;else s++;
		if(!f1||!f2)n++;
		s*2<=n?puts("TAK"):puts("NIE");
	}
}

T11 公共串 多串LCM后缀自动机裸题,先对一个串做SAM,然后每个串进去匹配,对于每种状态保留最大值,然后取最大值中的最小值,最后再在每种状态中取最大值

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 222222
using namespace std;
int la,S,i,n,cnt,tmp,p,ans,c,np,q,nq,Q,mn[N],fa[N],step[N],v[N],w[N],cl[N],son[N][26];
char s[N];
void add(int x){
    c=s[x]-'a',p=la,la=np=++cnt;step[np]=step[p]+1;
    for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
    if(!p)fa[np]=S;else{
        q=son[p][c];
        if(step[p]+1==step[q])fa[np]=q;else{
            nq=++cnt;step[nq]=step[p]+1;
            memcpy(son[nq],son[q],sizeof son[q]);
            fa[nq]=fa[q];fa[np]=fa[q]=nq;
            for(;son[p][c]==q;p=fa[p])son[p][c]=nq;
        }
    }
}
int main(){
	scanf("%d",&Q);Q--;
    scanf("%s",s);n=strlen(s);la=S=++cnt;
    for(i=0;i<n;i++)add(i);
    for(i=1;i<=cnt;i++)mn[i]=step[i];
    for(i=1;i<=cnt;i++)v[step[i]]++;
    for(i=1;i<=n;i++)v[i]+=v[i-1];
    for(i=1;i<=cnt;i++)w[v[step[i]]--]=i;
    while(Q--){
    	scanf("%s",s);n=strlen(s);memset(cl,0,sizeof(cl));tmp=0;
        for(p=1,i=0;i<n;i++){
            c=s[i]-'a';
            if(son[p][c])p=son[p][c],tmp++;else{
                while(p&&!son[p][c])p=fa[p];
                if(!p)p=1,tmp=0;else tmp=step[p]+1,p=son[p][c];
            }
            cl[p]=max(cl[p],tmp);
        }
        for(i=cnt;i;i--){
            int t=w[i];
            mn[t]=min(mn[t],cl[t]);
            if(cl[t]&&fa[t])cl[fa[t]]=step[fa[t]];
        }
    }
    for(i=1;i<=cnt;i++)ans=max(ans,mn[i]);
    printf("%d",ans);
}

T12 促销 直接set水过

#include<cstdio>
#include<set>
using namespace std;
multiset<int>st;
int n,k,x;long long ans;
int main(){
	for(scanf("%d",&n);n--;){
		for(scanf("%d",&k);k--;)scanf("%d",&x),st.insert(x);
		ans+=(long long)*--st.end()-*st.begin();
		st.erase(st.begin());st.erase(--st.end());
	}
	printf("%lld",ans);
}

感觉这届好水好无聊啊、、