原题链接题解找到每一个点右边能递增多远和左边能递增多远code#include<bits/stdc++.h>usingnamespacestd;inta[100005],r[100005],l[100005];intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];r[n]=n;for(inti=n-1;i>

oj:https://gxyzoj.com/d/gxyznoi/p/P266又是网格题，考虑染色：显然可以发现，每一个不合法的图形都可以被染成黄->蓝->特殊边->绿->红，且旋转后同样满足条件推广到整个棋盘就是：所以是否可以将颜色编号，然后按照上述方法连边呢？显然是可以的，若一个格子被填上了方块，则讨厌的形状一定

题目大意：一个长度为$M$的序列的中位数为这个序列从小到大排序后第$\lfloor\fracM2\rfloor+1$个数，将这个序列的所有子段的中位数放入一个序列中，求这个序列的中位数。设一个序列$a$的中位数为$x$，那么$a$中至少会有一半的数大于等于$x$，并且$x$是$a$中满足这个条件

原题链接题解由于选择每一条路径的概率是一样的，所以我们统计出所有路径的条数，和长度之和，然后除一下就行了，除法求模等价于乘模数下的逆元code#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstllmod=998244353;lllanes[100005]={0},sum[100005]={0

1.斐波那契数列，变量版，变量覆盖a=1,b=1;for(inti=1;i<=n;i++){cout<<a+b<<””a=b;b=c}2.进击的奶牛前置版：变量覆盖cnt=1;pre=a[1]; for(inti=2;i<=n;i++){ if(a[i]-pre>=mid){ cnt++,pre=a[i]; } }3.分段数列：变量版，数

2024.5.8今天写了洛谷 P1003[NOIP2011提高组]铺地毯关于这题，我有感悟：先呈上我学习的第一篇代码：#include<iostream>usingnamespacestd;intmain(){ intn=0; longlongarr[10001][10001]; cin>>n; for(inti=1;i<=n;i++){ inta,b,c,d; cin>>a>>b>>c&

原题链接题解1.如果\(x\oplusy\gtx\)，则\(y\)的最高位对应的\(x\)一定是\(0\)2.$f(x,y)\oplusf(y,z)\gtf(x,z)$等价于\(f(x,z)\oplusa_y\gtf(x,z)\)3.\(x\in[1,y]\)则\(x-1\in[0,y-1]\)code#include<bits/stdc++.h>usingnamespacest

T1[CF1279C]StackofPresentshttps://gxyzoj.com/d/hzoj/p/3686数据出锅了，100->40按题意模拟即可，可以发现，最优情况下，一定是将取出的数按后面的拿的顺序排序，O(1)取出，而在取之前未排序的，则需要花2k+1的时间排序并取出代码：#include<cstdio>#definelllonglongusingnamesp

原题链接题解1.把输出直接看成一个向量整体存在map里2.如果两个向量\(a>b\)代表a的字典序比b大code#include<bits/stdc++.h>usingnamespacestd;intvis[100005]={0};intdlx[100005]={0};intxf[100005]={0};intfa[100005]={0};intss(intnow){if(now==

原题链接题解1.由于每个点最多修改6次，所以我们可以暴力循环遍历所有点进行修改。然后可以把无需再修改的点跳过，即并查集，指向右端第一个仍然需要修改的值的下标这样就是单点修改加区间查询，树状数组时间复杂度\(6·n·log(n)\)（单点修改）+\(m·2·log(n)\)(区间查询)code#inc

原题链接题解1看代码，最简单的这叫什么思想？不知道，我暂时叫做信息标记法，但是标记的角度清奇code1#include<bits/stdc++.h>usingnamespacestd;intlate[100005]={0};//离自己最近的相同元素的位置intmaxleft[100005]={0};//最近的一个出现了两次的元素的前一次的位置int

原题链接题解1.观察数据法：看到\(1e^5\)想到线性递推，想到遍历每头奶牛试着在它们后面添加隔断时的分组方案数2.对于奶牛\(i\)它的状态转移方程为\(dp[i]+=dp[j];j<i;sum[j]<=sum[i]\)3.上述可以把\(sum\)看成x轴，\(dp\)看成\(f(x)\)，这样就变成了求小于\(sum[i]\)的

T1洛谷P3451ATR-TouristAttractions首先求出关键点间两两的最短路，然后状压dp。\(dp[i][S]\)表示当前在\(i\)，已经走过了\(S\)这个集合的最小距离。洛谷上卡空间，学校OJ上不卡，所以就没优化空间。会MLE的代码#include<iostream>#include<string.h>#include<qu

好久没写题解了，水一篇。这里主要想讲的是不同的处理方法，在阅读本篇题解前请确保读完题。详解一，排序这很好理解，题目要求将热帖从小到大输出，同时题目中还有相对的时间这一概念，因此将输入的\(id\)与\(ts\)按照优先\(id\)其次\(ts\)的排序方式从小到大，排序，这样输出时就没

oj:https://gxyzoj.com/d/gxyznoi/p/P35树上差分+线段树合并+树链剖分1.暴力从最基础的方法开始，暴力统计s-t上的点，然后用map直接统计，显然会T,20pts2.特殊性质测试点5,6保证了数据是一条链，将链上每一个节点编号为1-n对于每一次操作，可以记录其覆盖情况，设共有x个节点，有y个节

原题链接题解树上区间修改加单点查询，虽然可以树状数组，但是线段树更通用一点然而线段树通常处理的是点权，可这里是边权，怎么办呢？我们可以把边权转换成点权，由于每个点的子边有若干个，但父边有且只有一个，这样我们就把边权变成边下方点的点权然后区间修改和单点求和的时候把lca的点权

原题链接题解1.这k个城市一定是连成一团在中间的2.把树展开，变成散发图，剩下的n-k个城市一定在最边缘的位置3.拓扑排序dalao'sblogcode#include<bits/stdc++.h>usingnamespacestd;vector<int>G[100005];intdu[100005]={0};intdepth[100005]={0};intmain(){

题目一棵树有n个节点，每个节点都同有一个符号+或者-，表示该节点是正极节点还是负极节点。如果从正极走到负极，或者从负极走到正极，都会受到1点伤害。现在需要知道走过所有路径后会受到的总伤害是多少？树上任意2点存在唯一的路径。需要计算所有任意2点的路径的伤害和。注意：从u到，和从v

续昨天。T8洛谷P4150最短路问题行数很小，考虑使用矩阵。对于一个区间\([l,r]\)，维护\(ll_{i,j},rr_{i,j},lr_{i,j}\)分别表示\((i,l)\rightarrow(j,l)\)、\((i,r)\rightarrow(j,r)\)、\((i,l)\rightarrow(j,r)\)的最小代价。为了转移方便，再维护\(lm_{i

原题链接题解1.我们没法遍历每个区间然后找出他们的最小值，所以我们考虑每个元素对答案的贡献2.对于每一个元素来说，它的贡献等于它所在的区间长度乘上自身的值，这里的区间指的是以它为最小值的区间3.以每个元素为最小值的区间要怎么求呢？我们将其转换成求左边第一个小和右边第一

【题解】P2627[USACO11OPEN]MowingtheLawnG题目跳转数据量比较大，暴力肯定是不行的。只能考虑用动态规划的方式来做。这道题有许多dp设计的思路，这里提供两个：方法一：普通状态设计定义\(dp[i][1/0]\)表示截止遍历到第\(i\)个元素时，选择第\(i\)个元素或不选第\(i\)个元素可以

原题链接题解最大值最小化，想到了二分而对于一个二分到的\(\mathscr{maxlen}\)而言，如何判断是否存在一种分法使得最大值不大于它？对于一个给定的二分值而言，要想成功有两个约束条件，一个是间断值不超过\(\mathscr{maxlen}\)，一个是选中值之和不超过\(\mathscr{maxlen}\)由此

16.k倍区间-蓝桥云课(lanqiao.cn)首先，看到这个题，想到暴力求解，但显然，数据过大，暴力法过不了；然后看到了一个办法：对所有元素的前缀和取K的模，若s[i],s[j]相同，则在j-1到i的区间内，区间和为K的倍数。C++代码：#include<iostream>#include<queue>usingnamespacestd;ty

题目Caima给你了所有[a,b]范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于p的公共质因数，那么把它们所在的集合合并。重复如上操作，直到没有可以合并的集合为止。现在Caima想知道，最后有多少个集合。输入输出

原题链接题解核心技巧：两次搜索第一次搜索：搜索出\(f[now][i]\)以\(now\)为根节点的子树且距离根节点恰好为\(i\)的节点的个数搜索完了之后，把范围\(k\)以内的累加第二次搜索：由于整棵树的根节点的\(f\)等于整棵树里距离不大于\(k\)的节点个数，即已经符合题目要求