简要题意

给定一个 \(n\) 个数的序列 \(a\) 和一个数 \(k\) ，定义一个子区间 \([l,r]\) 是好的，当且仅当这个区间内存在一个子序列满足：

• 包含 \(a_l\) 和 \(a_r\)
• 任意两个相邻数的差的绝对值不超过 \(k\)

请求出所有合法的子区间数量。多组数据，\(1\le \sum n\le5\times10^5,0\le k\le10^5,1\le a_i\le10^5\) 。

Luogu P5304

求出所有点到特殊点的最短路和特殊点到所有点的最短路，枚举边更新答案

Luogu P7916

平面图最小割转最短路

简要题意

给定一个数列 \(a\) ，求 \(\sum_\limits{i=1}^{n}\sum_\limits{j=i}^{n}f(i,j)\) 其中 \(f(i,j)\) 表示对 \(a_i\sim a_j\) 依次做如下操作：

• 初始有一个空的序列的序列

• 对于每个 \(a_i\) 找到序列中第一个序列，使得这个序列的末尾和 \(a_i\) 的按位与不为 \(0\)

  • 如果找到了就把 \(a_i\) 放到那个符合条件的序列末尾
  • 如果没有找到符合条件的序列，则将 \(a_i\) 作为一个新的序列放到外层序列的末尾

• 对于每个 \(i\) 都操作完后有 \(f(i,j)=\) 外层序列的大小

数据范围 \(n\in[1,3\cdot 10^5], a_i\in[0,3]\) 。

简要题意

题解

这道题是一道非常有意思的思维题，这里给出一个小提示，只用 \(3\) 次询问就可以极大概率猜对答案，建议读者独自思考一下。

CF1761E

人类智慧题

1，假如本来就联通，答案显然为0

2，假如有连通块不是团，显然可以操作一次那个联通中没有连向所有点的点使联通

简要题意

平面上给定 \(n\) 个机械臂的长度和目标点，构造一个从坐标系原点出发的 \(n\) 个机械臂折线，使得折线另一端离目标点尽量近。\(n\le 20\) 坐标绝对值 \(2\times 10^4\) 。

A. Bridge

Status: \(\color{green}\text{Accepted +1}\)

Author: Dong

首先有一点观察：

• 在每次交换后，依然是每根棒上有且仅有一个人，而且是唯一确定的，只与现在有哪些交换有关

那么显然就可以分段维护，考虑根号分治，第一想法关于长度根号分治，然后维护在某一段内 \(1\sim n\) 的每个数会去哪里，即为转移数组\(p\)，但是我们发现在某段里可能有过多的交换，显然复杂度不可控。