CodingCow's Blog - Code solves everything

2024 TYOI 暑假集训游记 Day 0 第一天晚上刚到机房就被制裁了。原来放假的时候有比赛，一场没打）：，全去搞文化课了。 Day 1 开幕雷击，上来就比赛，随便水了一下，接近垫底了。太久没有打比赛手感就是不好。 Day 2 - End 此后就开始一直学算法，KMP、Trie 树、AC 自动机什么的都不难，到 DP 就老实了。还好后面回归算法，讲了树剖，舒服了。 最后一天打 CPC，

Luogu P7537 [COCI2016-2017#4] Rima 题解 题意 简单类说就是通过拼接字符串，实现两个字符串之间的最长公共后缀长度恰好是较长的字符串的长度 \(-1\)。并使得最长公共后缀长度最长。 思路 随便做即可。 首先我们观察到题目要求的是后缀，但是显然求后缀的算法并不是很多，于是我们考虑将其反转。然后题目就变成了求前缀。 反转完我们继续考虑怎么做，对于这种字符串的问题，我们

OiClass PUJI P2232 Friends 题解 思路 容易发现枚举添加的是哪个字符是很好的，但是我们需要解决哈希的问题。 考虑拼凑，不难发现，对于 ABXC 去掉 X 之后的 AB C 这个字符串，他的哈希是 AB 的哈希乘上 C 的位权。于是我们分类讨论一下删去的字符在哪个位置，然后分别处理即可。 但是在统计答案的时候仍然有很多细节。首先是不能在每次都记录字串，因为取字串的函数复杂度

OiClass TIGAO P3280 牛牛的猜球游戏题解 思路 首先考虑暴力的做法，直接依题意模拟模拟，时间复杂度是 \(\mathcal{O}(nm)\)，显然不能通过。但是我们可以发现这种修改方式似乎很适合预处理，然后我就想到了使用前缀和的做法。然后每次进行替代，但是经过一段时间的调试，无法通过，果断放弃。 我们考虑时间复杂度稍高的分块做法，我们规定块长为 \(\sqrt{n}\)，然后将

OiClass TIGAO P3279 牛牛的方程式题解 思路 首先观察一下方程：\(ax+by+cz=d\)。观察可以得到，他有整数解当且仅当 \(\gcd(a,\, b,\, c) \equiv 0 \pmod d\)，也就是说 \(d\) 被 \(a,\, b,\, c\) 的最大公因数整除。显然这是正确的。 但是通过以上的思路，我们只能通过小样例，在面对大样例的时候这个方法仍然有些力不从心

OiClass TIGAO P3333 路径难题题解 思路 首先考虑暴力建边的做法，我们使用 \(\mathcal{O}({t_i}^2)\) 的时间建立公交站的边。然后我们考虑如何计算答案。考虑到每次坐公交车的时候都会进行出租车的结算，于是我们直接累计到最后才向上取整的做法是没有正确性的。 于是我们考虑每次到公交节点的时候就进行向上取整，这样就可以保证 Dijkstra 的正确性。 这样就解决了

OiClass PU2TI P3042 拓展的奇拼图题解 思路 首先发现这题是八数码问题的加强版，但是数据量非常大，爆搜+剪枝的方法非常的不可取，于是我们考虑是否可以通过一些神秘的判断方法来判断出是否可以构造出来。 从数据量可以感受出来应该是使用某种接近线性的算法，果断猜测是否是逆序对。把矩阵展开后去掉 \(0\)，然后计算逆序对个数，判断奇偶性即可。 代码 1234567891011121314

OiClass PU2TI P3186 小美的排队次数 题解 思路 以下格式模仿睿智的官方题解。 \(10\,\%\) 做法：呵呵，对于这种神奇的算法还是表示不明觉厉。 \(40\,\%\) 做法：呵呵，依题意模拟计数即可。 \(100\,\%\) 做法：呵呵，随便做即可。考虑以下先做一轮，观察一下有什么性质。手磨样例，一轮以后是 1, 2, 3, 5, 4, 6 发现每一次只可能交换相邻的两个

SPOJ SETSTACK 题解 题意 有一个装着集合的栈，需要你实现以下操作： PUSH. 将把空集 \(\{\}\) 推到堆栈上。 DUP. 将复制最顶层的集合（弹出堆栈，然后将该集合推入堆栈两次）。 UNION. 会弹出堆栈两次，然后将两个集合的联合值推入堆栈。 INTERSECT. 会弹出堆栈两次，然后将两个集合的交集推到堆栈上。 ADD. 会弹出堆栈两次，将第一个集合加入第二个集合，然

SPOJ MARTIAN 题解 思路 首先简单理解一下题目，会发现题目就是在网格上选择若干列（或列的上面一段）以及若干行（或行的左边一段）似的这些被选中的列和行之间的和最大。具体可以看题目的这张图： 很明显这是一个 DP 问题，于是我们着手设计状态转移方程。首先我们先分别预处理出纵向的和横向的两个前缀和分别是 \(y_{i,\,j}\) 和 \(b_{i,\,j}\)，字母对应题目的矿物名称首字