负担集训-Test2
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_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≤ｌ≤ｒ≤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的错误都没有找出来
另一方面，在一两道题上吊死了，有很多送分题连题都没有看
总之需要注意对心态的控制，尤其是这种时间很紧张的比赛。
还有就是注意时间分配，不能在一道题上吊死。
--------------------------------------------------------
评论 (0)
