pjudge，质量真的很高！
A. 恰钱
枚举 \(\text{ctz}\) 然后用类似数位 DP 的做法。
B. 排序（DP 优化）
因为某些奇怪原因只会 \(2\log\)。
考虑 DP，然后依次构造栈中元素。定义 \(f_i\) 表示当前栈顶为 \(i\) 且 \(i\) 在最终答案里面的答案。考虑是直接加还是替换。假设 \(nx_i\) 表示 \(i\) 后第一个大于 \(i\) 的元素位置，那么 \([i+1,nx_i]\) 之间的元素是可以直接加进去的。考虑替换怎么替换，发现如果加入 \(nx_{nx_i}\) 之后就没救了，所以下标要在 \((nx_i,nx_{nx_i})\)，并且值域在 \((a_i,a_{nx_i})\) 之间。
可以用类似扫描线的方法加入操作，线段树上维护 multiset，可以做到 \(2\log\)。但是你发现第一类点是不存在的！并且第二类点一定满足上界！那么值域限制就变成后缀了，可以扫值域做到单 \(\log\)。
所以 DP 一定要注意去除一些本来就满足的条件，不然会多一些 \(\log\)。
C. 图同构（操作类问题、操作转化）
很厉害！
把操作转化为：交换两个数，并且交换颜色并反色。那么一个点从起始位置到终止位置经过的路径长度的奇偶性决定了它的颜色。二分图没有奇环所以不能转化路径奇偶性，否则就可以。瞎猜结论就行了。
最近遇到了不少这种操作题，有些操作本来就不是给人理解的，需要等价地转化操作 / 在不同的模型上讨论操作。在此题中，做颜色实际上是好做的，但是颜色和数字的不统一性使得颜色的做法很难进一步推广到值上面，这个转化把将颜色和数字达成了统一。
在考虑可扩展性的时候不一定需要单单关注被扩展的算法本身，还可以在两个做法相接的地方做一些转化（我在说什么）
D. 找零（DP 优化、决策单调性）
决策单调性。这个问题揭示了正权值背包存在一个 \(\mathcal{O}(\max Vn\log n)\) 做法，\(V\) 是代价。
随便猜几个小结论：不会把 \(1\) 抵消，不会合并两个物品。这样可以把每个点代价看成 \(\left\lceil\dfrac{a_i}{5}\right\rceil\cdot 5\)，权值看做 \(a_i-\left\lceil\dfrac{a_i}{5}\right\rceil\cdot 5\)。然后就变成了一个背包，有显然 \(\mathcal{O}(n^2)\) 做法。
看起来这个 DP 比较基础，但是实际上它还有优化空间。考虑一次加入相同代价的数，显然我会选权值小的。那么确定选的个数 \(x\) 后，代价 \(f(x)\) 为排序后的前缀和第 \(x\) 位置。这个代价是凸的，可以使用决策单调性优化到 \(\mathcal{O}(n\log n)\)。
因为后面还有一些奇怪的内容所以代码不想写了。
总结
B 和 D 都是 DP 优化相关问题。B 体现我在数据结构问题上不太熟练，思维比较混乱，不能关注到重要的条件。D 的话就是对于 DP 优化还不敏感吧，有些基础优化的使用范围其实很广，需要做题人敢于尝试而不是放弃优化去找一些其它的状态设计。另外要特别注意决策单调性，作为冷门考点它的适用范围实际上相当广，并且也比较灵活。
C 的话我本来就不应该会，但是转化操作的思路还是可以学的（
标签：转化,log,NOIP,nx,操作,Div,优化,Public,DP From： https://www.cnblogs.com/yllcm/p/16757902.html