NOI2021 加油！

RainAir's Blog

XXI Open Cup: Grand Prix of Krakow 部分题解

挺有意思的：我大概写完这套题的时候被通知被权贵申诉杀了，后来买了 C 决定还是补完比较好。A. Edit Distance Yet Again题意求两个字符串的编辑距离，如果答案 $> k$ 就输出 NO，否则需要输出方案。$k \leq 1000,|s|,|t| \leq 10^6$。题解一个比较套路的做法：考虑最基本的暴力 dp：$f_{i,j}$ 表示 $s$ 的长度为 $i$ ...

  • RainAir
  • May 17, 2021
  • No comments

    • ARC119F AtCoder Express 3

    题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2...

  • RainAir
  • May 17, 2021
  • No comments

    • ARC119D Grid Repainting 3

    题意有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。$n,m \leq 2500$。题解比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题...

  • RainAir
  • May 17, 2021
  • No comments

    • ABC201F Insertion Sort

    题意有一个长度为 $n$ 的排列 $p_i$，你可以执行以下操作任意次：将数字 $x$ 移动到任意一个位置，花费 $A_x$将数字 $x$ 移动到开头，花费 $B_x$将数字 $x$ 移动到结尾，花费 $C_x$求排序最小代价。$n \leq 2 \times 10^5$。题解首先 $B_x,C_x$ 都要和 $A_x$ 取 $\min$。手动模拟一下，我们先固定一些不动的数 $a_1,a_...

  • RainAir
  • May 16, 2021
  • No comments

    • Educational Codeforces Round 108

    由于是恢复训练，所以会把所有题目解法都写写。A显然是少的每一堆就放一个，大的尽量均摊，设 $r < b$，那么就是判断 $\lceil \frac{b}{r} \rceil -1\leq d$。B模拟一下发现这东西无论什么路径权值都是 $nm-1$。证明可以考虑对 $n+m$ 归纳：首先 $n=m=1$ 是对的，考虑到达 $(n,m)$ 最后一步是怎么走的，如果是从 $(n-1,m)$...

  • RainAir
  • May 16, 2021
  • No comments