2023 CCPC Asia Regional Qinghuangdao
Problem D 茶和咖啡
思路
观察到能用的券只取决于最早的选择天数，设当前最早的喝咖啡日为pos，则每新增一天，我们有以下两种策略：
- 选择比目前最早的天数更早的一天，即从
[1, pos-1]天中选择一天。 - 选择比
pos更晚的一天，即[pos+1, n]天。
对于第一种，我们可以做优惠券的后缀和w[i]，表示第i天能享用的优惠券的总优惠，则可知选择第i天的贡献值为w[i]-w[pos]，则最优决策显然为：\(min_{i=1}^{pos-1}(w[i])-w[pos]\)，显然可以用std::set或权值线段树进行维护。
对于第二种，我们只需求[pos+1, n]中最小的a[i]，即\(min_{i=pos+1}^n(a[i])\)。同样用set或权值线段树维护即可。
然后对比两种决策，选更优的决策即可。
*当两种最优决策贡献值相等时，注意到前一种可以使下一次的决策数量增加更多，所以选择向前扩展。
总的复杂度\(O(Tnlog_2n)\)。
## Problem F 质数之谜
思路
注意到，若a[i]+a[i-1]是质数，则a[i]与a[i-1]的奇偶性必然不同（相同相加为偶数）。
可以大胆猜测：对于一个确定的数，我们总能找到一个与其奇偶性不同的数，使二者的和为质数（波利尼亚克猜想）。
进一步观察，发现有特例：1+1=2，2为质数。
则考虑分为几类情况考虑：
- 保持原数不变
- 改为1
- 改为除1外的奇数
- 改为除2外的偶数
对4种情况分类讨论，dp即可。
复杂度\(O(n)\)。