Codeforces Round #700 (Div. 1) C. Continuous City 构造 + 二进制

发布日期：2021-05-07 18:32:49 浏览次数：25 分类：精选文章

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

文章目录

题意：

构造一个图，使其从 $1$ 到 $n$ 的路径的长度与 $[L, R]$ 中某个值一一对应，不能有两条路径长度一样，且每个值都必须出现一次，每两个点之间只能连一条边。

n\le32

，

a_i,b_i\le n

，

1\le c_i\le 1e6

。

思路：

看到 $n\le 32$ ，不难想到二进制拆分，我们分情况来讨论。

1)\ \ L=1,R=2^k

对于这种情况，我们需要拿出来

k + 2

个点，从

1

向

[2, k + 2]

的点连边权为

1

的边，让后对于后面的每一个位置

i

，都向后连边权为

2^{i-2}

的边，这样就可以构造出

1,2^k]

内的边权了。

(2)\ \ L=1,R>1

对于这种情况，我们依旧按照

(1)

的思路构造出

1,2^k]

的边权，让后再新加一个点

k + 3

，考虑用新的点来构造出来

2^k+1,R]

的边权。

对于

R

，他的二进制形式大概是这样的

100100100 . . .

，很明显，我们可以根据

1

来分段，因为我们已经构造出来了

1,2^i]

，即

[1, 1000 . .]

，假设

R

的从低位到高位的第

i

位(从

0

开始)是

1

，那么我们只需要从

i + 2

的位置向

k + 3

连一个

R

将

i

位及其之后的数都变成

0

的边权，但是这样会有点问题，就是因为构造的是

1,2^i]

，缺少

0

，那么连完之后也就缺少后面全

0

的边权。所以我们考虑将

R - 1

之后建边，在新边的边权都

+ 1

即可。

(3)\ \ L>1,R>1

只需要在最后新加一个点，在原来的最后一个点向他连

l - 1

的边即可，转化成情况

(1)

或

(2)

。

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")//#pragma GCC optimize(2)#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define pb push_back#define mk make_pair#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define random(a,b) ((a)+rand()%((b)-(a)+1))#define db puts("---")using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL;typedef unsigned long long ULL;typedef pair
                 
                   PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int l,r;int tot;struct Node{ int a,b,w;}edge[N];void add(int a,int b,int c){ edge[++tot]={ a,b,c};}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); cin>>l>>r; puts("YES"); int rr=r-l+1; int k=0; while((1<
                  
                   
                    1) add(cnt,cnt+1,l-1),cnt++; printf("%d %d\n",cnt,tot); for(int i=1;i<=tot;i++) printf("%d %d %d\n",edge[i].a,edge[i].b,edge[i].w); } else { k--; int cnt=k+3; for(int i=2;i<=k+2;i++) add(1,i,1); for(int i=2;i<=k+2;i++) for(int j=i+1;j<=k+2;j++) add(i,j,1<<(i-2)); add(1,k+3,1); for(int i=0;i<=k;i++) if((rr-1)>>i&1) add(i+2,k+3,((rr-1)>>(i+1)<<(i+1))+1); if(l>1) add(cnt,cnt+1,l-1),cnt++; printf("%d %d\n",cnt,tot); for(int i=1;i<=tot;i++) printf("%d %d %d\n",edge[i].a,edge[i].b,edge[i].w); } return 0;}/**/

上一篇：Codeforces Global Round 14 E. Phoenix and Computers 思维 + dp

下一篇：2021-05-05

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

文章目录

题意：

思路：

发表评论

最新留言

关于作者

推荐文章