## 题目大意 给定正整数 $n$ 和 $m$，和 $m$ 个区间。要求构造一个 $0$ 到 $n-1$ 的排列，一个区间的代价为区间内所有数的 $mex$ ，排列的代价为所有区间代价的 $mex$，最小化排列的代价。$3\leq n \leq 3000,1 \leq m \leq 3000$。 一个集合的 $mex$…

## CSP-S 2025 游记 >多年以后，面对【】，PenguinJ将会想起老师带他去见识信息学的那个遥远的下午。 ### Day -??? 暑假去杭州信友队待了一个月。 开学之前几周以及开学后的3周停课训练，主要是我们班上其他竞赛组要准备比赛，统一停课方便管理。 ### Day -?? 段考，排名预期之内，比上次…

[题目](https://codeforces.com/problemset/problem/2137/F) ## 思路 以样例5为例，分析一下样例，对于 $x=[5,1,2,6,3,4],y=[3,1,6,2,5,4]$，$z$ 的第一位只能填 $5$，第二位的 $1$ 不是前缀最大值，于是第二位可填任意一个不超过…

先考虑一个序列的贡献， 一个序列 $X$ 要满足存在对应的树的充要条件是 $\sum X_i =2N-2$。 如何构造一棵直径最长的树？不妨令根节点度数为 $1$，每次可以在当前最深的点下接上一个非叶子节点，使最长链延长，再算上链的末尾的一个叶子节点，记序列中大于 $1$ 的数的数量为 $k$，序列的贡献为 $k+1$…

[题目](https://www.luogu.com.cn/problem/CF1265E)。 设 $f_i$ 表示问完了前 $i-1$ 面镜子，还期望要多少天。 有 $f_i=p_i f_{i+1}+(1-p_i)f_1 +1,f_{n+1}=0$ ，答案即为 $f_1$ 。 将递推式变形，有 $f_i-f_1=p_…

## 题意 构造一棵有 $n$ 个节点的二叉树，使所有点的深度之和为 $d$，根节点为 $1$，根节点深度为 $0$。 ## 思路 深度之和达上界时树为链的形态，达下界时为满二叉树的形态。考虑初始先构造一条链，逐步向满二叉树的形态调整。 ## 代码 ``` #include using namespace std; #…

## 题意 一棵有 $n$ 个点的树，对于一条边，记该边深度较大的一个端点为 $u$，该边的权值为 $\sum 2^v$，其中 $v$ 是 $u$ 的子树中的点的编号。按边权从大到小的顺序给出每条边的深度较浅的端点，求树的根节点以及每条边的端点。 ## 思路 由于点的编号是不重复的，对于两条没有祖孙关系的边，一条边的权…

在讨论《一个疑问》回复：

此贴结，错因是连续相同长度的最大值可能大于3，空间开小了。

```cpp //计数器一定要能计数 //计数器一定要能计数 #include #define int long long using namespace std; int l,r,a[13],dp[13][13][4][4][2][2],len; bool vis[13][13][4][4][2][2]; int d…

题意：单点修改与查询前缀最大值个数。 维护 $ans_k$ 为区间 $[l,r]$ 的答案，怎么由 $[l,mid]$ 和 $[mid+1,r]$ 合并?显然可以直接把左区间的答案加上去，考虑右区间的贡献，右区间的一个前缀最大值，只有它大于左区间的最大值才能对答案有贡献，记这个贡献为 $val_{k*2+1}$ 。首先…

题意：有一个数轴， $Q$ 次操作，三种操作类型： - 1.在位置为 $x$ 处插入权值为 $w$ 的数，不会在有数的位置重复插入。 - 2.删除位置 $x$ 处的数，保证删前 $x$ 处有数。 - 3.给定位置 $x$ ，对于一个数轴上有数的位置 $y$ ,定义其价值为 $\frac{w_y}{|y-x|}$ ，查询…

在文章《CF868F题解》发表评论：

%%%

先考虑朴素的暴力，设 $f_{k,i}$ 表示前 $i$ 个数划分为 $k$ 段的最小代价，有 $f_{k,i}=\min_j\{f_{k-1,j-1}+w(j,i)\}$ ，其中， $w(x,y)$ 表示 $[x,y]$ 中相同元素的对数。 可以先在外层枚举 $k$ ，考虑如何处理 $f_i$ 的转移。记数组 $g$…

考虑反着做，把树变回链，这和原问题是等价的。 假设一个点的所有儿子的子树已经恢复成链，想让我们可以让一条长链和任意一条短链合并，把长链下移到短链的末尾，产生短链长度的代价，得到一条更长的长链。继续此类操作，直到所有儿子全部合并，不难发现，这个过程中与短链合并的顺序对答案没有影响。 实现上，长链剖分，先递归短儿子，按访问…

考虑统计每一对数 $(i,j)$ 对答案的贡献，记 $f_{i,j}$ 表示经过了若干次操作，每次操作执行或不执行， $a_i>a_j$ 的概率，假设某次操作交换 $x$ 和 $y$ ，且 $x \lt y$ ，则这次操作只会影响所有的 $f_{i,x},f_{x,i},f_{i,y},f_{y,i},1 \leq i…

考虑将询问离线，按边权从大到小依次向途中加边。 如何计算当前的图经过一系列操作后的点数和边数？ 注意到，操作（a）不影响任何其它点的点权；操作（b）同样不影响。所以图中度数为 $0$ 的点一定会被删去，不考虑自环，所有度数为 $2$ 的点也一定会被删去，其它点不会被删。考虑什么时候会形成自环，每一个没有其他分支的环，也…

先考虑一棵基环树上有多少条简单路径，设环上有 $num$ 个点，环上第 $i$ 个点的子树内共有 $a_i$ 个点。有 $$ \begin{aligned} ans &= \sum _{i=1} ^{num} \frac{1}{2} a_i \times (a_i -1)+(a_i \times (n-a_i)) \\…

只需求不加椅子时最多能使多少人有椅子坐。 开始想了一种网络流做法: 1.源点向每个人连一条容量为 $1$ 的边。 2.由于每个人有两种坐法，坐在 $L_i$ 及其左边的椅子或坐在 $R_i$ 及其右边的椅子，可以考虑把每个椅子拆成 $3$ 个点，将拆出来的点划分为三个部分，第 $i$ 个人向第一部分的点 $L_i$ 连…

由于每种颜色的钥匙至多有5把，我们可以提前找出能匹配的钥匙和箱子对，这里的能匹配是指如果一个箱子和一把钥匙之间还有一把未配对的钥匙，则让箱子和中间的那把钥匙配对，因为若按原来的匹配，能包含这个匹配的查询一定能包含新的匹配。求出所有匹配的过程类似处理树上括号序列，但是对于每种颜色的每把钥匙，直接在原树上跑会超时，可以把同…

rt

在文章《如何在 whk 与 oi 间做取舍？来自米塞莉娜小姐的建议！》发表评论：

你完全赢了，NOIp3=，文化课稀烂的我只能蜷缩在角落，抱头痛哭。

## 题意 给一颗有根树染色，根节点为绿色，其他节点可染为绿色，黄色或蓝色。一种染色方案是好的需满足任意一对绿色点和蓝色点之间没有黄色点，且任意一对绿色点和黄色点之间没有蓝色点。求一棵恰好有 $m$ 种好的染色方案的树的最少节点数，若不存满足的树则输出`-1`。 ## 思路 考虑1棵确定的有 $n$ 个点的树有多少种好…

```cpp #include #define ll long long using namespace std; ll n,m,p,k,x,y,z,t,ans=1e15,nz; ll nS[201]; ll fir[201],nxt[6001],to[6001],w[6001],eS[6001],tot; ll di…

在文章《P12465题解》发表评论：

%%%

在讨论《扣 1 复活讨论区》回复：

2

在文章《三大实用的分治算法》发表评论：

%%%

在文章《NOIP2024 退役记》发表评论：

闪光灯不评

在文章《NOIP2024 退役记》发表评论：

%%%

在讨论《CCF把our code藏哪了？》回复：

@[帝都_henry26268](/user/315655) 已关

在讨论《CCF把our code藏哪了？》回复：

@[帝都_henry26268](/user/315655) 能给一下GD的吗，谢谢