昨晚码敲完了没保存，导致还原卡直接把我码肘没了。。。气死了只能重新敲了一遍。题面TouristGuide分析考虑每一个联通块分开处理。先将每一个联通块变为生成树，任意生成方式皆可。对于每一个联通块，一定可以构造一种组合方法，使得该联通块中最多只有一个关键点无法被选择。并

邮寄开场秒B。A稍微退了一会儿，推出一个解法（后面发现假掉了）......然后CD，D感觉是一个SA。结果SA写错了，算法假掉了......A智乃的差分分类讨论。\(x>0\)最大值\(=x\)，最小值\(=0\)此时可以直接找一个不是\(x\)，不是\(0\)的数来（严格次小值），然后其他的数从大往小

PetrozavodskWinter2020.Day3.300iqContest3.ProblemG.GiantPenguinGiantPenguin-Problem-QOJ.ac题目描述有一个\(n\)个点\(m\)条边的连通无向无权图，满足每个节点在至多\(k\)个简单环上（没有重复顶点的环是简单环）。\(q\)次操作支持：1.标记一个点；2.询问

我们先理解题意，大致意思是：给你一个序列让你组成一个中间有一个数，左侧递增右侧递减的数列。从这道题的题意来看，大概思路是：1.我们要将最大值设为中间的数，然后左右两端尽可能的小。2.跑两遍循环，分别为左边的递增边的递减。3.还有，因为一个数可以出现很多次，我们需要一个vis

KLC数点由KLC大神在模拟赛中发明。其算法复杂度与答案值域大小挂钩。其能解决的问题一般有着如下的特点：给定一个序列，每次询问一个区间有多少个子区间满足什么性质，数据随机生成。其算法流程为：通过某种方法预处理出所有满足性质的子区间将得到的区间表示在二维平面上

闲话回滚莫队板题被卡到28pts了歴史の研究回滚莫队题。莫队笔记考虑很好加（维护cnt并更新答案即可），但是不好删。那么回滚莫队代码：#include<bits/stdc++.h>#defineintlonglong#definerep(i,l,r)for(inti=l;i<=r;i++)#defineper(i,l,r)for(inti=

https://www.luogu.com.cn/problem/UVA11235没看到多测调了半天每组数据给定\(n,q\)。接下来给出一个长度为\(n\)的不降序列\(A\)。接下来\(q\)次询问，每次询问给定\(l,r\)，求\(A_{l\simr}\)中出现最多的那个数出现了多少次。\(1\len,q\le10^5\)。序列不降，意味着一个数在序

题目传送门前置知识树链剖分|线段树解法树链剖分后维护一个支持区间修改，单点查询的线段树即可。也可以树上差分，同146.DFS序3，树上差分1的\(1,2\)操作，时间复杂度比树链剖分更优。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#define

p8774include<bits/stdc++.h>usingnamespacestd;defineintlonglongdefinef(i,a,b)for(inti=(a);i<=(b);i++)definecl(i,n)i.clear(),i.resize(n);defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;type

题目链接戳我\(Solution\)很容易发现对于每个\(ai^2\)的因子最多在5000以内，所以先将\(ai\)质因数分解然后求出\(ai^2\)的因子然后看每个因子出现了多少次加起来即可\(Code\)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;typedeflonglongll;intr

暴力（12分）#include<bits/stdc++.h>usingnamespacestd;constintinf=0x3f3f3f3f;#definelllonglonginta[100010];intmain(){ intn; cin>>n; for(inti=0;i<n;i++){ cin>>a[i]; } set<int>st; for(inti=0;i<n;i++){

AtcoderEducationalDPContest\(\textbf{A.Frog1}\)对于一块石头\(i(3\lei\leN)\)，\(i-1\)和\(i-2\)均能到达。用\(f[i]\)表示跳到第\(i\)个石头用的最小体力消耗：\[f[i]=min(abs(h[i]-h[i-1])+f[i-1],abs(h[i]-h[i-2])+f[i-2])\qquadi\ge3\]时间复杂度\(O(n)\)。

题目传送门前置知识后缀数组简介解法对于一个后缀\(s_{sa_{i}\simn}\)，它产生了\(n-sa_{i}+1\)个前缀，其长度和为\(\frac{(n-sa_{i}+1)(n-sa_{i}+2)}{2}\)；和\(s_{sa_{i-1}\simn}\)相比产生了\(height_{i}\)个相同的前缀，其长度和为\(\frac{height_{i}(height_{i}+1)

（一）虽说代码较长，但非常好理解，还是最优解（公开的就两个）。考虑对每个数单独算贡献，循环枚举与它进行运算的数的长度，然后确定那个数的位置即可，再乘以出现的数位对应的贡献，如出现在倒数第二位就乘\(10\)。难度应该不到绿。（二）AC代码。#include<bits/stdc++.h>#defineintlonglo

（一）从\(i\)到\(j\)有两种走法，一种是用\(a_j-a_i\)的代价，一种是用\(1\)的代价，前提是\(j\)是\(i\)最近的。显然如果符合条件选第二种。先考虑从左向右走。（和从右向左相同）考虑走到了节点\(i\)，如果\(a_{i+1}-a_{i}>a_{i}-a_{i-1}\)，那么花费\(1\)的代价向右走，否则花

P9755[CSP-S2023]种树首先，容易看出单调性，可以对最少天数二分。转为判定性问题后，我们思考如何判定。对于每棵树，都可以从刚种下长到最后一天。我们由此可以写出\(calc(i,l,r)\)表示第\(i\)棵树从第\(l\)天长到第\(r\)天的高度。\(calc(i,l,r)=\sum\limits_{i=l}^r\max(

BronzeSilverT1Question给你长度为\(n\)的序列\(c\)，$0\lec_i\leC$。若当前位置为\(0\)则表示这个数未知，要求你填数使得序列字典序最小，并满足给出的\(q\)条限制\((a_j,h_j)\)，使得\(C_{h_j}\)是第一个严格大于\(C_1\cdotsC_{a_j}\)的数。Solution我的方法叫

#include<bits/stdc++.h> #defineintlonglongusingnamespacestd;intn,m,x,x1,y,z;inta[100010],d[100010],c[100010];intlowbit(intnum){returnnum&-num;}voidadd(intx,inty){ inta=x; while(x<=n)d[x]+=y,c[x]+=(a-1)*y,x+=lowbit(x);

CF1922B分析注意到\(2^0+2^1<2^2\)，因此若\(a_i\nea_j\nea_k\)，这组数就是不合法的，所以题目转化为有多少对三元组\(i,j,k\)使得\(a_i,a_j,a_k\)中至少有两个数相等。考虑分类讨论。第一类，\(a_i,a_j,a_k\)中有两个数相等，不妨设\(a_i=a_j\)，那么先开一个map维护所有\(a

更好的阅读体验P9361[ICPC2022Xi'anR]Contests首先观察一下性质，每个\(l\)在每场比赛里一定是对应着某个前缀。发现题目要求的是最小的满足要求的\(l\)，最暴力的大概是维护五个指针，每次答案\(+1\)，然后尝试跳一步，什么时候某个前缀包含了\(x\)当前的计数器就是答案。考

[CSP-S2023]种树Part-1特殊性质B将种树时间设为\(l\)，结束时间为\(r\)，则可以把数的高度记作：\[\sum_{i=l}^r\max(1,b_i+x\timesc_i)\]分类讨论：\(c_i\ge0\)可以表示为\(b_i\times(r-l+1)+\frac{(r-l+1)\times(r+l)}{2}\timesc_i\)\(

放张图自己体会(doge类似于爬楼梯的递推题动态转移方程，或者说递推式：dp[i]=dp[i-1]+dp[i-k]其中\(i≥k\)代码：#include<bits/stdc++.h>usingnamespacestd;constintmod=1000000007;longlongt,k,a,b;longlongdp[100010],sum[100010];intmain(){cin>>t>>k;

CF1039DYouAreGivenaTree更好的阅读体验一种神奇套路：对答案根分，根分的依据是链的长度和答案大致是一个成反比的关系。考虑确定了\(k\)怎么做。因为一个点只能在一条链里，所以dfs的时候如果能拼成一条链就一定会拼成一条链，不然就把贡献传给父亲继续尝试。对于\(k\)比

题解P6560[SBCOI2020]时光的流逝首先考虑图上的点为\(y\)终点时，或者这个点无法继续向下走，即\(du_i=0\)时，从这个点为起点先手必败，而对于每一个有一条指向先手必败的点的边的点，显然从这个点出发都是先手必胜的，以此类推。可以考虑建反图，进行拓扑排序，转移状态。#include<q

做了一天，终于做出来了。。结题报告：考虑题目的一个简化版本：使双端队列单调上升。对于序列A和队列Q，找到队列中最早出现的数字Ax，则Ax将Q分成的两个部分分别是原序列中以Ax开始的最长上升和最长下降序列，答案即为这两者之和的最大值。而对于本题，由于存在相同元素，所以只要找到以Ax