【Arc102b】All Your Paths are Different Lengths

Source and Judge

Arc102b

Record

2h

Analysis

请先思考后再展开

原来这就是传说中的构造题
首先明确,基本的结构一定是二进制拆分
但不难发现,很难保证只有L条路径,得出来的长度还绝对不能重复

其实我有点思维僵化了
如果把1和后面的东西拆开来,分开讨论,后面的全部都是完全的二进制
(也就是2的次幂边,以及0)

那么我们记录一个当前已经搞定的最大范围mx-1,从mx开始
然后对L二进制拆分,然后假如加入之后,依然在合法范围内,那么就加上mx,并更新范围
不难发现,现在得出来的路径长度,一定不会重复出现(通过简单地记录一个当前上界)

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=110000,MAX_M=410000;
const int INF=0x3f3f3f3f;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int bin[20];
struct Edge
{
int x,y,c;
};
vector<Edge> q;
void main()
{
bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
int mx;scanf("%d",&mx);//0~mx-1
int nowmx=0;
for(int i=18;i>=0;i--)
while(nowmx+bin[i]-1<=mx-1)
{
q.push_back( (Edge){1,20-i,nowmx} );
nowmx+=bin[i];
}
printf("20 %d\n",18*2+q.size());
for(int i=2;i<=19;i++) printf("%d %d %d\n%d %d 0\n",i,i+1,bin[19-i],i,i+1);
for(int i=0;i<q.size();i++) printf("%d %d %d\n",q[i].x,q[i].y,q[i].c);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/9f63.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%