- 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不要
- 2024-05-17「杂题乱刷」AT_abc211_e
题目链接[ABC211E]RedPolyomino(luogu)[ABC211E]RedPolyomino(at)解题思路从第三个样例可以看出总的方案数一定很少,因此我们可以直接确定第一个被染色的格子后直接向外爆搜,搜到最后可以使用哈希判重,但光凭这样的话\(2\)秒钟肯定跑不过去,因此我们可以在搜索的过程中使用
- 2024-04-23「杂题乱刷」AT_abc279_e
链接很一眼。容易发现除非操作时影响\(1\)这个数字,否则答案一定改变,直接特判影响到\(1\)这个数字的两种情况即可。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?*/#include<bits/stdc++.h>using
- 2024-04-22「杂题乱刷」AT_abc253_c
感觉要好好补补set了。链接直接用set模拟即可。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?*/#include<bits/stdc++.h>usingnamespacestd;#definemapunordered_map#defineforl(i,a,b)for(re
- 2024-04-18「杂题乱刷」洛谷 P2398
典题。发现问题可以变为枚举\(i\),求出两两数\(gcd\)为\(i\)的个数,但是这样还是\(O(n^2)\)的。然后可以将两边同时除以\(i\),原式变为暴力筛复杂度是\(O(n\log_2(n))\)的,加个前缀和时间复杂度为\(O(n)\)。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是