NOIP2016提高组蚯蚓算法一容易想到用优先队列维护最大值，但是有“其余蚯蚓长度增加\(q\)”这个条件，考虑怎么快速地处理。我们把增加的总长度记为偏移量\(delta\)。每个数在加入前，把不产生贡献的时间的偏移量减去，再存进去就可以了。时间复杂度\(O(mlogn)\)，用priority_queu

链接区间最值操作HDU-5306支持对区间取\(\min\)，维护区间\(\max\)，查询区间和。很容易想到一个暴力，我们每一次找出这个区间的最大值\(mx\)，如果\(mx>x\)，那么暴力修改这个位置的值，否则已经修改完毕，退出，时间复杂度为\(O(n^2\logn)\)。打一打补丁，对线段树上的每一个区间维

CodeforcesRound987(Div.2)总结A常见的套路，将一个序列变为不下降序列所需要改变的值的最小数量，考虑最大能保留多少个，显然是求最长上升子序列，而这题给出的\(a\)序列保证不上升，所以只需要考虑相同长度的一段。#include<iostream>#include<cstdio>#include<cstring>#

原题链接最后悔的一集，感觉D\(<\)everything。考虑由确定的点推出其他点的答案，发现最高点的答案是确定的，设其位置为\(x\)。然后根据题目定义，发现可以分成\([1,x-1],[x,n]\)两个区间，\([x,n]\)答案均为\(h_x\)。对于\([1,x-1]\)区间，我们找到第一个\(>[x,n]\)区间最小

Description你用销售机器人的利润雇佣了一名助手，现在你准备好去拿走装有CEOI奖章的保险箱了。保险箱位于一所由\(n\)个房间所组成的大学建筑内，这些房间由\(n-1\)扇门连接。每个房间都可以从其他任何房间到达，且每个房间最多与\(3\)扇门相连。你和你的助手都有描述建筑物

打得抽象。T3,T4放俩难的板子。由于是MX的题，就不放题意了。邻间的骰子之舞发现复制操作不会超过\(64\)次，而粘贴操作肯定是越均匀越好，直接二分暴力跑就行了。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#

SS241113C.数据结构(struct)题意有\(n\)个数，\(m\)个操作，\(n,m,a_i\le10^6\)，每次操作给区间\([l,r]\)的所有数字加\(1\)，然后输出全局颜色数量，操作独立。思路感觉不好想，对我来讲有点难，需要更聪明的脑袋和丰富的想象力。首先\(O(n\sqrt{n})\)的莫队做法是显然的，假设

最大值最小是二分答案的特征。二分完后每个公园可以覆盖距离不超过\(k\)的领域，要覆盖整棵树。二分完后需要check。最可能的路线是贪心和dp。好像本质上都存储了可能成为答案的组合的部分信息，但贪心确定了这个组合当前的唯一性，dp并没有，只能保证最优解一定属于被划分出来的某

A\(n\)是偶数，\(a,b,c\)都是素数，平方不改变奇偶性，则\(a,b,c\)中有一个偶数或三个偶数，但偶素数只有一个，所以不妨令\(a=2\)，枚举\(b\leq\sqrtn\)就可以算出\(c\)。需要判断\(b,c\)是否是素数，可以用线性筛或是埃氏筛做到这点。为了避免常数过大，最好只枚举\(b\)为素数的

MX-S5题解A.王国边缘题目链接见到循环结构，先把下标转成从\(0\)开始，以方便用同余描述位置。倍增。用二元组来表示位置：\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,

发现很久不写字符串所有模板都忘了，还是要复习一遍。SA后缀排序令\(sa_{i}\)表示排名为\(i\)的后缀编号，\(rk_i\)表示后缀\(s[i:n]\)的排名。有两种求法：朴素倍增，时间复杂度\(\mathcalO(n\log^2n)\)。每次更新两个关键字，暴力sort，重新编号\(sa\)。基数排序，时间复

P4344[SHOI2015]脑洞治疗仪说句闲话:模拟赛因为没注意push_up痛失70ptsSolution:感觉比较好写的线段树，维护几个变量：\(lmx,rmx,mx,cnt\),lmx表示该区间从左端点开始的最长连续脑洞的长度,rmx,mx类似.cnt表示该区间内有多少个点是0然后注意一下push_up:voidpush_up(Tree

好题好题，太棒了这题！直接想是十分困难的，你连\(dp\)状态都想不出合理的，因此考虑二分答案，转化成一个判定问题。下文\(d\)表示二分出的答案。设\(sum_i\)表示\(i\)子树内的合法路径数，那他就一共分为两部分：来自于\(sum_{son}\)，直接累加即可。经过\(i\)的路径。我们

C.小红打怪（python解）-牛客原题链接：C.小红打怪问题分析：小红的全体打击技能对所有怪物造成1点伤害。队友1的单体打击技能可以对任意单个怪物造成1点伤害。队友2的范围攻击技能可以对相邻的两只怪物分别造成1点伤害（可对已死亡的怪物使用）。思路:设定一个函数check(mx)

A对于一个子矩阵\((x_1,y_1),(x_2,y_2)\)，其元素和为\(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}S_i\cdotS_j=(\sum_{i=x_1}^{x_2}S_i)(\sum_{j=y_1}^{y_2}S_j)\)，\(O(n^2)\)枚举一下\(S\)的所有子区间的和放进一个桶里再检验一下即可。即对于一个子区间和为\(S_1\)，需要累加和

[IMO2018]TrianglesofAbsoluteDifferences-反帕斯卡三角形前言叠甲笔者不是学数竞的，在此感谢我的数竞生为我讲解题目。笔者学艺不精，且知识面浅薄。所以本文章仅用作搞抽象(争取练就惊人注意力。正文一、引入看完这道题目的要求，相信大家都能想起一个很熟悉的东西：

题意给一棵\(n\)个节点的无根树，共\(m\)次操作，每次操作是一个三元组\((x,y,z)\)，表示路径\((x\toy)\)全部发一袋类型为\(z\)的救济粮。问最后每座房子存放最多的是哪种救济粮。思路看到树上路径的操作，首先考虑差分，但本题的特殊之处在于每个节点有\(10^5\)种不同的

[IOI2011]Race题目描述给一棵树，每条边有权。求一条简单路径，权值和等于\(k\)，且边的数量最小。输入格式第一行包含两个整数\(n,k\)，表示树的大小与要求找到的路径的边权和。接下来\(n-1\)行，每行三个整数\(u_i,v_i,w_i\)，代表有一条连接\(u_i\)与\(v_i\)，边权为\(w_i\)

模拟赛题，不知道为什么放在最后一题，感觉评分过高了。首先是经典问题，最大值是\(\sum\min(siz,n-siz)\)，证明考虑每条边上界。考虑证明的构造，对于重心的每个儿子拉出子树，求出子树大小即可转为序列上问题：每个点不跟内部匹配即可满足最大，容易证明充要。朴素dp发现怎么也避不开两

P4178Tree题目描述：给定一棵n个节点的树，每条边有边权，求出树上两点距离小于等于k的点对数量。数据范围：\(1≤n≤4×10^4\)\(1≤k≤2×10^4\)说句闲话感谢著名CB大师red_fire倾情推荐%%%在机房三个人唇枪舌剑了一小会，我们的CB大师直接开搞线段树，而仔细研读了数据范围的本

2024每日刷题（198）Leetcode—624.数组列表中的最大距离实现代码classSolution{public:intmaxDistance(vector<vector<int>>&arrays){intm=arrays.size();intn=arrays[0].size();intmn=arrays[0][0];intmx=ar

CF980-Div2-D题意从\(1\)开始决策，若选当前数，则累计贡献\(a[i]\)并跳到\(j\)位置，\(j\)是\(\lti\)且没有决策过（包括选了和没选）的最大位置（操作\(1\)）。若不选当前数，则跳转到\(j\)位置，\(j\)是\(\leb[i]\)且没有决策过（包括选了和没选）的最大位置（操作\(2\)）。求最大得

睡了一觉，打呼噜被老胡叫醒了/lh睡醒场切，vectorfind是\(O(size)\)的调了40min/fn思路考虑最终得到了\(\mathcalO(Q)\)个连续的\((len,val)\)代表线段长度和线段的\(A_i\)，可以用map简单得到。结论：必然存在一种方案，使得在\((i-K,i]\)中必然存在跳跃的起点

P11234[CSP-S2024]擂台游戏题解前言作者在考场上用了约1h把前三道题做完了，然后用了约半小时想了带\(\log\)的做法，但是我决定放手一搏去想线性的做法，于是又想了有1h之后觉得想到了正解，然后我就一直写到了考试结束，但是最终没有调出来遗憾离场，因此写个题解来纪念一下。