ARC102D All Your Paths are Different Lengths-白红宇

ARC102D All Your Paths are Different Lengths

阅读量：7030 次

发布时间：2019-06-28

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

题目大意

让你构造一个有向图，使得从1到n有L条不同路径且长度分别是0~L-1。

分析

我们不难想到每一对相邻点之间连一条权值为0的边，之后二进制分解，将每一对点之间连一个权值为2^i的边，但是我们会发现这样在一些情况下还会剩下一些值不能覆盖。如果将剩下的值一一连边肯定会炸。于是我们还是利用二进制的思想，从最后一个点开始向前枚举，如果在这个点加上一条权值为之前不能构成的值中的最小值的边构成的数不会越界则加上这一条边。描述比较粗略，详见代码。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int LOG = 20;int ans[1100],ans2[1100],ans3[1100];int main(){ int n,m=0,l,i,j,k; scanf("%d",&l); for(i=0;i<=LOG;i++) if((1<
                   
                    l){ n=i; break; } for(i=1;i
                    
                     0;i--) if((1<<(i-1))<=l){ ans[++m]=i; ans2[m]=n; ans3[m]=t; t+=1<<(i-1); l-=1<<(i-1); } printf("%d %d\n",n,m); for(i=1;i<=m;i++) printf("%d %d %d\n",ans[i],ans2[i],ans3[i]); return 0;}

转载于:https://www.cnblogs.com/yzxverygood/p/9694800.html

你可能感兴趣的文章