Noj – 在线强化训练2

Problem A九鼎之尊（一）时限：1000ms 内存限制：10000K 总时限：3000ms描述：夏朝初年，夏王大禹划分天下为九州，令九州州牧贡献青铜，铸造九鼎，将全国九州的名山大川、奇异之物镌刻于九鼎之身，以一鼎象征一州。这样，九州就成为中国的代名词。九鼎成了王权至高无上、国家统一昌盛的象征。周幽王烽火戏诸侯之后，周王室的地位快速下降，到了周赧（nǎn）王时期，天子的地位已大不如前，只是名义上的统治者了。秦武王想取而代之，周赧王说：这里有九个鼎，咱俩数鼎，每次可以数一个或者两个，谁数到最后那个“龙文赤鼎”并且把它举起来谁得天下，秦武王很高兴，就与周赧王开始数鼎。实际上周赧王知道最后那个龙文赤鼎铸造时用了很多黄金，实际重量比其它的重很多，秦武王根本就不可能举起来。秦武王霸道的说我先数：、，周王：、，秦王：、，周王：、，秦王：。按游戏规则，秦王获得了举鼎资格。世事难料，秦王居然把鼎举起来了，但是由于“龙纹赤鼎”太重了，举起来已经受了内伤，又被鼎砸伤胫骨，当晚气绝身亡。请叙述周王心理变化过程。输入：输入鼎的个正整数n。输出：假设双方都足够聪明，不会有失误，谁数到最后一个数谁输，如果先数可以必胜则输出“Yes”，否则输出“No”。输入样例：输出样例：Yes

Problem A 九鼎之尊（一）

 #include <iostream> using namespace std; int main() {     int n;     while(cin>>n)     {          == )             cout<<"No"<<endl;         else             cout<<"Yes"<<endl;     }     ; } /* n % 3: 0: 数2个（1,2） 1：X 2：数1个（1） */

代码A

这个问题可以理解为 “谁报数字n，谁输”，报数只能为1个 或 2个对于不同的n，分为“先数必输”或“先数必赢”的问题    一、假定 n% == :这会是“先数必赢”：    你如果想赢，那你要保证两点：        . 在一个回合中，要保证让对方报3的倍数；        . 3的倍数（，，9等），自己绝对不要报        . 因为最后的n也是3的倍数，所以这样继续下去的话，最后的n一定被对方报        e.g:  n=，“先数必赢”                () 你要报1，；让对方报3或者3，                () 对方若报3，你就报45；让对方报6                () 对方若报3，，你就报5；让对方报6                () 以此类推，最后一个30，必定被对方报上    二、假定 n% == :这会是“先数必输”：    这种情况下，“能被n模1的数”（，，...）是不能报的，但是如果你先数，1必定是你先报；如果对方足够聪明，那么他可以保证4，，，，n都将被你报    三、假定n% == :这会是“先数必赢”：    这种情况下，“能被n模2的数”（，，...）是不能报的，所以你可以先报1，让对方报2，只要开了这个头，就可以保证对方一直报5，，...n所以代码很简单，只需要判断 n模3等于多少就行了，，如果不明白这个规律，可以通过穷举的方式列举几个数，，可以发现“先数必输”每三个数出现一次

解析A

#include <iostream>#include <cstdio>using namespace std;int main(){    int n;    ] = {};    pot[] = ;    pot[] = ;    pot[] = ;    while(cin>>n)    {        ; i<=n; i++)        {            /*              前两个数里面，只要有一个0，就可以让对方再取必输;              除非2个都为1，那样无论你怎么取，对方再取必赢              此代码参考九鼎之尊（二）的解析            */            ] && pot[i-])) // 或if(int(pot[i-1] && pot[i-2]) == 0) int不可少            {                pot[i] = ;            }            else                pot[i] = ;        }        )            cout<<"Yes"<<endl;        else            cout<<"No"<<endl;    }    ;}

代码A – 模拟过程

Problem B九鼎之尊（二）时限：1000ms 内存限制：10000K 总时限：3000ms描述：秦人雄视天下之心，由来已久，秦武王死后，秦昭襄王即位，励精图治，继续扩张，多年之后已经具备了统一天下的实力，周赧王对秦昭襄王说：这里有n个鼎（≤n≤），咱俩轮流数鼎，谁数到最后一个鼎谁做天子（这次不用举鼎:-D），要求每次数的数量必须是1、2和4这三个数字之一。你能否写一个程序帮秦昭襄王算一下，要想取得胜利应该先数还是后数？输入：输入一个正整数n。输出：如果先数必胜则输出“Yes”,否则输出“No”。输入样例：输出样例：No

Problem B 九鼎之尊（二）

 #include <iostream> using namespace std; int main() {     int n;     while(cin>>n)     {          == )             cout<<"No"<<endl;         else             cout<<"Yes"<<endl;     }     ; }

代码B

这是谁先抢占n，谁赢的问题。每次可以报数 1个、2个、4个前几个数字（，，，）可以很简单就判断出来:n= : 必赢n= : 必赢n= : 必输n= : 必赢对于5之后的问题，可以通过前4次判断出来：n= ：    你可以理解为你先数一次，然后让对方先数必输，其实是对方是第二次数    你可以数1，，；    你若数1个，还剩4个，通过我们前面已经得出的规律，对方先数必赢（再数）    你若数2个，还剩3个，通过我们前面已经得出的规律，对方先数必输（再数）    你若数4个，还剩1个，通过我们前面已经得出的规律，对方先数必赢（再数）所以如果你足够聪明，可以通过数2赢得胜利得到：n= : 必赢n= : 必赢n= : 必输n= : 必赢n= : 必赢n= ：    你可以数1，，；你若数1个，还剩5个，对方再数必赢你若数2个，还剩4个，对方再数必赢你若数4个，还剩2个，对方再数必赢所以n= : 必输所以可以通过一个for循环，从5开始不断判断，不断丰富数组（存放规律的）....也可以通过穷举的方法，列举一些，可以发现3，，，....3n 必输

解析B

#include <iostream>#include <cstdio>using namespace std;int main(){    int n;    ] = {};    pot[] = ;    pot[] = ;    pot[] = ;    pot[] = ;    while(cin>>n)    {        ; i<=n; i++)        {            ] && pot[i-] && pot[i-]))            {                pot[i] = ;            }            else                pot[i] = ;        }        )            cout<<"Yes"<<endl;        else            cout<<"No"<<endl;    }    ;}

代码B -模拟过程

 Problem C 筛法(Sieve Method) 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 用筛法求［a，b］中的素数。 Find out the prime numbers in [a, b].  输入： 2个正整数：a b。 a、b均在1000以内，且a小于等于b。  positive integers: a, b. Both a and b are less than or equal  and a is less than or equal to b. 输出： [a b]区间内的所有素数，每个单独一行。 All primes in [a, b], each one in a row. 输入样例： 输出样例：

Problem C 筛法(Sieve Method)

 #include <iostream> #include <cmath> #include <cstring> using namespace std; int main() {     int a,b;     ];     int i,j;     memset(flag, , sizeof(flag));     while(cin>>a && cin>>b)     {         flag[] = ;         ; i<=sqrt(b); i++)         {             if(flag[i])             {                 ; j<=b/i; j++)                 {                     flag[i*j] = ;                 }             }         }         for(i=a; i<=b; i++)         {             if(flag[i])                 cout<<i<<endl;         }     }     ; }

代码C

 参考百度百科“筛法”定义： 筛法是一种简单检定素数的算法。 百度百科“筛法”代码： 以下是利用筛法求100以内素数的代码： #include<cmath> #include<cstring> #include<iostream> using namespace std; int main(int argc, char* argv[]) {     ;     ];     int i, j;     memset(a, , sizeof(a));     a[] = ;     ; i <= sqrt(n); i ++)     {         if(a[i])         {             ; j <= n/i; j ++)             {                 a[i*j] = ;             }         }     }     ; i <= n; i ++)     {         if(a[i]) cout << i << " ";     }     ; }

解析C

Problem D亲密数(close numbers)时限：2000ms 内存限制：10000K 总时限：2000ms描述：两个整数a和b，如果a的不包含自身的因子之和等于b，并且b的不包含自身的因子和等于a，且a不等于b，则称a，b为一对亲密数。找出满足a<=10000且b<=10000的全部亲密数对。A pair of close numbers(a and b) .输入：本题无输入。None输出：升序输出所有满足条件的数对，每对数字一行，小数字在前，大数字在后，用空格分隔。注意：本题要求程序效率要高，直接写成二重循环肯定超时。Output all pair of close numbers in ascending order,and each pair occupies one line with the smaller one in front and the pair is separated by a space.输入样例：无输出样例：无

Problem D 亲密数(close numbers)

 #include <iostream> using namespace std; int sum_factor(int n); int main() {     int i;     int sum1;     ; i<=; i++)     {         sum1 = sum_factor(i);         if(i<sum1 && i==sum_factor(sum1))         {             cout<<i<<" "<<sum1<<endl;         }     }     ; } /*求n的因子之和*/ int sum_factor(int n) {     ;     ; i*i<=n; i++)     {         )         {              || i*i==n)                 sum += i;             else                 sum += i + n/i;         }     }     return sum; }

代码D

Problem E求最大公约数时限：1000ms 内存限制：10000K 总时限：3000ms描述：给你两个正整数a、b，请你编写程序求出它们的最大公约数，并输出这个数 输入：两个正整数a、b输出：输出最大公约数（以回车结束）输入样例：输出样例：

Problem E 求最大公约数

 #include <iostream> using namespace std; int* divisor(int n); ; int main() {     int *d;     int a,b;     while(cin>>a && cin>>b)     {         d = divisor(a);         ;         ; i>=; i--)         {             )                 break;         }         cout<<d[i]<<endl;     }     ; } int *divisor(int n) {     ];     ; i<=n; i++)     {         )             d[num++] = i;     }     return d; }

代码E

Problem F幸运的编号时限：1000ms 内存限制：10000K 总时限：3000ms描述：有n个人围成一圈，顺序编号。从第一个人开始报数（从1到m），凡报到m的人退出。问最后一个人的编号是多少？输入：输入两个正整数n和m输出：最后一个人的编号。输入样例：输出样例：

Problem F 幸运的编号

 #include <iostream> #include <cstring> using namespace std; int main() {     int n,m;     int quit; //退出人数     ]; //    memset(p, 1, sizeof(p));     while(cin>>n && cin>>m)     {         ; //指针         ; //报数         quit = ; //退出人数         ; a<; a++)             p[a] = ;         )         {             )             {                 num++; //报数             }             if(num == m)             {                 p[i] = ;                 quit++;                 num = ;             }             i = (i+) % n;         }         ; j<n; j++)         {             )             {                 cout<<j+<<endl;                 break;             }         }     }     ; }

代码F

Problem G回文质数时限：1000ms 内存限制：10000K 总时限：3000ms描述：因为151既是一个质数又是一个回文数(从左到右和从右到左看是一样的)，所以151是回文质数．写一个程序来找出范围[a,b](<=a<b<=,,)间的所有回文质数．输入：第一行　两个整数：a和b．输出：输出一个回文质数的列表，一行一个．输入样例：输出样例：来源：USACO

Problem G 回文质数

 #include <iostream> #include <cmath> using namespace std; bool isPrime(int n); int getGigit(int n); int getPalindrome(int n); int getPalindrome_Ou(int n); int main() {     int a, b;     int num; //b的位数     int pal; //构造的回文数     while(cin>>a && cin>>b)     {         ) //若a<=11         {             &&i<=b; i++)             {                 if(isPrime(i))                     cout<<i<<endl;             }         }         num = getGigit(b); //获得b的位数，以便减少回文数生成范围         ) //因为11是唯一的回文质数，所以11-100都不用考虑,直接从三位的回文素数开始判断         {             ; i<pow(,num/+); i++)             {                 pal = getPalindrome(i);                 if(pal>=a && pal<= b)                 {                     if(isPrime(pal))                         cout<<pal<<endl;                 }             }         }     }     ; } /*通过n生成奇数位(2n-1)的回文数*/ int getPalindrome(int n) {     int palindrome = n;     n /= ;     while(n)     {         palindrome = palindrome* + n%;         n /= ;     }     return palindrome; } /*   通过n生成偶数位(2n)的回文数   但除了11不存在偶数位的回文数是素数，因为该回文数能被11整除   所以根本不需要生成偶数位的回文数，这个函数也没有必要   但是我就是写写而已... */ int getPalindrome_Ou(int n) {     int palindrome2 = n;     while(n)     {         palindrome2 = palindrome2* + n%;         n /= ;     }     return palindrome2; } /*判断n是否为素数*/ bool isPrime(int n) {     ; i<=sqrt(n); i++)     {         )         {             return false;         }     }     return true; } /*返回n有几位*/ int getGigit(int n) {     ;     while(n)     {         n /= ;         count++;     }     return count; } /* 如果通过两重循环遍历所有，无论是先判断会回文还是先判断素数，都会超时； 可以先构造出回文数，然后判断是不是素数：     除11不存在偶数位的回文数是素数，因为该回文数能被11整除，也就说明大于11的满足条件的回文数是奇数位，以中间数为对称轴。     因大于2的素数都是奇数，故在奇数位回文数中，首位为2、4、6、8的数均不是素数。首位是它们，根据回文数的性质，末尾也是他们。     因5的任何倍数末尾为5，故在奇数位回文数中，首位为5的数均不是素数。 */

代码G

Problem H选太子(select the prince)时限：1000ms 内存限制：10000K 总时限：3000ms描述：某皇帝有2m个儿子，现在要从中选出一个做太子，皇帝不知道该把那一个皇子立为太子，于是决定用下面的方法来选出太子，设每个太子的编号分别1、、、…、2m，按顺时针方向站成一个圆圈，现在从1号太子开始按顺时针方向数，数到第n个人，把他淘汰出局，然后从他的下一个人开始上述过程，当第m个人被淘汰时，转变方向继续从1开始数，重复上述过程，最后剩下的皇子将被立为太子。现在请你写一个程序，计算出几号皇子将被立为太子。输入：输入两个正整数m nInput two positive integer.输出：输出太子的编号Output the number.输入样例：输出样例：

Problem H 选太子(select the prince)

 #include <iostream> using namespace std; int main() {     int n,m;     int quit; //退出人数     ];     while(cin>>m && cin>>n)     {         ; //指针         ; //报数         quit = ; //退出人数         ; a<; a++)             p[a] = ;         *m-)         {             )             {                 ++num; //报数             }             if(num == n)             {                 p[i] = ;                 ++quit;                 num = ;             }             if(quit < m)             {                 i = (i+) % (*m);             }             else             {                 i = (i-) % (*m);                 )                 {                     i = i + *m;                 }             }         }         ; j<*m; j++)         {             )             {                 cout<<j+<<endl;                 break;             }         }     }     ; }

代码H

Problem I甲说乙在说谎时限：1000ms 内存限制：10000K 总时限：3000ms描述：甲说乙在说谎，乙说丙在说谎，丙说甲、乙在说谎。只有一个人说真话。问，谁说真话？A、甲；B、乙；C、丙；D、没有人说真话编程求解谁说的是真话。输入：无输出：输出说真话的人（甲、乙、丙分别用0、1和2来表示）输入样例：无输出样例：

Problem I 甲说乙在说谎

 #include <iostream> using namespace std; int main() {     int a,b,c;     ; a<; a++)     {         ; b<; b++)         {             ; c<; c++)             {                  || !c&&a+b!=))                 {                     )                         cout<<<<endl;                     )                         cout<<<<endl;                     )                         cout<<<<endl;                 }             }         }     }     ; }

代码I

Problem J合并有序数组(Merging sorted array)时限：1000ms 内存限制：10000K 总时限：3000ms描述：给你两个有序且升序的数组，请你把它们合成一个升序数组并输出Give you two ordered ascending array, you put them into one ascending array and output.输入：第一行为一个正整数n，n<= ；第二行为n个数字，这n个数字用空格隔开第三行为一个正整数m，m<= ；第四行为M个数字，这m个数字用空格隔开The first line ;The second line are n numbers separated by spaceThe third ;The fourth line are m numbers separated by space输出：输出合并后的数组，每个数字占一行，Output the combined array, each number per line,输入样例：输出样例：

Problem J 合并有序数组(Merging sorted array)

 #include <iostream> using namespace std; int main() {     int n, m, i;     ];     cin>>n;     ; i<n; i++)     {         cin>>arr[i];     }     cin>>m;     for(i=n; i<m+n; i++)     {         cin>>arr[i];     }     int temp;     ; i<m+n-; i++)     {         ; j<m+n--i; j++)         {             ])             {                 temp = arr[j];                 arr[j] = arr[j+];                 arr[j+] = temp;             }         }     }     ; i<m+n; i++)     {         cout<<arr[i]<<endl;     }     ; }

代码J

 #include <iostream> using namespace std; int main() {     int n, m, i;     ];     cin>>n;     ; i<n; i++)     {         cin>>arr[i];     }     cin>>m;     for(i=n; i<m+n; i++)     {         cin>>arr[i];     }     int temp;     ; i<m+n; i++)     {         ; j<m+n; j++)         {             if(arr[i]>arr[j])             {                 temp = arr[i];                 arr[i] = arr[j];                 arr[j] = temp;             }         }         cout<<arr[i]<<endl;     }     ; }

代码2

代码1是冒泡排序（排完再循环打印），代码2是选择排序（可以一边排，一边打印）

Problem K叙拉古猜长度时限：1000ms 内存限制：10000K 总时限：3000ms描述：叙拉古猜想又称科拉兹猜想、哈塞猜想、3n+1猜想、乌拉姆猜想或角谷猜想，是指对于每一个大于1的正整数，如果它是奇数，则将其乘3加1，如果它是偶数，则将除以2，如此循环，最终将得到1。输入一个数，求按照叙拉古猜想到达1的序列的长度。输入：大于2的自然数。输出：输出序列长度。输入样例：输出样例：

Problem K 叙拉古猜长度

 #include <iostream> using namespace std; int main() {     int n, num;     while(cin>>n)     {         num = ;         )         {              == )                 n /= ;             else                 n = (*n) + ;             num++;         }         cout<<num+<<endl;     }     ; }

代码K

Problem L八皇后的冲突问题时限：1000ms 内存限制：10000K 总时限：3000ms描述：八皇后问题是在8*8的国际象棋的棋盘上放置8个皇后，有多少种不同的放置方法，要求它们互相都不冲突（冲突是指在某一行或者某一列或者某一条斜线上出现两个皇后，因为这两个皇后可以互相吃掉对方）。其中行号和列号都从0开始。现在前三行（~2行）每行一个皇后已经放置好的情况下，第3行的皇后想要放在给定的列，需要你编一个程序判断它是否与前三行的皇后冲突。输入：首先输入3行8列数据(~2行，~7列)，1表示有皇后，0表示没有皇后然后输入第3行要摆放的皇后的列号。输出：第3行所给的列号处如果能放皇后，则输出Yes换行，不可以的话输出No，注意要有回车。输入样例：输出样例：Yes

Problem L 八皇后的冲突问题

 #include <iostream> using namespace std; int main() {     ][];     int n;     ; i<; i++)     {         ; j<; j++)         {             cin>>queen[i][j];         }     }     int flag;     while(cin>>n)     {         flag = ;         //判段列上有没有皇后         ; i<; i++)         {             )             {                 flag = ; //                cout<<"列"<<endl;             }         }         //判断左斜有没有皇后         ,j=n-; i>=,j>=; i--,j--)         {             )             {                 flag = ; //                cout<<"zuo"<<endl;             }         }         //判断右斜有没有皇后         ,j=n+; i>=,j<; i--,j++)         {             )             { //                cout<<"you"<<endl;                 flag = ;             }         }         if(flag)             cout<<"Yes"<<endl;         else             cout<<"No"<<endl;     }     ; }

代码L