「NOIP模拟赛」小奇的仓库

2015年3月30日5,0866

原题:「East!_XI」第一个问题 2015年10月4日hzwer改写了题面

「题目背景」

小奇采的矿实在太多了,它准备在喵星系建个矿石仓库。令它无语的是,喵星系的货运飞船引擎还停留在上元时代!

「问题描述」

喵星系有n个星球,星球以及星球间的航线形成一棵树。

从星球a到星球b要花费[dis(a,b) Xor M]秒。(dis(a,b)表示ab间的航线长度,Xor为位运算中的异或)

为了给仓库选址,小奇想知道,星球i(1<=i<=n)到其它所有星球花费的时间之和。

「输入格式」

第一行包含两个正整数n,M。
接下来n-1行,每行3个正整数a,b,c,表示a,b之间的航线长度为c。

「输出格式」

n行,每行一个整数,表示星球i到其它所有星球花费的时间之和。

「样例输入」

4 0

1 2 1

1 3 2

1 4 3

「样例输出」

6

8

10

12

「数据范围」

序号 N M

1 6 0

2 100 5

3 2000 9

4 50000 0

5 50000 0

6 50000 1

7 50000 6

8 100000 10

9 100000 13

10 100000 15

保证答案不超过2*10^9

题解

出题人18357:

算法1:

不会写函数的小伙伴们,我们只需要写个floyd,就有10分啦!

算法2:

在算法1的基础上,我们对每条边处理一下xor,就有20分啦!

算法3:

简单的树形DP,或者你会nlogn的dij,处理完每个点到其它点的最短路后再加上xor,那么这样就有30分啦!

算法4:

第4、5个点无需xor,那么我们树形DP扫一个节点与其它所有节点的路径长度之和,可以合并信息,最终均摊O(1),50分到手。

算法5:

第6个点xor 1,那么我们树形DP到一个点时记录有多少个0,多少个1,然后每当一条路径到2,那部分就再记录一个值,60分到手。

算法6:

如果你第6个点都过了,却没有满分,笨死啦!

一样的嘛,就是原来的“0”、“1”、大于等于2变成了0~16么~~

满了。

 

avatar
6 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
6 Comment authors
kkksc03微软而1134ZemtadreadNULL Recent comment authors
  Subscribe  
提醒
kkksc03

讲得很不错

微软而1134

%%%%244352345343452345

Zemta
Zemta

我太难了

dread
dread

我真是笨死了

NULL
NULL

ym

PoPoQQQ
PoPoQQQ

[捂脸熊]然后我过了前6个点,却没有AC,真是笨死了QAQ