欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2019 蓝桥杯省赛 B 组模拟赛(一)

程序员文章站 2022-04-22 23:49:53
传送门D. 结果填空:马的管辖爆搜,总的状态只有2252^{25}225个,判断每个状态是否成立。#include#include#include#includeusing namespace std;typedef long long ll;#define rint register int const int N=200010;#define fi first...

传送门

D. 结果填空:马的管辖
爆搜,总的状态只有 2 25 2^{25} 225个,判断每个状态是否成立。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rint register int 
const int N=200010;
#define fi first
#define se second
bool st[6][6],a[6][6];
int d[8][2]={-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1};
int d1[4][2]={0,1,1,0,0,-1,-1,0};
inline bool check()
{
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			a[i][j]=st[i][j];
	for(register int i=1;i<=5;i++)
	{
		for(register int j=1;j<=5;j++)
		{
			if(st[i][j]) 
				for(rint k=0;k<8;++k)
				{
					int dx=i+d[k][0],dy=j+d[k][1];
					if(dx>0&&dx<6&&dy>0&&dy<6&&!a[dx][dy])
					{
						if(!st[i+d1[k/2][0]][j+d1[k/2][1]]) a[dx][dy]=1;//蹩马脚,d1的顺序与d数组的顺序有关 ,每次只能动一只马,所以得是st数组为0!!!
					}
				}
		}
	}
	for(register int i=1;i<=5;++i)
		for(register int j=1;j<=5;++j)
			if(!a[i][j]) return 0;
	return 1;
}
int ans=0,res=10000000;
void dfs(int x,int y)
{
	if(x==6)
	{
		int num=0;
		for(register int i=1;i<=5;++i)
		{
			for(register int j=1;j<=5;j++)
				num+=(st[i][j]==1); 
		}
		if(num<=res&&check())
		{
			if(num==res) ans++;
			else if(num<res)
			{
			 	res=num;ans=1;
			 	cout<<' '<<num<<endl<<endl;
			}
			for(register int i=1;i<=5;++i)
			{
				for(register int j=1;j<=5;j++)
					printf("%d",st[i][j]);
				puts("");
			}
			puts("");
		}
		return ;
	}
	if(y==5) dfs(x+1,1);
	else dfs(x,y+1);
	st[x][y]=1;
	if(y==5) dfs(x+1,1);
	else dfs(x,y+1);
	st[x][y]=0;
}

int main()
{
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}

F. 程序设计:找质数
线性筛都记错了。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000010;
#define fi first
#define se second
int t,n,pri[N],cnt;
bool st[N];
inline void init()
{
	for(register int i=2;i<N;++i)
	{
		if(!st[i])
			pri[cnt++]=i;
		for(register int j=0;pri[j]<=(N-1)/i;++j)//
		{
			st[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	return ;
}
int main()
{
	init();
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(register int i=0;i<cnt;++i)
		{
			int k=lower_bound(pri,pri+cnt,n-pri[i])-pri;
			if(pri[k]==n-pri[i])
			{
				printf("%d %d",pri[i],pri[k]);
				break;
			}
		}
		if(t) puts("");
	}
	return 0;
}

G. 程序设计:后缀字符串
map的增删查改的复杂度都是log(n),完全没问题的,还hash个锤子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010,M=1000010;
const int p=233,mod=999983;
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
int t,n,h[N];
string s[N];
map<string,int> cnt;
int main()
{
	cin>>n;
	for(register int i=1;i<=n;++i) cin>>s[i];
	for(register int i=1;i<=n;++i)
	{
		int hash=0;
		for(register int j=s[i].size()-1;j>=0;--j)
		    cnt[s[i].substr(j)]++;
	}
	for(register int i=1;i<=n;++i)
	{
		printf("%d",cnt[s[i]]);
		if(i<n) puts("");
	}
	return 0;
}

H. 程序设计:轻重搭配
对于没被匹配的数a[i],找小于等于它二分之一的数去匹配,如果a[i]已经与a[k]匹配过但还存在a[j]*2<=a[i],那么要使匹配数最大化就要让a[i]匹配a[j],不浪费每一个大数,而且a[k[一定比a[i]大,就让他去匹配比a[j]小的下一个数(如果存在的话)(这四个数的匹配方式可以变,但是一定匹配两对)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const int N=500010,M=1000010;
const int p=233,mod=999983;
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
int n,a[N];
bool st[N];

int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i) scanf("%d",a+i);
	sort(a+1,a+n+1);
    int num=0;
	for(register int i=n,j=n-1;i>0;--i)
	{
		while(j>0&&(a[j]*2>a[i])) j--;
        if(j>0)
		{
			st[j--]=1;
			num++;
		}
		if(st[i]==1&&j>0)
		{
			st[j--]=1;
			num++;
		}
	}
    num=min(num,n/2);
	printf("%d",n-num);
	return 0;
}

I. 程序设计:抠图
从边缘的大于0的点出发将大于0的连通块全部染成0即可,因为矩形不相邻不相交所以从边缘开始是没问题的,矩形内部的点也不会被改。
ps:只有两种颜色,那不应该是01两种数字嘛。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
#define  rint register int
const int N=510,M=1000010;
const int p=233,mod=999983;
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
int n,m,t;
int col[N][N];
int d[4][2]={0,1,1,0,0,-1,-1,0};
void dfs(int x,int y)
{
	col[x][y]=0;
	for(rint i=0;i<4;++i)
	{
		int dx=x+d[i][0],dy=y+d[i][1];
		if(dx>0&&dx<=n&&dy>0&&dy<=m&&col[dx][dy]>=1) dfs(dx,dy);
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(col,0,sizeof col);
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;j++) scanf("%d",&col[i][j]);
		for(int i=1;i<=m;++i)
		{
			if(col[1][i]>=1) dfs(1,i);
			if(col[n][i]>=1) dfs(n,i);
		}
		for(int i=1;i<=n;++i)
		{
			if(col[i][1]>=1) dfs(i,1);
			if(col[i][m]>=1) dfs(i,m);
		}
		for(int i=1;i<=n;++i)
		{
            printf("%d",col[i][1]);
			for(int j=2;j<=m;++j)
				printf(" %d",col[i][j]);
			puts("");
		}
	}
	return 0;
}

J. 程序设计:蒜厂年会
环行序列的常规操作拆成2n的序列,在求前缀和,问题就是对于点i求sum[i]-sum[j]的最大值,i确定,找sum[j]的最小值,i-n <= j < i,单调队列模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
#define  rint register int
const int N=200010,M=1000010;
const int p=233,mod=999983;
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
int n,m,t;
int a[N];
ll sum[N];
int q[N],l,r;

int main()
{
	scanf("%d",&n);
	for(rint i=1;i<=n;++i) scanf("%d",a+i),a[i+n]=a[i];
	//n<<=1;
	for(rint i=1;i<=2*n;++i) sum[i]=sum[i-1]+a[i];
	ll ans=-1e18;
	l=r=1;
	for(rint i=1;i<=2*n;++i)
	{
		while(l<r&&q[l]<i-n) l++;
		if(l<r) ans=max(ans,sum[i]-sum[q[l]]);
		while(l<r&&sum[i]<=sum[q[r-1]])
			 r--;
		q[r++]=i;
	}
	printf("%lld",ans);
	return 0;
}

本文地址:https://blog.csdn.net/qq_45288870/article/details/109005061