传送门小\(C\)有一棵\(n\)个结点的有根树，根是\(1\)号结点，且每个结点最多有两个子结点。定义结点\(x\)的权值为：1.若\(x\)没有子结点，那么它的权值会在输入里给出，保证这类点中每个结点的权值互不相同。2.若\(x\)有子结点，那么它的权值有\(p_x\)的概率是它的子结点

Rank考前不挂就是赢A.冒泡排序签，简单的有点格格不入。发现错误代码实质上是将原序列划分成了若干个连通块，并对每个连通块做一遍排序。并查集维护，\(\mathcal{O(n)}\)扫一遍合并连通块，然后按顺序输出即可。复杂度最坏\(\mathcal{O(n\logn)}\)。点击查看代码#include<b

Rank还行A.排列最小生成树(pmst)签，有点可惜。考虑连\(i\)与\(i+1\)时，所有边边权都是小于\(n\)的，因此我们只考虑边权小于\(n\)的边即可。因为边权为\(|p_i-p_j|\times|i-j|\)，所以只考虑\(|p_i-p_j|\lt\sqrt{n}\)和\(|i-j|\lt\sqrt{n}\)的情况，每个点只用连

TAMAYA挺有意思的维护题。题面n个小夫坐成一排，每个小夫有一个真实值vi。小夫们有m场聚会，第i次聚会会在编号为[li,ri]的小夫中举办。聚会之后，这些小夫的真实值会变为他们之中的真实值的最大值。将会发生q次事件，有两类事件。第一类事件，第x个小夫的真实值变成了y。第二类事

0+40+10+0一言以蔽之曰“一上午白干”T1一般图最小匹配首先，对答案有贡献的点对一定在排序后的位于相邻位置所以排序后取出所有\(a_{i+1}-a_{i}\)但不能像Kruskal一样每次取最小，因为其只需要考虑连通性，不涉及其它限制。所以用dp或者可反悔贪心取最优解点击查看代码#in

因为正式集训所以不叫加赛了。RankUpd：非常好数据，掉分掉Rank。还行，其实是Rank6，其实其实是Rank4（丁真说正式比赛不会改数据。A.奇观简单题（？）。赛时琢磨了一会想到了\(Ans=C\cdotC\cdotF\)，打出了\(m=0\)性质和\(O(n^2)\)dp的暴力一共80pts。赛后发现在我做法的

Rank一般A.string签。开始还想复杂了点，后来发现表面上\(\mathcal{O(n^2)}\)的复杂度但第二层循环最多跑26次，所以事实上复杂度最坏也就\(\mathcal{O(26n)}\)，显然可过。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint(x)=(y);(x)<=(z);(

并查集好题首先我们知道并查集是可以维护一个区间的覆盖问题的，具体操作就是，对于一个区间，我们让所有的点都有一个指针，这个指针指向这个区间的右端点+1（具体操作可以每个点指向右边，这样后面我们查到一个点的时候用路径压缩就可以了，能从\(\Theta(nlogn)\)变成\(\Theta(n)\)），这样我们

hollow原题链接给你一个由\(n\)段若干个\(0\)或\(1\)组成的序列，每次可以选择一段区间翻转，每次操作后问最长不下降子序列长度。显然地，我们可以把连续的相同数字看成一个带权的整体。最长不下降子序列（以下用LIS来表示）可以枚举分割点，前面都是\(0\)，后面都是\(1\)。对于

拖更了一个暑假。P6492很妙的线段树阿。对于修改，我们无需用lazytag，只要每次跑到叶子节点去直接修改即可。对于询问，答案即为树根的信息，因为它每次询问的都是整个区间。最难的是pushup部分：我们需要维护三个东西，ans,lx,rx，分别表示当前节点的整个串的最长合法串/左端点开

Rank非常好数据，使我成为Rank1（雾数据换源后的狂流——齐秦北风在吹着清冷的街道街灯在拉开长长的影子走过的路想过的事仿佛越来越远越来越长越来越多越难以抛开多少平淡日子以来的夜晚你曾是我渴望拥有的企盼太多分手的记忆仿佛越来越远越来越长越来越多越难

题意鉄道旅行(RailwayTrip)分析非常神仙的倍增做法。我们设\(l_{i,j}\)表示从\(i\)点出发，停靠\(2^j\)站后能抵达的最左位置。同理设\(r_{i,j}\)表示从\(i\)点出发，停靠\(2^j\)站后能抵达的最右位置。考虑如何更新这两个状态。因为可以走回头路，所以简单的\(l

Rank玩蓝图玩的A.进击的巨人（原题都是牛客的，没号所以不挂了）赛事看到概率期望一眼润，但是又可惜暴力分，遂打（最坏情况下）\(\mathcal{O(n^2)}\)暴力，结果很给力啊，调出来小样例后大样例嗖的一下就过了，惊喜了属于是，喜提100pts。事实上跑这么快是因为0的数量很平均，导致复杂度大

Rank意外地还凑合，本来以为这场要GG了。A.黎明与萤火原[CF963B]DestructionofaTree签，勉强签了。开始脑子乱，胡乱打了一个含有3个dfs函数，每个函数里含两次遍历链式前向星，不负众望大样例T了。后来也是摸着摸着就出正解了，先一遍dfs跑出基本的数据，然后再一遍df

Rank小挂，还好。A.数字三角形原[CF1517C]Fillomino2锣鼓Rmj炸了所以挂cf链接。签。倒叙考虑，优先向下，到底或者下面有数就向右，有正确性，复杂度\(\mathcal{O(n^2)}\)。水了篇题解，点点推荐rp++。点击查看代码#include<bits/stdc++.h>constintRatio=0;cons

第一眼是想写\(kd-tree\)的。然后发现这就是一道三维前缀和的板子题。三维前缀和要想学习三维前缀和，我们首先得了解前缀和的概念，并且学会一维、二维前缀和。什么是前缀和前缀和是容斥原理的典型应用。这种优化方式可以使求和操作的时间复杂度降低到\(O(1)\)（但是需要提前预

RankA.符号化方法初探原[ABC081D]Non-decreasing挺水的，不过赛时想了错解。赛时做法是都塞到一个set里一遍推过去，如果比上一个小就lower_bound找一个最接近差的数加上，不过它存在比较大的问题。首先全是负判不了，会进入死循环；其次用map存下标也会出现存在两个相同的

Rank题目泰国尼添所以暴力挂一点分也能拿到22/98A.BA签到题。总记得小时候在《冒险岛数学奇遇记》的第28册左右看到过这道题，关键在于你可以分次烙完一张饼。举例2口锅5张饼，54433，最优策略的一种是先将5的那张饼烙3单位时间，然后烙一张4一张3；另一口锅

Rank上半最后一次正式模拟赛，感觉还彳亍A.小孩召开法1原[ABC278F]Shiritori签到题。博弈论+状压+记搜秒了，感觉不用太细说。不过是暑假以来第一次首A啊，开始还胡乱想SG定理的做法，后来发现不用那么复杂。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for

Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法，因此我们只枚举和在这个范围内的两个值，寻找约分前的值即可，复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,

KM做法这么简单好想为什么都在dp？我第一次过也是用的dp。建模非常好想，每天只能收一次钱，最简单的思路是我们枚举第几天开车跑路，但是再一想我们不关心是第几天，只关心每次贷款离开车跑路还差几天，于是我们从\(i\)向\(j\)连边，边权是\(a_i+b_i\times\min(k_i,j)\)，意义为第\(i\)

暂时未完成qwq[NOIP2003提高组]侦探推理（这道题思路很简单，但是细节一大堆qwq，调吐了QAQ这个题一共就20个人，星期一共就有7种可能，100句证词，所以可以直接暴力枚举，看一看假设第$i$个人是罪犯（guilty），今天是星期$j$,那么一共有几个人说了谎话。然后就好了awa…………了吗……这

党同伐异可以发现,每次只会是\(a_i\)最大或者\(a_i\)最小的人被淘汰,所以留下的肯定是从小到大排序后的一段区间。还可以发现一个单调性,越靠近左边就越不可能票左边,所以可以通过二分求出左右两边各被票了多少。#include<bits/stdc++.h>usingnamespacestd;const

原题链接：https://www.luogu.com.cn/problem/P1022题意解读：求解一元一次方程。解题思路：直接采用模拟法，对字符串进行解析设x保存未知数字母设lx保存"="左边的未知数系数，多个系数要累加设l保存"="左边的整数，多个整数要累加设rx保存"="右边的未知数系数，多个系数要累加设r保存"

简介一般来说，我们处理某些可以离线的问题，我们会将询问离线，然后将修改挂在左端点或右端点，然后从左往右扫描这些修改，并处理询问，数据结构记录的一般是下标\(i\)到当前走到的地方的一些信息。而换维扫描线则采取了截然相反的措施：我们将区间修改转化成差分，然后从左往右扫描序列，线段