Misaka16172's Blog

前言 这个题真的是太困难了。 思路 考虑从每个人向他想坐的地方建图。 发现 ≤n\leq n≤n 的点出度均为 111，>n>n>n 的点出度为 000，如果联通块里全是 ≤n\leq n≤n 的点那里面就有 nnn 条边，否则就有 n−1n-1n−1 条边（因为构成一个联通块至少需要 n−1n-1n−1 条边），所以这一定是一个内向基环树 + 内向树森林。 然后我们考虑怎么选座位。分类讨论，对于树的情况答案为树上到根节点的最长链长度再 -1（根节点 ≥n\geq n≥n 所以根节点可以随便让人坐），而基环树的情况只能选环上的所有节点，不然就有人没地方坐。 实现上，树的情况可以对于每个 ≥n\geq n≥n 的点 dfs；基环树的情况直接拓扑排序，没有出队过的点一定在环上，求出一共有几个点没有入队即可。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344constexpr int N = 2e5+5;vector<int> tr[N];set ...

前言 怎么题解区全是假做法，这里提供一个和标解思路略微不同的方法。 思路 对于每个 xix_ixi​，设 xi=⌈kα⌉−1x_i=\lceil k\alpha\rceil-1xi​=⌈kα⌉−1，解不等式可得 xi<kα≤xi+1x_i<k\alpha \leq x_i+1xi​<kα≤xi​+1，考虑枚举 kkk 把不等式解集转化成一堆区间（即 [xik+eps,xi+1k][\frac{x_i}{k}+eps,\frac{x_i+1}{k}][kxi​​+eps,kxi​+1​]），同时注意到答案保底为 111，于是可以忽略右端点在 111 左边的区间，这样枚举到 kkk 的上界就不会超过 xix_ixi​。 于是问题就变成了找到最大的、被每个 xix_ixi​ 形成的区间都覆盖过的数，而这个过程可以离散化后用差分解决；具体地，枚举每个 xix_ixi​，将其形成的所有区间都推平为 111，处理完之后将每个当前为 111 的下标的 sumsumsum 值都加上 111，最后 sum=nsum=nsum=n 的下标就是合法的。 容易发现答案一定是某个区间的右端点 ...

前言 第一次场切 G（虽然被 after_contest 叉了），纪念一下。 思路 贪心地，考虑最优秀的操作一定是修改中间的一个元素，把左右两边的 LIS 接在一起。 于是可以预处理每个以每个下标 iii 开头 / 结尾的最长 LIS 长度 RiR_iRi​ 和 LiL_iLi​，然后枚举右边 LIS 开头的下标 rrr，代表修改 ar−1a_{r-1}ar−1​ 的值，则答案为 max⁡r=2n+1{Rr+max⁡l=0r−2{Ll}(al+1<ar)+1}\max^{n+1}_{r=2}\{R_r+\max_{l=0}^{r-2}\{L_l\}(a_l+1<a_r)+1\}maxr=2n+1​{Rr​+maxl=0r−2​{Ll​}(al​+1<ar​)+1}。 预处理和统计答案使用离散化 + 线段树优化 dp 实现即可，时间复杂度为 O(nlog⁡n)\mathcal{O}(n\log n)O(nlogn)。 需要注意的是统计答案时，应先将 a0a_0a0​ 设为极小值，an+1a_{n+1}an+1​ 设为极大值，这样就可以分别覆盖到左边的 LIS 为空和右 ...

思路 一眼看上去像一个 dp，但怎么 dp 不太显然。 先考虑爆搜怎么打：最先爆搜获得了 000 个暗物质时的状态，枚举接下来做哪个实验，再枚举这次实验产生了多少暗物质并继续爆搜，对每个实验的结果取 min⁡\minmin（最坏情况下），再对 nnn 个实验的 min⁡\minmin 值取 max⁡\maxmax（最多能得到多少利润）。 于是我们得到了一个倒着的 dp 式子：fx=max⁡i=1n{min⁡j=x+lix+ri{fj+109×(j−x)}−cj}f_x=\max^n_{i=1}\{\min^{x+r_i}_{j=x+l_i}\{f_j+10^9\times (j-x)\}-c_j\}fx​=maxi=1n​{minj=x+li​x+ri​​{fj​+109×(j−x)}−cj​}，要枚举 x,i,jx,i,jx,i,j 三维，复杂度为 O(a2n)\mathcal{O}(a^2n)O(a2n)，最后答案为 f0f_0f0​。 考虑怎么优化掉一个 aaa，把 min⁡\minmin 里面的式子拆出来，得到 min⁡{fj+109×j}−109×x−cj\min\{f_j ...

前言 这远古题怎么还能交题解。 思路 考虑使用数据结构直接模拟题目操作，这里直接使用线段树。 线段树的下标代表内存空间，每个节点里存两个 int 和一个 pair，两个 int 分别代表当前节点里有几个下标已经有数了，另一个只在叶子节点有用，代表当前节点存储的数是多少；pair 第一维代表访问次数，第二维代表插入时间。同时开一个 map，记录某个数在内存里的下标。 模拟过程如下： 若当前数在 map 里有值，则将线段树上其对应下标处加 111，同时答案加 111，否则继续下一步； 使用线段树上二分找出一个还没有被占用的下标，若能找到这样的下标，则将其修改为当前值，同时更新 map 里的下标，否则继续下一步； 若当前所有下标都被占用，则在线段树上查询访问次数最少、插入时间最早的下标，将该位置之前对应的值在 map 里的下标置为 000，并在线段树上修改为当前值。 细节详见代码。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515 ...

思路 思路是简单的，使用分层图的思想递推地求出对于每个格子走了 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 ...