负担集训-Test3
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------
简直谜啊..
题意理解错挂一道
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错误...
调试的时候应该多检查看起来很简单的细节
----------------------------------------------
评论 (0)
