**排序不等式** 假设对于两辆车$i,j$，$i$在$p_1$，$j$在$p_2$，如果把$i$移到$j$更优，就要求原来的总代价大于交换后的总代价，即： $$ 2a_ip_1 + 2b_i(x - p_1) + 2a_jp_2 + 2b_j(x - p_2) > 2a_ip_2 + 2b_i(x - p_2) +…

证明：排序不等式 假设对于两辆车$i,j$，$i$在$p_1$，$j$在$p_2$，如果把$i$移到$j$更优，就要求原来的总代价大于交换后的总代价，即： $ 2 \times a[i] \times p_1 + 2 \times b[i] \times (x - p_1) + 2 \times a[j] \times…

在讨论《没做出T1有救吗》回复：

有的兄弟

在讨论《求T4正解》回复：

洛谷今年csp-j模拟t3就是这个思路 你谷牛逼

## 图论 1. 树上一个点集的LCA为这个点集中DFS序最大点和最小点的LCA。CF1062E 2. 最小生成树上，任意两点之间唯一路径上边权最大值，一定是整张图上，这两点之间任意路径上边权最大值的最小值。P4768 3. 修改任意一条边求最短路，其修改后的最短路径最多不经过原图最短路树上的一条边。CF1163F 4…

> 引用名言：在提高组，看到字符串的相关题目，几乎可以闭眼建字典树，然后通过分析性质与建模将问题转化为树上 dp 问题。 题目感觉翻译得有点抽象，判断子集 $X$ 合法的核心条件应该是：**无论**这个长为 $10^{100}$ 的 AB 字符串 $S$ **形态如何**，**都一定有**一个 $s_i \in X$，…

看起来是 dp 的样子。 显然我们可以对 $a[i]$ 同时取模 $2$，是没有影响的。则 $a$ 就成了一个 01 序列。 发现： 1. 每次交换一定是 $0$ 和 $1$ 交换（交换相同的显然没必要），进而想到交换操作是不会变化 $a$ 数组中 $1$ 的总量的。 2. 每个位置最多被交换一次（交换多次显然不优，如…

在讨论《样例不过求调》回复：

@[KNO3](luogu://user/83168) 哦哦哦对，中间会改变。感谢硝酸钾大佬！已关

在讨论《样例不过求调》回复：

 左边是我的输出，右边是题解正确代码的输出

```cpp #include using namespace std; const double eps = 1e-6; // 避免精度问题 double a[105][105]; void solve() { int n; cin >> n; for(int i = 1; i > a[i][j]; } } for(…

发现区间不定长，这就很讨厌。 ## 暴力 考虑对于每个以 $i$ 为左端点的区间，因为长度范围 $[L,R]$，所以右端点范围为 $[i+L-1,i+R-1]$。 不难想到区间和可以用前缀和数组 $s$ 来快速取得。 考虑暴力存储所有的区间和再排序，时间复杂度可以达到 $O(n^2 \log n)$。 ## 正解 书接…

（暂无内容）

发现每个 $x_i$ 只有五种可能的值：$T$、$F$、$U$、$x_j$、$\lnot x_j$。 如果我们设 $x_{n+1}=T,x_{n+2}=U$，那么 $F$ 也可以用 $\lnot x_{n+1}$ 表示。这样所有元素就都可以表示成 $x_i=x_j$ 或 $x_i=\lnot x_j$ 的形式。 在输入…

有一道题和本题非常像，可以说是本题的弱化版，建议先去看看：[P4158 粉刷匠](https://www.luogu.com.cn/problem/P4158)。 对于本题，我们发现可以类比上面那道题的套路，先对于每个小团体内部 dp 求一遍答案，再对所有小团体跑分组背包把答案整合起来。（第三个部分分或许对此有所启发）…

如果你最后的无解特判是类似ans==inf，那么对于以下数据： ``` 3 2 2 1 2 1 2 3 1 ``` 就会出现错误，因为floyd赋的几个初始值一顿操作后不一定是inf，也可能是一个极大值。所以无解特判改成类似ans>=2e9之类的就能过了

先多尝试几个例子，可以发现同一个盒子中，球和球之间其实是两两限制的关系。我们习惯用图来刻画这种限制关系，考虑对同一个盒子中上方球的**颜色**向下方球的**颜色**连一条有向边，这样我们可以得到若干连通块。 不难发现每个连通块之间互不关联，因为如果两个点不在同一个连通块中就说明它们的颜色没有互相限制。所以不妨对每个连通…

```cpp namespace FastIO{char buf[1 inline T read(){T x=0,w=0;char ch=getchar();while(ch '9')w|=(ch=='-'),ch=getchar();while('0' inline void read(T&x){x=0;T w=0;…

在讨论《进食候人》回复：

@[Charged_Charge](luogu://user/1497480) @[int_inf](luogu://user/1201348) 直接写1e18是浮点数，double只能能精确存15-16位，会有误差，在比大小时是致命的。 考虑把1e18先强转成整形（longlong）再比较就没有误差了

在讨论《求正确的建图和求答案方法（玄关）》回复：

@[xuweiyi](luogu://user/756805) 好像是的，没卡log

应该能感觉到 $f$ 存在递推关系。打个表可以发现 $f(i)=f(i-1) + \lfloor \log_2 i \rfloor + 1$。 ::::info[证明] 考虑题目中不断二分查找的过程可以用一棵 $[1,n]$ 的二叉搜索树来刻画，每个结点的深度就是需要二分查找的次数。 例如对于 $n=7,8,9$： !…

在讨论《求正确的建图和求答案方法（玄关）》回复：

我会01bfs。我知道问题了，不从下层跑也会有问题，我再试试。大佬太厉害了，已关，感谢！

在讨论《求正确的建图和求答案方法（玄关）》回复：

这种fread只要输入之后换行，再加一个Ctrl+Z应该就好了

在讨论《求正确的建图和求答案方法（玄关）》回复：

@[StarsIntoSea_SY](luogu://user/1121518) 这就是我正常的代码呀……能不能麻烦说一下求答案的时候是怎么求，剩下的我自己调就好，感谢

在讨论《求正确的建图和求答案方法（玄关）》回复：

@[StarsIntoSea_SY](luogu://user/1121518) 就是在第一层的点如果没访问过 or 是连通块中的最大点权，就以此为起点向两层图跑最短路。最后答案是两层的dis取min ```cpp #include using namespace std; namespace FastIO{char…

rt，本人想的是：一层是原图，另一层是反图，这些边权都是 $0$。然后上下每个对应的点建一个边权为 $1$ 的双向边（相当于把中转时的花费放到层与层之间的转换上）。再从任意一层向另一层按照点权从大到小跑最短路即可。 每个点答案为两层中答案取min。 但这样有一组hack： ``` input: 6 6 1 3 1 9…

讨论区中有很多有用的 hack，没过的话可以去看看。 --- 每个点都可以换到其所在弱连通分量的最大点权，这是毋庸置疑的。 为了方便陈述，下文中记当前弱连通分量中点权最大的点为 $x$，点 $u$ 的最终答案为 $ans[u]$。 考虑一个点 $u$ 的交换过程，可能有以下几种情况： 1. $x$ 本身，不用交换。 2…

题目的特殊性质很有帮助。发现 $3$ 是大于等于 $2$ 中最小的二进制全为 $1$ 的数，所以考虑把 $n$ 尽可能拆出更多的 $3$ 一定是最优的。 考虑对余数分类讨论： - $n \equiv 0 \pmod 3$：显然全拆成 $3$ 即可，答案为 $2 \times \frac{n}{3}$； - $n \eq…

考虑枚举所有四个方向中连续三个字符能组成的字符串，然后看是否有一个串与 $s$ 相等即可。 ```cpp #include using namespace std; typedef long long ll; void solve() { string s; cin >> s; if(s[0] == s[1] || s…

在讨论《这题算人类大智慧吗》回复：

编程老师教的呀……话说过了吗 @[Xiaonao_Dali](luogu://user/1076621)

在讨论《这题算人类大智慧吗》回复：

@[Xiaonao_Dali](luogu://user/1076621)