脚本宝典收集整理的这篇文章主要介绍了CF1479C Continuous City 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Codeforces Luogu
构造一个带权 DAG，使得从 (1) 到 (n) 的所有路径构成一个可重集 (S)。 使得 (forall xin[L,R])，(x) 在 (S) 中只出现一次。 边权 (ge 1)，点数 (le n)
每个部分都不会，加起来怎么可能会呢
Part1：构造 ([1,2^k])。 就可以构造 ([0,2^k)+1)，那这样肯定存在一个最高 (1) 位。 然后后面肯定都是 (1000cdots1000cdots1000cdots) 这样的。 可以考虑枚举下一个 (1) 的位置，如果没有就连向终点。 然后这样就对于每个点所有出边都是 (2^i)，起点需要枚举一下最高位。 这样总共用了 (k) 个点。 当然枚举最高位还是最低位都是本质相同的吧。
Part2：从 ([1,2^k]rightarrow[1,sum2^i])。 考虑每次建这样一张图太累了，图上某些节点是可以重复利用的。 从低到高考虑，如果当前有一个 (1)，我们就需要加上一段的答案。 我们可以重复利用上一段的信息，新增一个点。 对于一个 (1)，我们可以考虑把这个点和新增的点连成一条到结尾的直达路，让这条路权值使后面全都填满。 然后就可以构造了。
//Coded by Kamiyama_Shiki on 2021.11.08 {{{
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
int L,R,tot,id[55],et=0,fr[5555],tw[5555],we[5555];
inline void adde(int x,int y,int w) {++et,fr[et]=x,tw[et]=y,we[et]=w;}
inline void flush()
{
printf("YESn%d %dn",tot,et);
for(int i=1;i<=et;i++) printf("%d %d %dn",fr[i],tw[i],we[i]);
}
int main()
{
read(L,R);int n=R-L+1,lg=0;for(;(1ll<<lg)<=n;lg++);
int s=++tot;if(L!=1) adde(1,s=++tot,L-1);
for(int i=0;i<lg;i++) id[i]=++tot;
int o=++tot;swap(id[lg-1],o);
for(int i=0;i<lg;i++) adde(s,id[i],1);
for(int i=0;i<lg;i++) for(int j=i+1;j<lg;j++) adde(id[i],id[j],1<<i);
for(int i=1;i<lg;i++) if((n>>(i-1))&1) adde(id[i-1],o,((n>>i)<<i)-1);
return adde(o,tot,1),flush(),0;
}
以上是脚本宝典为你收集整理的CF1479C Continuous City 题解全部内容，希望文章能够帮你解决CF1479C Continuous City 题解所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。