- 2024-11-11「杂题乱刷2」CF1288E
题目链接CF1288EMessengerSimulator解题思路发现向前移的部分普通维护比较困难,因此我们考虑通过某种方式来维护这个东西。考虑建立\(m\)个虚点来维护,每次询问都将实点移至虚点去。这里求答案我们需要支持单点加,区间求和,可以用树状数组轻松维护。参考代码#include<bits/s
- 2024-11-11「杂题乱刷2」CF1219G
题目链接CF1219GHarvester解题思路就是个嗯分讨题。发现最终选择的方案总共就以下五种情况:选\(4\)行\(0\)列。选\(3\)行\(1\)列。选\(2\)行\(2\)列。选\(1\)行\(3\)列。选\(0\)行\(4\)列。对于第一,五种情况,直接取每行或每列的前四大值
- 2024-11-10「杂题乱刷2」CF1354E
题目链接CF1354EGraphColoring(*2100)解题思路发现这个东西就是类似于二分图染色的东西。因为\(2\)只能和\(1,3\)链接。其余种类的点都不能连接。不妨把\(1,3\)都看成同一个点放到最后处理。那么我们就相当于是要找到一种方案使得选择每个联通快的黑点或白点,使得最
- 2024-11-10「杂题乱刷2」CF1370F2
题目链接CF1370F2TheHiddenPair(HardVersion)(*2700)题目描述真的很难吗?我们首先考虑找出第一个特殊点。我们可以先求出这两个点路径中的任意一个点。发现询问\(1\simn\)就使我们需要的询问、接下来以这个路径中的一个点为根来确定每个节点的深度。接下来考虑二
- 2024-10-04「杂题乱刷2」CF1227D2
题目链接CF1227D1OptimalSubsequences(HardVersion)*1600CF1227D2OptimalSubsequences(HardVersion)*1800解题思路本篇题解分D1,D2两个部分来写。D1sol:我们容易发现有以下两点性质:要想子序列和最大,必须选择前\(k\)大的数字。比第\(k\)大的数字还要大
- 2024-10-04「杂题乱刷2」CF1433F
题目链接CF1433FZeroRemainderSum(*2100)解题思路简单dp,只是状态有点多。首先我们根据题目里的定义,可以构造\(dp1_{i,j,a,b}\)表示考虑到第\(i\)行前\(j\)列当前所选数之和模\(k\)为\(a\)且此时选了\(l\)个数的最大选取数字之和。那么这样,我们就可以求出每
- 2024-09-17「杂题乱刷2」CF1108E2
题目链接CF1108E1(luogu)CF1108E2(luogu)CF1108E1(codeforces)CF1108E2(codeforces)解题思路这篇题解分E1,E2两个部分来讲。E1sol:我们发现可以暴力枚举最后经过所有操作之后的最大值,那么显然的,我们将不会做任何经过这个位置的操作,会做不经过这个区间的所有操作。直接暴力进行操
- 2024-08-29「杂题乱刷2」CF862D
简单题。题目链接CF862DMahmoudandEhabandthebinarystring解题思路首先我们可以发现,字符串的第一个字母不是\(1\)就是\(0\),因此我们可以容易花费\(2\)次询问来找到数字\(0\)或数字\(1\)所在的一个位置。然后,显然的,我们以先找到的数字为\(0\)为例,那么我们就
- 2024-08-16「杂题乱刷2」CF1183E & CF1183H
vp到的。题目链接CF1183ESubsequences(eazyversion)CF1183HSubsequences(hardversion)解题思路考虑动态规划。设\(dp_{i,j}\)表示考虑到字符串前\(i\)个字符中选取的字符长度为\(j\)的不同的子序列数量。于是我们就有以下转移:\(dp_{i,j}=dp_{i-1,j}+dp_{
- 2024-07-25「杂题乱刷2」P3107
题目链接P3107[USACO14OPEN]OdometerS解题思路数位dp模板。令某个数的特殊数字为在一个数字中至少出现过一半的数位的数字。首先我们可以依次拆分数位来枚举当某个数位为特殊数字时来进行数位dp,状态为\(dp_{last,len,num,sum,\_1,\_0}\)来代表还剩余\(last\)个数位
- 2024-07-14「杂题乱刷2」CF727D
duel到的。题目链接CF727D解题思路首先只能选一个尺码的人直接给就是了,这样我们就只用考虑选两个尺码的人了。因为两个尺码的人适合的两个尺码是相邻的,因此我们直接从小到大按照有两个尺码的人排序,再将剩下的衣服大小从小到大排序,然后依次给就可以了。这里我用了桶排,时间复
- 2024-07-05「杂题乱刷2」CF402D Upgrading Array
题目链接CF402DUpgradingArray(luogu)CF402DUpgradingArray解题思路首先有一个很显然的结论,就是你一旦在第\(i\)个位置上做了一次操作后,那么你之后所有在第\(j(i\lej)\)个位置做的操作都无效了,因为此时前缀的公因数为\(1\)了。因此有个很显然的结论就是操作需要
- 2024-07-05「杂题乱刷2」CF1454F Array Partition
题目链接CF1454FArrayPartition解题思路我们发现显然第一个和第三个区间的值区间随着长度的增大而增大。于是我们就可以枚举第一个区间的右端点位置,然后现在问题就转化成了找到一个断点来确定第二,三个区间的长度,由于前文提到的第三个区间的值区间随着长度的增大而增大,于是我
- 2024-07-03「杂题乱刷2」CF1702F
哎哎哎,题解区里怎么没我的做法啊/yun。于是就有了这篇题解。题目链接CF1702FEquateMultisets(luogu)CF1702FEquateMultisets(codeforces)解题思路首先我们发现,\(a\)序列中的数字的末尾的\(0\)是无意义的,因此我们可以将\(a\)序列中的每一个数字一直除以\(2\)直
- 2024-07-02「杂题乱刷2」CF607B
代码恢复训练2024.7.2.链接(codeforces)链接(luogu)一道很基础的区间dp。只讲状态定义,\(dp_{i,j}\)表示\(i\simj\)区间需要的最少消除次数。时间复杂度\(O(n^2)\)。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来
- 2024-06-16「杂题乱刷」AT_abc358_g
代码恢复训练2024.6.15(补)链接(luogu)链接(atcoder)abc最水的G了吧。你发现,你最后肯定全在在同一个点上不动,而且你一定可以在\(n\timesm\)回合内走到这个点,因此我们直接\(dp_{i,x,y}\)表示走\(i\)步到\((x,y)\)这个格子所能得到的最大值即可。时间复杂度\(O(
- 2024-06-08「杂题乱刷」AT_abc357_f
代码恢复训练2024.6.8.题目链接链接(atcoder)链接(luogu)解题思路数据结构板子题。设\(ans_i=a_i\timesb_i\)(\(a_i\)和\(b_i\)是此时的\(a_i,b_i\))。设\(f1(i,j)\)表示\(a_i+a_{i+1}+a_{i+2}+\dots+a_j\)的值。设\(f2(i,j)\)表示\(b_i+b_{i+
- 2024-06-07「杂题乱刷」AT_abc160_e
代码康复训练2024.6.7无所谓,随便贪。直接取前\(x\)大的红苹果,前\(y\)大的绿苹果和和所有无色苹果合起来取最大的\(x+y\)个苹果的值加起来即可。容易证明一定合法。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出
- 2024-06-06「杂题乱刷」AT_abc126_e
代码康复训练2024.6.6.链接并查集板子。直接看代码。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思路:*/#include<b
- 2024-06-01「杂题乱刷」P8816
链接没啥好说的,直接看代码吧。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思路:*/#include<bits/stdc++.h>usingname
- 2024-05-31「杂题乱刷」P8279
链接(Link)一个好题。就是说,你直接先求出这个数列的异或和,然后发现之后就可以两两匹配,如果无法匹配就默认这个数为\(0\),然后做完了。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住
- 2024-05-30「杂题乱刷」 AT_abc285_e
好题。直接上代码吧。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思路:*/#include<bits/stdc++.h>usingnamespacest
- 2024-05-28「杂题乱刷」P8572
链接发现这东西就很根号分治。考虑两种情况:\(k\le1000\),这部分直接用前缀和维护然后暴力做,时间复杂度\(O(kq)\)。\(k>1000\),此时\(n\le500\),这部分直接预处理答案,时间复杂度\(O(n^2k)\)。两个时间复杂度均正确,因此可以通过此题。代码:点击查看代码/*Tips
- 2024-05-23「杂题乱刷」CF1650F
题目链接CF1650F(luogu)CF1650F(codeforces)解题思路我们发现要想让第\(i\)个数变换一次就需要给第\(i\simn\)中的一个位置做一次操作,因此我们很自然的就想到了倒推,容易证明这样是不劣的。时间复杂度\(O(n^2)\)。参考代码#include<bits/stdc++.h>usingnamespace
- 2024-05-19「杂题乱刷」AT_abc354_f
大家一起来做下这个典题。链接(at)链接(luogu)我们很容易可以想到处理前后缀的最长上升子序列的长度,然后容易\(O(n\log_2n)\)预处理。做完了。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要