负担集训-Test3

----------------------------------------------
简直谜啊..
题意理解错挂一道
sb错误挂一道
就这么崩了
----------------------------------------------

 
概述
----------------------------------------------
赛中通过6题,赛后通过3题,共通过9题
----------------------------------------------
 
比赛经历
----------------------------------------------
一开始看到题面都爆炸长,卧槽了一下,然后默默点开A,发现还是比较简单的,后面又跟着大流把CEGHI做了,然后去看J,想了一下好像会了,写一写,果断WA了,调了半天调不出来,于是又跑去做D,想了一想好像会了,写一写又WA了,泪流满面..又调了一会儿,调不出来,就没有然后了。
----------------------------------------------
 
比赛题解
----------------------------------------------
A:(赛中通过)

定义一个整数c的奇怪指数,首先把这个数的尾0全部去掉,得到的数假设是x,假设x有a个数字,那么如果x的末尾数字是5,他的奇怪指数就是2a-1,否则就是2a
如果[0.95c,1.05c]内有一个整数的奇怪指数比c的奇怪指数小,那么c就是一个奇怪的数
现在给你一个c,问c是不是一个奇怪的数
c <= 10^9
 
首先如果x末尾不是5的话,那么[0.95c,1.05c]里面有一个数对应的x末尾是5,他的奇怪指数就比x小了,如果x末尾是5的话,那么[0.95c,1.05c]如果有一个数对应的x末尾是0,他的奇怪指数也比x小。因此x上下5以内必然有一个数奇怪指数比他小,因此如果x>100的话,他肯定是一个奇怪的数,100以内的暴力就好了
----------------------------------------------
B:(赛后通过)
题意是,现在世界杯抽签分组,一共g组,每组m个队伍,每个队伍有一个强度值,规则是这样的,首先钦定g个队伍,作为每个小组的第一成员,叫做种子队伍,然后有m-1个档,每档有g支队伍,每个小组的第i成员就从第i个档里面随机抽,然后每个队伍来自一个洲,每个洲的队伍不能分在同一个小组,但是如果这个洲的队伍数超过了g个就没有这个限制,对于那些队伍数小于等于g个的洲,所有没有作为种子队伍的队伍一定在同一个档里,现在给定一支队伍,求他的小组其他成员的强度值的和的期望。
g<=8,m<=4
 
这道题最难的地方就是理解题意
首先全排列一下,设f[i][j][k]表示第i档的成员j分在第k组的概率
然后枚举一下要问的那个队伍在第几小组,以及其他小组成员分别是谁,把答案算出来就行了。

----------------------------------------------
C:(赛中通过)
现在有两个前锋,你可以选择把球传给某一个人,然后这两个人就一起向前跑,跑n步之后当前带球的人射门,跑某一步之前都可以选择是否把球传给另个人,然后每一次传球,每一次跑动,每一次射门都有一个危险值,请你规划方案,使危险值最小。n<=100000
 
dp即可。设f(i,j)表示第i步,当前带球的人是j,最小危险值。随便转移一下就好了
----------------------------------------------
D:(赛后通过)
给你一个有向图,问你哪些点满足从他们出发可以到达任意点,点数、边数<=100000
 
首先tarjan缩环,然后判断一下缩完点之后是不是一棵树即可
----------------------------------------------
E:(赛中通过)
给你一个字符串s,给定m和k,要求构造一个长度小于等于m的只是用了前k个字母的不在s中出现过的字符串
|s|<=10000,m<=100,k<=26
 
首先钦定答案的长度为m,因为如果一个字符串出现过,那他的子串肯定也出现过,显然更长的字符串更不容易出现。
随便构造一个长度为m的字符串,匹配一下,如果成功就随机换一个字母,这样直到他不匹配就好,因为n中只有O(n)个长度为m的子串,期望的匹配字数应该是O(n)的
匹配的时候可以用哈希
----------------------------------------------
G:(赛中通过)
说是有11个人和11个位置,第i个人放到第j个位置可以产生a[i][j]的价值,让你分配位置,使得总价值最大,但是要求不能有某一个人分配到了他的价值为0的位置上
 
f[i][j]表示前i个人,已经使用的位置是j(j是一个二进制串,第i位表示位置i是否被使用),最大的价值
随便转移一下就行了
----------------------------------------------
H:(赛中通过)
给你n个数,问他们是否全部是同一个三次多项式的值
n<=1000000
因为一个k次多项式的值序列差分之后就变成了一个k-1次多项式的值序列
所以把原序列差分4次看是否全部为0即可
----------------------------------------------
I:(赛中通过)
有16支球队,打了16场比赛,每场比赛淘汰败者(我也不知道为什么有16场...可能是半决赛要定23名吧..),知道每场比赛的队伍和分别的得分,求冠军
一直没输过的就是冠军了
----------------------------------------------
J:(赛后通过)
平面上有n个点,有四个特殊的点,s1,t1,s2,t2,要求s1连线连到t1,s2连线连到t2,连线就是每次在两个点之间连一个线段,要求连线不能交叉,也不能有某一个点重合,问能否成功
 
首先跑一个凸包出来,然后除了四个点都在凸包上的情况,其他情况都不难构造出方案,因此只有在凸包上并且是交叉的情况需要考虑
----------------------------------------------
 
比赛总结
----------------------------------------------
我又双叒叕读错题了...
英文题面伤不起啊...
以后要注意这个
调不出来的时候可以想一想是不是读错题了
还有就是是不是一些sb错误...
调试的时候应该多检查看起来很简单的细节
----------------------------------------------