博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【atcoder】All Your Paths are Different Lengths[arc102D](乱搞)
阅读量:5923 次
发布时间:2019-06-19

本文共 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;}
arc102D

 

转载于:https://www.cnblogs.com/quzhizhou/p/9571837.html

你可能感兴趣的文章
内存管理高级1---转自光远的iOS
查看>>
Hyper-V 3.0功能部署PART 5:秒级实时迁移
查看>>
Java集合详解
查看>>
通过IPC$***,通过命令开启远程协助,。。
查看>>
http/apache错误代码汇总
查看>>
搜索引擎的小技巧
查看>>
Syslog服务器配置
查看>>
WinAPI: GetComputerName - 获取计算机名称
查看>>
springCloud--补充:热部署
查看>>
Linux学习日志(三)
查看>>
我的友情链接
查看>>
解决每次Appium启动时的自带apk安装
查看>>
Objective-C之成魔之路【3-数据类型】
查看>>
更改UIView的背景
查看>>
多线程之三-单例模式
查看>>
唠唠 RDS 那些事 ——发布虚拟机
查看>>
极好的数据库学习资料
查看>>
tomcat service启动脚本
查看>>
linux入门之文本处理工具sed粗略使用(1)
查看>>
C语言生成随机数保存在文件中
查看>>