题解leader 1886e wanna
CF938F Erasing Substrings 题解
Erasing Substrings 一个神奇的想法是设 \(f_{i,j}\) 表示在位置 \([1,i]\) 中,我们删去了长度为 \(2^k(k\in j)\) 的一些串,所能得到的最小字典序。使用二分加哈希可以做到 \(O(n^2\log^2 n)\),无法承受。 发现对于状态 \(f_{i ......
[ARC067F] Yakiniku Restaurants 题解
Yakiniku Restaurants 明显在最优方案中,行走方式一定是从一条线段的一端走到另一端,不回头。 于是设 \(f[i,j]\) 表示从 \(i\) 走到 \(j\) 的最优代价。明显,该代价对于不同的券相互独立。故我们依次考虑每一张券。 我们发现,假设有一张位置 \(k\) 的券,则所 ......
[AGC013E] Placing Squares 题解
Placing Squares 关键是将问题从抽象的“正方形面积”转为具象的形式:一段长度为 \(d\) 的区间,有两个不同的小球要放进去,则总放置方案就是 \(d^2\) ,且不同的区间间方案是通过乘法原理结合的,刚好是题目中 \(\prod d^2\) 的形式。 于是我们可以设计 DP:设 \( ......
洛谷P3713 [BJOI2017] 机动训练 题解
机动训练 这题的瓶颈,在于把 \(a_i^2\) 看作 \(\sum\limits_{i=1}^{a_i}\sum\limits_{j=1}^{a_i}1\),然后我们就可以看成“两两相同的机动路径都能贡献 1”。于是我们设 \(f_{x1,y1,x2,y2}\) 表示两条起点为 \((x1,y1) ......
P1864 [NOI2009] 二叉查找树 题解
二叉查找树 首先该树的中序遍历是唯一可以确定的(直接按照数据值排序即可)。 然后,因为权值可以被修改成一切实数,故我们完全可以把权值离散化掉。 于是我们现在可以设置一个 DP 状态 \(f[l,r,lim]\) 表示: 区间 \([l,r]\) 中的所有东西构成了一棵子树,且树中最小权值不小于 \( ......
[AGC030F] Permutation and Minimum 题解
Permutation and Minimum 看到 300 的数据范围,再加上计数题,很容易就往计数 DP 方向去想。 为方便,我们将 \(n\) 乘二。 因为是两个位置取 \(\min\),于是我们便想到从小往大把每个数填入序列。于是DP数组第一维的意义便出来了:当前已经填入了前 \(i\) 小 ......
CF261D Maxim and Increasing Subsequence 题解
Maxim and Increasing Subsequence 首先,我们可以发现,当这个重复次数很大的时候,答案就等于序列中出现的不同权值个数。实际上,这个“很大”就可以被当作“大于等于不同权值个数”。 不同权值个数实际上是 \(\min(n,m)\) 级别的,其中 \(n\) 是序列长度,\( ......
CF979E Kuro and Topological Parity 题解
Kuro and Topological Parity 我们考虑在一张染色完成的图里,我们连上了一条边,会有何影响? \(\bullet\) 在同色节点间连边——明显不会有任何影响。 \(\bullet\) 在异色节点间连边,但是出发点是个偶点(即有偶数条路径以其为终点的节点),终点的路径数增加了, ......
洛谷P3607 [USACO17JAN] Subsequence Reversal P 题解
Subsequence Reversal P 思路: 发现,翻转一个子序列,就意味着两两互换子序列里面的东西。 于是我们就可以设 \(f[l][r][L][R]\) 表示: \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。 则边界为: \(L>R\) 时, \(f=-\inft ......
洛谷P3576 [POI2014] MRO-Ant colony 题解
MRO-Ant colony 根据下取整除法的性质 \((\left\lfloor\dfrac{\left\lfloor\dfrac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\dfrac{x}{yz}\right\rfloor)\),我们可以反 ......
CF264B Good Sequences 题解
Good Sequences 状态很显然,设 \(f[i]\) 表示位置 \(i\) 的最长长度。 关键是转移,暴力转移是 \(O(n^2)\) 的,我们必须找到一个更优秀的转移。 因为一个数的质因子数量是 \(O(\log n)\) 的,而只有和这个数具有相同质因子的数是可以转移的; 因此我们可以 ......
CF908D New Year and Arbitrary Arrangement 题解
New Year and Arbitrary Arrangement 思路: 期望题果然还是恶心呀! 我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便,设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfra ......
洛谷P3118 [USACO15JAN] Moovie Mooving G 题解
Moovie Mooving G 设 \(f[i][S]\) 表示在第 \(i\) 场(注意是场,不是部)电影时,已经看了 \(S\) 里面的电影是否合法。 然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了, \(21\%\)。 发现当一场电影结束后,无论这一场是在哪里看的都没关系。 ......
题解 AtCoder wtf22_day1_b【Non-Overlapping Swaps】
给定一个排列,要求交换最多 $n-1$ 对元素,使得这个排列变成 [1,2,...,n] 的有序排列。
当然没有那么简单,对于交换还是有限制的,对于相邻的两次交换,不妨叫做 $(l_i, r_i)$ 和 $(l_{i+1}, r_{i+1})$,必须满足**这两个交换所对应的区间,没有交集**,即... ......
题解 CF486D Valid Sets
题目链接 相当牛逼。 这种找数量的题型,确定树形 \(dp\) 没跑了。 首先思考常规树形 \(dp\),不难想到设 \(f_{u,a,b}\) 表示以 \(u\) 为根节点的子树内(包括点 \(u\)),最大值是 \(a\),最小值是 \(b\) 的连通子图数量,转移很容易,但是这样时间空间复杂度 ......
原创题题解
实时更新。 众所周知的,原创题就是即原神又创人的题。 当然有的题不会放,等考了在放。 波特 问题描述 流水线上有 \(n\) 个波特,每个波特有一个工作效能 \(a_i\) 。对于每一个波特,当它遇到一个工件时,它会对其进行加工,耗费 \(1\) 个单位时间,然后把它传递给它前面中工作效能最大的波特 ......
NOI2021 庆典题解
又是一道锻炼代码能力的题目。 首先遇到这种求经过多少个节点的题可以先缩点,然后我们考虑那个特殊限制怎么用。 如果对于两个强联通分量 \(x\) 能到 \(z\),\(y\) 能到 \(z\),则 \(x,y\) 之间一定有一个限制,假设这个限制是 \(x\) 能到 \(y\),那么我们可以只记录 \ ......
[AGC003D] Anticube题解
首先对每个数分解只因数,然后把只因数的指数对3取模,把 \(s\) 划分成多个等价类。对于每一个等价类,有唯一对应的另一个等价类不能同时选,取最多的即可。 分解只因数用 polard's rho 算法,时间复杂度 \(O(nw^{0.25})\) code: #include<bits/stdc++ ......
[AGC002D] Stamp Rally 题解
整体二分板题 首先瑞平翻译。 考虑整体二分,用分治函数 solve(l,r,L,R) 解决答案在 \([L,R]\) 之间的边。每次我们加入所有 \([1,MID]\) 之间的边,查询这时的询问是否满足要求,进行整体二分即可。 由于多次加入边比较麻烦,我们用可撤销并查集维护。 时间复杂度 \(O(n ......
[AGC001E] BBQ Hard 题解
一道十分有趣的题。 一眼推式子,发现自己不会。 看了题解,发现是有趣思维题。但是由于我的朋友学习了有趣的思维题做法,因此我决定学习更有趣的生成函数做法!!! 考虑把原式拆开, \[\frac{1}{2}\times \left( \sum_{i=1}^{n}\sum_{j=1}^{n} \binom ......
P5934 [清华集训2012]最小生成树 题解
考虑 kruskal 算法的过程。 先将边按边权排序,考虑当加入 \((u,v)\) 时只有 \((u,v)\) 不联通才可能使得其出现在最小生成树中,所以对于所有的边权小于 \(L\) 的边,我们希望去除尽可能少的边使得 \((u,v)\) 不联通。这显然是一个网络流模型。对于每一条边 \((x, ......
[AGC001D] Arrays and Palindrome 题解
非常有意思的思维题。 首先我先瑞平一下翻译,我根本没看懂,还是去看英文题面看懂的。 首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边,如果得到的图是联通的,那么就只能填入 \(1\) 种字符,否则就可以填入 ......
#9134. 翻转硬币 题解
首先考虑一些简单的情况,比如 \(m=1\)。 容易发现操作 1 和操作 2 的顺序不会影响结果,于是可以钦定所有操作 1 在操作 2 之前。并且可以发现,进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。 然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) ......
[CF1098E] Fedya the Potter 题解
[CF1098E] Fedya the Potter 题解 前言 一道类欧好题。 题解 这道题让求 \(c\) 数组的中位数,那么有一个比较套路的方法就是二分答案 \(mid\) 然后计算 \(b\) 数组中区间和小于 \(mid\) 的区间个数进行 \(check\)。但是 \(b\) 数组总共有 ......
CF882E1+CF1882E2 Two Permutations 题解-构造题
CF882E1+CF1882E2 Two Permutations 题解-构造题 哇,人类智慧,太智慧了。。。 此题作为20231010联考的 T3。 感觉赛时根本没有去往这方面想。 CF1882E1 CF1882E2 E1 是简单版,就是没有要求操作数最小化。 E1-Easy Version 方法 ......
[ABC245G] Foreign Friends 题解
[ABC245G] Foreign Friends 题解 想法 考虑所有颜色相同的弱化版。 这种情况下,只需要把所有特殊点都推入队列之后跑多源 Dijkstra 即可。 思路 正解与上述做法大致相同。 如果有颜色限制,那么可以考虑这个神仙思路: 把所有特殊点的颜色用二进制表示,对于每一位,这一位是 ......
[USACO17JAN] Promotion Counting P 题解
[USACO17JAN] Promotion Counting P 题解 前言 好久没写题解了,今天趁我心情好赶紧水一篇。 思路 首先拿到这题,关键词检索:子树,比 \(p_i\) 大的,树状数组!现在考虑如何去掉其他子树的贡献……emm,我直接在算贡献的时候去掉其他子树的贡献不就好了! 当然,暴力 ......
[USACO08FEB]meteor Shower S题解(bfs)
题目描述 贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。 如果将牧场放入一个直角坐标系中,贝茜现在的位置是原点,并且,贝茜不能踏上一块被流星砸过的土地。 根据预报,一共有 \(M\) ......
P1457 [USACO2.1] 城堡 The Castle 题解
分析 感觉没有蓝题难度 一道 bfs 题目,相较于大部分 bfs 题,它较为复杂,但分析一下还是很好水过的。 建立墙时,可以用三维数组,\(wall_{~i, ~j, ~pos}\) 表示 第 \(i\) 行第 \(j\) 列 \(pos\) 方向有墙。 观察发现,\(8 = 2^3,4 = 2^2 ......
Shuffle 题解
Shuffle 题目大意 给定一个长度为 \(n\) 的 01 序列 \(a\),你可以进行至多一次以下操作: 选定 \(a\) 的一个连续段,满足连续段内恰好有 \(k\) 个 \(1\),将该连续段任意排列。 问能产生多少种不同的 01 序列。 思路分析 (这题 \(n\) 完全可以开到 \(1 ......