简介此文为本人泛刷思维题的简要题解，用以记录一些思维精彩的题。 折叠的代码中有原题链接方便跳转。（实现过于简单的题直接提供链接） 正文Luogu_P6075link 题目中 个元素可以看作 种颜色。关键在于注意到每种颜色是独立的，可以分开考虑。 对于一种颜色，在图上染色的轮廓应为左上部分染而右下不染，而每种方案正好对应一条从左下角点出发到达对角线的右上顶点的路径。 如图所示： 由于每条路

简介此文为本人泛刷 AtCoder 过程中遇到题目的简要题解，目的包括但不限于总结题目的思维链。 折叠的代码中有原题链接方便跳转。 正文ARC058B 整个图明显可以划分为两个子问题（合法区域分割为上下两个矩形） 分割线作为边界，枚举点进入分割线的入口进行统计即可。 扩展：如果题目改为 禁入矩形区域 在中间（而不是固定在左下角），那就考虑反面，枚举第一次进入禁入区域的点进行统计。

A范围很小，可以直接 枚举。 复杂度较低的做法是枚举 的决策，然后通过求出最大的正乘积以及最大负乘积来更新答案。用 multiset 来维护 操作后的序列也许实现上较为简单。 B简单贪心，尽可能选 8，奇数情况额外选个 9 （或其他贡献为 的数码）。 C发现答案由 [1s] [2s, 1s] [2s] 组成，考虑用 的 DP 预处理出中间区间 [2s, 1s] 的贡献。 12345678