2018-10-25 模拟测试

问题 A: 魏传之长坂逆袭

题目描述

众所周知,刘备在长坂坡上与他的一众将领各种开挂,硬生生从曹操手中逃了出去,随后与孙权一起火烧赤壁、占有荆益、成就霸业。而曹操则在赤壁一败后再起不能,终生无力南下。
建安二十五年(220年),曹操已到风烛残年,但仍难忘当年长坂的失误,霸业的破灭。他想如果在刘备逃亡的路中事先布下一些陷阱,便能拖延刘备的逃脱时间了。你作为曹操身边的太傅,有幸穿越到了208年的长坂坡,为大魏帝国贡献一份力,布置一些陷阱。但时空守卫者告诉你你不能改变历史,不能拖增大刘备的最大逃脱时间,但你身为魏武之仕,忠心报国,希望能添加一些陷阱使得刘备不论怎么逃跑所用的时间都一样。
已知共有n个据点,n-1条栈道,保证据点联通。1号据点为刘备军逃跑的起点,当刘备军跑到某个据点后不能再前进时视为刘备军逃跑结束。在任意一个栈道上放置1个陷阱会使通过它的时间+1,且你可以在任意一个栈道上放置任意数量的陷阱。
现在问你在不改变刘备军当前最大逃跑时间的前提下,需要添加最少陷阱,使得刘备军的所有逃脱时间都尽量的大。

输入

第一行一个数n,表示据点个数。
接下来n-1行每行三个数,ai、bi、ti,表示从据点ai通过第i个栈道到bi耗时ti

输出

仅包含一个数,为需要添加的最少陷阱数。

样例输入

样例输出

对于 5%的数据,1<=n<=100000,1<=ti<=200000
对于 100%的数据,1<=n<=500000,0<ti<=1000000

题解


此题是一道树形DP,很显然,它就是让你求 从根开始到每一个叶子结点的权值和相等需要改多少边权
设$f[x]$表示以$x$为跟,到它的子树中权值的最大值
再设$sum$表示已$x$为根的权值总和
再设x为根的节点有$cnt$个孩子
则对于$x$,答案要加上$cnt*f[x]-sum$

代码如下(因为比较简单,就不解释了)
还有,记得开$long\ long$啊


问题 B: 蜀传之单刀赴会

题目描述

公元215年,刘备取益州,孙权令诸葛瑾找刘备索要荆州。刘备不答应,孙权极为恼恨,便派吕蒙率军取长沙、零陵、桂阳三郡。长沙、桂阳蜀将当即投降。刘备得知后,亲自从成都赶到公安(今湖北公安),派大将关羽争夺三郡。孙权也随即进驻陆口,派鲁肃屯兵益阳,抵挡关羽。双方剑拔弩张,孙刘联盟面临破裂,在这紧要关头,鲁肃为了维护孙刘联盟,不给曹操可乘之机,决定当面和关羽商谈。“肃邀羽相见,各驻兵马百步上,但诸将军单刀俱会”。双方经过会谈,缓和了紧张局势。随后,孙权与刘备商定平分荆州,“割湘水为界,于是罢军”,孙刘联盟因此能继续维持。

【问题描述】

关羽受鲁肃邀请,为了大局,他决定冒险赴会。他带着侍从周仓,义子关平,骑着赤兔马,手持青龙偃月刀,从军营出发了,这就是历史上赫赫有名的“单刀赴会”。关羽平时因为军务繁重,决定在这次出行中拜访几个多日不见的好朋友。然而局势紧张,这次出行要在限定时间内完成,关公希望你能够帮助他安排一下行程,安排一种出行方式,使得从军营出发,到达鲁肃处赴会再回来,同时拜访到尽可能多的朋友,在满足这些条件下行程最短。注意拜访朋友可以在赴会之前,也可以在赴会之后。现在给出地图,请你完成接下来的任务。

输入

第一行n,m,k,t,代表有n个地点,m条道路,有k个朋友(不包括鲁肃),以及限定时间t(行走1单位长度的路程用时1单位时间)。
接下来m行,每行有x,y,w三个整数,代表x和y之间有长度为w的道路相连。
接下来一行有k个整数,代表朋友所在的都城编号(保证两两不同,且不在1和n)(我们约定1是关羽的营地,n是鲁肃的营地)

输出

输出两个整数,分别是最多可以拜访的朋友数,以及在这种情况下最少需要耗费的时间,如果连到达鲁肃再回来都无法完成,输出一个-1就可以了。

样例输入

样例输出

有10%数据,n<=10,m<=50,k<=5;
有10%数据,k=0;
有10%数据,k=1;
另30%数据,k<=5;
对于100%数据, n<=10000,m<=50000,k<=15,t<=2147483647,w<=10000

题解


这道题目发现k非常小,于是考虑状态压缩

这个时候,我发现n似乎没有什么用……
我们只需要知道朋友之间的距离即可

因为关羽的阵地和鲁肃的阵地是必须去的
我们不妨把关羽和鲁肃分别设为$0$号朋友与$k+1$号朋友
在统计答案时令关羽的阵地和鲁肃的阵地必须到即可

我们先统计出每一个朋友之间的距离为$dis[i][j]$
状态$f[sta][i]$表示$sta$的状态,且当前留在最后一个朋友的位置

$f[sta\ \ | \ \ (1<<(i-1))][i]=\displaystyle\min_{j\ \in\ sta\ \ and \ \ i\ not \in\ sta}{(f[sta][j]+dis[j][i])}$

这是什么意思呢??

如果关羽还没有到过i,但他到过j,他就可以从j走到i

最后的答案就是$f[sta][i]+dis[i][0]$(若$sta$到过$0$号与$k+1$号且$f[sta][i]+dis[i][0]<=d$)
及到过他自己的与鲁肃的阵地中且最后再返回自己的阵地

上代码:


问题 C: 吴传之火烧连营

【题目背景】

蜀汉章武元年(221年),刘备为报吴夺荆州、关羽被杀之仇,率大军攻吴。吴将陆逊为避其锋,坚守不战,双方成对峙之势。蜀军远征,补给困难,又不能速战速决,加上入夏以后天气炎热,以致锐气渐失,士气低落。刘备为舒缓军士酷热之苦,命蜀军在山林中安营扎寨以避暑热。陆逊看准时机,命士兵每人带一把茅草,到达蜀军营垒时边放火边猛攻。蜀军营寨的木栅和周围的林木为易燃之物,火势迅速在各营漫延。蜀军大乱,被吴军连破四十余营。陆逊火烧连营的成功,决定了夷陵之战蜀败吴胜的结果。

【问题描述】

刘备带兵深入吴境,陆逊却避而不出,蜀军只得在山林中安营扎寨。而刘备在扎营时却犯了兵家大忌,将兵营排列成一条直线,远远看去,就像是一条串着珠子的链,美其名曰:链寨。如果吴军将领是一般人,那么这也许不算什么,而陆逊何许人也,他可是江东才子,能力不低于周瑜的一代儒将。他看到刘备这样排阵,心生一计,决定用火攻破阵。然而,火计除了要有风,选定引火点也非常重要,对于刘备的布阵,最佳引火点一定是n个兵营中的一个。而因为风水轮流转,每天的最佳引火点都不一样。我们给每个兵营定下一个固定不变的火攻值Ai,每天定下一个风水值K,对于每天的最佳引火点,显然是所有兵营中火攻值与风水值异或的结果最大的那一个兵营。然而,陆逊是个谨慎的人,他要观察时机,在m天中选定一个最佳的进攻的日期,为此他演算出了这m天每天的风水值,然后他希望你能够告诉他这m天每天最佳引火点的兵营编号。

输入

第一行n,m,代表有n个兵营,m天.
接下来一行有n个非负整数,代表这n个兵营的火攻值。
接下来一行有m个非负整数,代表这m天的风水值。

输出

输出共m行,每行输出一个整数,代表第m天最佳引火点的编号。
如果存在多个最佳引火点使得火攻值与风水值的异或值最小,请任意输出一组解即可。

样例输入

样例输出

【样例解释】

对于第1天,由于4 xor 1=5, 4 xor 2=6, 4 xor 3=7,选择第3个引火点是最佳的。
对于第2天,由于5 xor 1=4, 5 xor 2=7, 5 xor 3=6,选择第2个引火点是最佳的。

【数据规模和约定】

对于30%数据,n<=1000,m<=1000
对于100%数据,n<=100000,m<=100000, 0<=k,ai<=2147483647

题解


其实这道题目就是一道Trie树模板题
Trie树我就不再赘述了,可以戳这里
从$2^{33}->2^{0}$每次扫一遍即可
平均时间复杂度$O(35n)$
数组一定要开大一点!!
代码:


4 thoughts on “2018-10-25 模拟测试”

发表评论