NOI2021 加油！

RainAir's Blog

「BZOJ3659」Which Dreamed It

链接题目大意一个欧拉图，从 $1$ 出发的欧拉路径个数。 $n \leq 100$题解这种结论题可能只有知道结论才能做。首先我们求出一个 $1$ 点为根的内向生成树：我们考虑从两个方向来证明：生成树 $\to$ 欧拉回路我们对于每个点 如果存在未走过的非树边就走过去 否则走树边 这样构造显然是一个欧拉回路 且满足引理 1。欧拉回路 $\to$ 生成树把每一个点最后走的边作为树边 这样构造显然...

  • RainAir
  • April 17, 2020
  • No comments

    • 「AGC018F」Two Trees

    题意有两个有根树 每个树的点都用 $1 \ldots n$ 编号。现在你要给每一个点指定一个权值 满足所有子树的和的绝对值是 1（两棵树上相同编号的点的权值相同）$n \leq 10^5$题解首先我们考虑转化一下题意：由于只有两种状态，考虑给边定向。如果这个子树=1我们就把这个点到父亲的点往下连 否则往上连（上，下都是表示深度）。发现根没有被考虑到 新建一个虚点 向两个根连边。我们记这个点的...

  • RainAir
  • April 16, 2020
  • No comments

    • 「BZOJ3724」Krolestwo

    题目大意题目链接 你有一个无向连通图，边的总数为偶数。设图中有 $k$ 个奇点（度数为奇数的点），你需要把它们配成 $\frac{k}{2}$ 个点对（显然 k 被 $2$ 整除）。对于每个点对 $(u,v)$，你需要用一条长度为偶数（假设每条边长度为 $1$ ）的路径将 $u$ 和 $v$ 连接。每条路径允许经过重复的点，但不允许经过重复的边。这 $\frac{k}{2}$ 条路径之间也不...

  • RainAir
  • April 16, 2020
  • No comments

    • 「BZOJ3706」反色刷

    题目大意题目链接给一个无向图 边有黑白两种颜色。你每次可以指定一个回路上的所有的边颜色都反色。问至少多少次操作可以都变成白色。支持边颜色的修改。$n \leq 10^6$题解这种题目就比较神仙，代码好写 但是思维难度不低（至少我这种菜鸡想不出来）我们首先考虑如果有了一个方案 它有哪些性质。我们把所有的回路上每一次经过的边都连上去建一个新图。发现这个新图有如下性质：白边都经过偶数次黑边都经过奇...

  • RainAir
  • April 14, 2020
  • No comments

    • 「ZJOI2018」 历史

    题目链接题目描述有一个一号点为根的有根树 初始时所有点均无颜色。定义对某个点的操作是将这个点到根的所有路径涂上和这个点编号相同的颜色。定义一次这样的操作的收益是这个点到根上的路径与这个点颜色不同的颜色种类个数（未涂过的不算）现在你知道了每个点最多只行了多少次这种操作 让你安排一种操作顺序 使得收益最大。带修改。题解这个题意看起来花里胡哨，我们先考虑如何转化这个题意。每个点到根的路径涂上新颜色...

  • RainAir
  • April 14, 2020
  • No comments