当前位置: 首页 > news >正文

P13754 【MX-X17-T3】Distraction

原题链接:P13754 【MX-X17-T3】Distraction - 洛谷

非常好的题,非常好的思想。简单思想的结合体就是不易察觉的难题。这题实际上就两个难点:1. 处理每个点的权值 \(v_i\)。2. 推导交换权值并找出最长字段和

首先对于每个点的权值,一种直接的求法(以求左边的大于 此点 \(u\) 的数量为例)是维护一个新的序列 \(b\),然后从原序列 \(a\) 的左边开始不断将,每个点数值 \(u\) 在 上对应的地方加一。然后每次统计 \(b\) 序列上 \([1 ,u - 1]\) 里面 \(1\) 的数量,这个数量就是 \(b\) 左边大于他的数的数量。因为设计单点修改和区间查询,所以可以使用树状数组解决。这种方法较为直观,但是时间上不算最有,且写起来比较麻烦,于是探索新的办法。

观察题目,\(a\) 序列实际上是一个 \(1 \sim n\) 的排序,如果 \(a\) 序列是按照 \(1,2,3,\dots,n\) 的方式排列,那么 \(v_i\) 都等于 \(0\)。如果保持一个点 u 位置不变,而随意改变除了 u 之外的数字,你会发现,无论如何改变,\(v_i\) 均为 \(0\),因为当一个数 k 从左边变到右边时,右边的一个数也变到了左边,两边的逆序对数量的奇偶性不会发生变化,因此 \(v_i\) 也就不会发生变化。如果要想改变 \(v_i\) 那就只能改变 u 的位置,如果把 u 向左移动一位,那么和他交换的那个数,如果大于它,那么 \(v_i\)会因为逆序对减少一个而改变;如果那个数小于它,那么 \(v_i\) 会因为逆序对增加一个而改变。
此时在对其他数进行交换,无论如何 \(v_i\) 也不会改变,因为大、小的逆序对都同增同减的。可知,对于 \(v_i\) 来说,\(v_i = \lvert i从小到大的原位置 - i的当前位置 \rvert \bmod 2\)。依靠这一点,我们就可以在 \(\operatorname O(n)\) 的时间复杂度之内简单地(就是 \(i - i 当前的位置\))算出来 \(v_i\)

然后是关于交换,通过分析可以发现,在交换的区间内,除了被交换点,区间内的其他点(下面称为被影响点)都移动了一位,因此这些点的 \(v_i\) 会变化(变化指从 \(1\) 变成 \(0\) 或者从 \(0\) 变成 \(1\))。而交换的那个点的数值变与不变,只取决于这个区间大小(在去掉当前点的情况下)的奇偶性(即位移的距离大小),如果为奇数则变化,如果为偶数则不变。

关于被影响点,设区间内被影响的点有 \(k\) 个,其中 \(v_i\) 为 1 的有 x 个,那么在交换后,这些点的贡献会从 \(x\) 变为 \(k - x\),即变化了 \(k - 2x\),如果划分给每个点,那么每个点在交换后对整体的影响就是 \(1 - 2v_i\),那么对于这批贡献只需要求最大字段和即可,这部分可使用 DP 解决。

记下来就剩下了交换点的变化,因为交换点的变化与否取决于 k 的奇偶性,因此我们在做上面的 DP 时需要分两个做,一个是区间大小为奇数的,一个区间大小为偶数的,以方便我们处理交换点。

看得出,这确实一道好题啊,不亏我费这么长时间。

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 5000010;int n, m;
int g[N], w[N];
int f[N], h[N]; // 分别是区间长度为奇数int read()
{int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch =  getchar();}while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();return x * f;
}int main() 
{int T;cin >> T;while (T -- ){int sum = 0;cin >> n;for (int i = 1; i <= n; i ++ ) {scanf("%d", &g[i]);w[i] = i - g[i] & 1;sum += w[i];}memset(f, -0x3f, sizeof f);memset(g, -0x3f, sizeof g);f[1] = 1 - 2 * w[1];f[2] = 1 - 2 * w[2];h[2] = 2 - 2 * (w[1] + w[2]);int ans = 0, res = 0, maxv1 = 0, maxv2 = 0; // 长度为奇数,长度为偶数maxv1 = max({maxv1, f[1], f[2]});maxv2 = max(maxv2, h[2]);for (int i = 3; i <= n; i ++ ){f[i] = max(f[i - 2] + 2 - 2 * (w[i] + w[i - 1]), 1 - 2 * w[i]);h[i] = max(h[i - 2] + 2 - 2 * (w[i] + w[i - 1]), 2 - 2 * (w[i] + w[i - 1]));maxv1 = max(maxv1, f[i]);maxv2 = max(maxv2, h[i]);}if (maxv2 == 0) cout << sum + max({maxv1 - 1, maxv2 - 1, 0}) << endl;  else cout << sum + max({maxv1 - 1, maxv2, 0}) << endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=16102

相关文章:

  • 2025.9.24
  • 初学汇编
  • 架构图设计还得是华为 - 智慧园区
  • 解决zsh: corrupt history file /home/sgud4h5gh/.zsh_history的办法
  • StarRocks GitHub 工作流程
  • 对象初始化器的使用方法
  • C++、Java 和 Python 在输入输出差别
  • 我的学习记录之自我介绍、思维导图和监督措施
  • 用 Java 和 Tesseract 进行验证码识别:基础实现与优化
  • Java第二次实验
  • 详细介绍:【2025PolarCTF秋季个人赛】WEB方向wp
  • 英语_阅读
  • Nuget安装以及西门子PLC通信
  • 每日反思(2025_09_24)
  • 安装Flask库
  • 《新概念英语》在线朗读,单句点读,随时随地在线学习。
  • P10004 [集训队互测 2023] Permutation Counting 2
  • 毕赤酵母细胞工厂升级:CRISPR 技术破局传统局限,解锁多基因代谢工程新可能
  • 日总结 7
  • 读书笔记:OpenPBR 规范(1)
  • 9月24号
  • linux系统下nginx网站ssl证书自动续签
  • C#使用Bitmap操作图像的基础方法
  • 知识学报:位运算(1)
  • CentOS 7 下 Kubernetes 集群搭建与配置指南
  • 2024/9/24
  • Git 工作树 (worktree)、合并 (merge) 流程、拉取请求 (PR) 机制,以及基线分支概念
  • 【HD300I 】基于昇腾 310P 的全国产化智能计算模组
  • 《密码系统设计》第三周
  • 详细介绍:Cloudflare 推出 GenAI 安全工具,守护企业数据