第二题
标题：等差素数列 2,3,5,7,11,13,....是素数序列。 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。 上边的数列公差为30，长度为6。 2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！ 有这一理论为基础，请你借助手中的计算机，满怀信心地搜索： 长度为10的等差素数列，其公差最小值是多少？ 注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。
//一开始想都没想，以为挨着的最小，结果gg,gg在越界 #include<cstdio> #include<iostream> 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<mp; i++) { for(int k=i+1; k<mp; k++) { d=primer[k]-primer[i]; int j; for(j=1; j<10; j++) if(primer[i]+j*d>=100000||vis[primer[i]+j*d]) break; if(j==10) { cout<<d<<endl; return 0; } } } return 0; }第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 <xxx> 不能通过工程设置而省略常用头文件。 提交程序时，注意选择所期望的语言类型和编译器类型。
//其实从题目数据的大小中也可以获取大量的数据的 //一般的，我们可以把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<cstdio> #include<iostream> 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<k;i++) if(vis[i]) ans+=vis[i]*(vis[i]-1)/2; ans+=vis[0]; printf("%lld\n",ans); return 0; } //优化了一下空间 #include<cstdio> #include<iostream> 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<k;i++) if(vis[i]) ans+=vis[i]*(vis[i]-1)/2; ans+=vis[0]; printf("%lld\n",ans); return 0; } 第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<cstdio> #include<iostream> 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("%d\n",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<cstdio> #include<iostream> 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("%d\n",ans); return 0; } } else ans++,t=0; } return 0; }