星星博客 »  > 

2021蓝桥杯第二场省赛C/C++B组*

2021蓝桥杯第二场省赛C/C++B组

在这里插入图片描述
这题…
一眼就看出来了答案是1.

在这里插入图片描述
两个数相乘的积最后5位由这两个数的最后5位决定,所以每次乘完就取模保留最后5位防止爆long long。

#include<stdio.h>
#define mod 100000
int main(){
	long long n=2021,ans=1;
	while(n>1){
		ans=ans*n%mod;
		n=n-2;
	}
	printf("%I64d",ans);
	return 0;
} 

答案:59375
在这里插入图片描述
暴力枚举不多说。

#include<stdio.h>
int main(){
	int i,j,cnt=0;
	for(i=1;i<=2021;i++)
	for(j=1;j<=2021;j++)
	if(i*j<=2021)cnt++;
	printf("%d",cnt);
	return 0;
}

答案:15698
在这里插入图片描述

1.看起来像动态规划,其实不需要,这就是高中的隔板法解排列组合方案数;

2.2021分成5个正整数的和,题目可以转化成:有2021个小球排成一排,现在要把这2021个小球分成5堆,问有多少种分发;
解决思路:在2021个小球之间(有2020个位置)挑4个位置出来放隔板把小球隔开(就分成了5堆,被隔开了的就不再是一堆了),显然答案就是C(2020,4)=202020192018*2017/1/2/3/4.

#include<stdio.h>
int main(){
	long long ans=1,i;
	for(i=2020;i>=2017;i--)
	ans*=i;
	for(i=1;i<=4;i++)
	ans/=i;
	printf("%I64d",ans);
	return 0;
}

答案:691677274345

在这里插入图片描述
1.计算每两个点之间的费用:
比较个位,如果不相等就加上各自的个位,相等就跳过,然后这两个数都除10,再比个位…直到两个数都为0;
2.对所有的费用(边的权值)排序;
3.求最小生成树,用并查集按边收录比较简单.

#include<stdio.h>
#include<stdlib.h>
typedef struct{
	int a;
	int b;
	int value;
}Node;
int root[2022];
Node map[2021*2021+1];
int Find(int x){//并查集 
	if(x==root[x])
	return x;
	return root[x]=Find(root[x]);
}
int Value(int a,int b){//计算费用函数 
	int sum=0;
	while(a>0||b>0){
		if(a%10!=b%10)
		sum=sum+a%10+b%10;
		a/=10;
		b/=10;
	}
	return sum;
}
int cmp(const void *a,const void *b){//快排参数-函数指针 
	return (*(Node*)a).value-(*(Node*)b).value;
}
int main(){
	int i,j,k=0,length=2021*2021,sum=0;
	for(i=1;i<=2021;i++)//计算费用 
	for(j=1;j<=2021;j++){
		map[k].a=i;map[k].b=j;
		map[k].value=Value(i,j);
		k++;
	}
	qsort(map,length,sizeof(Node),*cmp);//快速排序 
	for(i=1;i<=2021;i++)//并查集初始化 
	root[i]=i;
	for(i=0,k=0;i<length&&k<2020;i++){
		if(Find(map[i].a)!=Find(map[i].b)){
			root[Find(map[i].a)]=Find(map[i].b);
			k++;
			sum+=map[i].value;
		}
	}
	printf("%d",sum);
	return 0;
}

在这里插入图片描述
暴力暴力。

#include<stdio.h>
int M(int x){
	if((x/1000==x%100/10)&&(x%1000/100+1==x%10))
	return 1;
	return 0;
}
int main(){
	int i,x,cnt=0;
	for(i=1;i<=5;i++){
		scanf("%d",&x);
		cnt+=M(x);
	}
	printf("%d",cnt);
	return 0;
}

在这里插入图片描述
一个个枚举,还是暴力。

#include<stdio.h>
int main(){
	int i,n,cnt=0;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	cnt+=(i*i%n)<<1<n;
	printf("%d",cnt);
	return 0;
}

在这里插入图片描述
1.读完题目,知道了什么是完全平方数,其实计算开方可以开出整数的;
2.如果输入是 n ,不考虑输出的x最小,那么 x = n一定是一个解,因为 n * n一定是一个完全平方数,开方的结果就是 n;
3.题目要 x 的值尽可能小,就是要让最初始的解 x = n除一个数 y ,并且可以除尽,还要满足 n * ( x / y )是一个完全平方数,n * ( x / y ) = ( n / sqrt( y ) ) * ( x / sqrt( y ) ),如果 sqrt ( y )是一个整数且 y 能被 x 的初值 n 整除,就找到了答案,答案就是 n / y;
4.例如输入 n = 8,很明显 x = 8 是一个满足平方数但不是最小的数,即 8 * 8 是一个平方数,因为 8 = 8,需要把右边的 8 除一个数 y (y必须是平方数),取 y = 4,原式 = 8 * ( 8 / 4),然后把 y = 4,分成sqrt(y) * sqrt(y),也就是2 * 2,然后把右边的 分母( 2 * 2 )匀一个2给左边的8作为分母,原式 = ( 8 / 2 ) * ( 8 / 2 ),显然,这两个乘数又是相等的,结果又是一个完全平方数;
5.所以只要从大往小遍历 y ,如果找到了一个 y 使 n / y可以除尽,并且 y 是一个完全平方数,就可以输出答案 n / y了,y 的最大值10E12肯定超时,不妨枚举 sqrt(y),最大值为10E6,复杂度为O(10E6)。

#include<stdio.h>
int main(){
	long long n,i,j,k;
	scanf("%I64d",&n);
	for(i=1E6;i>=1;i--)
	if(n%(i*i)==0)break;
	printf("%I64d",n/i/i);
	return 0;
} 

在这里插入图片描述
在这里插入图片描述
1.模拟:每读入一条任 务就判断能不能处理,能处理就处理,并且把算力回收的时间点放入某个集合,然后遍历时间节点,如果有算力回收就回收对应计算机的算力,然后如果有任务就处理任务,不能处理就输出 -1;
2.这个集合其实就是优先队列,用最小堆实现,是一个完全二叉树,所以堆可以用数组实现。

#include<stdio.h>
#include<stdlib.h>
#define Len 200020
#define Min(a,b) (a>b)?(b):(a)
typedef struct{
	int time;
	int number;
	int res;
}Computer;
int Res[Len];//第 i 台计算机剩余的算力 
Computer queue[Len];//优先队列 
int last=0;
int a[Len],b[Len],c[Len],d[Len];//存任务 
int cmd_p=1;//指向当前的任务的下标 
void Release(int Now_time){//算力回收 
	if(last==0||queue[1].time>Now_time)return;//如果没有算力回收了就退 
	Res[queue[1].number]+=queue[1].res;
	queue[1]=queue[last--];
	queue[last+1].number=queue[last+1].res=queue[last+1].time=0;
	int i=1,min_p,La=last>>1;
	while(i<=La){//维护 
		min_p=i<<1;
		if(queue[min_p+1].time<queue[min_p].time&&min_p+1<=last)
		min_p++;
		if(queue[i].time>queue[min_p].time){
			Computer temp=queue[i];
			queue[i]=queue[min_p];
			queue[min_p]=temp;
			i=min_p;
		}
		else break;
	}
	if(queue[1].time<=Now_time)//如果当前时间节点还有待回收的算力,继续回收 
	Release(Now_time);
}
void Insert(int a,int b,int c,int d){//消耗算力 
	Computer temp;
	temp.number=b;
	temp.res=d;
	temp.time=c+a;
	Res[b]-=d;
	int i,j,k;
	i=++last;
	for(;queue[i/2].time>temp.time;i/=2)
	queue[i]=queue[i/2];
	queue[i]=temp;
}
int main(){
	int n,m,i,j,k;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%d",&Res[i]);
	for(i=1;i<=m;i++)
	scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
	for(i=1;i<=1E9&&cmd_p<=m;i=a[++cmd_p]){
		Release(i);//回收算力 
		if(Res[b[cmd_p]]<d[cmd_p])
		printf("-1\n");
		else{
			printf("%d\n",Res[b[cmd_p]]-d[cmd_p]);
			Insert(a[cmd_p],b[cmd_p],c[cmd_p],d[cmd_p]);
		}
	}
	return 0;
}

在这里插入图片描述
在这里插入图片描述
1.N 小,M 大,一看就是状态压缩,这题就是状态压缩的多重背包;
2.用 1 表示放了马(如 3 = 000011,表示第1,2列放了马,其余不放),相邻列间怎么判断是否冲突:状态A 左移2位与 状态B相与,再右移2位与状态B相与,如果结果都是 0,说明不冲突;
3.判断三列间是否冲突,先判断第1,2列,再判断第2,3列,如果不冲突,继续判断第1,3列,把第一列的状态A左移1位,与第3列状态相与,然后右移…如果都不冲突,说明这三列不冲突;
4.dp[列号 i ] [前 i 列放马的个数(包含第 i 列)] [前一列状态] [当前列状态]。

#include<stdio.h>
#define Mod 1000000007
int cnt[150],dp[105][25][70][70];//dp[列号 i ][前 i 列放马的个数(包含第 i 列)][前一列状态][当前列状态]
int Cnt(int x){//计算x状态里有几个马 
	if(cnt[x]!=0)
	return cnt[x];
	int sum=0,temp=x;
	for(;x>0;x>>=1)
	sum+=(x&1);
	cnt[temp]=sum;
	return sum;
}
int Check1(int a,int b){//相邻两列间检查 
	if((a<<2)&b||(b<<2)&a)
	return 0;//冲突 
	return 1;//不冲突 
}
int Check2(int a,int b,int c){//相邻三列间检查 
	if(Check1(a,b)&&Check1(b,c))
	if(!((a<<1)&c||(c<<1)&a))
	return 1;//不冲突 
	return 0;//冲突 
}
int main(){
	int i,j,k,a,b,c,M,N,K,max;
	scanf("%d %d %d",&N,&M,&K);
	max=(1<<N)-1;//由行数确定每列最大状态
	dp[0][0][0][0]=1;//第 0 列不放马且前 0 列有 0 个马的方案数为 1 
	for(i=1;i<=M+2;i++)//枚举列 
	for(k=0;k<=K;k++)//枚举马的数量 
	for(a=0;a<=max;a++)//枚举 i-2 列状态 
	for(b=0;b<=max;b++){//枚举 i-1 列状态 
		if(!Check1(a,b))continue;//剪枝优化 
		for(c=0;c<=max;c++)//枚举第 i 列状态 
		if(Check2(a,b,c)&&k-Cnt(c)>=0)//如果状态不冲突且数组下标不越界 
		dp[i][k][b][c]=(dp[i][k][b][c]+dp[i-1][k-Cnt(c)][a][b])%Mod;//状态转移 
	}
	printf("%d",dp[M+2][K][0][0]);//前 M+2 列放了 K 个马,且第 M+2 列和第 M+1 列都没放
	//相当于第 0 列到第 M 列放 K 个马的方案数 ,初始状态:第 0 列没放  =>> dp[M+2][K][0][0] 即为第 1 列到第 M 列的方案数
	return 0;
}

相关文章