Noj - 在线强化训练3

状态 题号 竞赛题号 标题
  1091 A 求解逆波兰表达式(Calculate the reverse Polish notation)
  1017 B 数列
  1323 C 穷举n位二进制数
  1579 D 三阶幻方
  1324 E 穷举所有排列
  1203 F 装盘子
  1216 G 大数乘法
  1007 H 8皇后问题
  1004 I 0-1背包问题
  1551 J 求给定一组数能构造多少个素数环
  1141 K 走迷宫
  1142 L 踩气球
Problem A
求解逆波兰表达式(Calculate the reverse Polish notation)
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

编写函数int add(char s[]);计算字符串形式的逆波兰表达式(即两个操作数在前,计算符在后)。本题内,保证每个操作数均为1位数。操作符有'+','-','*','/'四种。且保证计算过程中除法运算全部为整数除法,结果为整数。
如23+*,,结果20
Write a function -digit. The operator have only four: '+', '-', '*', '/'. And to ensure that the division operation in the calculation process for all the integer division, the result is an integer.
Such +*, the result . 

输入:

一行字符串,长度不超过20。
Input a  characters. 

输出:

逆波兰表达式的计算结果。
Output the result of reverse Polish notation.

输入样例:

+*
输出样例:

Problem A 求解逆波兰表达式(Calculate the reverse Polish notation)

 #include <iostream>
 #include <cmath>
 #include <stack>
 using namespace std;
 int calc(int a, int b, char op);
 int main()
 {

     stack<int> s;
     ];
     cin >> str;
     ;
     int n1, n2, temp;;
     while(str[i] != '\0')
     {
         //若为数字
         if(isdigit(str[i]))
         {
             s.push(str[i++] - ');
         }
         else //若为操作符
         {
             n2 = s.top();
             s.pop();
             n1 = s.top();
             s.pop();
             temp = calc(n1, n2, str[i++]);
             s.push(temp);
         }
     }
     cout<<s.top()<<endl;

     ;
 }

 int calc(int a, int b, char op)
 {
     if(op == '+')
         return a+b;
     else if(op == '-')
         return a-b;
     else if(op == '*')
         return a*b;
     else if(op == '/')
         return a/b;
 }

A代码 - 栈

 #include <iostream>
 #include <cmath>
 using namespace std;
 int calc(int a, int b, char op);
 int main()
 {
     ];
     cin >> str;
     int n1, n2;
     n1 = str[] - ';
     ;
     while(str[i] != '\0')
     {
         //若为数字
         if(isdigit(str[i]))
         {
             n2 = str[i] - ';
         }
         else //若为操作符
         {
             n1 = calc(n1, n2, str[i]);
         }
         i++;
     }
     cout<<n1<<endl;
     ;
 }

 int calc(int a, int b, char op)
 {
     if(op == '+')
         return a+b;
     else if(op == '-')
         return a-b;
     else if(op == '*')
         return a*b;
     else if(op == '/')
         return a/b;
 }

 /*
     例如这种输入:
                     521--
     标准输出:4
     用户输出:3

     此程序无法解决类似于 "521--" 的表达式
 */

A代码 - 不用栈(错了)

Problem B
数列
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

已知k阶裴波那契数列的定义为f0=,f1=,…,fk-=, fk-=; fn=fn-+fn-+…+fn-k,n=k,k+,…,试编写求k阶裴波那契数列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。

输入:

输入两个正整数k m(其中1<k<m,本题所有数据都在长整形数据的范围之内)

输出:

输出k阶裴波那契数列的第m项值fm。

输入样例:

(注意:本题所涉及的所有数据都在长整形数据的范围之内)
输出样例:

Problem B 数列

 #include <iostream>
 #include <cmath>
 using namespace std;
 long fun(int k, int m);

 int main()
 {
     long k1, m1;
     while(cin>>k1 && cin>>m1)
     {
         cout<<fun(k1, m1)<<endl;
     }
     ;
 }

 long fun(int k, int m)
 {
     ;
      && m<=k-)
         fm = ;
     )
         fm = ;
     else
     {
         ; i++)
         {
             fm += fun(k, i);
         }
     }
     return fm;
 }

 /*
 __int64 和 long long都报错
 */

代码B

Problem C
穷举n位二进制数
时限:100ms 内存限制:10000K 总时限:300ms
描述:

输入一个小于20的正整数n,要求按从小到大的顺序输出所有的n位二进制数,每个数占一行。

输入:

输入一个小于20的正整数n。

输出:

按从小到大的顺序输出所有的n位二进制数,每个数占一行。

输入样例:

输出样例:

Problem C 穷举n位二进制数

 #include <iostream>
 #include <cmath>
 #include <cstring>
 using namespace std;

 int main()
 {
     int n;
     ];
     int temp, i, j;
     memset(a, , sizeof(a));
     while(cin>>n)
     {
         /* 先输出第一个全0*/
         ; i<n; i++)
         {
             cout<<;
         }
         cout<<endl;
         /*从1,开始到2的n次方-1,以此打印*/
         ; i<pow(,n); i++)
         {
             memset(a, , sizeof(a));
             j = ;
             temp = i;
             //十进制转二进制,并存进数组
             while(temp)
             {
                 a[j] = temp % ;
                 temp /= ;
                 j++;
             }
             ; j>=; j--)
             {
                 cout<<a[j];
             }
             cout<<endl;
         }
     }
     ;
 }

代码C

Problem D
三阶幻方
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

三阶幻方是最简单的幻方,又叫九宫格,是由1,,,,,,,,9九个数字组成的一个三行三列的矩阵,其对角线、横行、纵向的的和都为15。

输入:

无

输出:

按字典序输出所有的满足条件的幻方矩阵,每两个数字之间带一个空格,行尾无空格,每个幻方后带一个空行。

输入样例:

无
输出样例:

无

Problem D 三阶幻方

 #include <iostream>
 using namespace std;

 void printMatrix();
 void testMatrix();
 void create(int n);
 ][]; // 矩阵
 ]; // 1-9 是否被使用

 int main()
 {
     create();
     ;
 }

 /*回溯生成所有矩阵*/
 void create(int n)
 {
     int num; //数字1-9
     )
     {
         testMatrix();
     }
     else
     {
         ; num<=; num++)
         {
             if(!isUsed[num])
             {
                 a[n/][n%] = num;
                 isUsed[num] = ; //已使用过不能再次使用
                 create(n+); //生成第一个
                 isUsed[num] = ; //回溯时使isUsed[i]恢复原值
             }
         }
     }
 }

 /*判断矩阵是否为三阶幻方*/
 void testMatrix()
 {
     ;
     ; i<; i++)
     {
         //判断行和列
         ]+a[i][]+a[i][] !=  || a[][i]+a[][i]+a[][i] != )
         {
             f = ;
             break;
         }
     }
     if(f)
     {
         //判断两条对角线
         ][]+a[][]+a[][] !=  || a[][]+a[][]+a[][] != )
         {
             f = ;
         }
     }
     if(f)
         printMatrix();
 }

 /*打印矩阵*/
 void printMatrix()
 {
     ; i<; i++)
     {
         ; j<; j++)
         {
             cout<<a[i][j]<<" ";
         }
         cout<<a[i][]<<endl;
     }
     cout<<endl;
 }

代码D

Problem E
穷举所有排列
时限:100ms 内存限制:10000K 总时限:300ms
描述:

输入一个小于10的正整数n,按把每个元素都交换到最前面一次的方法,输出前n个小写字母的所有排列。

输入:

输入一个小于10的正整数n。

输出:

按把每个元素都交换到最前面一次的方法,输出前n个小写字母的所有排列。

输入样例:

输出样例:

abcacbbacbcacbacab

Problem E 穷举所有排列

 #include <iostream>
 using namespace std;
 void array(int m);
 ];
 int n;
 int main()
 {
     /*构造字符数组*/
     ; i<; i++)
     {
         letter[i] =  + i;
     }
     while(cin>>n)
     {
         array();
     }
     ;
 }

 /*回溯法*/
 void array(int m)
 {
     int i;
     if(m == n)
     {
         ; i<n; i++)
         {
             cout<<letter[i];
         }
         cout<<endl;
     }
     else
     {
         for(i=m; i<n; i++) //每个元素打头一次
         {
             swap(letter[m],letter[i]);
             array(m+);
             swap(letter[m],letter[i]);
         }
     }
 }

代码E

Problem F
装盘子
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

N人为了大快朵颐,行至云餐二楼,取了N个盘子,打了M个饺子。现欲将M个饺子装入N个盘子中,试问共有多少种不同的装法?
假设盘子足够大,并且盘子里可以什么都不放。注意像2  0和5  2之类的属于同一种放法。

输入:

两个整数M、N(=< M,N <=)以空格隔开。

输出:

单独一行输出共有几种装法。

输入样例:

输出样例:

Problem F 装盘子

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 using namespace std;

 void  push(int m, int n);
 ][];
 int main()
 {
     int m, n;

     while(cin>>m && cin>>n)
     {
         ; i <= ; i++)
         {
             dish[i][] = ;
             dish[][i] = ;
             dish[i][] = ;
             dish[][i] = ;
         }
         push(m, n);
         int num = dish[m][n];
         cout<<num<<endl;
     }
     ;
 }

 void  push(int m, int n) //根据数学意义推出的递推方程遍历打表
 {
     ; i <= ; i++)
     {
         ; j <= ; j++)
         {
             )
                 continue;
             if(i >= j)
             {
                 ; k <= j; k++)
                 {
                     dish[i][j] += dish[i - k][k];
                 }
             }
             else
             {
                 dish[i][j] = dish[i][i];
             }
         }
     }
 }

 /*
 错误思路:递归因为迭代层数太多,很容易导致栈溢出,俗称爆栈,还费时间。

 此题关键在于求出递推方程式或状态转移方程,可以根据数学意义推导出公式:
 1:定义函数C(m,n)的数学意义为向n个盘子里放入m个饺子,盘子可空;
 2:定义函数K(m,n)的数学意义为向n个盘子里放入m个饺子,但是盘子不可空,即每个盘子至少有一个饺子;
 3:显然有:c(m,n) = k(m,1) + k(m,2) + ... + k(m,n)——数学意义即:所有情况 = 空n-1个盘子的情况+空n-2个盘子的情况+...+不空的情况;
    注意,这样分解问题是可以做到一定没有重复情况干扰答案的。

 4:显然还有:k(m,n) = c(m-n, n);————数学意义即:盘子不为空的情况数 = 先用n个饺子填满每一个盘子后剩下m-n个饺子随意放在n个盘子中;

 5: 联立以上两个方程可求出状态转移方程如下:
     c(m,n) = c(m-1,1) + c(m-2,2) + ... + c(m-n,n);——注意边界值0、1的情况应该需要单独考虑;

 6: 得到方程后,直接打表,将所有C(m,n)情况计算出来,时间复杂度应为(100 * 100 (1 + ... + 100))*o(1) = 50500000*o(1),
    方案可行。
 */

代码F

Problem G
大数乘法
时限:100ms 内存限制:10000K 总时限:1000ms
描述:

计算两个大整数的乘积。

输入:

输入有两行,第一行单独一个大整数A,第二行单独一个大整数B。每个数的长度不超过1000。

输出:

单独一行输出A,B的精确乘积。结果请注意换行。

输入样例:

输出样例:

Problem G 大数乘法

 #include<iostream>
 #include<cstring>
 using namespace std;

 void multiply(int len1, int len2);
 ];
 ];
 ]; //相乘后的位数不会超过a+b

 int main()
 {
     ];
     ];
     int len_A, len_B;
     int len1, len2;
     int i, j;

     while(cin>>str_A && cin>>str_B)
     {
         memset(mul,,sizeof(mul));
         len_A = ;
         len_B = ;
         i = ;
         j = ;
         while(str_A[len_A] != '\0')
         {
             len_A++; //计算A的长度
         }
         while(str_B[len_B] != '\0')
         {
             len_B++; //计算B的长度
         }
         len1 = len_A;
         len2 = len_B;
         while(len_A)
         {
             A[i++] = str_A[--len_A] - '; //字符数组倒序转int数组
         }
         while(len_B)
         {
             B[j++] = str_B[--len_B] - '; //字符数组倒序转int数组
         }
         multiply(len1, len2);
     }
     ;
 }
 void multiply(int len1, int len2)
 {
     ; i<len1; i++)
     {
         ; j<len2; j++)
         {
             mul[i+j] += A[i] * B[j];
         }
     }
     ; //mul的下标从0开始,len1和len2是从1开始
      || mul[t]!=)
     {
         )
         {
             mul[t+] += mul[t]/;
             mul[t] = mul[t]%;
         }
         t++;
     }
     )
     {
         t--;
         cout<<mul[t];
     }
 //    for(int i=t; i>=0; i--)
 //    {
 //        if(t==len1+len2-1)
 //        {
 //            if(mul[t] == 0)
 //            {
 //                ;
 //            }
 //            else
 //            {
 //                cout<<mul[i];
 //            }
 //        }
 //        else
 //        {
 //            cout<<mul[i];
 //        }
 //    }
     cout<<endl;
 }

代码G

Problem H
8皇后问题
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

输出8皇后问题所有结果。

输入:

没有输入。

输出:

每个结果第一行是No n:的形式,n表示输出的是第几个结果;下面8行,每行8个字符,‘A’表示皇后,‘.’表示空格。不同的结果中,先输出第一个皇后位置靠前的结果;第一个皇后位置相同,先输出第二个皇后位置靠前的结果;依次类推。

输入样例:

输出样例:

输出的前几行:No :A...........A..........A.....A....A...........A..A.........A....No :A............A.........A..A...........A....A.....A..........A...

Problem H 8皇后问题

 #include <iostream>
 #include <cmath>
 using namespace std;
 void search(int m);
 int compare(int row, int col);
 void printQueen();
 void printQueen2();

 ; //代表N皇后
 ]; //数字代表存放皇后的列数;
 ; //结果编号

 int main()
 {
     search();
     ;
 }

 /*假设前m-1行已经摆放好了,从m行穷举所有情况*/
 void search(int m)
 {
     if( m== N)
     {
         count++;
         printQueen(); //输出
     }
     else
     {
         ; i<; i++)
         {
             //判断第m行,第i列
             if(compare(m,i))
             {
                 //存放皇后
                 queen[m] = i;  //代表第m行第i列存放皇后;
                 search(m+);
                 /*
                    理论上下一步需要去掉皇后;
                    但是因为存放皇后的时候,会直接覆盖掉上一个皇后
                    所以不需要那一步(正常回溯是需要有这一步来恢复原值的)
                 */
             }
         }
     }
 }

 int compare(int row, int col)
 {
     ; //1代表可以存放皇后
     /*判断前row-1行*/
     ; i<row; i++)
     {
         /*
         判断列和对角线,行不用判断
           对角线通过两个元素的行列互减判断
         */
         if(queen[i]==col || abs(queen[i]-col)==row-i)
         {
             flag = ;
             break;
         }
     }
     return flag;
 }

 void printQueen()
 {
     int j;
     cout<<"No "<<count<<":"<<endl;
     ; i<N; i++)
     {
         ; j<queen[i]; j++)
         {
             cout<<".";
         }
         cout<<"A";
         ; j<N; j++)
         {
             cout<<".";
         }
         cout<<endl;
     }
 }

 /*另一种打印方法*/
 void printQueen2()
 {
     cout<<"No "<<count<<":"<<endl;
     ; i<N; i++)
     {
         ; j<N; j++)
         {
             if(j==queen[i])
                 cout<<"A";
             else
                 cout<<".";
         }
         cout<<endl;
     }
 }

代码H

Problem I
-1背包问题
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。

输入:

多个测例,每个测例的输入占三行。第一行两个整数:n(n<=)和c,第二行n个整数分别是w1到wn,第三行n个整数分别是p1到pn。
n 和 c 都等于零标志输入结束。

输出:

每个测例的输出占一行,输出一个整数,即最佳装载的总价值。

输入样例:

输出样例:

Problem I 0-1背包问题

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 void search(int m);

 int n, c;
 ], p[];
 int sumW, sumP, maxP;

 int main()
 {
     while(cin>>n>>c)
     {
          && c==)
         {
             break;
         }
         ; i<n; i++)
         {
             cin>>w[i];
         }
         ; i<n; i++)
         {
             cin>>p[i];
         }
         sumP = ; //目前总价值
         sumW = ; //目前总重量
         maxP = ; //最大质量

         search();
         cout<<maxP<<endl;

     }

     ;
 }

 void search(int m)
 {
     if(m == n) //搜索到了最底层
     {
         if(sumW <= c)
         {
             maxP = max(maxP, sumP); //一直保留所有结果的最大值
         }
     }
     else
     {
         search(m+);//不装m,直接去装m+1
         if(sumW <= c)
         {
             sumP += p[m];
             sumW += w[m];
             search(m+); //装完m之后再去装m+1
             /*
               你加完m之后的状态已经传递到下一层了;
               为什么要删除m呢?
               是因为那棵树有很多分支,如果不删掉,再计算其他分支的时候,会将之前分支的sumP和sumW带过去
               由于那个状态已经传递到下一层了,所以删掉之后,不影响此分支的计算。
             */
             sumP -= p[m];
             sumW -= w[m];
         }
     }
 }

代码I

Problem J
求给定一组数能构造多少个素数环
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

给定一组正整数,把他们排成一个环,任意相邻的两个数之和为素数的环称为素数环,问这组数能构成多少个素数环?

输入:

先输入一个小于等于16的正整数n,然后输入给定的n个不相同的小于等于16的正整数。

输出:

输出这组数能够成的不同的素数环的个数。

输入样例:

输出样例:

Problem J 求给定一组数能构造多少个素数环

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 using namespace std;

 int isPrime(int k);
 void creatPrime();
 void search(int m);

 ]; //存放32以内的所有素数,prime[i]=1,代表i是素数
 int n;
 ];
 int countRing; //存储素数环的个数
 int main()
 {
     creatPrime();
     while(cin>>n)
     {
         countRing = ;
         ; i<n; i++)
         {
             cin>>num[i];
         }
         /*
           注意一定要从1开始,因为search函数中调用了num[m-1],如果从0开始,会发生数组越界
           而且因为这是一个环,里面的元素无先后顺序,所以无论谁在第1个位置上都无所谓,第1个位置不需要遍历所有
         */
         search();
         cout<<countRing<<endl;
     }
     ;
 }

 /*回溯法*/
 void search(int m)
 {
     if(m==n)
     {
         ]+num[n-]])
         {
             countRing++;
         }
     }
     else
     {
         for(int i=m; i<n; i++)
         {
             ];
             if(prime[temp])
             {
                 swap(num[i], num[m]);
                 search(m+);
                 swap(num[i], num[m]);
             }
         }
     }
 }

 void creatPrime()
 {
     ; i<=; i++)
     {
         prime[i] = isPrime(i);
     }
 }

 int isPrime(int k)
 {
     ;
     ; i<=sqrt(k); i++)
     {
         )
         {
             flag = ;
             break;
         }
     }
     return flag;
 }

代码J

Problem K
走迷宫
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

判断是否能从迷宫的入口到达出口

输入:

先输入两个不超过20的正整数表示迷宫的行数m和列数n,再输入口和出口的坐标,最后分m行输入迷宫,其中1表示墙,0表示空格每个数字之间都有空格。

输出:

只能向上、下、左、右四个方向走若能到达,则输出"Yes",否则输出"No",结果占一行。

输入样例:

输出样例:

Yes

Problem K 走迷宫

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 using namespace std;

 void DFsearch(int a, int b);
 int m, n;
 int beginX, beginY;
 int endX, endY;
 ][]; //迷宫矩阵
 int flag; //是否可以走出
 ][];  //是否已经走过
 ][] = {{,},{,},{-,},{,-}}; //用来控制上下左右
 int main()
 {
     while(cin>>m>>n)
     {
         flag = ;
         memset(visited,,sizeof(visited)); //初始情况下,什么节点都未访问
         memset(matrix,,sizeof(matrix)); //迷宫全都初始化为1,这样未初始化的地方就都是墙壁

         cin>>beginX>>beginY;
         cin>>endX>>endY;

         ; i<m; i++)
         {
             ; j<n; j++)
             {
                 cin>>matrix[i][j]; //初始化迷宫
             }
         }
         DFsearch(beginX, beginY);
         if(flag)
             cout<<"Yes"<<endl;
         else
             cout<<"No"<<endl;
     }
     ;
 }

 void DFsearch(int a, int b)
 {
     if(a==endX&&b==endY)
     {
         flag = ;
     }
     else
     {
         visited[a][b] = ;
         ; k<; k++)
         {
             ];
             ];
             if(!visited[nextX][nextY] && !matrix[nextX][nextY])//当下一个节点没有被访问而且不是墙壁(1)时
                 DFsearch(nextX, nextY);
         }
     }
 }

代码K

Problem L
踩气球
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:

六一儿童节,小朋友们做踩气球游戏,气球的编号是1~,两位小朋友各踩了一些气球,要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负,判断的规则是这样的:如果两人都说了真话,数字大的人赢;如果两人都说了假话,数字大的人赢;如果报小数字的人说的是真话而报大数字的人说谎,则报小数字的人赢(注意:只要所报的小数字是有可能的,即认为此人说了真话)。

输入:

输入为两个数字, 0表示结束;

输出:

输出为获胜的数字。

输入样例:

输出样例:

Problem L 踩气球

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 using namespace std;

 void dfSearch(int sm, int bg, int k);

 int small, big;
 int flag_small, flag_big;

 int main()
 {

     while(cin>>small>>big)
     {
          && big==)
         {
             break;
         }
         flag_big = ;
         flag_small = ;
         if(small > big)
             swap(small, big);

         dfSearch(small, big, );

         /*
           如果small说真的 且 二人不匹配,则small赢;
           否则big赢
         */
         if(flag_small && !flag_big)
             cout<<small<<endl;
         else
             cout<<big<<endl;;
     }
     ;
 }

 void dfSearch(int sm, int bg, int k)
 {
     )
     {
         flag_small = ;
         )
             flag_big = ;
     }
      || (flag_big&&flag_small))
         return;
     )
     {
         dfSearch(sm, bg/k, k-);
     }
     )
     {
         dfSearch(sm/k, bg, k-);
     }
     dfSearch(sm, bg, k-);
 }

代码L

上一篇:A + B Again 2057 有符号的64进位的运算


下一篇:Android 7.1.1 系统截屏