Cnoi

[Cnoi2021] 区间 题目背景 Cirno 有一个区间 \([a,b](1\le a \le b \le n)\)，而你的任务是在规定的次数内帮 Rumia 猜出这个区间。 每次，你可向Cirno询问一个数字 \(k\)，而 Cirno 会告诉你这个数字与区间 \([a,b]\) 的关系。 题 ......

题目描述 现在 Cirno 手上有着 \(T\) 天的作业，每天的作业可以用一个二元组 \(( n, V )\) 表示，其中 \(n\) 表示集合的大小， \(V\) 表示大小为 \(n\) 的集合. 现在，Cirno 需要求出的是 \(V\) 的所有子集的异或和的和，答案对 \(998\,244\ ......

[Cnoi2019] 青染之心 题目描述： Cirno初始有一个空的物品序列，一个大小为 \(V\) 的背包，现在你有 \(q\) 个操作，分为两种： add x y : 表示加入一种体积为 \(x\), 价值为 \(y\) 的物品到序列末尾 erase : 表示删除序列末尾的物品 对于每个操作结束 ......

（无需 LCT 简化版：P4764）主要是记录一个 Trick 而非 LCT、主席树 等的使用。 给定无向图，\(q\) 次询问，求边权在 \([l,r]\) 内的边的生成子图的连通块数目。强制在线。 对于连通块问题，考虑提取生成森林。连通块数目等于顶点数减去 边数最多的生成森林的边数。 强制在线也 ......

看到一年前的 40pts 突然想填坑，就当顺便回忆一下怎么写题解了。 # 思路 线段树合并 / dsu on tree / 长链剖分 / vector + 二分 / dfs 序 + 树状数组（差分）。 ## 线段树合并 复杂度 $O(n \log n)$，可以卡掉。 考虑用线段树合并维护每个结点的子 ......

应该是最简单的做法，同时也是 AT 官方题解做法。 考虑计算 $\min\sum\limits_{1\le i\le j\le n}|a_i-a_j|$，乘二即为答案。 考虑 $n$ 个线段中使 $l_x$ 最大的 $x$ 以及使 $r_y$ 最小的 $y$。 - 若 $l_x\le r_y$，那么 ......

# P6835 [Cnoi2020] 线形生物题解 ## 题目描述 求从 $1$ 到 $n+1$ 的链的期望，其中有 $m$ 条返祖边：$u->v$ 这条边 $u\ge v$，**等概率**，求期望 ## Solution 这种爬楼梯的题一般求解 $E(x\rightarrow x+1)$，则最后答 ......

首先分析一下给出的图的形态，限制 $1$ 表示每相邻两层之间对应点之间两两连边，限制 $2$ 和限制 $3$ 表示每一层是一个环，所以整张图可以形象地看成是由 $L$ 个大小为 $x$ 的环上下顺次相连形成的柱状图。 观察数据范围，$L$ 很大但 $x$ 很小，所以可以考虑对每一层做状态压缩，然后利 ......

# P5391 [Cnoi2019]青染之心 [洛谷：P5391 [Cnoi2019]青染之心](https://www.luogu.com.cn/problem/P5391) ## Solution 把每次（`add`）询问看成一个节点，原问题相当于以 `dfs` 序给定一棵树，对每个节点求其到根 ......

cnoi是黄，群里一堆软色情言论头像。 cnoi是赌，比赛全是随机选拔。除非有接近国家队水平。 cnoi是毒，退役后有强烈的戒断反应。 建议取缔cnoi。 是什么把你变成这样，原神吗？ 不，是cnoi。 cnoi是什么？感觉，不如原神。 的确。如果可以选咋，我宁愿去玩原神。 福建省选变成联合省选？ ......