Day 5

今天似乎神奇地出现了四题？估计咱又要被虐了吧QwQ
看题戳这=ω

T1 解方程

这题似乎有点裸
不定方程的最小正整数解。。。除了扩展欧几里得还有啥。。。
本题要求的是ax+by=c当x在正整数范围内最小以及y在正整数范围内最小时原方程的解。我们可以将其转化为求\frac{a}{g}x+\frac{b}{g}y=\frac{c}{g}的最小正整数解，其中g=\gcd(a,b),这样我们就可以直接套用exgcd求解了。显然,若c \nmid g，原方程无整数解。
我们令c=\frac{a}{g}，d=\frac{b}{g}，求出cx+dy=1的最小正整数解。至于x最小还是y最小，我们互换c、d，带入exgcd求解，即可得出x最小与y最小时的两组解了。
然鹅此时我们求出的是cx+dy=1的解，这并不是题目里要求我们解的方程。我们将方程两边同时乘以\frac{c}{g}，得到c(\frac{c}{g}x)+d(\frac{c}{g}y)=\frac{c}{g}
于是我们就轻松愉快地解决了这道题

了吗？
跑了几组数据之后，你会发现似乎自己的输出和答案差了不少。最大的问题在于，虽然我们求出的是cx+dy=1的最小正整数解，但是这并不意味着这组解在c(\frac{c}{g}x)+d(\frac{c}{g}y)=\frac{c}{g}这个方程下最小。我们注意到，c(\frac{c}{g}x-d)+d(\frac{c}{g}y+c)=\frac{c}{g}也成立，那么我们可以令答案为\frac{c}{g}x \mod d(此处以x最小作为示例)，这样得到的答案一定是正确的（当然不排除您打挂的可能）。

T2 买卖

看似DP的暴力。或许我应该感谢这道题？感觉要不是被我的神奇直觉劝退了我可能就不会去做T4了（虽然T4最后还是打挂了T4）顺便再一次Orz czh，考场上直接看出是贪心（可惜也打挂了）。
我们考虑如下的贪心策略。显然，我们应“低买高卖”，即在买入价格低的地方买入，在卖出价格高的地方卖出，这样可以取得最大收益。维护一个堆，每次将当前位置的买入价格插入，然后若堆顶的值小于当前的卖出价格的话，卖出一定能有收益，我们给答案加上这个差值，此时再将卖出价格插入，即表示若后面有能获得更大收益是，我们可以不在此处卖出（即在这个时候再将刚刚卖出的东西买回来）。
顺便STL是真的方便=wpriority_queue10分钟就搞定这题了

T3 投资

好啦，又到了喜闻乐见的线段树环节Ow（虽说这题似乎用线段树有点亏）
我们可以发现，此题O(n \log n)的时间复杂度是正确的，那么我们考虑下面的这种算法：
对于询问的s、e，我们枚举每一个右端点i，求出i+s-1到i+e-1的前缀和最大值（此处可以用最值线段树维护，时间复杂度O(\log n)），这样，我们就用O(n \log n)的复杂度解决了本题

T4 拉拉队排练

所谓“技多不压身”大概正是如此叭。昨天刚把manacher过了今天就考这有点恐怖啊Qw
我们知道manacher算法能够O(n)求出以字符串任一字符为中心的回文串长度。显然求出一个较长的回文串后我们可以将其两端各删掉一个字符，其仍是一个回文串（注意，题目中只要求求长度为奇数的回文串）。那么，我们开一个桶统计一下各个长度的串共有多少个，扫一遍即可。注意到回文串数目可能很大，应使用快速幂来处理。

The Nights

推了一下堆在U盘里好久的Summer Pockets，希望咱能够成为和zcysky一样优秀的鸟白岛学家
感觉很有趣Qw OP大概是咱推过Gal里面制作比较好的叭（咱没看过sppl的OP==或许那个让中二社变成欧派社的OP可能比SP还要优秀的多吧Qw）据说小游戏是Key社常规？咱反正觉得超级有趣=w
不过以Key社的常规来看，应该还是会虐的叭……毕竟Summer Pockets的脚本可是温暖人心新岛夕+麻枝大魔王+魁写的，G.O老贼的岛就已经能把咱击沉了……可能会哭的不成样子叭
不管啦，反正Summer Pockets给咱的第一感觉非常棒的，大概推完了之后会来写长评叭（前提是咱能顶得住胃痛）