题目传送门:https://arc102.contest.atcoder.jp/tasks/arc102_b

  这道题有点毒瘤啊,罚时上天。。

  显然若$ l=2^n $那么就可以直接二进制拆分,但是如果不满足这个要求就有点难办了。。。

  但是我们可以按照数位dp的那个树形结构一样,把整个区间$ [0,l) $拆成多个满足二进制拆分的结构(在树上则表现为满二叉树),然后在树根对应的位置额外连边补足权值就行了。(数位dp不懂的可以在这里看:初探数位dp - QuartZ_Z - 博客园,其他细节可以看代码,这题我因为细节wa3。。。)

  代码:

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define ull unsigned long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define lowbit(x) (x& -x)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-18
#define maxn 100010
inline ll read(){ll tmp=; char c=getchar(),f=; for(;c<''||''<c;c=getchar())if(c=='-')f=-; for(;''<=c&&c<='';c=getchar())tmp=(tmp<<)+(tmp<<)+c-''; return tmp*f;}
inline ll power(ll a,ll b){ll ans=; for(;b;b>>=){if(b&)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[],y[],d[];
int a[],base[];
int n,m,l;
int main()
{
l=read();
if(l<=){//特判是因为若l<=2,下面建图是时图只有一个点,无法连边
printf("2 %d\n",l);
for(int i=;i<l;i++)
printf("1 2 %d\n",i);
return ;
}
int len=;
while(<<len<=l)++len;
n=len; m=;
for(int i=;i<len-;i++){//二进制拆分
x[++m]=i+; y[m]=i+; d[m]=;
x[++m]=i+; y[m]=i+; d[m]=<<i;
}
for(int i=len-;i>=;i--)
if(l&(<<i)){//其实和数位dp一样啦
x[++m]=i+; y[m]=n; d[m]=l>>(i+)<<(i+);
}
printf("%d %d\n",n,m);
for(int i=;i<=m;i++)
printf("%d %d %d\n",x[i],y[i],d[i]);
return ;
}

arc102D

最新文章

  1. Oracle Partition Outer Join 稠化报表
  2. PgwSlideshow-基于Jquery的图片轮播插件
  3. 96. Unique Binary Search Trees
  4. Java中Date各种相关用法
  5. WPF DataBinding之我见
  6. cocos2d-x -- 渠道SDK【棱镜】接入(2)
  7. Microservice架构模
  8. Catch That Cow_bfs
  9. Python自动化中的键盘事件
  10. jQuery ajax如何传多个值到后台页面,举例:
  11. javascript获取时间戳
  12. POJ1151Atlantis 矩形面积并 扫描线 线段树
  13. 〖Android〗arm-linux-androideabi-gdb报 libpython2.6.so.1.0: cannot open shared object file错误的解决方法
  14. [Android App]IFCTT,即:If Copy Then That,一个基于IFTTT的&quot;This&quot;实现
  15. Delphi 语言
  16. 洞悉linux下的Netfilter&amp;iptables:什么是Netfilter?
  17. 让你的应用支持新iPad的Retina显示屏
  18. 【WPF】C#代码动态添加控件的Margin属性
  19. 不要忘记最后那个 default 分支
  20. https://github.com/arut/nginx-rtmp-module.git

热门文章

  1. docker搭建lnmp环境(问题,资料,命令)
  2. Tomcat虚拟目录
  3. django 1.10以上版本,引入js
  4. dos下查找进程,如果找到echo find并结束该进程
  5. JS HTML DOM 事件对象(onclick、onmouseenter)
  6. Using InfluxDB in Grafana,influxDB在grafana中使用
  7. python系列十二:python3模块
  8. ECMAScript6面对大于0xFFFF的Unicode字符如何正确返回长度
  9. ztree的异步加载
  10. setlocale(LC_ALL, &quot;&quot;); 取值为空字符串&quot; &quot;(注意,不是NULL),则locale与本地环境所使用的编码方式相同(在本地化时,应该很有用);