打表找规律与分析判断：ARC144C
打表找规律与分析判断：ARC144C
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133607035
https://atcoder.jp/contests/arc144/tasks/arc144_c?lang=en
一开始我猜的结论是前后 个预处理，中间贪心。
通过打表：
可以发现是前面 连续块直接暴配，最后一段再用我想的贪心。
究其原因，其实是我们本质上代表着只要大于 就必然有解。所以这样构造必然是对的。
至于直接贪心为何不对，待补坑
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-11-01
树上贪心类——子树之和 / 新贡献：1031T1
树上贪心类——子树之和 / 新贡献：1031T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134170718 http://cplusoj.com/d/senior/p/SS231031A 可以发现从上面打下来，我们有两种对策： 直接引一条上来 下面每条分别对付 我们直接按照这种方法维护一个类似树形dp的东西就行了 123456789101112131415161718192021222324252627282930313233343536...
2021-12-04
【Loj #10002. 「一本通 1.1 例 3」喷水装置】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15643380.html 题目链接 题目 长 LLL 米，宽 WWW 米的草坪里装有 nnn 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W2frac{W}{2}2W 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。 请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？ 思路 首先直径不足 www 直接排除。 然后我们希望每个在覆盖到左边的情况下越右越好。 所以我们按左端点排序后贪心取右端点即可...
2021-12-04
【Loj #10007. 「一本通 1.1 练习 3」线段】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15643524.html 题目链接 题目 数轴上有 nnn 条线段，选取其中 kkk 条线段使得这 kkk 条线段两两没有重合部分，问 kkk 最大为多少。 思路 按右端点排序，贪心选可行的最左右端点。 由于右端点最小可以保证为后面留出更多空间。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243// Problem: #10007....
2023-11-08
树上移动类贪心：1108T4 / CF1381D
树上移动类贪心：1108T4 / CF1381D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134297045 http://47.92.197.167:5283/contest/428/problem/4 我们定义关键点为有3条路径大于 ≥L\ge L≥L 的点。 如果其中一个点可以到达关键点，那么就可行。这是一个充要条件。 我们以关键点为根，如果某个时刻两个点一个是另一个是父亲，那么一定可以开到关键点那里。 我们只需要两个端点轮流往他们子树最深处的地...
2021-11-21
【P1248 加工生产调度】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15584623.html 题目链接 首先考虑两个物品A，B。 假设先做A，则时间为：Ax+max(Ay,Bx)+ByA_x+\max(A_y, B_x)+B_yAx+max(Ay,Bx)+By。 假设先做B，则时间为：Bx+max(By,Ax)+AyB_x+\max(B_y, A_x)+A_yBx+max(By,Ax)+Ay。 对于A、B，我们可以在上面两种情况中取时间较少的方案。 同理，对于每一对物品，我们都可以采用以上方案...
2021-12-05
贪心小结（一本通 1.1 口胡题解）
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15645806.html 本文章对一本通上题目来讲 题解基本上是口胡的，所以很简短。 「一本通 1.1 例 1」活动安排 按右端点排序后优先选右端点靠前的即可。 「一本通 1.1 例 2」种树 按右端点排序，对于每个区间差多少棵就在它尾部重多少棵，双指针维护一下。 「一本通 1.1 例 3」碰水装置 排除不行的后计算出左右端点，然后在满足覆盖左边的情况下贪心使右边最右即可。 「一本通 1.1 例 4」加工生产调度 考虑两个商品的情况作为快排依据，...