P11214粗糙题解

· · 个人记录

（如果思路可行，再进行排版）

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int maxn = 2e5+10;
int k[maxn], s=1999999999;
long long ans;
long long mod = 1e9+7;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> k[i];
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        s = min(s, max(t-1, k[i]-t));
        k[i] = min(t-1, k[i]-t);
    }
    sort(k+1, k+n+1);
    for(int i = 1; i <= n; i++) {
        if(k[i] >= s) k[i] = s;
        ans = ((((k[i]-k[i-1]) + ans)%mod)*2)%mod;
    }
    ans += (s-k[n])%mod;
    ans = (ans+1) % mod;
    cout << ans << endl;
    return 0;
}

基础思路

从题目给出的具体定义入手，先看原题对对角线的定义：

在位置 (a_1, a_2, \dots, a_n) 处有一颗黑洞。这片 n 维空间中所有与它在同一条对角线上的位置都将被吞噬：

转化一下题意，就是寻找一个满足条件的 k，使得 k \ge 0，且每一维坐标，都要满足 \lvert a_i - b_i \rvert = k，对每一维的坐标，由于中心位置是确定的，而对角线的点是不确定的，设一个对角线的点 (b_1, b_2, b_3,...,b_n)，我们可以对第 i 个维度作出函数图像，即

y=\left |b_i-a_i \right |

且这个函数的自变量 b_i 的取值范围是 [1,m_i]，作出图像，如下图：

我们发现，满足条件的 b_i，会有两种情况，第一种是有两组满足条件的 b_i，对应着是直线 y = k 与图像有 2 个交点；第二种是仅有一组满足条件的 b_i，对应着是直线 y = k 与图像有 1 个交点。

忽略 k = 0 的情况，因为在题目给出的范围内，k=0 的情况有且仅有 1 个。

多画几组图像观察可知， 端点处离这个函数对称轴最近的距离，就是满足有两组解的 k 的临界值，我们记这个距离为 q_i, 则有

q_i = \min(a_i-1, m_i-a_i)

当 1\le k \le q_i 时，对于该维度 i，存在两组可能的 b_i。

端点离这个函数对称轴最远的距离，就是满足有一组解的 k 的临界位置，我们记这个距离为 h_i，则有

当 1\le k \le h_i 时，对于该维度 i，仅存在一组可能的 b_i。

h_i = \max(a_i-1, m_i-a_i)

综上，当 1\le k \le h_i 时，对于该维度 i，有可能成为答案的 b_i。

后面维度所有求出来的 k 必须在这个范围，如果不在这个范围，也要取交集，必须保证对于任意一个维度求出的 k 的范围都属于任意一个维度 k 的范围的子集，否则，会有不符合要求的解（结合定义思考）。

那么现在就需要通过 q,h,k 来维护答案

根据乘法原理，枚举每个 k，统计该 k 在每个区间对应的 b_i 解的个数并相乘，最后将相乘的答案相加，复杂度比较大 ，过不了本题。

换个角度思考，我们能求出能枚举的 k 的取值范围，就是所有 q_i 的最小值，我们来仔细想想更新答案的过程，以样例1 为例子：

2
6 6 
2 3

按照上面的思路，我们求出来 k 的取值范围是 [1,3]。

当 k = 1 时第 1 维度有两种可能的 b，第 2 维度有两种可能的 b，有 4 种情况；

当 k = 2 时第 1 维度有一种可能的 b，第 2 维度有两种可能的 b，有 2 种情况；

当 k = 3 时第 1 维度有一种可能的 b，第 2 维有一种可能的 b，有 1 种情况；

加上最后 k = 0 的情况，共 8 种情况。

再看每一个维度，

第 1 维度，满足两组解的 k 只有 1。

第 2 维度，满足两组解的 k 的取值范围为 [1,2]

对于我们最初求出的 k 的范围，每一组 k，至少也就是只有一种情况，对答案有贡献的也就是存在两组解的情况，我们对于每个维度得到满足两组解的 k 的范围，给这个范围所有的 k 对应的答案都乘上 2，问题便转化到维护区间的问题。

例如，对于样例的情况，初始的 k\in [1,3]，每个 k 对答案的贡献是

1 1 1

第 1 维度，满足两组解的 k 只有 1。给区间 [1,1] 都乘上 2，这个时候 k 就是

2 1 1

第 2 维度，满足两组解的 k 的取值范围为 [1,2].给区间 [1,2] 都乘上 2，这个时候 k 就是

4 2 1

求和，最后加上 1 就是我们要的答案。

有没有一个很好的方式维护这个区间的值呢？

我们上面的操作是满足交换律的，也就是先更新第 2 维度的 k 的值与先更新第 1 维度的 k 的值是一样的，如果有更多维度也可以随意选择更新的顺序。

那么我们先把满足有 2 组解的 k 的临界值从小到大排序，至于原因，看完下面的过程应该能明白。

由于更新答案的区间的左端点总是 1，从小到大更新，就保证了我们更新的区间是一步一步向右扩展的，例如区间

1 1 1 1 1

假设我们要给 [1,4], [1,2] 这些区间分别乘上 2。我们优先更新 [1,2] 区间，整个区间的和就会变成前两个区间的和的乘上 2，前两个区间和变成了 2。

然后更新 [1,4]，首先原来更新的 [1,2] 的区间和要乘 2，然后加上 [3,4] 内 1 的数量乘上 2，然后这个就是新的区间和的值。

最后还剩下没更新的区间 [5,5]，答案加上 1 就行。

推广到一般，在每次更新的答案的基础上，加上往后更新区间与原区间多出来的 1 的个数，然后乘上 2，最后加上没有更新的区间的值，就是答案。但是要特判一下有两组解的 k 的区间比最开始求得 k 答案区间还要大的情况，这个时候直接把范围设置成 k 答案区间的右端点即可。

其实就是源码的这个式子的来历：

ans = ((((k[i]-k[i-1]) + ans)%mod)*2)%mod