acm入门基础题解二
Problem A: 数字菱形
#include
int main()
{ intn,i,j,a;
while(scanf("%d",&n)!=EOF)
{ for(i=1;i<=n;i++)
{ for(j=1;j<=n-i;j++)
printf(" ");
for(a=1;a<=(2*i-1);a++)
printf("%d",i);
printf("\n");
}
for(i=n-1;i>=1;i--)
{ for(j=1;j<=n-i;j++)
printf(" ");
for(a=1;a<=(2*i-1);a++)
printf("%d",i);
printf("\n");
}
}
return 0;
}
Problem B: 保卫钓鱼岛
#include
int main()
{ ints,T,n,a[100],i,j,t;
scanf("%d",&T);
for(s=1;s<=T;s++)
{ scanf("%d",&n);
for(i=0;i scanf("%d",&a[i]); for(i=1;i for(j=0;j if(a[j] { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } for(i=0;i if(i==0)printf("%d",a[i]); elseprintf(" %d",a[i]); printf("\n"); } return 0; } Problem C: 最大盈利 #include #include int a[100005]; int main() { intt,i,j,k,l,m,n; while(~scanf("%d",&t)) { intcas=1; while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); intmax,st,ed,sum,s,e; max=sum=a[1]; st=ed=s=e=1; for(i=2;i<=n;i++) { if(sum+a[i] sum=sum+a[i]; e++; } if(sum>max){st=s;max=sum;ed=e;} } printf("Payoff %d:\n",cas++); printf("%d %d %d\n",max,st,ed); printf("\n"); } } return 0; } Problem D: 基因分裂 #include int main() { int f[100],n,i,j; f[1]=1; f[2]=2; f[3]=3; scanf("%d",&n); while(n!=0) { {for(i=4;i<55;i++) f[i]=f[i-1]+f[i-3]; } printf("%d\n",f[n]); scanf("%d",&n); } return 0; } Problem E: 碉堡 #include char map[4][5]; intmaxCount; intCanPut(int n, int x, int y) { int i; i=x; while(i>0 && map[i-1][y]!='X') if (map[--i][y]=='O') return 0; i=y; while(i>0 && map[x][i-1]!='X') if(map[x][--i]=='O') return 0; return 1; } void Search(int n, int k, intcurCount) { intx,y; if(k==n*n) { if(curCount>maxCount) maxCount=curCount; return; } else { x=k/n; y=k%n; if(map[x][y]=='.' &&CanPut(n,x,y)) { map[x][y]='O'; Search(n, k+1, curCount+1); map[x][y]='.'; } Search(n,k+1,curCount); } } int main() { intn,i,count; while(scanf("%d",&n)!=EOF && n>0) { for(i=0;i scanf("%s", map[i]); maxCount=0; Search(n, 0, 0); printf("%d\n",maxCount); } } 这个训练计划我也只是把我知道的知识点罗列出来而已. 其实acm还有很多方面的知识。 可能到acm生涯结束的时候还是无法把所有的知识都吃透 所以acm的知识能学多少算多少，知识重要的不是你知道的多，重要的是你能否熟练的运用他们！ 题目注意事项： zoj：https://www.wendangku.net/doc/b06047853.html,/ grid：https://www.wendangku.net/doc/b06047853.html,/ hdu：https://www.wendangku.net/doc/b06047853.html,/ zquoj：也就是我们的oj 一．数据机构基础。 请自学完数据结构书：2，3，4，6，7，9.1，9.2.1 9.3 10 这几章，带*号可以暂时掠过，以后再看。然后自行完成oj DS开头的题目。 注意栈队列这些数据结构一般不用像书本那样写得那么严谨。在acm中，往往因为时间关系，一般写成简单的模式：请参考附件：栈与队列acm中的简单实现.txt 其它数据结构请自行简化。 二．其他数据结构 1.trie树 请看附件trie树的相关附件或到网上搜索。注意自己写好和简化模版。 Trie树最好使用静态分配实现！ poj 3630 hdu 1251 2.并查集 Hdu：1558 1811 1829 1198 3.图论专题： 简单的说下图怎么存储。 图通常分为邻接表和邻接矩阵两种方式储存。 请先移步到数据结构书祥看这两种实现方式。 邻接表：我们知道要动态分配内存。这种方式有时会导致效率低下。我们可以模拟一下动态分配内存，详见附件静态分配。 这部分图论可参考 https://www.wendangku.net/doc/b06047853.html,/p-251720691.html 部分题目.这本书有讲解。 1.图的基本概念 poj：1659 2.图的遍历和活动问题 zoj：2110 1709 1649 2913 1060 2193 2412 1008 2165 1136 1361 1091 1083 poj：2935 1270 3687 POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: poj 1061 青蛙的约会 这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下： 对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下： 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 以上内容转自https://www.wendangku.net/doc/b06047853.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html Problem A: 数字三角形 #include } int main(){ while(scanf("%d",&n)!=EOF&&n!=0){ data_set(); solve(); } return 0; } Problem B: 去北京看奥运 #include 1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include 有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断； ②是否是最大限和最小限之间的数都能表示呢？ 都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）； #include ACM入门（杭电oj） Hdu 1000 #include a[j]=a[j]+str2[i]-'0'; a[j+1]=a[j+1]+a[j]/10; a[j]=a[j]%10; } count++; printf("Case %d:\n",count); printf("%s + %s = ",str1,str2); int flag=0; for(i=1004;i>=0;i--) if(flag||a[i]) { printf("%d",a[i]); flag=1; } printf("\n"); if(ca!=0) printf("\n"); } } Hdu 1003 #include 1、公约数和公倍数 https://www.wendangku.net/doc/b06047853.html,/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为： a*b=gcd(a,b)*lcm(a,b); 代码如下： #include ?????≡≡≡)33(mod ) 28(mod )23(mod d n e n p n 那么找到k1、k2、k3满足： k1：k1%23==0&&k1%28==0&&k1%33==1 k2：k2%33==0&&k2%28==0&&k2%23==1 k3：k3%33==0&&k3%23==0&&k3%28==1 则n=k2*p+k3*e+k1*i+k*21252； 代码如下： #include ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法 竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况 总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识 语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当 数论50题 1．由1，3，4，5，7，8这六个数字所组成的六位数中，能被11整除的最大的数是多少？ 【分析】各位数字和为1+3+4+5+7+8=28 所以偶数位和奇数位上数字和均为14 为了使得该数最大，首位必须是8，第2位是7，14-8=6 那么第3位一定是5，第5位为1 该数最大为875413。 2．请用1，2，5，7，8，9这六个数字（每个数字至多用一次）来组成一个五位数，使得它能被75整除，并求出这样的五位数有几个？ 【分析】75=3×25 若被3整除，则各位数字和是3的倍数，1+2+5+7+8+9=32 所以应该去掉一个被3除余2的，因此要么去掉2要么去掉8 先任给一个去掉8的，17925即满足要求 1）若去掉8 则末2位要么是25要么是75，前3位则任意排，有3！=6种排法 因此若去掉8则有2*6=12个满足要求的数 2）若去掉2 则末2位只能是75，前3位任意排，有6种排法 所以有6个满足要求 综上所述，满足要求的五位数有18个。 3．已知道六位数20□279是13的倍数，求□中的数字是几？ 【分析】根据被13整除的判别方法，用末三位减去前面的部分得到一个两位数，十位是7，个位是（9-□），它应该是13的倍数，因为13|78,所以9-□=8 □中的数字是1 4．某自然数，它可以表示成9个连续自然数的和，又可以表示成10个连续自然数的和，还可以表示成11个连续自然数的和，那么符合以上条件的最小自然数是？（2005全国小学数学奥赛） 【分析】可以表示成连续9个自然数的和说明该数能被9整除，可以表示成连续10个自然数的和说明该数能被5整除，可表示成连续11个自然数的和说明该数能被11整除 因此该数是[9,5,11]=495，因此符合条件的最小自然数是495。 5．一次考试中，某班同学有考了优秀，考了良好，考了及格，剩下的人不及格，已知该班同学的人数不超过50，求有多少人不及格？ 【分析】乍一看这应该是一个分数应用题，但实际上用到的却是数论的知识，由于人数必须是整数，所以该班同学的人数必须同时是2，3，7的倍数，也就是42的倍数，又因为人数不超过50，所以只能是42人，因此不及格的人数为（1---）×42=1人 6．（1）从1到3998这3998个自然数中，有多少个能被4整除？ （2）从1到3998这3998个自然数中，有多少个数的各位数字之和能被4整除？ （第14届迎春杯考题） 【分析】（1）3998/4=999….6所以1-3998中有996个能被4整除的 （2）考虑数字和，如果一个一个找规律我们会发现规律是不存在的 因此我们考虑分组的方法 我们补充2个数，0000和3999，此外所有的一位两位三位数都在前面加上0补足4位 然后对这4000个数做如下分组 ACM部分习题答案： A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include 断断续续的学习数论已经有一段时间了，学得也很杂，现在进行一些简单的回顾和总结。学过的东西不能忘啊。。。 1、本原勾股数： 概念：一个三元组(a,b,c)，其中a,b,c没有公因数而且满足：a^2+b^2=c^2 首先，这种本原勾股数的个数是无限的，而且构造的条件满足： a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2 其中s>t>=1是任意没有公因数的奇数！ 由以上概念就可以导出任意一个本原勾股数组。 2、素数计数（素数定理） 令π(x)为1到x中素数的个数 19世纪最高的数论成就就是以下这个玩意儿： lim(x->∞){π(x)/(x/ln(x))}=1 数论最高成就，最高成就！！！有木有！！！ 3、哥德巴赫猜想(1+1) 一个大偶数(>=4)必然可以拆分为两个素数的和，虽然目前还没有人能够从理论上进行证明，不过我根据科学家们利用计算机运算的结果，如果有一个偶数不能进行拆分，那么这个偶数至少是一个上百位的数！！ 所以在ACM的世界中（数据量往往只有2^63以下）哥德巴赫猜想是成立的！！所以拆分程序一定能够实现的 4、哥德巴赫猜想的推广 任意一个>=8的整数一定能够拆分为四个素数的和 证明： 先来说8=2+2+2+2，（四个最小素数的和）不能再找到比2小的素数了，所以当n小于8，就一定不可能拆分为四个素数的和！ 那么当n大于等于8，可以分情况讨论： （1）n&1==0(n为偶数)，那么n就一定可以拆分为两个偶数的和 那么根据哥德巴赫猜想，偶数可以拆分为两个素数的和，于是，n一定可以拆分为四个素数的和 （2）n&1==1(n为奇数)，n一定可以拆分为两个偶数+1 由于有一个素数又是偶数，2，那么奇数一定有如下拆分：2+3+素数+素数 得证。 -北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.wendangku.net/doc/b06047853.html,/JudgeOnline 1. 标记难和稍难的题目大家可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。 2. 标记为A and B 的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。 3. 列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。 4. 这里不少题目在BUPT ACM FTP 上面都有代码，请大家合理利用资源。 5. 50个题目要求每个题目都要写总结，养成良好的习惯。 6. 这50道题的规定是我们的建议，如果大家有自己的想法请与我们Email 联系。 7. 建议使用C++ 的同学在POJ 上用G++ 提交。 8. 形成自己编写代码的风格，至少看上去美观，思路清晰(好的代码可以很清楚反映出解题思路)。 9. 这个列表的目的在于让大家对各个方面的算法有个了解，也许要求有些苛刻，教条，请大家谅解，这些是我们这些年的经验总结，所以也请 大家尊重我们的劳动成果。 10. 提交要求：一个总文件夹名为bupt0xx (即你的比赛帐号), 这个文件夹内有各个题目类别的子目录(文件夹)，将相应的解题报告放入对应 类别的文件夹。在本学期期末，小学期开始前，将该文件夹的压缩包发至buptacm@https://www.wendangku.net/doc/b06047853.html,。 对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件，注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目，请尽快和我们联系，我们将指导下一步的训练。 下面是一个解题报告的范例： 例如：POJ1000.cpp 目录 数A01 敲七 (1) 数A02 三角形面积 (2) 数A03 3n+1数链问题 (3) 数A04 统计同成绩学生人数 (4) 数A05 分解素因子 (5) 数A06 亲和数 (6) 数B01 寒冰王座 (7) 数B02 整数对 (8) 数B03 麦森数 (9) 数B04 Feli的生日礼物 (10) 注：数表示本题属于初等数论，A表示简单，B表示稍难。 数A01 敲七 【问题描述】 输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【数据输入】一个整数N。(N不大于30000) 【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。 【样例输入】 20 【样例输出】 7 14 17 数A02 三角形面积 【问题描述】 给出三角形的三个边长为a，b，c，根据海伦公式来计算三角形的面积： s = (a+b+c)/2； area = sqrt(s*(s-a)*(s-b)*(s-c)); 【数据输入】测试的数据有任意多组，每一组为一行。 每一行为三角形的三个边长为a，b，c； 【数据输出】输出每一个三角形的面积，两位小数。如果不是一个三角形，则输出错误提示信息：“Input error!” 【样例输入】 3 4 5 6 8 10 1 2 3 【样例输出】 6.00 24.00 Input error! 数A03 3n+1数链问题 【问题描述】 在计算机科学上，有很多类问题是无法解决的，我们称之为不可解决问题。然而，在很多情况我们并不知道哪一类问题可以解决，那一类问题不可解决。现在我们就有这样一个问题，问题如下： 1. 输入一个正整数n； 2. 把n显示出来； 3. 如果n=1则结束； 4. 如果n是奇数则n变为3n+1 ，否则n变为n/2； 5. 转入第2步。 例如对于输入的正整数22，应该有如下数列被显示出来： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 我们推测：对于任意一个正整数，经过以上算法最终会推到1。尽管这个算法很简单，但我们仍然无法确定我们的推断是否正确。不过好在我们有计算机，我们验证了对于小于1,000,000的正整数都满足以上推断。对于给定的正整数n，我们把显示出来的数的个数定义为n的链长，例如22的链长为16。 你的任务是编写一个程序，对于任意一对正整数i和j，给出i、j之间的最长链长，当然这个最长链长是由i、j之间的其中一个正整数产生的。我们这里的i、j之间即包括i也包括j。 【数据输入】输入文件只有一行，即为正整数i和j，i和j之间以空格隔开。0 < i ≤j < 10,000。 【数据输出】文件只能有一行，即为i、j之间的最长链长。 【样例输入】 1 10 【样例输出】 20 最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible Feli 的生日礼物 【问题描述】 Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8 程序设计比赛试题 主办方：迅翔计算机协会 最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <=1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible Feli的生日礼物 【问题描述】 Felicia的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8 目录 目录 (1) 一．扩展的欧几里德和不定方程的解 (2) 二．中国同余定理 (3) 三．原根 (5) 四．积性函数 (6) 五．欧拉函数性质 (7) 六．线性求1-max的欧拉函数值 (9) 七．求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) (10) 一．扩展的欧几里德和不定方程的解 解不定方程ax + by = n的步骤如下: (1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1 (2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。 (3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为： x = n'x0 + b't y = n'y0 - a't (t为整数) 这也就是方程ax + by = n的所有整数解 利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得： x = n/gcd * x0 + b/gcd * t y = n/gcd * y0 - a/gcd * t (t是整数) int extend_Euclid(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd= extend_Euclid ( b, a % b, x, y ); int temp = x; x = y; y = temp - (a / b) * y; return gcd; } ACM竞赛简介： ACM国际大学生程序设计竞赛是由国际计算机界历史悠久、颇具权威性的组织ACM学会（美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。(网上有更详细的介绍，这里只做个简介) ACM竞赛特点： 竞赛中一般有10道题，比赛时间为5个小时，每支参赛队伍由3名选手组成，可以携带诸如书、手册、程序清单等参考资料，对每一道题编完代码后，将代码提交裁判，每一次提交会被判为正确或者错误，判决结果会及时通知参赛队伍。 在规定时间内提交并通过题目数越多排名越靠前。（时间5小时，题目8~12题，同题目数按所用时间多少排名） ACM题目限制： 时间限制（即程序运行所用的时间）空间限制（即程序运行时所开内存的多少） ACM基本要求 ?英语 ?分析理解能力 ?算法 ?编码 ?合作 ACM竞赛意义 学习编程，并不是为了参加竞赛，ACM竞赛对于我们的意义更多的还是专业能力的提高。在备战过程中，无论是对自己的编程能力，还是团队合作解决问题的能力，都是一种很好的锻炼机会。一般而言，每个在做ACM竞赛的学生，他们的编程能力会比较出色。与数学建模相比，由于ACM竞赛针对的是我们学计算机的同学，所以没有数学建模的比赛规模，但是依旧是国际上最有影响力的大学生竞赛之一。 ACM竞赛入门 现在有很多大学有专门为ACM竞赛开设自己的测评网站，上面有很多贴近竞赛的题目。比如说北大poj，浙大zoj等等。所以选择一个自己专门练习的网站，我们都用北大的poj，然后开始自己在上面做题，和同学交流经验。等到回到本部，要是有了一定的实力和基础，张震老师就会对我们进行选拔和组队，最后参加省赛和亚洲的区域赛。 ?在poj上做20左右道简单的题目，熟悉ACM题目的基本特点。（这里列出几道相对 较简单的题目的题号：1000，1003，1004，1046，1207，1226，1504，1552） ?熟悉了poj之后，按照poj的题目分类，买一本或借一本算法的书（暨大ACM校队 的基本都用机械工程出版社的《算法导论》）开始学习，然后做算法的专题，一般每个专题做10~30道。主流的算法分类为： 1.搜索//回溯 2.DP（动态规划） 3.贪心 4.图论//Dijkstra、最小生成树、网络流 5.数论//解模线性方程 6.计算几何//凸壳、同等安置矩形的并的面积与周长 7.组合数学//Polya定理 8.模拟 9.数据结构//并查集、堆 10.博弈论 ?专题做完后，你已经很强了，就可以找另外2个同学或师兄组成自己的队伍，开始 做poj上的难题，开始模拟比赛，为今后的竞赛做准备。 第二讲——数的奇偶性 一、基本概念和知识 一、奇数和偶数 整数可以分成奇数和偶数两大类.能被2整除的数叫做偶数，不能被2整除的数叫做奇数。 偶数通常可以用2k（k为整数）表示，奇数则可以用2k+1（k为整数）表示。 特别注意，因为0能被2整除，所以0是偶数。 二、奇数与偶数的运算性质 性质1：偶数±偶数=偶数， 奇数±奇数=偶数。 性质2：偶数±奇数=奇数。 性质3：偶数个奇数相加得偶数。 性质4：奇数个奇数相加得奇数。 性质5：偶数×奇数=偶数， 奇数×奇数=奇数。 三、奇反偶同：搞清一件事情的初始状态，进行奇数次操作，会和起始状态相反，进行偶数次操作，会回到初始状态。 二、例题 例1 1+2+3+…+99的和是奇数？还是偶数？ 例2 能不能在下面的每个方框中，分别填入加号或减号，使等式成立1□2□3□4□5□6□7□8□9=10 例3 元旦前夕，同学们相互送贺年卡.每人只要接到对方贺年卡就一定回赠贺年卡，那么送了奇数张贺年卡的人数是奇数，还是偶数？ 为什么？ 例4 桌上有9只杯子，全部口朝上，每次将其中6只同时“翻转”.请说明：无论经过多少次这样的“翻转”，都不能使9只杯子全部 口朝下。 例5 某校六年级学生参加区数学竞赛，试题共40道，评分标准是：答对一题给3分，答错一题倒扣1分.某题不答给1分，请说明该校 六年级参赛学生得分总和一定是偶数。 例5 在中国象棋盘任意取定的一个位置上放置着一颗棋子“马”，按中国象棋的走法，当棋盘上没有其他棋子时，这只“马”跳了若 干步后回到原处，问：“马”所跳的步数是奇数还是偶数？ 例6 一个俱乐部里的成员只有两种人：一种是老实人，永远说真话； 一种是骗子，永远说假话。某天俱乐部的全体成员围坐成一圈， 每个老实人两旁都是骗子，每个骗子两旁都是老实人。外来一位 记者问俱乐部的成员张三：“俱乐部里共有多少成员？”张三答：ACM一期 基础训练计划
ACM经典算法及配套练习题
(2020年编辑)ACM必做50题的解题-数论
acm入门基础题解一
ACM必做50题——数学
ACM入门十题(杭电oj)
ACM数论方面十道基础题目详解
ACM入门之新手入门
数论50题
ACM部分练习题目答案
数论
北大 poj acm题目推荐50题
step1-数论 程序设计基础题ACM
acm编程比赛入门题目集
acm入门题集
ACM数论模板
ACM竞赛简介和入门
数论2—数的奇偶性