给定序列\(a_{1\simn}\)，其中\(0\lea_i\lem\)。给定\(V\)。询问是否存在\(S\subseteq\{1,2,\cdots,n\}\)满足\(\sum\limits_{i\inS}a_i=V\)。\(n\ge1,m,V\ge0,n,m\le10^4,V\lenm\)。先咕一下，贴个代码（#include<bits/stdc++.h>constint

A-FightingoverCandies简单排序。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); vector<int>a(3); cin>>a[0]>>a[1]>>a[2]; sort(a.begi

背包问题背包，即询问一个背包装最大价值的物品总价值。01背包例题：P1048采药想到使用DP。\[f_{i,j}=\left\{\begin{matrix}\maxf_{i-1,j-c_i},f_{i-1,j}&j\gec_i\\f_{i-1,j}&j<c_i\end{matrix}\right.\]（公式中，\(f_{i,j}\)表示使用前\(i\)个物品，重量小

就是背包01问题#include<iostream>#include<cstring>/*01背包问题*/usingnamespacestd;constintmaxn=120;constintmaxm=1e5+10;intdp[maxm],a[maxm];intn,m;intmain(){intt;cin>>t;while(t--){cin>>n;

首先有个动态加叶子的操作，考虑到树剖需要离线下来预处理，便考虑用倍增来维护。首先要找到\(\gea_u\)的最深的父亲\(v\)，便可以先用倍增处理好长度为\(2^i\)的链上的\(\max\)。如果\(\max<a_u\)，就往上跳，跳不了就是到点\(v\)了。考虑连边\(v\tou\)，这仍然会是一棵树（建

考虑到这个是\(\max-\min\)的形式，可以先固定下一维。考率固定下\(\min\)，这样就只需要使\(\max\)尽量小即可。考虑对于\(x\)，可以拆为\(i\)和\(x/i\)，然后又分成子问题去考虑。于是可以\(\text{DP}\)，令\(f_{i,j}\)为\(\min\gei\)，拆\(j\)的最小的\(\max\)。

P4119Ynoi2018未来日记lxl出的题好duliu啊。感谢来自fr200110217102的博客题解P4119【Ynoi2018未来日记】。下标分块+值域分块+并查集其实一开始的方向应该是尝试线段树或者其它的动态维护的算法，直到时间复杂度和空间复杂度对不上，你才会想到——要分块！区间第\(k\)

背包dp；1.01背包（1）领域展开#include<bits/stdc++.h>//simpleusingnamespacestd;constintmaxm=2024;intn,m;intw[maxm],v[maxm],f[maxm][maxm];intmain(){ cin>>n>>m; for(inti=1;i<=n;i++) cin>>v[i]>>w[i]; for(i

洛谷传送门AtCoder传送门考虑相当于把每个标记点的边全部断掉，然后求连通块个数。考虑一条边\((u,v)\)（设\(u<v\)）的出现时间，不难发现是\([1,u-1]\cup[u+1,v-1]\cup[v+1,n]\)。于是考虑直接套线段树分治和可撤销并查集。时空复杂度均为\(O(n^2\logn)\)

洛谷传送门CF传送门感觉和CF1889C2Doremy'sDryingPlan(HardVersion)有异曲同工之妙。显然去除每个数的平方因子后，两个数相乘为完全平方数当且仅当它们相等。考虑若确定了分段方案，那么修改次数就是，每一段重复出现的数的个数。那么我们设\(f_{i,j}\)为\([1,i]\)

用树剖补完了普及组OJ所有LCA的题DistanceQueries距离咨询POJ-1986翻译:FJ有\(N（2\leN\le40000）\)个农场，标号\(1\)到\(N\)。\(M（2\leM\le40000）\)条的不同的垂直或水平的道路连结着农场，道路的长度不超过\(1000\).这些农场的分布就像下面的地图一样，图中农场用\(F1\cdotsF7\)

SP1557GSS2-CanyouanswerthesequeriesII更好的阅读体验扫描线。把询问挂在右端点上，扫描右端点，纵轴仍为序列维。对于这种出现多次的数只算一次的，记\(pre_i\)表示\(i\)这个值上一次的出现位置，套路化的可以强制让出现多次的在\(pre_i<l\wedgei\)统计，用二维线段树状

2023NOIPA层联测32T4红楼~EasternDream根号分治加分块。Ps：分块后面真的用的多。思路考虑根号分治，将\(x\)分为\(x\leq\sqrtn\)的情况和\(x>\sqrtn\)的情况。\(x\leq\sqrtn\)由于这一部分较小，如果在线段上暴力添加肯定会超时。先设\(f_{x,i}\)表示模\(

P5901[IOI2009]Regions给你一棵树，每个点有颜色\(h_i\)。多次询问，每次询问有多少对\((u,v)\)满足\(u\)是\(v\)的祖先且\(u\)的颜色是\(r_1\)且\(v\)的颜色是\(r_2\)。\(n,q\le2\times10^5,h_i\le2.5\times10^4\)。总颜色数一定，考虑对颜色的出现次

100+100+30+100，T4自己写了Check最后一分钟发现Check锅了，赌了一发替换了部分分，赢！A.构造默认\(n\geq3,n\in\{2x+1,x\inN\},m\geq4\)。考虑构造rrrrr---yyyyy---xxxxx---yyyyy---rrrrr---yyyyy---xxxxx-----------这样有\(\dfrac{n-1}{2}\times(3m-4)\)个

放假之后回机房第一天，后面洛谷永久封了，第一次尝试AT随便打打,先试试不知道那场比赛T1题面：InAtCodercity,therearefiveantennasstandinginastraightline.TheyarecalledAntenna\(A,B,C,D\)and\(E\)fromwesttoeast,andtheircoordinatesare\(a,b,c,

目录D-GridIceFloorABC简单题D思维题D-GridIceFloor题意给定一个\(n\timesm\)的矩阵，矩阵每个位置上的字符要么是'.'要么是'#'，保证矩阵的最外围一圈都是'#'。玩家初始位于位置(2,2)。玩家可以进行移动，但是移动有条件：玩家首先选定一个移动方向，之后在这个方

D.Bagofmice题意待补充~思路可利用DP或者记忆化搜索求解本问题，实际上这两个方法等价。当\(w=0\)时必输当$w\ne0$但$b=0$时必赢剩下的情况，先考虑一个问题：赢的局面是怎么构成的？代码记忆化搜索//>>>Qiansui#include<bits/stdc++.h>#definelllong

目录图论-最小环问题例题无向图相关资料图论-最小环问题可以利用floyd算法求最小环长度floyd算法有个性质：在最外层循环到点k时（尚未开始第k次循环），$d_{ij}$表示的是从i到j且仅经过编号1~k-1的点的最短路（即$\gek$点的最短路尚未计算）。那么，我们设最小

目录单调栈例题单调栈单调的栈，即插入元素时保证栈内元素是有序的。例题P2422良好的感觉贪心，其实对每一个最小值，找到其的左右小于最大范围，但关键在于怎么快速找到这个范围，这里利用了单调栈详见代码：constintmaxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;lln,a[maxm],sum[

洛谷传送门AtCoder传送门考虑第一问。发现这个东西长得很像二分图匹配，考虑建图，第\(i\)个盒子建\(b_i\)个左部点，第\(i\)个球建\(a_i\)个右部点，每个盒子的每个点往可以放的球的每个点连边。显然要求能被满足等价于，这个二分图存在一个左部点的完全匹配。因为一个盒子的

给定长为\(n\)的01字符串\(s\),求一个最大的\(k\),使得能选出\(k\)个形如\([l_i,r_i]\)的区间,满足:\(\foralli\in[2,k],l_i\gtr_{i-1}\).\(\foralli\in[2,k]\),\(s_{l_i\simr_i}\)的字典序严格大于\(s_{l_{i-1}\simr_{i-1}}\).\(1\len\le2.5\tim

后缀数组做法。用不同的分隔字符将\(n\)个串连接起来，如\(\texttt{abcdefg}\)、\(\texttt{qaq}\)、\(\texttt{qwq}\)拼成\(\texttt{abcdefgAqaqBqwqC}\)。求出新串的后缀数组和height数组，然后二分答案，问题转变为判断是否有一个长度为\(p\)的串在所有的串中出现，判断

C.猫猫与数列可以猜测，答案应当很小，所以可以直接暴力判断最大的n首先我们可以走两种路：第一种，利用求对数来比较，注意精度问题即可，但我感觉这里的快速幂会溢出嘛？while(1){ a=qpow(x,y); if(y*log(x)>log(maxm)+1e-5)break; ++c; x=y;y=a;}cout<<c<<"\n";第二种做法，快速幂

T2P2306被yyh虐的mzc传送门：洛谷P2306很显然的一道背包，但是\(n,m<=1e5\)，普通的背包会T飞，怎么办呢。。。认真看一下数据规模，\(a[i],b[i]<=10\)那么\(a[i],b[i]\)组合最多\(100\)种不同的家丁，说明会有重复，那么我们把所有重复的记在\(t[a[i]][b[i]]\)中，那这样就