topcoder srm 680 div1 -3-白红宇

topcoder srm 680 div1 -3

阅读量：6412 次

发布时间：2019-06-23

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

1、一个长度为$n$的数组$A,1\leq A_{i} \leq b$。$n$是偶数。$A$中任意两个数字不相等，且$A$中奇数的个数等于偶数的个数。另外有$m$个限制，第$i$个限制是$A$中$[1,x_{i}]$之间的数字的个数为$c_{i}$。问是否存在一个数组 $A$满足上述所有条件？

$n\leq 50,n \leq b \leq 2000,m\leq 50$

思路：将限制按照$x$排序。那么$[x_{i}+1,x_{i+1}]$中数字个数为$c_{i+1}-c_{i}$。然后进行动态规划。$f[i][j]$表示考虑了前$i$个区间的限制，其中偶数的个数为$j$时是否成立。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;const int mod=1000000007;struct node{ int ll,rr,cnt; node(){} node(int _ll,int _rr,int _cnt):ll(_ll),rr(_rr),cnt(_cnt) {}};int f[55][55];class BearFair{public: string isFair(int n,int b,vector
                
                  x,vector
                 
                   c) { const int m=(int)x.size(); vector
                  
                   
                     > V; for(int i=0;i
                    
                      all; for(int i=0;i
                     
                      V[i].first) return "unfair"; all.push_back(node(1,V[i].first,V[i].second)); } else { if(V[i].second
                      
                       V[i].first-V[i-1].first) return "unfair"; if(V[i].second!=V[i-1].second&&V[i].first==V[i-1].first) return "unfair"; if(V[i].first!=V[i-1].first) { all.push_back(node(V[i-1].first+1,V[i].first,V[i].second-V[i-1].second)); } } } if(V.back().second>n) return "unfair"; if(V.back().first
                       
                        >1])return "fair"; return "unfair"; }};

2、计算最小生成树的伪代码如下：

While H is not connected yet:    For each component C in H:        Find the lightest edge in G that has exactly one endpoint in C.        Mark this edge for addition.    Add all marked edges to H.

　其中，$G$是给定的图，$H$是最后要求的最小生成树。现在构造一个$n$个顶点$m$条边的图$G$使得上述$while$循环恰好执行$k$次。

思路：首先$[1,n]$区间每个节点是单独的一个分量，每次将该区间分为两半，最后将这两部分连在一起。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;const int N=1005;int h[N*N];int n,m;set
                
                 
                   > S;vector
                  
                    ans;void add(int u,int v,int w){ h[w]=1; ans.push_back(u); ans.push_back(v); if(u
                   
                    >1; int cc=R-L+1; if(cc==3) return 0; if(!dfs(L,M,k-1)) return 0; if(!dfs(M+1,R,k-1)) return 0; add(L,R,++cur); return 1;}class BearSpans{public: vector
                    
                      findAnyGraph(int nn,int mm,int k) { for(int i=1;i<=nn;++i) { for(int j=i+1;j<=nn;++j) { S.insert(make_pair(i,j)); } } n=nn; m=mm; if(!dfs(1,n,k)) return vector
                     
                      {-1}; while(cur
                      
                        p=*S.begin(); S.erase(p); add(p.first,p.second,++cur); } return ans; }};

转载地址：http://ipdra.baihongyu.com/

你可能感兴趣的文章