移动类匹配——固一枚一：ARC154C
移动类匹配——固一枚一：ARC154C
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133606890
https://atcoder.jp/contests/arc154/tasks/arc154_c?lang=en
发现本质是两个环旋转的匹配。 题目支持 ，所以我们可以固定一个开头（B的），枚举A的开头再暴力匹配
此题中，能转的充要条件是由两个连续相同的。当发现这一点后，可以考虑特判，而不是归纳（理论上遇到应该先拓展，再看是归纳还是特判）。
选定B的开头是个技巧，为了方便后面匹配，我们应该选某个连续段的开头
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-14
【洛谷P2134 百日旅行】 题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552404.html 题目描述 小明和小红还剩下N天的假期，小明可以安排旅行的计划。如果连续X天旅游，小明需要花旅行费用PXX元；如果连续X天不旅游，小明需要请小红吃饭，花费为Q*X元。（P,Q都是输入的常数） 请你帮小明写一个程序，计算出假期里他至少需要花费多少元。 只会贪心做法… 首先可以明确一点，在天数相同的情况下，吃饭天数连不连续不重要，旅行天数能分开就分开。 于是我们可以直接枚举吃饭天数 iii，剩下的 n−in-in−i 天旅游...
2022-05-13
【一本通 1488：新的开始】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16267581.html 题目链接 题目 发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 nnn 口矿井，但他似乎忘记考虑的矿井供电问题…… 为了保证电力的供应，小 FF 想到了两种办法： 在这一口矿井上建立一个发电站，费用为 vvv（发电站的输出功率可以供给任意多个矿井）。 将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 ppp。 小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想...
2023-11-09
类直径树上贪心
类直径树上贪心 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134317828 http://cplusoj.com/d/senior/p/SS231109C 场上想到枚举点，然后最大值为高，然后可以求最大值。但是感觉计数会重 计数其实不会重，如图中，红色线段显然比蓝色线段优 所以我们枚举3叉点时没错的 123456789101112131415161718192021222324252627282930313233343536373839404142...
2023-12-18
约束条件转保序回归问题——之间用贪心+单调栈维护：P7294 / 1218T3
约束条件转保序回归问题——之间用贪心+单调栈维护：P7294 / 1218T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135067510 https://www.luogu.com.cn/problem/P7294 http://47.92.197.167:5283/contest/439/problem/3 发现行很大，那肯定是一列列枚举。 考虑单个询问 (x,y)(x,y)(x,y) ，假设第 iii 列向第 i+1i+1i+1 列的转折点是 p...
2023-09-07
异或和大小比较类问题——抓住最高位：CF1863F
异或和大小比较类问题——抓住最高位：CF1863F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186 https://codeforces.com/contest/1863/problem/F 因为有等于，所以考虑异或和为0的合法区间，它可以随意切 现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？ 此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是...
2023-10-05
长剖与贪心+树上反悔贪心：1004T4
长剖与贪心+树上反悔贪心：1004T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133575747 长剖的本质是一种贪心。（启发式合并本质也是类似哈夫曼树的过程） 在此题中，首先肯定变直径，然后选端点为根。然后选叶子。而每个叶子为了不重复计算，可以只计算其长剖后所在链的贡献。（本题精髓，用长剖来贪心） 然后钦定某个点必选，就是一种反悔贪心。很显然的思路是删掉排名 2∗k−12*k-12∗k−1 的叶子，但考虑： 所以需要考虑离其最近被选的点 1234...