17.10.28&29

28上午

骚猪选讲

28下午

BOZJ 1081 [SCOI2005]超级格雷码

感觉就是一个找规律，然后模拟输出。
半天没找到一个比较简便的模拟方法，
这份代码是学习网上一位大佬的，很巧妙。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int n,m,pow[40];

void print(int y){

	if(y<10) printf("%d",y);

	else printf("%c",y-10+'A');

}

int main(){

	scanf("%d%d",&n,&m);

	pow[0]=1;

	for(int i=1;i<=n;i++) pow[i]=pow[i-1]*m;

	for(int i=0;i<pow[n];i++){

		for(int j=n-1;j>=0;j--){

			int x=i/pow[n-j];

			int y=(i/pow[n-j-1])%m;

			if(x&1) print(m-y-1);

			else print(y);

		}

		printf("\n");

	}

	return 0;

}

BOZJ 1082 [SCOI2005]栅栏

二分+dfs_check（剪枝）。（感觉这个模型不容易看出来，太弱了555）

对木板和木材从小到大排序。
先二分答案mid，然后我们看看是否可以弄出前mid个小木板。
check时，用贪心策略：即尽量用小的木材去造大的木板。
所以从大到小枚举前mid个木板，然后从小到大枚举木材。

至于剪枝，就是记录浪费的木材，即某次裁剪后剩下的木材都不足以造最小的木板，就计入waste，
如果 waste+need(前mid个木板的总长)>tot(木材总长)，就直接return 0；

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int A[55],totA,B[1005],sumB[1005],waste,need;

int n,m;

bool dfs(int p1,int p2){

	if(p1==0) return 1;

	if(waste+need>totA) return 0;

	for(int i=p2;i<=m;i++){

		if(A[i]>=B[p1]){

			A[i]-=B[p1];

			if(A[i]<B[1]) waste+=A[i];

			bool fg=dfs(p1-1,B[p1]==B[p1-1]?p2:1);

			if(A[i]<B[1]) waste-=A[i];

			A[i]+=B[p1];

			if(fg) return 1;

		}

	}

	return 0;

}

int binary(int l,int r){

	int mid,ans=0;

	while(l<=r){

		mid=(l+r)>>1;

		need=sumB[mid];

		if(dfs(mid,1)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	return ans;

}

int main(){

	scanf("%d",&m);

	for(int i=1;i<=m;i++) scanf("%d",&A[i]);

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&B[i]);

	sort(A+1,A+m+1); sort(B+1,B+n+1);

	for(int i=1;i<=m;i++) totA+=A[i];

	for(int i=1;i<=n;i++) sumB[i]=sumB[i-1]+B[i];

	int ans=binary(0,n);

	printf("%d",ans);

	return 0;

}

BOZJ 1083 [SCOI2005]繁忙的都市
最小生成树kruskal。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

struct edge{

	int u,v,w;

	bool operator <(const edge &rtm) const{

		return w<rtm.w;

	}

}e[10005];

int fa[305];

int n,m,need;

int find(int x){

	return x==fa[x]?x:fa[x]=find(fa[x]);

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1;i<=m;i++)

		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

	sort(e+1,e+m+1); need=n-1;

	for(int i=1;i<=m;i++){

		int fu=find(e[i].u),fv=find(e[i].v);

		if(fu==fv) continue;

		fa[fv]=fu; need--;

		if(!need){

			printf("%d %d",n-1,e[i].w);

			break;

		}

	}

	return 0;

}

29下午+晚上

看了看bzoj的10月月赛题（和题解），后两道没看懂、、、
BOZJ 5071 [Lydsy十月月赛]小A的数字

找到 A序列的变化规律，即每次操作使得A的前缀序列中的相邻两个元素交换位置。
代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll sumA[100005],sumB[100005];

int main(){

	int T,n;

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		for(int i=1;i<=n;i++) scanf("%lld",&sumA[i]),sumA[i]+=sumA[i-1];

		for(int i=1;i<=n;i++) scanf("%lld",&sumB[i]),sumB[i]+=sumB[i-1];

		sort(sumA+1,sumA+n+1);

		sort(sumB+1,sumB+n+1);

		for(int i=1;i<=n+1;i++){

			if(i==n+1) printf("YES\n");

			if(sumA[i]!=sumB[i]){

				printf("NO\n");

				break;

			}

		}

	}

	return 0;

}

BOZJ 5072 [Lydsy十月月赛]小A的树

很扯的树形dp。
看官方题解吧（感觉70%数据的题解有毒，怎么搞出的n^3?）
然后这份代码学习网上的一位大佬的。
在dp转移时，要多开两个数组防止用到本次转移的dp结果，
（当然也可以逆向枚举，但是因为for循环大了一点，会超时、、、）

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

struct edge{

	int to,next;

}e[5005*2];

int head[5005],color[5005];

int dmin[5005][5005],dmax[5005][5005],amin[5005],amax[5005],siz[5005],dn[5005],dx[5005];

int n,q,ent;

void read(int &x){

	static int f; static char ch;

	x=0; f=1; ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}

	while('0'<=ch&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}

	x=x*f;

}

void add(int u,int v){

	e[ent]=(edge){v,head[u]};

	head[u]=ent++;

}

void dp(int u,int fa){

	if(color[u]) dmax[u][1]=dmin[u][1]=1;

	else dmax[u][1]=dmin[u][1]=0;

	siz[u]=1;

	for(int i=head[u];i;i=e[i].next){

		int v=e[i].to;

		if(v==fa) continue;

		dp(v,u);

		memcpy(dx,dmax[u],sizeof(dmax[u])),memcpy(dn,dmin[u],sizeof(dmin[u]));

        for(int j=1;j<=siz[u];j++)

			for(int k=1;k<=siz[v];k++){

            	dx[j+k]=max(dx[j+k],dmax[u][j]+dmax[v][k]);

            	dn[j+k]=min(dn[j+k],dmin[u][j]+dmin[v][k]);

        	}

        siz[u]+=siz[v];

        for(int j=1;j<=siz[u];j++)

			dmax[u][j]=dx[j],dmin[u][j]=dn[j];

	}

	for(int i=1;i<=siz[u];i++){

		amax[i]=max(amax[i],dmax[u][i]);

		amin[i]=min(amin[i],dmin[u][i]);

	}

}

int main(){

	int T; read(T);

	while(T--){

		memset(dmin,0x3f,sizeof(dmin));

		memset(amin,0x3f,sizeof(amin));

		memset(dmax,0,sizeof(dmax));

		memset(amax,0,sizeof(amax));

		memset(head,0,sizeof(head));

		ent=2;

		read(n); read(q);

		for(int i=1,u,v;i<n;i++){

			read(u); read(v);

			add(u,v); add(v,u);

		}

		for(int i=1;i<=n;i++) read(color[i]);

		dp(1,0);

		for(int i=1,x,y;i<=q;i++){

			scanf("%d%d",&x,&y);

			if(amin[x]<=y&&y<=amax[x]) puts("YES");

			else puts("NO");

		}

		printf("\n");

	}

	return 0;

}

BOZJ 5073 [Lydsy十月月赛]小A的咒语

dp[i][j] 表示到了A串的第i位，已经选了j段，构成B串的最大长度。
转移，刷表法：
1).A串的下一位不贡献，即不是构成B串的一份子。
   dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
2).A串的i位以后要贡献，即尝试去成为B串的一份子。
   显然，按照贪心策略，此时选的要尽量长，
   令l=lcp(A[i+1],B[dp[i][j]+1]),即A串后缀A[i+1~n-1]与B串后缀B[dp[i][j]+1~m-1]的最长公共前缀。
   dp[i+l][j+1]=max(dp[i+l][j+1],dp[i][j]+l)
   然后就是后缀数组+RMQ表维护lcp

网上还有一种不用后缀数组直接dp的方法，（但我没看懂）。

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 100005

using namespace std;

char s[MAXN*2];

int sa[MAXN*2],rk[MAXN*2],ht[MAXN*2];

int dp[MAXN][105],st[MAXN*2][20],log2[MAXN*2];

void print(int n){

	puts("sa:");

	for(int i=0;i<n;i++) printf("%d ",sa[i]); puts("");

	puts("rk:");

	for(int i=0;i<n;i++) printf("%d ",rk[i]); puts("");

	puts("ht:");

	for(int i=0;i<n;i++) printf("%d ",ht[i]); puts("");

}

bool cmp(int *y,int len,int k,int p1,int p2){

	int a=y[p1],b=y[p2];

	int aa=p1+k<len?y[p1+k]:-1,bb=p2+k<len?y[p2+k]:-1;

	return a==b&&aa==bb;

}

void build(int n,int m){

	static int wa[MAXN*2],wb[MAXN*2],c[MAXN*2],*x,*y,p;

	x=wa; y=wb;

	for(int i=0;i<m;i++) c[i]=0;

	for(int i=0;i<n;i++) c[x[i]=s[i]]++;

	for(int i=1;i<m;i++) c[i]+=c[i-1];

	for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;

	for(int k=1;k<n;k<<=1){

		p=0;

		for(int i=n-k;i<n;i++) y[p++]=i;

		for(int i=0;i<n;i++) if(sa[i]-k>=0) y[p++]=sa[i]-k;

		for(int i=0;i<m;i++) c[i]=0;

		for(int i=0;i<n;i++) c[x[y[i]]]++;

		for(int i=1;i<m;i++) c[i]+=c[i-1];

		for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];

		m=1; swap(x,y); x[sa[0]]=0;

		for(int i=1;i<n;i++)

			x[sa[i]]=cmp(y,n,k,sa[i-1],sa[i])?m-1:m++;

		if(m>=n) break;

	}

	for(int i=0;i<n;i++) rk[sa[i]]=i;

	int h=0;

	for(int i=0,j;i<n;i++){

		if(h) h--;

		if(rk[i]!=0){

			j=sa[rk[i]-1];

			while(i+h<n&&j+h<n&&s[i+h]==s[j+h]) h++;

		}

		ht[rk[i]]=h;

	}

	for(int i=1;i<n;i++) st[i][0]=ht[i];

	for(int k=1;(1<<k)<n;k++)

		for(int i=1<<k;i<n;i++)

			st[i][k]=min(st[i-(1<<(k-1))][k-1],st[i][k-1]);

}

int lcp(int i,int j){

	i=rk[i]; j=rk[j];

	if(i>j) swap(i,j); i++;

	int k=log2[j-i+1];

	return min(st[i+(1<<k)-1][k],st[j][k]);

}

int main(){

	log2[1]=0;

	for(int i=2;i<200000;i++) log2[i]=log2[i>>1]+1;

	int T; scanf("%d",&T);

	while(T--){

		int n,m,x; bool fg;

		memset(dp,0,sizeof(dp));

		scanf("%d%d%d",&n,&m,&x);

		scanf("%s",s); s[n]='%';

		scanf("%s",s+n+1); fg=0;

		build(n+m+1,301);

		for(int i=-1;i<n;i++)

			for(int j=0;j<=min(i+1,x);j++){

				int d=i>=0?dp[i][j]:0;

				if(d==m) fg=1;

				dp[i+1][j]=max(dp[i+1][j],d);

				int l=(i+1<n&&n+1+d<n+m+1)?lcp(i+1,n+1+d):0;

				if(l==0) continue;

				dp[i+l][j+1]=max(dp[i+l][j+1],d+l);

			}

		if(fg) printf("YES\n");

		else printf("NO\n");

	}

	return 0;

}

BOZJ 5074 [Lydsy十月月赛]小B的数字

假设B序列为 b1,b2,b3.......
那同时也可以表示为 2^k1,2^k2,3^k3......
所以 x=2^(k1+k2+k3+......),令ak==k1+k2+k3+......
要使得每一个bi^ai(==2^(ki*ai))都能被x整除，
即需要满足(ki*ai)>=ak
所以列出不等式:
     k1*a1>=ak
     k2*a2>=ak
     k3*a3>=ak
     .........
把左边的a移动到右侧
     k1>=ak/a1
     k2>=ak/a2
     k3>=ak/a3
     .........
再把所有式子相加得：
     ak>=ak/a1+ak/a2+ak/a3+......
即 1>=1/a1+1/a2+1/a3+......
所以只要判断这个不等式是否满足就好了。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const double eps=1e-8;

int main(){

	int T; scanf("%d",&T);

	while(T--){

		double sum=0; int n;

		scanf("%d",&n);

		for(int i=1,a;i<=n;i++)

			scanf("%d",&a),sum+=1.0/a;

		if(sum<=1+eps) printf("YES\n");

		else printf("NO\n");

	}

	return 0;

}

相关文章