2019-Sp050-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(3.png,700px)]]
[[Image(2.png,700px)]]
[wiki:2019-team2 返回Runespoor]
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001421 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 今天我感觉状态很差。可能因为前天晚上和昨天的事情，现在还有一点虚弱，我会尽快调整好状态。
今天A题可能想到的是另一个方向，比直接后缀自动机多了一点点转化，但是其实也挺好写的。但是我忘了并查集需要双向维护。
G题本来是很简单的签到题，结果还想了挺久，还写了一个错误的算法。然后J题还迷迷糊糊的读错了
E题我们都感觉都是exgcd解同余方程，但是连ax + by = c解出来以后怎么得到方案都没有想到。感觉我的锅真的很大，不知道在想什么
最后时间不够去搞构造然后很快写完算是一个比较好的策略吧
其实感觉D也是可以想到的，只是没有时间了。
'''lyk:''' 开局给A题想了个假的做法浪费半小时。有空学学后缀自动机。
=== 题解 ===
[wiki:2017-Sp267-team2 legilimens]
* A : 后缀自动机对每个右端点求最长的合法括号序列。或者找出每个合法的括号序列（只有O(n)个），递归的找，加入分隔符。然后重新定义字符，跑后缀数组求权值和 * 出现次数最大的子串。注意并查集如果要维护向两边走要双向写，或者直接维护联通的一块，在记录左右端点。
* C ：一定是999910.......枚举组成10的数对，对剩下的数DP计算方案数。注意选相同的数要一起考虑贡献
* D ：也一定是组成99999k...枚举k的大小，如果k >= 10则尽量把后面数填小。k <= 8则填大。可以贪心完在考虑进位，很好写。特判全为9
* E ：设a < b , exgcd解方程（ ax + by = c ）后希望abs(x)尽量小。答案是 2 * (abs(x) + abs(y) - 1 + (x > 0 && a < c)) 减掉的部分是以为a瓶太小，装不下这么多水，需要转移到b瓶
* F ： @Heltion
* G ：一定选值域连续的一段。注意两边都不完整的情况
* I ： 非常巧妙的想法。可以用归纳法证明一定走斜率小的更优。把行和列建成点 ：（i,row[i]） , (j,col[j]) 分别求凸包，然后每次选斜率小的走（注意走到下一个点的意思是花费另一边的贡献）
=== 补题 ===
* A ： zqq
* D ：zqq
* E : zqq
* I : zqq
流水账
总结
zqq: 今天我感觉状态很差。可能因为前天晚上和昨天的事情，现在还有一点虚弱，我会尽快调整好状态。
今天A题可能想到的是另一个方向，比直接后缀自动机多了一点点转化，但是其实也挺好写的。但是我忘了并查集需要双向维护。
G题本来是很简单的签到题，结果还想了挺久，还写了一个错误的算法。然后J题还迷迷糊糊的读错了
E题我们都感觉都是exgcd解同余方程，但是连ax + by = c解出来以后怎么得到方案都没有想到。感觉我的锅真的很大，不知道在想什么
最后时间不够去搞构造然后很快写完算是一个比较好的策略吧
其实感觉D也是可以想到的，只是没有时间了。
lyk: 开局给A题想了个假的做法浪费半小时。有空学学后缀自动机。
题解
- A : 后缀自动机对每个右端点求最长的合法括号序列。或者找出每个合法的括号序列（只有O(n)个），递归的找，加入分隔符。然后重新定义字符，跑后缀数组求权值和 * 出现次数最大的子串。注意并查集如果要维护向两边走要双向写，或者直接维护联通的一块，在记录左右端点。
- C ：一定是999910.......枚举组成10的数对，对剩下的数DP计算方案数。注意选相同的数要一起考虑贡献
- D ：也一定是组成99999k...枚举k的大小，如果k >= 10则尽量把后面数填小。k <= 8则填大。可以贪心完在考虑进位，很好写。特判全为9
- E ：设a < b , exgcd解方程（ ax + by = c ）后希望abs(x)尽量小。答案是 2 * (abs(x) + abs(y) - 1 + (x > 0 && a < c)) 减掉的部分是以为a瓶太小，装不下这么多水，需要转移到b瓶
- F ： @Heltion
- G ：一定选值域连续的一段。注意两边都不完整的情况
- I ： 非常巧妙的想法。可以用归纳法证明一定走斜率小的更优。把行和列建成点 ：（i,row[i]） , (j,col[j]) 分别求凸包，然后每次选斜率小的走（注意走到下一个点的意思是花费另一边的贡献）
补题
- A ： zqq
- D ：zqq
- E : zqq
- I : zqq