经典问题_NYOJ_选拔必考

《经典问题_NYOJ_选拔必考》由会员分享，可在线阅读，更多相关《经典问题_NYOJ_选拔必考（14页珍藏版）》请在装配图网上搜索。

1、1.蛇形填数时间限制：3000 ms | 内存限制：65535 KB 难度：3描述 在n*n方陈里填入1,2,.,n*n,要求填成蛇形。例如n=4时方陈为：10 11 12 19 16 13 28 15 14 37 6 5 4输入直接输入方陈的维数，即n的值。(n=100)输出输出结果是蛇形方陈。样例输入3样例输出7 8 16 9 25 4 3蛇形填数#includeint main()int i,k,t,n,a100100;while(scanf(%d,&n)!=EOF)for(k=0,t=0;kn/2;k+)for(i=k;ik;i-)an-k-1i=+t;for(i=n-k-1;ik;i

2、-)aik=+t;for(i=k;in-k-1;i+)aki=+t;if(n%2)akk=t+1;for(k=0;kn;k+)for(i=0;in;i+)printf(%-4d ,aki);printf(n);return 0;输出要有空格，2.字符串替换时间限制：3000 ms | 内存限制：65535 KB 难度：2描述 编写一个程序实现将字符串中的所有you替换成we输入输入包含多行数据 每行数据是一个字符串，长度不超过1000 数据以EOF结束输出对于输入的每一行，输出替换后的字符串样例输入you are what you do样例输出we are what we do字符串替换#in

3、cludeint main()int i;char a1010;while(gets(a)for(i=0;ai!=0;i+)if(ai=y&ai+1=o&ai+2=u)printf(we);i+=2;else printf(%c,ai);putchar(n);return 0;3.韩信点兵时间限制：3000 ms | 内存限制：65535 KB 难度：1描述 相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队 伍的排尾就知道总人数了。输入3个非负整数a,b,c ，表示每种队形排尾的人数（a3,b5,c7），输出总人数的最小值

4、（或报告无解）。已知总人数不小于10，不超过100 。输入输入3个非负整数a,b,c ，表示每种队形排尾的人数（a3,b5,c7）。例如,输入：2 4 5输出输出总人数的最小值（或报告无解，即输出No answer）。实例，输出：89样例输入2 1 6样例输出41法一：#include#includeint main()int a,b,c,n;scanf(%d%d%d,&a,&b,&c);n=(a*70+b*21+c*15)5;if(n=10&n=100)printf(%dn,n);elseprintf(No answer);/system(pause);return 0;韩信点兵的计算方法，

5、它的意思是：凡是用3个一数剩下的余数，将它用70去乘（因为70是5与7的倍数，而又是以3去除余1的数）；5个一数剩下的余数，将它用21去乘（因为21是3与7的倍数，又是以5去除余1的数）；7个一数剩下的余数，将它用15去乘（因为15是3与5的倍数，又是以7去除余1的数），将这些数加起来，若超过105，就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。这样，所得的数就是原来的数了法二：#include#includeint main()int a,b,c,t=10;scanf(%d%d%d,&a,&b,&c);while(1)if(t%3=a)&(t%5=b)

6、&(t%7=c)printf(%dn,t);break;if(t100)printf(No answer);elset+;/system(pause);return 0;4.寻找最大数时间限制：1000 ms | 内存限制：65535 KB 难度：2描述 请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大，比如当n=92081346718538，m=10时，则新的最大数是9888输入第一行输入一个正整数T，表示有T组测试数据每组测试数据占一行，每行有两个数n,m（n可能是一个很大的整数，但其位数不超过100位，并且保证数据首位非0，m小于整数n的位数）输出每组测试数据的输出占

7、一行，输出剩余的数字按原次序组成的最大新数样例输入292081346718538 101008908 5样例输出988898/*最初做法：先用冒泡排序找到strlen(str)-m个最大数，然后分别找出来他们在原来串中的位置，然后对位置排序之后按位序输出这些最大数，则连在一起就是最大数。运行无误，但是通过不了*/#include#includeint visited101;int fun(char *s,int n,char ch)int i;for(i=0;in;i+)if(si=ch&visitedi=0) visitedi=1;return i;int main()char str110

8、1,str2101,ch;int N,n,a101,m,i,j,t;scanf(%d,&N);while(N-)for(i=0;i=100;i+)visitedi=0; scanf(%s %d,str1,&m);strcpy(str2,str1);n=strlen(str1);for(j=1;jn;j+)for(i=0;i=n-j-1;i+)if(str1istr1i+1)ch=str1i;str1i=str1i+1;str1i+1=ch;for(i=0;in-m;i+)ai=fun(str2,n,str1i);for(j=1;jn-m;j+)for(i=0;iai+1)t=ai;ai=ai+

9、1;ai+1=t;for(i=0;in-m;i+)printf(%c,str2ai);printf(n);return 0;/*换一种思路：这道题可以理解为：在字符串中找出一个由strlen(str)-m个字符按顺序（不要求连续）拼成的最大数。其实这是个不断贪心的过程，首先要在str0到strm（包括strm）找到第一个最大的数字（注意哦，是第一个最大数字）作为最高位数（之所以要在0到m间找，是因为至少要留出strlen(str)-m-1位放在最高位后面的低位），假设是strk，然后再从strk+1到strm+1（因为此时已经选了1个，所以留出至少strlen(str)-m-2位放在第二位位后

10、面的低位）找到第一个最大的作为第二位数一直到strlen(str)-m个数被确定完，这样从最高位到最低位都是所能选择的最大值，所以得到的结果也将是最大值。*/#include#includeint main()char a102,b102;int i,j,p,k,N,n,m,max;scanf(%d,&N);while(N-)scanf(%s %d,a,&m);n=strlen(a);for(i=p=k=0;in-m;i+,k+)max=-1;for(j=p;jmax)max=aj;p=j+1;bk=max;bk=0;printf(%sn,b);return 0;5.过河问题时间限制：1000

11、 ms | 内存限制：65535 KB 难度：5描述 在 漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电 筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需 的时间。问题是，如何设计一个方案，让这N人尽快过桥。输入第一行是一个整数T(1=T=20)表示测试数据的组数每组测试数据的第一行是一个整数N(1=N=1000)表示共有N个人要过河每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0Si=

12、 1)过桥最佳方案的方法：1)如果N=1或者N=2，所有人直接过桥。2)如果N=3,由最快的人往返一次把其他两人送过河。3)如果N=4,设A，B为走的最快的和次快的旅行者，过桥所需时间分别为a,b；而Z,Y为走得最慢的和次慢的旅行者，过桥所需时间分别为z,y。那么当2ba+y时，使用模式一将Z和Y移动过桥当2bt2,即2ba+y时，选择模式二，t1t2，即2ba+y时，选择模式一#includeint fun(int a,int n)int sum=0;if(n=1) sum=a1;else if(n=2) sum=a2;else if(n=3) sum=a1+a2+a3;elseif(a2*

13、2a1+an-1) sum+=2*a1+an+an-1;else sum+=2*a2+a1+an;sum+=fun(a,n-2);return sum;int main()int N,n,a1000,i,j,t,sum;scanf(%d,&N);while(N-)scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);for(j=1;jn;j+)for(i=1;iai+1)t=ai;ai=ai+1;ai+1=t;sum=0;sum=fun(a,n);printf(%dn,sum);return 0;6.括号配对问题时间限制：3000 ms | 内存限制：65535

14、KB 难度：3描述 现在，有一行括号序列，请你检查这行括号是否配对。输入第一行输入一个数N（0N=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有,(,)四种字符输出每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No样例输入3()()()样例输出NoNoYes#include#include#includeint main()int n;void fun(int n);while (scanf(%d,&n)!=EOF)fun(n);

15、system(PAUSE);return 0;void fun(int n)void deal(char str);char str10000;for (int i=1;i=n;i+)scanf(%s,str);deal(str);return;void deal(char str)int sum=0;int len;len=strlen(str);if (len%2!=0)printf(Non);return;for (int i=0;i=0;j-)if (strj=)printf(Non);return;if (strj=()sum-;strj=0;stri=0;break;elsefor

16、 (int j=i-1;j=0;j-)if (strj=()printf(Non);return;if (strj=)sum-;strj=0;stri=0;break;/puts(str);if (sum=0) printf(Yesn);else printf(Non);return;7一种排序时间限制：3000 ms | 内存限制：65535 KB 难度：3描述 现在有很多长方形，每一个长方形都有一个编号，这个编号可以重复；还知道这个长方形的宽和长，编号、长、宽都是整数；现在要求按照一下方式排序（默认排序规则都是从小到大）；1.按照编号从小到大排序2.对于编号相等的长方形，按照长方形的长排序

17、；3.如果编号和长都相同，按照长方形的宽排序；4.如果编号、长、宽都相同，就只保留一个长方形用于排序,删除多余的长方形；最后排好序按照指定格式显示所有的长方形；输入第一行有一个整数 0n10000,表示接下来有n组测试数据；每一组第一行有一个整数 0m1000，表示有m个长方形；接下来的m行，每一行有三个数 ，第一个数表示长方形的编号，第二个和第三个数值大的表示长，数值小的表示宽，相等说明这是一个正方形（数据约定长宽与编号都小于10000）；输出顺序输出每组数据的所有符合条件的长方形的 编号 长 宽样例输入181 1 11 1 11 1 21 2 11 2 22 1 12 1 22 2 1样例

18、输出1 1 11 2 11 2 22 1 12 2 1/基本思路是每输入一个长方形的数据就将它与前面的长方形进行比较，如果是相同则将此数据忽略/否则查询该长方形应插入到排好序的序列中的位置，最后移位进行插入/最近常到南阳理工的ACM网站去A题了，虽然做的题大多都不是很难的，但每当做完一道题，心里都有一种说不出的愉悦。/程序本身应该也不难，应该是自己的方法选得不对才导致程序写得这么难看，改了大半天，好在最后还是AC了，还是挺开心的/程序中还多处用到了goto，,没办法呀，想从多重嵌套的for循环中一下子跳出来，还是用goto最省事了。/网上应该有很多写得更好的代码，我等下也去看看别人写的。#in

19、clude#includetypedef struct Boxint num;int length;int width;CBox;int cmp(const void *a,const void *b)CBox *aa=(CBox *)a;CBox *bb=(CBox *)b;if(aa-num!=bb-num)return aa-num-bb-num;elseif(aa-length!=bb-length)return aa-length-bb-length;elsereturn aa-width-bb-width;int main()int N,n,i,temp;CBox box10000

20、;scanf(%d,&N);while(N-)scanf(%d,&n);for(i=0;in;i+)scanf(%d%d%d,&boxi.num,&boxi.length,&boxi.width);for(i=0;in;i+)if(boxi.lengthboxi.width)temp=boxi.length;boxi.length=boxi.width;boxi.width=temp;qsort(box,n,sizeof(CBox),cmp);i=0;printf(%d %d %dn,boxi.num,boxi.length,boxi.width);i+;for(;in;i+)if(!(boxi.num=boxi-1.num&boxi.length=boxi-1.length&boxi.width=boxi-1.width)printf(%d %d %dn,boxi.num,boxi.length,boxi.width);return 0;