2021-team10-004

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[wiki:2021-team10 返回]

= 排名 =

[[Image(Rank.png, 1000px)]]

[[Image(status.png, 1000px)]]

= 流水账 =

by csr

开场看题看一题跳一题，看啥啥不会。csr跟榜开H签到，签完之后跟榜开F，lxy上机签F。签完之后没有榜能跟了，于是在每道题上做出了一些无用的努力，之后lxy开始写E。csr和wy继续在其他题上做无用努力。发现榜上大家都在A题做一些看起来有用的努力，于是硬着头皮去想A。lxy写完E的时候csr觉得A好像有点戏了，lxy5发过E的时候csr觉得A会了但写不出。无题可写于是上机写A，写到比赛快结束3A。


= 总结 =

lxy:今天雨太大车开得太慢了，不过因为是jb场大概迟到点问题不大（？），事实果然如此。总得来说硬着头写了之前看到绝对跑路的题，过了还是很好的。别的题想不出来了呜呜呜😭😭😭

csr:开场lxy被大雨堵在路上☔️☔️☔️，一个人坐在机房看一题跳一题像在做梦🆘。但有了一些巨大的进步（指罚坐时长大大缩短）不过上机写A的时候非常自闭……“我不知道我在写啥但我好像写完了”“我不知道我在写啥但它过样例了”“我不知道我在写啥但是我要交了” 虽然A写得很不聪明但它看起来跑的很牛（x） 反思一下的话，就是交流还有问题……后半场的A和E都是单开🆘

wy:被学姐们带飞🆘/不知道自己在干什么☔️/干啥啥不会没有灵魂😭 的一天x //8.17：终于补完J了呜呜学姐们好好

= 题解 =

A:所有字符串排序，暴力求字典序相邻两个串的公共前缀长度。用一个set记录confirmation prefix，每个confirmation prefix是一个pair（i,len），表示串i的前len个字符。每次激活一个字符串i的时候，先找一个len使得所有激活时间>i的串和i的最长公共前缀长度都<len，i串的len前缀就是一个新的confirmation prefix；再从当前的答案set里删除所有这个prefix替代的旧confirmation prefix。理论上删除最多做O(n)次所以复杂度没问题，但找哪个串要删这个part我写的复杂度感觉不太对……但是可能没人这么写所以没被卡x

     update:稍微改了一个if之后复杂度没问题……但不会证它为什么是对的

B:

C:

D:

E:讨论，考虑快速改变单维贡献，线段树一下。

F:刚刚出栈和入栈的两个数必须不一样，连边，可以发现一个连通块的都必须不一样，所以贪心放进去。

G:

H:二进制下1个数为奇数的涂黑，偶数涂白。

I:

J:点到多边形切线模板求每个灯控制区间，然后环上最小覆盖可以倍增。

K:

返回

排名

流水账

by csr

开场看题看一题跳一题，看啥啥不会。csr跟榜开H签到，签完之后跟榜开F，lxy上机签F。签完之后没有榜能跟了，于是在每道题上做出了一些无用的努力，之后lxy开始写E。csr和wy继续在其他题上做无用努力。发现榜上大家都在A题做一些看起来有用的努力，于是硬着头皮去想A。lxy写完E的时候csr觉得A好像有点戏了，lxy5发过E的时候csr觉得A会了但写不出。无题可写于是上机写A，写到比赛快结束3A。

总结

lxy:今天雨太大车开得太慢了，不过因为是jb场大概迟到点问题不大（？），事实果然如此。总得来说硬着头写了之前看到绝对跑路的题，过了还是很好的。别的题想不出来了呜呜呜😭😭😭

csr:开场lxy被大雨堵在路上☔️☔️☔️，一个人坐在机房看一题跳一题像在做梦🆘。但有了一些巨大的进步（指罚坐时长大大缩短）不过上机写A的时候非常自闭……“我不知道我在写啥但我好像写完了”“我不知道我在写啥但它过样例了”“我不知道我在写啥但是我要交了” 虽然A写得很不聪明但它看起来跑的很牛（x） 反思一下的话，就是交流还有问题……后半场的A和E都是单开🆘

wy:被学姐们带飞🆘/不知道自己在干什么☔️/干啥啥不会没有灵魂😭 的一天x //8.17：终于补完J了呜呜学姐们好好

题解

A:所有字符串排序，暴力求字典序相邻两个串的公共前缀长度。用一个set记录confirmation prefix，每个confirmation prefix是一个pair（i,len），表示串i的前len个字符。每次激活一个字符串i的时候，先找一个len使得所有激活时间>i的串和i的最长公共前缀长度都

update:稍微改了一个if之后复杂度没问题……但不会证它为什么是对的

B:

C:

D:

E:讨论，考虑快速改变单维贡献，线段树一下。

F:刚刚出栈和入栈的两个数必须不一样，连边，可以发现一个连通块的都必须不一样，所以贪心放进去。

G:

H:二进制下1个数为奇数的涂黑，偶数涂白。

I:

J:点到多边形切线模板求每个灯控制区间，然后环上最小覆盖可以倍增。

K:

附加文件