众所周知虹动画第 2 季制作组厨力拉满，呈现出了一部精彩绝伦、细节可赏、值得每周期待的作品。那么以虹动画第 2 季为主题的虹 5th live 会怎么样呢？

  纯粹是杂写里面占篇幅太长了，所以拉出来单开一篇。
  但为了一部番单开一篇 blog 实在是有点。。。

“你们不是已经毕业了吗？” ——遇到的所有熟人

题目大意

  设全集为 $\{1,2,\cdots,n\}$，给出 $n-1$ 个子集 $E_1,\cdots,E_{n-1}$，$|E_i| \ge 2$，请从每个子集中选出两个元素，视为给两个节点连一条边，使得最后构成一棵树。
  输出一种方案或是“-1”表示无解。

  $n \leq 10^5,\ \ \sum |E_i| \le 2 \times 10^5$
  4s

题目大意

  给定长度为 $n$ 的序列 $a_1,\cdots,a_n$ 和一个参数 $m$，对于每个 $i$，问是否能从序列中选出满足如下条件的子集：

• 集合包含 $a_i$；
• 集合大小为 $m$；
• 集合内不存在一个数是另一个数的倍数。

  $m \le 3 \cdot 10^5,\ m \le n \le 2m$
  $1 \le a_1 < a_2 < \cdots < a_n \le 2m$
  2s

题目大意

  给定一个 $n$ 行 $m$ 列的矩阵，里面的元素是 $1,\cdots,nm$ 每个恰好出现一次。依次执行以下操作：

1. 对每一行任意重排；
2. 对每一列任意重排；
3. 对每一行任意重排，

使得最后矩阵第 $i$ 行第 $j$ 列恰好是 $i(m-1)+j$。输出一种方案（第 1 步和第 2 步后的结果）。可证明一定有解。

  $n, m \le 100$
  2s

题目大意

  给定一幅 $n$ 个点 $m$ 条边的带权无向图（权值表示距离），现在想要加一些单向边，权值自定（需是正整数），使得：

• 从 $1$ 号点到每个点的最短路长度不变；
• 从 $1$ 号点到每个点都有至少两条点不相交的最短路径。

  新建一条从 $u$ 号点出发的单向边代价为 $w_u$。求最小代价。
  以及有 $q$ 次修改操作，每次选择一个点 $k$ 把 $w_k$ 增加 $x$。

  $n \le 2 \times 10^5,\ m \le 3 \times 10^5,\ q \le 2 \times 10^5$
  $1 \le w_i \le 10^9$，初始边权 $d$ 满足 $1 \le d \le 10^9$，每次操作增加的代价 $x_i$ 满足 $1 \le x_i \le 4 \times 10^8$。
  2.5s

  其实偶像作品中也有很多很有趣的美学、哲学、艺术问题可以思考。我逐渐觉得我应该再修一个艺术理论的学位，去读一些书。
  博客逐渐变成了奇怪的形状

  继“Aqours 东蛋之路”后，现在差不多可以开始起草“Aqours 蛋巡之路”了。。。

题目大意

  给定两个数组 $A=\langle a_1,\cdots,a_n \rangle$ 和 $B=\langle b_1,\cdots,b_m \rangle$，定义 $A+x$ 表示 $\langle a_1+x,\cdots,a_n+x \rangle$，求 $\sum_{x=-10^{100}}^{10^{100}} LCS(A+x,B)$。

  $n,m \le 4000,\ \ |a_i|,|b_i| \le 10^8$
  10s，16MB

12.31 已经成为每年最期待的日子了 qaq

  发现自己真的好久没写游记了啊。。。倒是各式各样的其他小作文写了不少。。。

题目大意

  给定两个长度为 $n$ 的 01 串 $s,t$，每个串都不会有连续三个相同的字符。现在每次操作可以将 $s$ 的一位反转，但反转之后也要保证没有连续三个相同的字符，求最少的步数使得 $s$ 变成 $t$。

  $n \le 5000$
  2s

题目大意

  设 $x$ 的质因数分解为 $p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，记 $f(x) = c_1^{p_1}c_2^{p_2}\cdots c_m^{p_m}$，给定 $n$，求 $\sum_{i=1}^n f(n) \bmod 10^9+7$。

  $n \le 10^{14}$
  10s

大概就随便记一记读过的有亮点的东西，觉得很牛逼的东西就分享一下，随缘更新。

当然也不是教程或者阅读笔记。

TCS 是指 Theoretical Computer Science。