2017 Multi-University Training Contest - Team 5——HDU6095&&HDU6090&&HDU-白红宇

2017 Multi-University Training Contest - Team 5——HDU6095&&HDU6090&&HDU

阅读量：5169 次

发布时间：2019-06-13

本文共 3002 字，大约阅读时间需要 10 分钟。

HDU6095——Rikka with Competition

题目链接：

题目意思：抱歉虽然是签到题，现场真的没做出来，因为题目没看懂，题目说明现在给出n个选手的能力值，现在举办n-1场比赛，如果每场比赛中选出的两名选手之间能力的差大于k，则能力高的人获胜，否则两个人都获胜，问最后有多少人获胜了。（注：如果他如果有人可以击败他，则就不算获胜）

代码：从代码里面我们看出，先对n个选手的能力值排序，然后ct=1，然后从大到小两两相邻比较。如果有一组相邻的差大于k，则说明前面的所有选手都会被击败，获胜的人就是当前ct的值，否则ct++。

1 //Author: xiaowuga 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 #include 
                
                 13 #include 
                 
                  14 #define maxx INT_MAX15 #define minn INT_MIN16 #define inf 0x3f3f3f3f17 #define mem(s,ch) memset(s,ch,sizeof(s))18 #define nc cout<<"nc"<
                  
                   >T;29 while(T--){30 II n,k;31 cin>>n>>k;32 for(II i=0;i
                   
                    >a[i];33 sort(a,a+n); 34 II ct=1;35 for(II i=n-1;i>=1;i--){36 if(a[i]-a[i-1]<=k) ct++;37 else break;38 }39 cout<
                    
                     <

View Code

HDU6090——Rikka with Graph

题目链接：

题目意思：给出n个点，m条边，构成一个无向图，使得任意两个点之间的之间的距离之和，两个联通的点之间距离等于他们之间需要经过的边数，两个不连通的点之间的距离是n，求这个距离和的最小值。

思路：首先明确一点可以联通的两个点之间的距离要么是1，要么是2，我也不知道怎么说，反正就是xjb贪心，我们思考一个问题如果m==n-1，那么刚好是一棵树，这个时候最小的距离一定是形成一棵一个根连着n-1个点的数。我们根据这一点分成以下这四种情况

1.n*(n-1)/2<=m：这种情况下，m的数量足以形成一个完全图。

2.m>n-1&&m<n*(n-1)/2：这种情况下，足以形成一棵树，但是不足以形成一个完全图。

3.m==n-1：这种情况下刚好形成一棵树

4.m<n-1：这种情况下不够形成一棵树，我们可肯定在边够的范围内先构造一个树，剩下的之间距离是n，xjb往上加就好了。

代码：

1 //Author: xiaowuga 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 #include 
                
                 13 #include 
                 
                  14 #define maxx INT_MAX15 #define minn INT_MIN16 #define inf 0x3f3f3f3f17 #define mem(s,ch) memset(s,ch,sizeof(s))18 #define nc cout<<"nc"<
                  
                   >T;29 while(T--){30 cin>>n>>m;31 if(n*(n-1)/2<=m){32 cout<
                   
                    <
                    
                     n-1&&m

View Code

HDU6092——Rikka with Subset

题目链接：

题目意思：给出n，m，n表示A数组元素的数量，m表示A数组的元素之和，给出一个B数组，下标从0-m，代表原来A数组（具有n个数）中和为i（代表B数组中的下标）的子集数量，现在要还原A数组，将A数组的元素从小到大输出。

思路：比赛的时候没想出来，看了题解说是一个反向背包，于是反向推了一下。我们假设A数组的第i个是x，那么对于B数组的影响就是所有 B[i]都增加了B[i-x]，表示原来集合和等于i-x的因为多了A中的第i个数x，使得集合和为i的数量怎么加了原来B数组中B[i-x]的数量。然后我们想当与反向推，就像题解里面说的每次对于A数组中的每一个数，我们都把B数组从1扫到m，发现的第一个不等于0的数就是，就是当前剩余的元素里面最小的一项，具体看代码吧！

代码：

1 //Author: xiaowuga 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 #include 
                
                 13 #include 
                 
                  14 #define maxx INT_MAX15 #define minn INT_MIN16 #define inf 0x3f3f3f3f17 #define mem(s,ch) memset(s,ch,sizeof(s))18 #define nc cout<<"nc"<
                  
                   >T;31 while(T--){32 cin>>n>>m; 33 mem(B,0);34 mem(ans,0);35 for(II i=0;i<=m;i++) cin>>B[i];36 for(II i=1;i<=n;i++){37 for(II j=1;j<=m;j++){38 if(B[j]!=0){39 ans[i]=j;40 for(II k=j;k<=m;k++){41 B[k]-=B[k-j];42 }43 break;44 }45 }46 } 47 int flag=1;48 sort(ans+1,ans+1+n);49 for(II i=1;i<=n;i++){50 if(flag){ cout<

View Code

转载于:https://www.cnblogs.com/xiaowuga/p/7323105.html

你可能感兴趣的文章