【7.14】代码源 -【拆方块】【XOR Inverse】【连续子序列】【三角果计数】

#501. 拆方块

题意：有 $n$ 堆方块，第 $i$ 堆方块由 $h_i$ 个方块堆积而成。具体可以看样例。

接下来拆方块。一个方块称为内部方块当且仅当他的上下左右都是方块或者是地面。否则方块就是边界方块。每一次操作都要把边界方块拿掉。

问多少次操作之后所有方块会消失。

思路：最后剩下的肯定是底端的。然后发现某个底端方格的存活时间即为改方格到达空气的最短路。第 $i$ 个到达第 $j(j\le i)$ 个顶端的路径为 $w=i-j+a_j$ ，维护后两项极值即可。 $(j\ge i)$ 同理。

AC代码：http://oj.daimayuan.top/submission/286915

#497. XOR Inverse

题意：给你一个有 $n$ 个非负整数组成的数组 $a$ ，你需要选择一个非负整数 $x$ ，对数组 $a$ 的每一个 $a_i$ 与 $x$ 进行异或后形成新的数组 b，要求 $b$ 数组的逆序对个数最小，如果有多个 $x$ 满足条件，输出最小的 $x$ 。

题解：(01字典树/归并排序求逆序对) 代码源每日一题Div1 XOR Inverse

思路：首先需要知道 01 字典树是可以实现归并求逆序对的，因为它本身就是一个二叉搜索树，我们可以从根节点向下搜，求逆序对。假如我们需要对所有元素的某一位置反，那么相当于在字典树上的这一层的左右儿子子树互换。容易知道互换只影响当前层的贡献。

那么做法就是：求出每一位不置反和置反对逆序对数量做出的贡献，选数量最少的方式即可，因为置反是不会影响其他层的贡献。

AC代码：http://oj.daimayuan.top/submission/287292

顺便做了一道 01 trie 上的 DP

E. Xor Tree

题意：给定你一个长度为 $n$ 的序列 $a(a_i\ne a_j)$ ，对于每个$i$，它会向序列中的满足$a_i\oplus a_j$（$\oplus$代表异或）最小的$j$连双向边，并且如果$j$也向$i$连了边，只算一条边。现在要让你删去序列中的一些数，使得最后形成的图是一颗树，输出最少需要删除几个数。

题解：题解 CF1446C 【Xor Tree】
题解 CF1446C 【Xor Tree】

思路：懒得写了。

AC代码：https://codeforces.com/problemset/submission/1446/164118190

#504. 连续子序列

题意：找出 $a_n$ 最长的连续子序列 $b_m$ 并输出。这里的连续指的是 $b_i+1=b_{i+1}$ 。

思路：类似于 LIS ，这里维护每一个数的最大 $dp$ 值即可。

AC代码：http://oj.daimayuan.top/submission/286941

#505. 三角果计数

题意：给一个 n 个节点的树, 三角果定义为一个包含 3 个节点的集合, 且他们两两之间的最短路长度a, b, c能够构成一个三角形。

计算这棵树上有多少个不同的三角果。

思路：首先发现如果三点同时在一条简单路径上，必然不会是三角形。如果某个点是其他两点路径中的某点分叉出去的点（或者说是三个点中任意两点的路径不会经过第三点），即为三角形。

可以计算组成一条链的三元集合数量。我们对这种集合按照中间点分类，即枚举链的中间点，计算有多少个二元集合的路径会经过该点。dfs 即可。

AC代码：http://oj.daimayuan.top/submission/287542