题解 10

期中到了，好快。

CF 1512 E Permutation by Sum

求 $n$ 的任何一个全排列，使得其区间 $[l, r]$ 内的元素和恰为 $s$。
$1\le T\le 500, 1\le n \le 500, 1\le l, r\le n, 1\le s \le \frac{n(n + 1)}{2}$

给定全排列的一个区间，可以求出区间和的上下界。上下界之间的值都可以取到，因为我们总可以通过将一个元素替换成比它大 $1$ 的元素，一直替换到上界为止。

于是可以从最初的 $s$ 中扣除元素。枚举 $1$ 到 $n$，可以扣除这个元素当且仅当剩下的和在新的上下界内，扣到 $0$ 后，就会得到区间内所有的元素。

CF 1465 C Peaceful Rooks

$n\times n$ 的国际象棋棋盘上有 $m<n$ 个车，给出这些车的位置，求最小的移动次数，使所有的车都在主对角线上。输入保证车不会互相攻击。
$1\le T\le 1000, 2\le n\le 10^5, 1\le m < n$

如果车要去的那个位置，行列上有别的车，需要先把那辆车移走，最优的方案是把那辆车移到另外一个它该去的主对角线位置。递归想下去可以发现一个互相等待的死锁情况，几个车循环占住了位置，需要先移出去一次。除此情况之外，需要移动的次数和不在主对角线的车的数量一样。

可以看作图论题。车的位置 $(x, y)$ 代表一条从 $x$ 到 $y$ 的边，我们要调整每条边的端点使所有的边都是自环。输入保证了节点的出入度至多各为 $1$。不是自环的边里，要移动的次数等于边数，另外要加上成（长度大于一的）环的数量。

CF 1529 C Parsa’s Humongous Tree

一棵 $n$ 个结点的树，每个结点 $v$ 有一个区间 $[l_v, r_v]$，此外可以获得一个区间内的权值 $a_v$。定义这棵树的价值为所有相邻结点权值差的绝对值之和。给定每个结点的区间和树的结构，求树最大的价值。
$1\le T\le 250, 2\le n\le 10^5, 1\le l_i\le r_i\le 10^5$

首先证明权值一定是贴着边界的。对于一个取权值 $a$ 的结点，在与它相邻的结点中，设 $p$ 个结点的权值更大，$q$ 个更小，则

1. $p > q$ 时，结点取小于 $a$ 的值更优
2. $p < q$ 时，取值应该尽量大
3. $p = q$ 时，怎么取值都无妨

注意在 $a$ 变化时三种情况可以随时转换。

于是简化成一个 01 问题：每个结点有两种取值，求树的最大价值。

树上 dp 解决，每个结点的值从子树合并得到，每做完一个子树两种情况的价值，结点这棵树两种价值的增量分别是子树两个取法算出的最大值。

CF 1556 C Compressed Bracket Sequence

以这样一种方式来描述一个括号序列：一串数 $c_1,c_2,c_3,\cdots,c_n$，$c_i$ 在 $i$ 为奇数的时候代表连续左括号的数量，偶数时代表右括号。给出这样一串数，在它表示的括号序列中找出所有是合法括号序列的子段，输出数量。
$1\le n\le 1000, 1\le c_i\le 10^9$

字符串模拟题。本质上还是一般的栈处理，但是这里需要求所有的序列数量，所以需要另外一个栈记录各个深度（层数）下的序列个数。左括号正常入栈，右括号弹栈时需要更新对应层的合法序列数量。不太好讲，上代码。

int ans = 0;
tmp.push(0);  // 最浅层现在没有序列
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (i % 2 == 0) {
      st.push(x);  // x 个左括号入栈
      // 左括号这段所在的一层，现在还没有匹配的序列
      tmp.push(0);
    } else {  // x 个右括号，准备弹栈
      // 一个一个弹，因为要处理每一层的序列
      while (!st.empty() && st.top() <= x) {  
        tmp.pop();  // 先弹出多塞的 0
        // 这一层的所有序列，和当前右括号所在的序列
        // 组合形成的序列数量
        ans += tmp.top();  
        if (st.top() == x)
          // 正好相等，则这一层的序列多一个
          tmp.top()++;
        else
          // 不相等，这一层清空
          tmp.top() = 0;
        // 循环条件限制，右括号不会被消耗完，可以放心配对
        ans += st.top();
        // 消耗右括号
        x -= st.top();
        // 这一段左括号消耗完了，弹出
        st.pop();
      }
      // 右括号没有消耗完，且左括号还剩时
      // 此时左括号一定多于右括号
      if (x != 0 && !st.empty()) {
        // 左括号在的这层，多了一个序列
        tmp.top()++;
        // 匹配
        ans += x;
        // 消耗
        st.top() -= x;
      }
    }
  }
// ans 就是答案

CF 1592 C Bakry and Partitioning

一棵带点权的 $n$ 结点简单树，分成至少 $2$ 个至多 $k$ 个连通块，要求各块的结点异或和都相等。输出是否可行。
$1\le T\le 5\cdot 10^4, 2\le k\le n\le 10^5, 1\le a_i\le 10^9, \sum n\le 2\cdot 10^5$

利用异或的性质去合并分块可以发现，如果最后分成了偶数个块，一定可以规约成 $2$ 个块的情况，奇数个则可以规约到 $3$ 个。

首先对所有权求一遍异或和 $x$，如果结果是 $0$，则一定可以分成异或和相等的两块。

如果结果非 $0$，可以确定不能分成偶数个分块，但这没什么用。

只能分成奇数个分块的情况下，至少要分成三块，每块的异或和都是 $x$。那么先找最深的子树，找到之后删去这棵子树，接着找其他的，这样可以把符合条件的分块数量最大化。

深搜去数子树，记录以每个结点为根的子树的异或和，“删除子树”可以通过直接把对应根的异或和改成零实现。