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