提供一个无脑暴力背包做法。 前置知识 [LOJ 珠宝](https://loj.ac/p/6039)。 暴力背包 dp 复杂度是 $n^2$ 的，肯定不行。 我们发现重量相等的物品如果选 $i$ 个，必然是从大往小选，这意味着贡献函数 $f_i$ 是凸的，dp 转移等价于 dp 数组和 $f$ 做卷积。 这个问题属于凸…

这题太水了，$2^n$ 轻松过。 注意到最终 $b$ 序列中会有一段中间的和 $a$ 的一个子序列匹配，子序列中的元素不操作，其余的通过操作挪到前缀或后缀。 然后对每种数分开考虑，对每种数的初始位置以及目标位置做分讨（这里指的是相对位置），发现有一种情况是 $a$ 中有 $2$ 个数字要动，直接暴力 dp 是选 $a$…

未在最新发布的 NOI 大纲中找到拉格朗日插值，请问这是否意味着 NOI 不能考拉插。

在讨论《求助线段树上二分的最坏时间复杂度》回复：

你写的是线段树区间二分。 原理是先定位到 $[ql,qr]$ 所在的 $\log$ 个节点，如果当前节点有答案，采用一般的线段树上二分（全局二分）策略，没有答案立刻返回，由于你只会在一个节点采用全局二分策略，所以是 $\log +\log$ 而不是相乘。 所以复杂度 $\log n$

这是朴素的子集卷积： $h_{s|t}\sum_s\sum_{t,s\cap t=\emptyset}f_s\times g_t$ 可以做到 $n^22^n$ 如果把加法改为按位或，乘法改为按位与，保证 $f,g$ 值域为 $[0,1]$，这样的子集卷积可以做到什么复杂度。

在讨论《求问，可撤销线段树》回复：

@[Tmbcan](luogu://user/750524) 什么是边界节点

对于线段树，任何操作均可支持栈序撤销。只是想询问如何做到更优秀的空间复杂度。 当修改存在逆元时，空间复杂度为 $O(q)$。 当修改不存在逆元时，比如一种支持区间覆盖，且必须 `pushdown` 的线段树，请问能做到什么空间复杂度。 目前我能够做到 $4q\log n$。

### 初步观察 一次操作后，$u$ 子树内节点数量减少 $cnt_u$ 个，$cnt_u$ 为 $u$ 子树内叶子数量，据此可以考虑均摊。 由于数据范围 $n=10^6$，所以我们希望每次能够用不超过 $O(cnt_u\times \log n)$ 的时间复杂度解决问题。 ### 得出算法 我们将树划分为若干条链（目…

在讨论《如何用类型声明 lambda 函数》回复：

@[YBa2Cu3O7](luogu://user/1416433) 懂了，谢谢。

在讨论《如何用类型声明 lambda 函数》回复：

而且这个东西是不是比 auto 声明的慢？

在讨论《如何用类型声明 lambda 函数》回复：

@[xrlong](luogu://user/630778) @[YBa2Cu3O7](luogu://user/1416433) 这样可行，但是使用 typeid 输出后它们类型并不一样，请问这个 function 还是 lambda 函数吗？ ```cpp #include using namespace std;…

声明 lambda 函数可以用 auto，例如： ```cpp auto cmp=[](int x,int y){return x<y;}; ``` 但是我想知道能不能不用 auto，而是类似于 `int` 使用特定的类型。

去年 NOI 考了交互，今年不知道

在讨论《关于 -fsanitize=address》回复：

@[yukimianyan](luogu://user/509229)@[konyakest](luogu://user/482660) 了解了，谢谢

测试环境：虚拟机 NOI Linux 编译命令：g++ 1.cpp -o 1 -O2 -Wall -std=c++14 -fsanitize=address,undefined 代码： ```cpp #include using namespace std; string a; signed main(){ cout<…

下文中 $k$ 指字母种类数，颜色代指字母。 怎么题解都是跟 $2^k$ 有关的复杂度，来个 bitset。 直接从每个点开始跑最短路，复杂度 $O(n^2)$，不能接受。 我们有一个这样的思路： + 枚举颜色 $i$。 + 设颜色为 $i$ 的点组成的集合为 $S$，将 $S$ 中的点初始距离设为 $1$，跑一遍最短…

在讨论《关于 vector 的 insert 函数》回复：

@[Little_Cart](luogu://user/392157) 插入 $n$ 个数自带 $1\over 2$ 常数，$1\over 10$ 合理。

qoj 好题很多，但很多题没有好的题解，网上多数题解写的不清楚，并且存在互相贺的现象。 请问有什么好方法在做 qoj 题的时候，即使不会也能快速找到题解看懂解法。

在讨论《两份类似代码常数不同原因》回复：

@[vzcx_host](luogu://user/193198) 你是说循环外的赋值吗，这个执行次数大概是 $3\times 10^6$，肯定没影响

在讨论《两份类似代码常数不同原因》回复：

为了方便大家对比阅读，我把不同的地方放出来： ```cpp int bs=f2[i][j],x=k; for(int A=1;i+x<=n;A++){ bs=bs*inv[k]%mod; f[i+x][j+A]+=bs*inv[A]; f[i+x][j+A]%=mod; x+=k; } ``` ```cpp int x…

### 第一份代码，用时 $0.66s$ ```cpp #include using namespace std; #define int long long const int mod=998244353; const int N=1e3+5; int f[N][N],f2[N][N]; int n,m; int f…

在讨论《请求修改数据范围》回复：

@[_Kenma_](luogu://user/750163) 但是你有正确复杂度的做法吗？

在讨论《请求修改数据范围》回复：

@[_Kenma_](luogu://user/750163) 你得at管理。

在讨论《MnZn 求助卡常》回复：

https://www.luogu.com.cn/paste/w9ytev4p

在讨论《MnZn 求助卡常》回复：

@[Nt_Tsumiki](luogu://user/420129) 鄙人能力有限，从本机 $4.5s$ 卡到了 $3.5s$，但实在无能无力通过该题。

在讨论《MnZn 求助卡常》回复：

@[Nt_Tsumiki](luogu://user/420129) 数据范围是多少？

在讨论《MnZn 求助卡常》回复：

@[Nt_Tsumiki](luogu://user/420129) 有题目或代码吗？

在讨论《建议评绿/蓝》回复：

别骂了哥，我没过。 但是觉得 E，F1 都比 D 简单，因为我过了 F1。

在讨论《建议评绿/蓝》回复：

别骂了哥，我没过。 但是觉得 F1 比 D 困难，因为我过了 F1。

在讨论《建议评绿/蓝》回复：

虽然我觉得应该评这个颜色吧，但是因为赛时脑瘫不会绿题。