Misaka16172's Blog

思路 思路是简单的，使用分层图的思想递推地求出对于每个格子走了 k≤n×mk\leq n\times mk≤n×m 步之后最大的价值（记为 valx,y,kval_{x,y,k}valx,y,k​，递推式为 valx,y,k=max⁡{valx′,y′,k−1+ax,y},∣x′−x∣+∣y′−y∣≤1val_{x,y,k}=\max\{val_{x',y',k-1}+a_{x,y}\},|x'-x|+|y'-y|\leq 1valx,y,k​=max{valx′,y′,k−1​+ax,y​},∣x′−x∣+∣y′−y∣≤1），记 mk=min⁡(k,n×m)mk=\min(k,n\times m)mk=min(k,n×m)，最后答案则是 max⁡{valx,y,mk+ax,y×(k−mk)}\max\{val_{x,y,mk}+a_{x,y}\times (k-mk)\}max{valx,y,mk​+ax,y​×(k−mk)}，时间复杂度 O(n2m2)\mathcal{O}(n^2m^2)O(n2m2)。 这里证明一下“至多走 n×mn\t ...

思路 观察到 ∣s∣|s|∣s∣ 只有 555，于是考虑状态压缩。 可以枚举一个位数为当前字符串长度的二进制数 ststst，每一位代表这一位是否进行匹配。然后我们就可以根据 ststst 再进行一次状压，把字符串压成一个 272727 进制的数，每一位 ≥1\geq 1≥1 时代表字母，是 000 则代表这一位没有被匹配。这个数的最大大小为 ∑i=0426i<1.5×106\sum^{4}_{i=0}26^i<1.5\times 10^6∑i=04​26i<1.5×106，可以直接开数组统计。 插入时，我们把字符串对应的所有状态曾经对应过的 xxx 取 min⁡\minmin，查找时按匹配度从大到小查询，如果当前答案不为 inf 就直接输出，这题就做完了，复杂度 O(2∣s∣∣s∣×q)。\mathcal{O}(2^{|s|}|s|\times q)。O(2∣s∣∣s∣×q)。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445constexpr ...

前言 非常好交互题，使我的思维旋转。大概是最近几场 abc 里唯一一道比较值得带脑子做的 E 题。 思路 按照题意模拟后，可以画出一张允许被查询的区间的示意图： 你会发现这个东西长得跟线段树很像，但如果把线段树的递归查询函数照葫芦画瓢写上就会发现 WA 了三分之二的测试点，原因则是交互次数不能保证最优，比如说图里的 [1,7][1,7][1,7] 实际上只用查 [0,7],[0,0][0,7],[0,0][0,7],[0,0] 两次，用这种方法需要查 [1,1],[2,3],[4,7][1,1],[2,3],[4,7][1,1],[2,3],[4,7] 三次。 上面的乱搞给了我们一个启示，那就是最优的询问次数很可能小于 log⁡n\log nlogn，从而我们可以推断，我们需要使用的询问方式并不是一种基于复杂度分析的通用策略（因为不管什么固定策略都不会比 log⁡\loglog 的询问复杂度更优秀了），而是会根据输入动态调整的。此时可以开始考虑如何转化题意，使问题更加可做。 转化 看了官方题解的应该都知道是把询问转化成图上的边然后跑最短路，这里解释一下这样做的实际意义，便于理解。 ...

前言 没想到自己参加的第一场 ACM/ICPC 正式比赛竟然会在高中。 Day 0 机房用 SEERC 2018 的题出了场模拟赛。 我们队只切了三个题，说实话表现比较惨。隔壁小朋友 hyf 他们的队伍竟然切了 6 题，能不能每一队都发一个小朋友来 carry。 切掉的三个题里只有 E - [SEERC2018] Fishermen 是我自己做出来的，明明是签到题还花了好久时间。zzj 写掉了 [B - SEERC2018] Broken Watch 和 C - [SEERC2018] Tree，思路是 cyx 和 zzj 两个人一块想出来的，我参与的比较少。唉还是只能靠队友带飞。赛时还和 cyx 想了 D - [SEERC2018] Space Station 和 H - [SEERC2018] Modern Djinn，但是毫无结果。 赛后一翻题解，卧槽 H 正解怎么是个随机化，有病吧。J 明明这么可爱场上却没人做，应该是被题面吓跑了。 希望今天的发挥能给明天涨点 rp。 Day 1 昨天晚上没睡好，可能也有一部分是【数据删除】的缘故，早上不到六点就爬起来了。 带了一本紫书和 C ...

前言 很有意思的一道题。 做法参考了 CF 官方题解。 思路 考虑进行一次操作会对其他元素造成的影响。 删除 aia_iai​ 会使其右边的所有元素下标减少 111，而我们的任务是让最后得到的集合 SSS 字典序最大，所以我们希望每个数的下标都尽量不要减少。 但问题在于 SSS 并不是一个可重集，故我们不能直接从右往左执行操作，因为这样给 SSS 带来的元素虽然是最大的，但可能会出现重复的情况，例如样例里的 2 1，如果先删右边的 111 再删 222 就会带来两个重复的 333，去重后字典序小于答案 3 2。 于是我们可以考虑每个数的下标减小了几次，记作 ci (0≤ci<i)c_i\ (0\leq c_i<i)ci​ (0≤ci​<i)，则任务就变成了对于每个 aia_iai​ 找到最小的 cic_ici​，使得对于任意 j<ij<ij<i，ai+i−ci≠aj+j−cja_i+i-c_i≠a_j+j-c_jai​+i−ci​​=aj​+j−cj​。发现无论求解 cic_ici​ 的顺序如何，答案最优性都不会受到影响。 同时，由于 c1=0c ...

1ac26911158bb0a0335098254784b1df401a9a7299d482560702102f8d41a2ac5859957abeb416857fbc04b087c5fb2074335ec31d6efcdb66cf5b48859746fdefc6e4250f78b87129c3d3002ad4a375c3226128a2a4faf56902924bc91b309e20c21f1d52ad5c02a527e66e8f69a87c7d115b8fe1183892ab607dff0706219fdd234c89db47f5d993b5af8287d7c6f63f170c1cbe621333eccf0ca37f63334c30468a00397ef34a9ca65e927e16c1308a57db645427c0f983ab42665189b0ecc44f5f739920fb29ce220eec944837df8c54ed3ab315a5eab1596b437d0ac1ebb1a03983c4d79add12a33f0274b18a00da7071e73ea0c56d0 ...

前言 非常有趣的一道双指针好题，前前后后思考了好几天并写了一天半，终于实现了题解大佬的线性做法，做完这道题也让我对双指针以及函数单调性有了更深的理解。目前已经在所有 oj 上都 AC 了，正确性应该是没有问题的。这篇做题笔记思路与该大佬的题解基本一致，在细节方面有一些补充。 思路 这道题的切入点就是观察最终序列的翻转方式。 性质 1 观察可得性质 1： 最终序列被翻转的卡片一定是一段前缀和一段后缀。 证明 1 由于给出的 aaa 是升序的，所以翻转中间的卡片要么对最小值和最大值无影响（因为中间的 aia_iai​ 一定 ≥a1\geq a_1≥a1​，≤an\leq a_n≤an​），要么会使最小值更小/使最大值更大，而我们要求的是最小极差，所以翻转中间的卡片没有意义。 思考怎么用这个性质去解题。 设已经翻转了长度为 lll 的一段前缀和长度为 rrr 的一段后缀，可以定义如下变量： lmaxl=max⁡{bi}(1≤i≤l)lmax_l=\max\{b_i\}(1\leq i\leq l)lmaxl​=max{bi​}(1≤i≤l)； lminl=min⁡(min⁡{bi ...

题意 有 NNN 个球，每一个球有一个颜色 CiC_iCi​ 和价值 ViV_iVi​，现在要删除其中的 KKK 个球，使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。 数据范围 1≤K<N≤2×1051\leq K < N \leq 2\times 10^51≤K<N≤2×105 K≤500K \leq 500K≤500 思路 考虑 dp。 设计状态 fi,jf_{i,j}fi,j​ 代表不删除第 iii 个球，在前面删除 jjj 个球时最大的价值总和。 则 fi,jf_{i,j}fi,j​ 一定由前面的第 kkk 个球删除 (k,i)(k,i)(k,i) 之间的全部 i−k−1i-k-1i−k−1 个球转移而来，状态转移方程为 fi,j=max⁡{fk,j−(i−k−1)}(j≤K,i−j−1≤k<i,ci≠ck)+vif_{i,j}=\max\{f_{k,j-(i-k-1)}\}(j\leq K,i-j-1\leq k<i,c_i≠c_k)+v_ifi,j​=max{fk,j−(i−k−1)​}(j≤K,i−j−1≤k<i ...

前言 更可爱的阅读体验 思路 前置芝士：CF1764G1 的解法。 考虑在 G1 的基础上进行一个小小的优化。 G1 的最大询问次数是 3log⁡n3\log n3logn，其瓶颈在于当 nnn 为偶数时，我们需要预先额外花费 log⁡n\log nlogn 的时间去找到 nnn 的位置，从而消除后续询问里 nnn 的影响，因为这时 nnn 与 111 一样都具有除以 222 向下取整的结果唯一的性质。 而 G2 把最大询问次数限制到了 252525 次，所以我们需要找一种更高效的辨别 nnn 和 111 的方式来代替预先询问。 当我们对 [1,k][1,k][1,k] 和 [k+1,n][k+1,n][k+1,n] 两个区间进行询问时，除了 111 和 nnn 之外，两个区间里无法配对数字的数量一定是相等的，那我们可以分类讨论 111 和 nnn 的位置： 当 111 和 nnn 在同一个区间里时，这个区间里未配对的数字个数会比另一边大 222，于是继续处理这个区间就好。 当 111 和 nnn 分居在两个区间里时，两个区间里未配对的数字个数相等，我们只需要对其中一个区间进行一次 ...

思路 赛时没想出来贪心，于是写了爆搜但一直 WA，赛后发现是 dfs 函数忘记回溯了。 时间复杂度看起来是假的，但是跑得很快，推测是一堆卡牌里面能够进行匹配的数量实际上并没有那么多，实测最慢的点才 15ms，提交记录：link 爆搜的方法就是先用 (2n)2(2n)^2(2n)2 的时间预处理每两张牌是否能够匹配（匹配条件即两张牌中有且只有一张能赢过对方），然后再从第一张牌开始搜：对于每一张牌枚举和它匹配的另一张牌，标记之后接着搜下一张，搜不到就回溯继续搜，终止条件就是搜到第 2n2n2n 张牌时 return 1 以及无解时 return 0。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667constexpr int N = 40;char trump;int n;struct card{ char suit;int rank; inline void ...