在讨论《求本题目正解》回复：

这个性质是用不到，可以树形背包做到 $\mathcal O(n^2)$。

上一篇游记还是第一次参加 CSP-S，今年大概是最后一次 NOIP 了，再来写一篇。下面也简单回忆了一下这两年。 ## Day -1 早上不去学校了，下午抵达高级中学高中园附近的酒店。 ## Day 0 根本没有这一天，Day -1 就是周五。如果把周五定成 Day 0 又有一种这天很重要的错觉。 ## Day 1 前…

题意即为：给定一棵有根树，维护以下两种操作： 1. 将点 $x$ 到根路径上所有边颜色改为 $c$； 2. 查询出现 $k$ 次的颜色种数。 考虑维护同色树上连续段。具体地，当修改 $x$ 到根的路径时，将 $x$ 到根上的所有点从它们原来所在的连续段断开，并将这些点缩成一个新的连续段。 不难发现这就是 LCT 的 a…

最小直径生成树模板。 众所周知，边权全为正的树的所有直径中点重合（有可能在一条边上）。直径问题经常考虑这个点。对于一棵树，设点 $x$ 到直径中点的距离为 $d_x$，直径为 $D$，则 $D=2\max_x{d_x}$。进一步，如果将 $d_x$ 改为 $x$ 到任一其他点（包括一条边中间），这个等式右侧都会变大。…

本题只有两种修改操作，可以将每种修改操作看成对有已有的编号进行修改和加入新的编号： 1. 一类修改：来了 $k$ 个人，所有已有团队成员的编号都会加 $k$，新来的团队第 $i$ 个人编号为 $i-1$； 2. 二类修改：来了无限个人，所有已有团队成员的编号都会变为原来的 $2$ 倍，新来的团队第 $i$ 个人编号为…

先考虑单次询问整个序列。 将答案放在每座塔中编号最小的积木处，那么如果 $i$ 记入答案，则需要找到一个 $f_i<i$ 满足 $s_{f_i}\neq s_i$，且所有 $f_i$ 互不相同。 显然 $s_i=\texttt{P}$ 和 $s_i=\texttt{C}$ 的 $i$ 独立且对称，所以不妨认为 $s_i…

下文中“答案”均为题目所求期望值乘 $n$，即 $n$ 种可能性的时间 $t$ 之和。 首先分析 Julia 的最优策略是什么。 设一种策略中，Jane 如果以 $v_1,v_2,\dots,v_n$ 的速度前进，那么 Julia 与她相遇的时间为 $t_1,t_2,\dots,t_n$，不难发现 $t_1\geq t…

#### 算法一 下文中“区间 $i$” 指怪物 $i$ 或者区间 $[l_i,r_i]$，称 $w_i$ 为区间的权值。 首先考虑指数级算法。枚举集合 $S$ 表示最后权值计入答案的区间。设 $L=\displaystyle\min_{i\in S}\{r_i\},R=\displaystyle\max_{i\in…

### 题目大意 给定一个 $n$ 个点，$m$ 条边的简单无向图，其中 $K$ 条边是特殊边。要求构造一个简单环，使得所有特殊边要么在环上，要么两个端点都不在环上，或报告无解。 $n\leq 150,K\leq m\leq \frac{n(n+1)}{2}$。 时间限制 $12s$。 ### 解法 考虑有解的条件。…

在讨论《如何在比赛中打满所有暴力分》回复：

其实平凡的暴力也可以先写 只不过如果不是特别难的题或者最后一题可能用不上

在讨论《如何在比赛中打满所有暴力分》回复：

有非平凡部分分先写了，说不定还有意外收获

### 题目大意 有 $n$ 个人，每个人 $i$ 有两种喜爱食物 $f_{i,0},f_{i,1}(f_{i,0}\neq f_{i,1})$。定义这 $n$ 个人的友谊集合为 $S=\{(i,j)|i 定理 1：图 $H$ 是线图，当且仅当存在一系列子图 $C_1,C_2,\dots,C_k$，其中每个 $C_i$…

### 题目大意 平面上有 $2n$ 个点，第 $i$ 个位于 $(i-1,0)$，颜色为 $a_i$。保证 $a_{1\sim 2n}$ 中 $1\sim n$ 各恰好出现两次。 现在要将每种颜色的一对点用首尾相接且与坐标轴平行的折线连起来，并且任何两种颜色的折线不能有交点。 现在给出 $n,a_1,a_2,\dot…

### 题目大意 给定正整数 $n,K$ 及长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。 定义一个 $\{1,2,\dots,n\}$ 的子集 $S$ 为合法的，当且仅当 $\forall 1\leq i\leq n,\{i-1,i,i+1\}\cap S\neq\varnothing$。定义一个合…

### 题目大意 以如下方式给出一张带权无向图：点集为 $\{1,2,\dots,n\}$，边有两种： 1. $\forall 1\leq i 1$，$(i,j)$ 之间有边权为 $1$ 的边。 现在给定起点 $a$ 和终点 $b$ （保证 $a\neq b$），构造一条从 $a$ 开始，以 $b$ 结束的权值和最小的…

## 题意简述 给定 $n$，将 $2,3,\dots,3n+1$ 划分成 $n$ 组 $(a_i,b_i,c_i)$，使得每组中的三个正整数构成钝角三角形的三边长。 $n\leq 10^5$。 ## 做法 from 🐍🐍，比官解好。 观察 $n$ 小的情况： $$ n=1:(2,3,4)\\ n=2:(2,4,5…

设 $f_{0\sim n},g_{0\sim m}$ 是两个下凸序列（差分序列单调不降），那么通过如下方式构造 $h$： $$ h_i=\min_{j=0}^n\{f_j+g_{i-j}+j(i-j)\} $$ 得到的 $h$ 是下凸的吗？ 如果是能快速计算吗？

在讨论《50分蒟蒻求调》回复：

@[ADJJYX](luogu://user/1496690) 漏了最后一位是 X 且校验码是 10 输出 Right 的情况 ```cpp #include using namespace std; int main(){ char ISBN[15]; for(int i=0;i > ISBN[i]; int x;…

在讨论《86分求调》回复：

@[Xuanbo](luogu://user/1493458) dp 初值有问题，应该是 dp[0]=0。 但是这个复杂度不太对，$O(Tn)$ 过不了。 ```cpp #include #define Xuanbo return 0 using namespace std; const int M=1e6+6,N=2…

在讨论《64分求助》回复：

@[mengshengxuan123](luogu://user/1348810) 背包问题这样贪心是错的 建议查看题解学习dp

在讨论《wa求助》回复：

两个问题： 1. 马走的是 $1\times 2$ 的矩形，不是 $2\times 3$。 2. 要把不能走到的位置标记为 $-1$ ```cpp #include using namespace std; const int N=409; int n,m,x,y,ne[8][2]={{1,2},{-1,2},{1,-…

在讨论《求调（》回复：

@[gyf_](luogu://user/1727930) 不记忆化复杂度是平方的肯定不对 你这个记搜也没有道理，比如这个数据： ``` 3 3 1 3 3 2 2 1 ``` 从1开始搜到2的时候1已经vis了，但是f[2]是需要f[1]更新的，所以得到的结果f[2]=2是错误的。 不过其实你这个记忆化写的也是 $O…

在讨论《给每个歌赋权值然后排序，wa#2~#9》回复：

@[shadow_leader](luogu://user/1219010) 这个解答思路有点简略了。 具体一点来说，把UP放在下面没有问题，但是顺序应该是原来的顺序。比如上面那个例子中，A 和 B 放在 2，3 位置没有问题，只要按原顺序（也就是 A，B）放就是对的，但是你的贪心会导致这个顺序反过来变成 B，A。 这…

在讨论《给每个歌赋权值然后排序，wa#2~#9》回复：

@[shadow_leader](luogu://user/1219010) 做法有些问题，比如： ``` 3 A UP B UP C DOWN ``` 会输出 ``` C B A ``` 不满足要求

## 题意简述 给定 $n$ 个点，$m$ 条边的简单有向图，每个点有点权 $c_i$，并给出上面的两个点 $s,t(s\neq t)$ 和一个正整数 $K$。 要求构造一个点集 $S$，满足从 $s$ 到 $t$ 的任意一条路径中，至少有 $K$ 个点在 $S$ 中，且 $S$ 是所有这样的点集中 $\sum_{u\…

有趣的题目。 ## 题意简述 给出 $n$ 个长度为 $m$ 的字符串 $t_1,t_2,\dots,t_n$，都由前 $c$ 个小写字母组成。 定义 $E(S)$ 为当前有字符串 $S$，每过 $1$ 秒，会在 $S$ 后面随机接一个字母，其为第 $i(1\leq i\leq c)$ 个小写字母的概率是 $p_i$，…

## 题意简述 有一个 $n$ 个点 $m$ 条边的无向图，保证没有重边自环，你需要给每条边和每个点标上 $0/1$。 要求对于任意一个标了 $0$ 的点，都有一条标了 $0$ 的边和它相连。对于任意一个标了 $1$ 的边，两个端点中至少有一个端点标了 $1$。 问所有 $2^{n+m}$ 种方案中合法的方案数，**对…

## 题意简述 给定一棵 $n$ 个点的树。 对于点 $u,v$，定义它们之间的距离 $dis(u,v)$ 为树上两点间简单路径的边数。 对于点 $u$，路径 $P$，定义它们之间的距离 $dis(u,P)=\displaystyle\min_{v\in P}\{dis(u,v)\}$。 对于路径 $P,Q$，定义它们…

很有意思的题。 首先考虑 spj 怎么实现，那么要解决两个问题：如何判断无解，如何判断解合法。 对于判断合法，假设 $u$ 操作后的颜色为 $c$，相邻的三个点为 $v_1,v_2,v_3$，那么限制就是操作前这三个点中至少有两个颜色为 $c$，或者说如果操作前 $v_1$ 颜色不是 $c$，那么 $v_2,v_3$…