本文共 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