复旦集训-Test1
负担集训-Test3

负担集训-Test2

YYY posted @ 2017年7月19日 18:58 in ACM with tags DP 贪心 离散化 乱搞 , 506 阅读
_THIS_IS_START_OF_ARTICLE_
--------------------------------------------------------
这场做到一半都要哭出来了
我同时做D和H这两道题,卡了很久然后发现都调不出来
卡了很久跑去做B,写了个nlog^2的算法居然过不了...
生无可恋了...
--------------------------------------------------------
 

概述:
--------------------------------------------------------
赛中通过2题,赛后通过9题,共通过11题。
--------------------------------------------------------
 
比赛记录:
--------------------------------------------------------
一开始直接点开B,看完题,想了一会儿,发现不是很会,于是点开D,想了一会儿,想出来一个贪心,但是死活过不去,然后看一下A跟F好像过的人比较多,然后我就去把A和F过了,然后看H好像过得比较多,我就去做H,写一写发现过不了,又换了几种写法,死活过不去,然后我就写了个暴力,对拍,拍了一会发现完全拍不出错,又自己造了几组看起来比较特殊的数据,都没有问题,但是交上去就是WA2
然后就心态崩了。
调H调了很久,最后还剩一个小时的时候放弃了去做B,想了一会儿觉得可以用一个后缀数组搞一搞
但是我不会被基排的代码,自己想的话有点伤脑筋,我就写了个两个log的哈希算法,觉得是CF的评测机应该能过去。
然后果然没过。
然后我就崩溃了,又跑去调H和D,还是不知道哪里有错。
然后就没有然后了。
--------------------------------------------------------
 
比赛题解:
--------------------------------------------------------
A:(题目状态:赛中通过)
就是说给你一个字符串,然后用字母画把他表示出来
 
暴力即可
--------------------------------------------------------
B:(题目状态:赛后通过)
就是说给你一个字符串,然后把他循环来读,然后问你正着读反着读一共有多少个不同的子串(长度不超过n)
n<=50000
 
先把字符串复制一遍,中间加一个占位符$,然后把再把前面的部分翻转一遍接到后面,首先$两边分别求出长度不超过n的子串数,然后考虑减去重复的。
把后缀数组求出来,然后每个后缀和比他排名前一位的后缀的LCP,LCP的长度就是重复的字符串数量,减去即可,但是注意一开始就没有算长度大于n的子串,所以lcp长度大于n的时候只需要减去n。
注意$是没有影响的,因为任意两个包含$的子串一定都不相同($的位置不同),我们一开始没有算$,后面去重也不会算包含$的。
 
我死活调不出来居然是因为最大长度N开小了1!!!我忘记算占位符的空间了!!!
--------------------------------------------------------
C:(题目状态:赛后通过)
就是说有n个激光灯,每个激光灯可以在x和y方向分别发出一道射线,如果他击中了另一个激光灯,那么就可以加一定的分数(由他击中的是谁决定),激光击中一个激光灯后就被吸收了,而两道激光是可以交叉的(也可以重合),现在依次放入每个激光灯,问每个激光灯放进来之后最大得分是多少。
 
首先把x,y离散化一下,然后分别考虑。
一个激光灯加进来后,得分有可能发生改变的的只有他左边的,他右边的和他自己,更新一下就好。
随便用一个数据结构就可以维护x、y相同的每个人左右是谁。
--------------------------------------------------------
D:(题目状态:赛后通过)
就是说有n个狗房,m=n*x条狗,每个狗房是x条狗的第一住宅,x条狗的第二住宅,然后每条狗优先在第一住宅睡觉,如果第一住宅关闭了,他就回去第二住宅睡觉,每个住宅最多只能容纳x+1条狗,每次最多关闭一个狗房,让你安排每条狗的第一住宅和第二住宅,使得任何一个狗房关闭每条狗都有地方睡
n<=2017,x<=2017,m<=50000
 
首先第一住宅是无关紧要的,随便排就是了,按照题意,就是说同一个第一住宅的狗第二住宅不能相同,同一条狗的第一第二住宅也不能相同。
考虑贪心,每次优先给一条狗安排剩余空间最多的房间当第二住宅,如果有很多个,就优先选编号靠后的(因为不能选择本住宅,而且编号靠后的住宅里的狗选择更少,所以用前面的优先填他的住宅,免得浪费他的机会)
--------------------------------------------------------
F:(题目状态:赛中通过)
就是现在给所有可能的由英文字母组成的字符串排序,规则是长度小的优先排前面,长度一样的按字典序排,给定k,问第k个字符串是什么
k≤10^9
 
首先预处理出每个长度的字符串个数
然后从高到低枚举每一位字符,看一下如果后面都是A的话这是第几个,确定为恰好不超过k的那一个,这样从高到低确定他的字母就行了。
--------------------------------------------------------
I:(题目状态:赛后通过)
题意就是给你一棵树,两个操作,一个是给一个子树加一个关于深度的多项式,一个是给一条到根的链加一个关于深度的多项式,树的大小≤100000,多项式的次数≤20,问最后每个节点的值
 
因为每个节点的深度是不变的,所以这个多项式是可以合并的,然后每一项可以分开考虑。
两个操作也可以分开做,第一个操作每次只需在节点上加一下,然后最后dfs向上做一个前缀和,第二个操作也只需在节点上加一下,最后dfs,向下做前缀和
得到了每个节点最终的系数,就可以求出每个节点的值了
--------------------------------------------------------
G:(题目状态:赛后通过)
题意就是说你有n个英雄,每个英雄有一定的血量hi和攻击ai,然后有一个boss,也有一定的血量和攻击,然后你的英雄和boss轮流攻击,你的英雄先攻击,攻击的方式就是使得对方的血量减去你的攻击力,如果血量≤0,就死了,你可以任意排列英雄的上场顺序,问你最少死掉几个英雄干掉boss,或者输出无解。
n≤10^5
 
贪心即可。首先可以算出每个英雄可以对boss造成的伤害值,按这个值排序,就按这个顺序去跟boss打,后面的模拟即可,死了几个就是几个,打不过就是打不过。
--------------------------------------------------------
H:(题目状态:赛后通过)
就是问你[l,r]以内有多少个数他的最高位和最低位相同。1≤l≤r≤10^18
 
先把10以内的处理掉
考虑枚举位数和首末数字,然后找到他中间那一坨的上界和下界,使得下界恰好比l大,上界恰好比r大,然后上下界之间的所有数都是合法的,累加答案就行了。
现在来看怎么找上下界。比如说找下界,就先把所有位都设为9,然后从高位到低位枚举数字,从0枚举到9,每次确定为选了这个数字之后恰好比l大的那一个数字。找上界的话就是一开始每一位设为0,每次从9枚举到0,确定为选了这个数字之后恰好比r小的那一个数字。
 
我死活调不出来居然也是因为最大长度N开小了1!!!也就是只处理了10^17以内的!!!为什么世界上会有我这么sb的人啊啊啊!!!
--------------------------------------------------------
K:(题目状态:赛后通过)
题意就是说,给你一个长度为n的串,然后让你构造一个串,使得他和原串的最长公共子序列长度恰好为k,或者输出无解
n≤2000
 
如果k>n那么一定无解,先把这个判掉。
然后找到出现次数最少的字母,如果他的出现次数已经大于k了,那么也是无解,可以用反证法证明,如果存在一个合法的答案的话,他至少有一个字母出现了超过k次,而这个字母在原串中也出现了不止k次,因此只包含这个字母的子序列长度就已经大于k了。
观察到如果一个字母他在答案中出现的次数大于原串中出现的次数,那么他用多少次都没有关系,可以用来做占位符,因此就只需要找到出现次数最少的字母,把答案串中对应位置也填为这个字母,然后如果还不够的话,从头往后把原串抄下来,直到够了为止,然后剩下的就用这个出现次数最小的字母填满就行了。
--------------------------------------------------------
L:(题目状态:赛后通过)
题意:现在我们说一个序列a是k-有序的当且仅当每一个i≤n-k都有H(a[i],a[i+1],...a[i+k-1]) > H(a[i+1],a[i+2],...a[i+k])。
其中H(x1,x2,...xm) = (N / Sigma(i=1,m)(1/xi))^-1
给定n≤100000,求一个长度为n的排列,使得他是k-有序的,但不是t-有序(t≠k)的,并使得他字典序最小,或者说明他不存在
 
我原以为你身为倒数第二题,题面这么长必有高论,没想到竟然如此水!!!
首先可以发现H(a[i]...)≥H(a[i+1]...)当且仅当a[i]≥a[i+k]
因为是排列,没有相同数字,所以就等价于a[i]>a[i+k]
如果n>2k,那么一定无解,可以用反证法:假设n>2k,那么必然存在一个数a[m],使得,a[m-k]>a[m]>a[m+k],因此这个序列同时也是2k-有序的,不符合题意。
现在2k≥n了,整个排列可以分成三个部分,:前n-k个,中间2k-n个,后面n-k个
第一个部分每个数要大于第三部分的对应位置的数
因为字典序要小,所以我们优先给第一部分排最小的数,但是第三部分整体比第一部分小,所以我们给第一部分分配前2n-2k个数中的偶数(2,4,6,...),给第三部分分配前2n-2k个数中的奇数(1,3,5,...),剩下最大的数分给第二部分,从小到大排序。
这是满足k-有序的条件下字典序最小的,现在来证明他不是t有序的。
当t不等于k时,有a[1]<a[1+t],因为a[1]=2,只有a[1+k]小于他,所以这个序列不是t有序的。
--------------------------------------------------------
M:(题目状态:赛后通过)
就是说问你长度为n的排列中有多少个用快速排序进行排序需要恰好k次操作。
快速排序是这样的:
sort()
1.如果序列长度为0,返回0
2.选中第一个数,比他小的放到左边,比他大的放到右边
3.返回操作数为序列长度+sort(左边)+sort(右边)
n≤30,k≤900
 
dp,设f[i][j]表示长度为i的序列,恰好k次操作的方案数
那么只需要枚举序列的第一个数x,枚举左边的操作次数l,右边的操作次数r,转移就是:
f[i][l+r+i] <- f[x-1][l] * f[i-x][r] * C(i,x-1)
--------------------------------------------------------
 
比赛总结
--------------------------------------------------------
这一场心态爆炸
一方面,在过题数落后的情况下很慌,结果很sb的错误都没有找出来
另一方面,在一两道题上吊死了,有很多送分题连题都没有看
总之需要注意对心态的控制,尤其是这种时间很紧张的比赛。
还有就是注意时间分配,不能在一道题上吊死。
--------------------------------------------------------
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter