ARC102D All Your Paths are Different Lengths
2024-08-27 17:15:33
题目大意
让你构造一个有向图,使得从1到n有L条不同路径且长度分别是0~L-1。
分析
我们不难想到每一对相邻点之间连一条权值为0的边,之后二进制分解,将每一对点之间连一个权值为2^i的边,但是我们会发现这样在一些情况下还会剩下一些值不能覆盖。如果将剩下的值一一连边肯定会炸。于是我们还是利用二进制的思想,从最后一个点开始向前枚举,如果在这个点加上一条权值为之前不能构成的值中的最小值的边构成的数不会越界则加上这一条边。描述比较粗略,详见代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int LOG = ;
int ans[],ans2[],ans3[];
int main(){
int n,m=,l,i,j,k;
scanf("%d",&l);
for(i=;i<=LOG;i++)
if((<<i)>l){
n=i;
break;
}
for(i=;i<n;i++){
ans[++m]=i;
ans2[m]=i+;
ans3[m]=;
ans[++m]=i;
ans2[m]=i+;
ans3[m]=<<(i-);
}
int t=<<(n-);
l-=t;
for(i=n-;i>;i--)
if((<<(i-))<=l){
ans[++m]=i;
ans2[m]=n;
ans3[m]=t;
t+=<<(i-);
l-=<<(i-);
}
printf("%d %d\n",n,m);
for(i=;i<=m;i++)
printf("%d %d %d\n",ans[i],ans2[i],ans3[i]);
return ;
}
最新文章
- 如何阅读Java源码 阅读java的真实体会
- 对于大数据量的Json解析
- Ubuntu 下配置Ganglia监控
- 【读书笔记】iOS-头文件导入-@class注意事项
- Android 获取地理位置的经度和纬度(zz)
- Struts2配置文件
- MYSQL复制的几种模式
- 1021: [SHOI2008]Debt 循环的债务 - BZOJ
- RepeatedDNASequences BestTime_to_Buy_and_SellStockIV
- 消息提醒,初探Notification
- 那些过目不忘的无线端交互设计(DRIBBBLE GIF动态图)
- 凸包(BZOJ1069)
- 你真的了解ASP.NET Core 部署模型吗?
- Java Spring Boot VS .NetCore (八) Java 注解 vs .NetCore Attribute
- 跟踪mqttv3源码(一)
- JoinPoint
- Codeforces 781C Underground Lab 构造
- Python---http协议.md
- XML的四种解析方法
- Eclipse配置C++环境