发布时间 : 星期一 文章ACM程序设计 赛题样例更新完毕开始阅读
9 20 500 3
Sample Output 3
#include
void put(int n)//将前n个素数存入p中 {
int i,j,k=0; i=2; while(1) {
for(j=2;j<=(int)sqrt(i);j++) if(i%j==0) break;
if(j>(int)sqrt(i)) p[k++]=i; if(k>=n) return; i++; } }
int judge(int num)//判断num是否是一个平方数 {
int i=0,count; while(num!=1) {
count=0;
while(num%p[i]==0) {
num/=p[i]; count++; }
if(count%2) return 0; i++; }
return 1; }
int fun(int *p,int n,int m) {
int s,cou=0; int b[100]; int i,j,k,count; int min=0,max=0; for(i=0;i for(j=0;j b[j]=k%2; k/=2; if(b[j]) count++; if(count>m) break; j++; } if(count==m) { s=1; for(j=0;j s*=p[j]; } if(judge(s)) { for(j=0;j printf(\,p[j]); putchar('\\n'); cou++; } } } return cou; } void main() { int total=0,i,t,m; int a[100]; printf(\输入t：\); scanf(\,&t); put(t); printf(\输入m:\); scanf(\,&m); printf(\输入满足要求的%d个数:\,m); for(i=0;i printf(\一共有%d组数！\\n\,total); } 国家利益 Background 没有永远的朋友，也没有永远的敌人，国家的行为取决于国家利益，国家的地位取决于国家实力 Problem 伊拉克战争结束后... N个国家正在联合国开会商讨如何分配伊拉克的M块油田 N个国家按国家实力编号1，2，3...N，1号国家实力最强，第一个发言，N号最后一个发言，依次类推 发言国家会提出一个分配方案，所有有表决权的国家进行表决（包括发言国家自己），如果50%或以上 同意此方案，则会议结束，按照此国的方案分配油田，否则该国丧失表决权，下个国家重复上述过程 那么第一个国家提出怎样的方案才能使本国利益最大化？ Hint 每个国家分得的油田都是整数，不会出现几个国家共同拥有一块油田 每个国家都不希望别人的方案通过，但是每个国家都按照本国利益投票，比如1号国家提出一个方案， X号国家分Y油田，X号国家会进行比较， 如果该方案被否决，那么下次2号提出的方案X号国家分Z油田，而Z < Y，那么X号国家会赞成1号的方案， 否则反对 Input 每行包括2个整数N，M，（N,M <= 10^8） Output 每行包括1个整数，1号国家能获得的最多油田数 Sample Input 7 100 Sample Output 97 我是新手，大家看看我的思路对吗？ 当只有2个国家，100个油田时： 第1国第2国 100 0 当只有3个国家，100个油田时： 第1国第2国第3国 99 0 1 当只有4个国家 第1国第2国第3国第4国 99 0 1 0 当只有5个国家 第1国第2国第3国第4国第5国 98 0 1 0 1 当只有6个国家 第1国第2国第3国第4国第5国第6国 98 0 1 0 1 0 。 。 。 。 。 看出想要让自己的方案通过，就要让第3，5，7，9。。。。的 国家有1个油田 如：只有2个国家：第一个（100），第2个（0） 3个国家时，如果第一个国家的方案不通过，就用第2个国家的，那第 三个国家就没油田，所以只要第一个国家给第3个国家1个 油田，第三国就赞成。 同理：4国家时：第一国的方案不通过，那就用就用第2个国家的，那三个国家就没油田，所以只要三个国家有一个油田，其 就同意。 其他情况类推 代码： #include int a[100],i,sum=0; for(i=0;i