本文共 1047 字，大约阅读时间需要 3 分钟。
题目传送门：
这道题有点毒瘤啊，罚时上天。。
显然若$ l=2^n $那么就可以直接二进制拆分，但是如果不满足这个要求就有点难办了。。。
但是我们可以按照数位dp的那个树形结构一样，把整个区间$ [0,l) $拆成多个满足二进制拆分的结构（在树上则表现为满二叉树），然后在树根对应的位置额外连边补足权值就行了。（数位dp不懂的可以在这里看：，其他细节可以看代码，这题我因为细节wa3。。。）
代码：
#include #include #include #include #include #include #include #include #include #include #define ll long long#define ull unsigned long long#define max(a,b) (a>b?a:b)#define min(a,b) (a >=1){ if(b&1)ans=ans*a%mod; a=a*a%mod;} return ans;}inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}inline void swap(int &a,int &b){ int tmp=a; a=b; b=tmp;}using namespace std;int x[110],y[110],d[110];int a[30],base[30];int n,m,l;int main(){ l=read(); if(l<=2){ //特判是因为若l<=2，下面建图是时图只有一个点，无法连边 printf("2 %d\n",l); for(int i=0;i =0;i--) if(l&(1< >(i+1)<<(i+1); } printf("%d %d\n",n,m); for(int i=1;i<=m;i++) printf("%d %d %d\n",x[i],y[i],d[i]); return 0;}
转载于:https://www.cnblogs.com/quzhizhou/p/9571837.html
