本文从WordPress迁移而来, 查看全部WordPress迁移文章
A:n个骑士(1-n标号)比赛,有m个比赛记录,每个比赛记录的形式为L R winner 表示L到R标号内还没输的人比赛,胜者只有一个就是winner
例如 3 5 4 表示3,4,5比赛,4胜利,3和5都输了,退出
3 7 4 表示4,6,7比赛,4胜利,6和7都输了,退出
题目保证了数据是正确的不会出现矛盾,输出是,n个数字,ans[i]表示第i个骑士是被谁打败的,ans[1] = 5,1骑士是被5骑士打败的,最后胜利的人只有一个,ans[i] = 0
1.一开始ans初始化为0
2.把这些比赛从最后一个开始更新,对于L,R区间的ans值,全部更新为winner,但winner的ans值保持不变
3.依次更新到第1个比赛后,输出所有ans值即可
这样做的正确性就不解释了,还是很容易理解的,因为我的思路是用线段树,其实每个人的ans值是决定于最初的那些比赛的,但是倒过来更新,才方便使用线段树,线段树写了90行,不咋地
1 |
|
B.最后保证了两个短串a,b在翻倍后是更长的,把后来的长串称为S,T。求出lena和lenb的LCM,那么我们只需要知道LCM长度里面的匹配情况即可,后面的都是一样的周期。对于LCM的串,我们以GCD = (lena,lenb)的单位来分割两个串,这样做的结果是,不会出现一部分的分割是尾接着头的
例如 abcd , 不会分割出 cda 这样的尾接着头的串,也就是原来的a和b串都能被完整地分割掉
例如
a = abcd
b = aabbcc
GCD = 2 , LCM = 12
ab cd ab cd ab cd
aa bb cc aa bb cc
分割的结果就是这样
那么对于a串,a[i]可以马上知道它位于一个GCD的单元的哪个位置,那就是 i % GCD
那么a和b串,只要a[i]和b[j]是位于GCD单元的同一个位置的话,他们就会对上,就能比较是否相同
所以,对于a串里面的a[i],位于GCD单元的pos位置,那么b串中位于pos位置的字符都会且仅会和a[i]对上一次
因为只有26个字母,所以我们可以记录GCD单元中pos位置上,26个字母分别有多少个,那么计算起来就很方便了
1 |
|