POI1997

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

T2 The Number of Symmetrical Choices 新建源汇点S、T,把字符串建出一张拓扑图连号边,用$f[i][j]$表示方案数,边界条件$f[i][i]=1$,$f[i][la[i]]=(a[i]==a[la[i]])$,然后记忆化搜索就可以解决,时间复杂度$O(L^2)$

#include<cstdio>
#include<cstring>
#define N 999
int n,i,j,l,x,w,to,ot,cnt,a[N],fir[N],la[N],ne[N],fi2[N],n2[N],l2[N],f[N][N],st[2][N],ed[2][N];bool v[N][N];char s[N];
void add(int x,int y){
	la[++to]=y;ne[to]=fir[x];fir[x]=to;
	l2[++ot]=x;n2[ot]=fi2[y];fi2[y]=ot;
}
int get(int x,int y){
	if(v[x][y])return f[x][y];v[x][y]=1;if(a[x]!=a[y])return 0;
	for(int i=fir[x];i;i=ne[i])for(int j=fi2[y];j;j=n2[j])f[x][y]+=get(la[i],l2[j]);
	return f[x][y];
}
int main(){
	for(scanf("%d",&n),cnt=2,w=0;w<2;w++)
		for(i=1;i<=n;ed[w][i++]=cnt+=l,a[cnt]=s[l]-'a'+1)
			for(st[w][i]=cnt+1,scanf("%s",s+1),l=strlen(s+1),j=1;j<l;j++)add(cnt+j,cnt+j+1),a[cnt+j]=s[j]-'a'+1;
	for(i=1;i<n;i++)add(ed[0][i],st[0][i+1]),add(ed[0][i],st[1][i+1]),add(ed[1][i],st[0][i+1]),add(ed[1][i],st[1][i+1]);
	add(1,st[0][1]);add(1,st[1][1]);add(ed[0][n],2);add(ed[1][n],2);
	for(x=1;x<=cnt;x++)for(v[x][x]=f[x][x]=1,i=fir[x];i;i=ne[i])v[x][la[i]]=1,f[x][la[i]]|=(a[la[i]]==a[x]);
	printf("%d\n",get(1,2));
}

T6 gen 用$e[i][j]$表示$ij$可以由那些字母变出,用二进制表示;对于每个字符串,用$f[i][j]$表示$[i,j]$这个区间可能由哪些字符变过来,用二进制表示,这个转移暴力的话需要$26^2n^3$,但可以通过树状数组位运算优化减小常数;然后选取一些$f[i][j]$满足其>>18&1,使得选取数量最小就可以了

#include<cstdio>
#include<cstring>
#define N 103
int n,T,i,j,k,t,e[N][N],f[N][N],h[N];char s[N];
int cal(int U,int y){
	for(t=0;U;U-=U&-U)for(int i=__builtin_ctz(U&-U),V=y;V;V-=V&-V)t|=e[i][__builtin_ctz(V&-V)];
	return t;
}
int main(){
	for(scanf("%d",&n);n--;)scanf("%s",s),e[s[1]-'A'][s[2]-'A']|=1<<(s[0]-'A');
	for(scanf("%d",&T);T--;h[n]<N?printf("%d\n",h[n]):puts("NIE")){
		for(scanf("%s",s+1),n=strlen(s+1),i=n;i;i--)for(f[i][i]=1<<(s[i]-'A'),j=i+1;j<=n;j++)for(f[i][j]=0,k=i;k<j;k++)f[i][j]|=cal(f[i][k],f[k+1][j]);
		for(i=1;i<=n;i++)for(h[i]=N,j=0;j<i;j++)if((f[j+1][i]>>18&1)&&h[j]+1<h[i])h[i]=h[j]+1;
	}
}

T7 Monochromatic Triangles 如果一个三角形不合法,肯定是2+1,枚举一个点的所有出边,把不同的乘起来,然后除以2就是不合法的个数,用合法的个数减就可以了

#include<cstdio>
int n,m,i,x,y,now,du[1010];
int main(){
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&x,&y),du[x]++,du[y]++;
	for(i=1;i<=n;i++)now+=du[i]*(n-du[i]-1);
	printf("%lld",(long long)n*(n-1)*(n-2)/6-now/2);
}

T8 汽油花费 单调队列维护一段油价递增的区间,当前用的油一定是队头,当队尾和队头差超过p时弹队头,并把$c[i]$插入队尾使得队列单调递增

#include<cstdio>
#define N 1001000
int p,n,i,j,h,t,dsum,c[N],d[N],q[N];long long ans;
int main(){
	for(scanf("%d%d",&p,&n),i=1;i<=n;i++)scanf("%d%d",&c[i],&d[i+1]),d[i+1]+=d[i];
	for(q[h=t=1]=1,i=1;i<=n;q[++t]=++i){
		for(j=d[i]+1;j<=d[i+1];j++){
			for(;j-d[q[h]]>p&&h<=t;h++);
			ans+=c[q[h]];
		}
		for(;c[i+1]<=c[q[t]]&&h<=t;t--);
	}
	printf("%lld",ans);
}

还有几道似乎是NOIP的普及组原题啊。。真是醉了