2017第八届蓝桥杯C/C++ B组省赛

2017年04月14日 10点热度 0人点赞 0条评论

第二题

标题:等差素数列
2,3,5,7,11,13,....是素数序列。
类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为30,长度为6。
2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。
这是数论领域一项惊人的成果!
有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:
长度为10的等差素数列,其公差最小值是多少?
注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字。

//一开始想都没想,以为挨着的最小,结果gg,gg在越界
#include
#include
using namespace std;
int primer[10000+10],mp,vis[100000+10];
//0为素数
int main()
{
    int d;
    for(int i=2; i<100000; i++)
        if(!vis[i])
        {
            primer[mp++]=i;
            for(int j=i*2; j<100000; j+=i)
                vis[j]=1;
        }
    for(int i=1; i=100000||vis[primer[i]+j*d]) break;
            if(j==10)
            {
                cout<

第10题

标题: k倍区间
给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。  
你能求出数列中总共有多少个K倍区间吗?  
输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)  
输出
-----
输出一个整数,代表K倍区间的数目。  
例如,
输入:
5 2
1  
2  
3  
4  
5  
程序应该输出:
6
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。
提交程序时,注意选择所期望的语言类型和编译器类型。

//其实从题目数据的大小中也可以获取大量的数据的
//一般的,我们可以把1到i之间的数据之和为s[i],则可枚举区间和,这样就会爆时间
//故在计算区间和时进行一些处理,如果(s[j]-s[i])%k==0,则是s[j]%k==s[i]%k,
//那么就是计算1到i(i位1到n)区间和中%k后相等的对数,于是时间复杂度变成了n+k,666啊 
#include
#include
using namespace std;
const int mx=100000+10;
int n,k,s[mx],t,vis[mx];
long long ans;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&t);
		s[i]=(s[i-1]+t)%k;
		vis[s[i]]++;
	}
	for(int i=0;i
//优化了一下空间 
#include
#include
using namespace std;
const int mx=100000+10;
int n,k,st,t,vis[mx];
long long ans;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&t);
		st=(st+t)%k;
		vis[st]++;
	}
	for(int i=0;i

第9题

标题: 分巧克力
    儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
    小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。
    为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
    1. 形状是正方形,边长是整数  
    2. 大小相同  
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 
输入保证每位小朋友至少能获得一块1x1的巧克力。   
输出
输出切出的正方形巧克力最大可能的边长。
样例输入:
2 10  
6 5  
5 6  
样例输出:
2
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms

//这个题目不用二分确实会超时,比赛的时候没有用二分,只是简单的优化了下
//二分的时间复杂度是logn*n 
#include
#include
using namespace std;
const int mx=100000+10;
int n,k,h[mx],w[mx];
bool solve(int t){
	int s=0;
	for(int i=1;i<=n;i++)
	s+=(h[i]/t)*(w[i]/t);
	if(s>=k) return true;
	return false;
}
 int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	scanf("%d%d",h+i,w+i);
	int left=1,right=100000;
	while(left!=right){
		int mid=(left+right)/2;
		if(solve(mid)){
			left=mid+1;
		}
		else
		right=mid-1;
	}
	printf("%dn",left);
	return 0;
}

第8题

标题:包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)  
输出
----
一个整数代表答案。如果凑不出的数目有无限多个,输出INF。
例如,
输入:
2  
4  
5   
程序应该输出:
6  
再例如,
输入:
2  
4  
6    
程序应该输出:
INF
样例解释:
对于样例1,凑不出的数目包括:1, 2, 3, 6, 7, 11。  
对于样例2,所有奇数都凑不出来,所以有无限多个。  
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms

//仔细想了下,还真是扩展欧几里得的变形,如果所有数的最大公约数是1,则有有限,反之则有无限个 
#include
#include
using namespace std;
const int mx=11000,M=10000;
int g,dp[mx],n,a[mx],ans,mi=999999;
int gcd(int t,int tt){
	if(tt==0) return t;
	return gcd(tt,t%tt);
}
int main(int argc,char* argv[]){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		dp[a[i]]=1;
		mi=min(a[i],mi);
	}
	g=a[1];
	for(int i=2;i<=n;i++)
	g=gcd(g,a[i]);
	if(g!=1){
		puts("INF");
		return 0;
	}
	int t=0;
	for(int i=1;i<=M;i++){
		if(dp[i])
		{
		for(int j=1;j<=n;j++)
			dp[i+a[j]]=1;
		t++;
		if(t>=mi){
			printf("%dn",ans);
			return 0;
		}
		}
		else ans++,t=0;
	}
	return 0;
}

未经允许不得转载!2017第八届蓝桥杯C/C++ B组省赛

update

纸上得来终觉浅, 绝知此事须躬行。