当前位置：网站首页>【7.14】代码源 -【拆方块】【XOR Inverse】【连续子序列】【三角果计数】

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

2022-07-17 18:28:00 【ZhgDgE】

#501. 拆方块

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

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

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

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

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

#497. XOR Inverse

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

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

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

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

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

顺便做了一道 01 trie 上的 DP

E. Xor Tree

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

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

思路：懒得写了。

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

#504. 连续子序列

题意：找出 a n a_n an​ 最长的连续子序列 b m b_m bm​ 并输出。这里的连续指的是 b i + 1 = b i + 1 b_i+1=b_{i+1} bi​+1=bi+1​ 。

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

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

#505. 三角果计数

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

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

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

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

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

原网站

版权声明
本文为[ZhgDgE]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51948235/article/details/125790647

边栏推荐

猜你喜欢

随机推荐