九度OJ&北邮机试题（2010计算机） - c++编程基础

题目一、九度OJ-1169：比较奇偶数个数

www.2cto.com

题目描述：

第一行输入一个数，为n，第二行输入n个数，这n个数中，如果偶数比奇数多，输出NO，否则输出YES。

输入：

输入有多组数据。
每组输入n，然后输入n个整数（1<=n<=1000）。

输出：

如果偶数比奇数多，输出NO，否则输出YES。

样例输入：

5
1 5 2 4 3

样例输出：

YES

直接来代码：

AC代码：

/**
  *@xiaoran
  */
#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define LL long long using namespace std; int main() { int a,even,odd,n; while(cin>>n){ even=odd=0; for(int i=0;i
              
               >a; if(a%2) even++; else odd++; } if(odd>even) cout<
               
                 题目二、九度OJ-1170：找最小数
                ?
                http://ac.jobdu.com/problem.php?pid=1170
                ? 
                题目描述：
                第一行输入一个数n，1 <= n <= 1000，下面输入n行数据，每一行有两个数，分别是x y。输出一组x y，该组数据是所有数据中x最小，且在x相等的情况下y最小的。 
                输入：
                输入有多组数据。 每组输入n，然后输入n个整数对。 
                输出：
                输出最小的整数对。 
                样例输入：
                5  
3 3  
2 2  
5 5  
2 1  
3 6 
                样例输出： 
                2 1 不解释，AC代码 
                ? 
                ? 
                /**
  *@xiaoran
  *排序或者直接比较，排序O(nlogn),空间O(2n),直接O(n),空间O(1)
  */
#include
                 
                  
#include
                  
                    #include
                    #include
                    
                      #include
                     
                       #include
                      
                        #include
                       
                         #include
                        
                          #include
                         
                           #include
                          
                            #include
                           
                             #include
                            
                              #define LL long long using namespace std; int main() { int n,x,y,xmin,ymin; while(cin>>n){ cin>>xmin>>ymin; for(int i=1;i
                             
                              >x>>y; if(x
                              
                                题目三、九度OJ-1171：C翻转
                               ?
                               http://ac.jobdu.com/problem.php?pid=1171
                               ? 
                               题目描述：
                               首先输入一个5 * 5的数组，然后输入一行，这一行有四个数，前两个代表操作类型，后两个数x y代表需操作数据为以x y为左上角的那几个数据。






                               操作类型有四种： 1 2 表示：90度，顺时针，翻转4个数 1 3 表示：90度，顺时针，翻转9个数 2 2 表示：90度，逆时针，翻转4个数 2 3 表示：90度，逆时针，翻转9个数 
                               输入：
                               输入有多组数据。 每组输入一个5 * 5的数组，然后输入一行，这一行有四个数，前两个代表操作类型，后两个数x y代表需操作数据为以x y为左上角的那几个数据。 
                               输出：
                               输出翻转后的数组。 
                               样例输入：
                               1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
1 3 1 1 
                               样例输出： 
                               11 6 1 4 5
12 7 2 9 10
13 8 3 14 15
16 17 18 19 20
21 22 23 24 25 题目分析： 
                               ? 
                               二维数组模拟的问题，仔细想都能搞定。 
                               ? 
                               AC代码： 
                               ? 
                               #include
                                
                                 
#include
                                 
                                   using namespace std; int a[10][10],b[10][10]; //ok表示旋转方式,x,y,表示旋转数组的左上角下标,k表示旋转个数 void XuanZhuan(int ok,int k,int x,int y){ memcpy(b,a,sizeof(a)); if(ok==2){//逆时针旋转 int ky,kx=x; for(int j=y;j
                                  
                                   =0;i--){ a[i][j]=b[kx][ky++]; } kx++; } } else if(ok==1){//顺时针旋转 int ky,kx=x+k-1; for(int j=y;j
                                   
                                    >a[1][1]){ for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if((i+j)!=2) cin>>a[i][j]; } } cin>>ok>>k>>x>>y; XuanZhuan(ok,k,x,y); for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(j!=5) cout<
                                    
                                      题目四、九度OJ-1172：哈夫曼树
                                     ?
                                     http://ac.jobdu.com/problem.php?pid=1172
                                     ? 
                                     题目描述：
                                     哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。 
                                     输入：
                                     输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。 
                                     输出：
                                     输出权值。 
                                     样例输入：
                                     5  
1 2 2 5 9 
                                     样例输出： 
                                     37 题目分析： 
                                     ? 
                                     可以建立哈弗曼树，但是题目只让求权值，直接上优先队列就行了，当然也可以排序，因为数据太少，怎么都行。 
                                     ? 
                                     AC代码： 
                                     ? 
                                     /**
  *@xiaoran
  *优先队列
  */
#include
                                      
                                       
#include
                                       
                                         #include
                                         #include
                                         
                                           #include
                                          
                                            #include
                                           
                                             #include
                                            
                                              #include
                                             
                                               #include
                                              
                                                #include
                                               
                                                 #include
                                                
                                                  #include
                                                 
                                                   #define LL long long using namespace std; int main() { int n; while(cin>>n){ priority_queue
                                                  
                                                   ,greater
                                                   
                                                     > p; int ans=0,x; for(int i=0;i
                                                    
                                                     >x; p.push(x); } while(p.size()>1){ int a=p.top(); p.pop(); int b=p.top(); p.pop(); ans+=a+b; p.push(a+b); } cout<
                                                     
                                                      ?