由于最近更换了 KaTeX，公式崩了可以立刻发邮件/评论来 D 博主，我会立即更换的。。。

RainAir's Blog

CF1434D Roads and Ramen

题意给出一个 $n$ 个点的数，边有边权，支持翻转一条边的边权，以及求最长的满足路径上边权异或和是 $0$ 的路径。题解相当于子树翻转，求相同颜色的直径。赛时被卡常做法：直接动态维护直径端点，合并的时候暴力枚举合并。一个比较优秀的做法：转括号序后两个点的距离就是括号匹配后失配的括号数量。先考虑如何快速求区间内失配的括号数量：考虑维护失配的右括号和左括号数量，记为 $a,b$。合并的时候设左儿...

  • RainAir
  • November 20, 2020
  • No comments

    • gym100801I Insider's Information

    题意要求构造大小为 $n$ 的排列，要求至少 $\lceil \frac{m}{2} \rceil$ 条限制：第 $i$ 条限制 $(a_i,b_i,c_i)$ 形如排列中 $b_i$ 的位置要在 $a_i$ 和 $c_i$ 之间。题解神仙题。这个题一般确定排列的方法都不能用了，我们考虑这个在两个数中间的限制：考虑用按照顺序每次将一个数放到前面或者后面的方式。因为保证有解，所以肯定能搞出来一...

  • RainAir
  • November 20, 2020
  • No comments

    • 降智比赛题解

    A. 气球设 $f_i$ 表示最后一次选择的是 $i$ 的答案，暴力转移是枚举一个 $j$，判断 $c_i,c_j$ 是否相同对应乘上系数转移就行了。我们记 $mx_i$ 表示当前考虑完的所有 $f$ 的时候 $c_k = i$ 的 $f_k$ 的最大值，那么我们转移只需要知道 $mx_{c_i}$ 和剩下的数的最大值就行了，分别记录最大值和次大值是什么即可。#include <bit...

  • RainAir
  • November 10, 2020
  • No comments

    • 此内容被密码保护

    请输入密码访问

  • RainAir
  • November 3, 2020
  • No comments

    • 此内容被密码保护

    请输入密码访问

  • RainAir
  • November 3, 2020
  • No comments