洛谷P3770 [CTSC2017]密钥题解

题目链接：P3770 [CTSC2017]密钥

题意：

一个密钥是一个长度为 \(n = 2k + 1\) 的字符串，它包含 \(1\) 个字母 \(\tt{X}\)、k 个字母 \(\tt{A}\) 和k 个字母 \(\tt{B}\)。例如 \(k = 3\) 时，\(\tt{BAXABAB}\) 就是一个密钥。

如下图所示，可以按顺时针顺序把这 \(2k+1\) 个字母排成一个圈：

在 \(k\) 个字母 \(\tt{A}\) 中，有一部分可以定义为 “强的”。具体来说，从 \(\tt{X}\) 出发顺时针走到某个 \(\tt{A}\) 时，如果途中 \(\tt{A}\) 的数目严格多于\(\tt{B}\)的数目，则称此字母 \(\tt{A}\) 为强的。

对于上面的例子来说，顺时针方向从字母 \(\tt{X}\) 数起第 \(1\) 个和第 \(2\) 个字母 \(\tt{A}\) 是强的，而第 \(3\) 个字母 \(\tt{A}\) 不是强的。

一个密钥的特征值就是其中包含的强的字母 \(\tt{A}\) 的个数。

~~天才小朋友~~ cxy 给出了一个结论：

假设 \(k\) 个字母 \(\tt{A}\) 所在的位置已经固定，但是剩下的 \(k\) 个 \(\tt{B}\) 和 \(1\) 个 \(\tt{X}\) 的位置是未知的。（注意，满足这样要求的密钥一共有 \(k + 1\) 个，因为字母 \(\tt{X}\) 还剩下 \(k + 1\) 个可能的位置。）

可以证明：所有这 \(k + 1\) 个可能的密钥的特征值是各不相同的，它们恰好为 \(0, 1, 2, \cdots, k\)。

下面的图是一个具体的示例，从左到右的四个子图中分别有 \(3\) 个，\(2\) 个，\(1\) 个，\(0\) 个字母 \(\tt{A}\) 是强的。

类似地，如果固定 \(k\) 个字母 \(\tt{B}\) 的位置，那满足条件的所有 \(k + 1\) 个密钥的特征值也各不相同，恰好为 \(0, 1, \cdots , k\)。

现在你需要解决以下三个问题：

给定密钥中所有 \(\tt{A}\) 的位置，当密钥的特征值为 \(0\) 时，请问 \(\tt{X}\) 在哪个位置。

给定密钥中所有 \(\tt{A}\) 的位置，当密钥的特征值为 \(S\) 时，请问 \(\tt{X}\) 在哪个位置。

给定密钥中所有 \(\tt{B}\) 的位置，当密钥的特征值为 \(S\) 时，请问 \(\tt{X}\) 在哪个位置。

注意：字符串的 \(2k + 1\) 个字母的位置由 \(1\) 到 \(2k + 1\) 编号。

例：假定 \(k = 3, S = 2\)。那么：

当 \(\tt{A}\) 的位置是 \(\{2,4,6\}\) 且特征值为 \(0\) 时，\(\tt{X}\) 的位置在 \(7\) 。

当 \(\tt{A}\) 的位置是 \(\{2,4,6\}\) 且特征值为 \(2\) 时，\(\tt{X}\) 的位置在 \(3\) 。

当 \(\tt{B}\) 的位置是 \(\{2,4,6\}\) 且特征值为 \(2\) 时，\(\tt{X}\) 的位置在 \(5\) 。

输入格式：

第一行包含一个整数 \(k\)，意义如题所述。

第二行包含一个整数 \(\tt{seed}\) ，这个数将用于生成一个 \(k\) 元集合 \(P\)。

第三行包含一个整数 \(S\)，意义如题所述。

在数组 p[] 中，若 p[i] = 0，表示 i 不属于集合 P，否则，i 属于集合 P。

注：题目给出了一个数据生成器。太难看了懒得贴。

输出格式：

输出三行，每行一个数，依次对应问题描述中的三个子问题的答案。

即： 1. 第一个数表示当 \(k\) 元集合 \(P\) 代表 \(\tt{A}\) 的位置且特征值为 \(0\) 时 \(\tt{X}\) 的位置。

第二个数表示当 \(k\) 元集合 \(P\) 代表 \(\tt{A}\) 的位置且特征值为 \(S\) 时 \(\tt{X}\) 的位置。

第三个数表示当 \(k\) 元集合 \(P\) 代表 \(\tt{B}\) 的位置且特征值为 \(S\) 时 \(\tt{X}\) 的位置。

数据范围：

对于 \(100\%\) 的数据，\(0\le S\le k \le 10^7,~1\le \tt{seed} \le 10^4\)。

考虑暴力（30pts）怎么做。

枚举 \(\tt{X}\) 的位置，然后把 \(\tt{A}\) 当做 \(1\) ，把 \(\tt{B}\) 当作 \(-1\) ，

求一遍前缀和，则所有值大于 \(0\) 的 \(\tt{A}\) 的个数就是特征值。

考虑正解。类似于强字母 \(\tt{A}\) ，不妨定义强字母 \(\tt{B}\) 满足：

从 \(\tt{X}\) 出发顺时针走到这个 \(\tt{B}\) 时， \(\tt{B}\) 的数目严格多于 \(\tt{A}\) 的个数（包括这个 \(\tt{B}\) ）

然后有一个结论：强的字母（包括 \(\tt{A}\) 和 \(\tt{B}\) ）的总数恰好等于 \(k\) 。

证明：把 \(\tt{A}\) 当做 \(1\) ，把 \(\tt{B}\) 当作 \(-1\) 。

那么前缀和一定由若干个 \(0\) 分隔的区间组成，

并且这些区间一定全为正（强字母 \(\tt{A}\) ）或全为负（强字母 \(\tt{B}\) ）。\(\square\)

因此前两个小问均可以转化为第三个小问。

我们额外地把 \(\tt{X}\) 看作 \(-1\) ，令 \(s_i\) 为原序列权值的前缀和。

记原序列中 \(\tt{X}\) 的位置 \(x\) ，考虑一个强字母 \(\tt{B}\) （位置 \(i\) ）

如果它在 \(x\) 后面，那么一定有 \(s_i-s_x < 0 \Rightarrow s_i<s_x\)

如果它在 \(x\) 前面，那么一定有 \((s_{n}-s_x) + s_i < 0 \Rightarrow s_i \le s_x\)

可以发现，若有 \(t\) 个强字母 \(\tt{B}\) ，则有 \(t\) 个 \(s_i\) 满足 \((s_i < s_x) \lor (s_i = s_x \land i < x)\)

因此只要对所有可能是 \(\tt{B}\) 的位置，求出有序二元组 \((s_i,i)\) 的第 \(t\) 小元素，就是答案。

可以用计数排序来做，时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e7+15))

unsigned short seed;
int t,cnt,n,k,S,p[N],w[N/2],res[N/2],buf[N];
int rd() { return seed = (seed*12321)^9999; }
void generateData()
{
    cin >> k >> seed >> S; n = k*2 + 1;
    for(int i=1; i<=n; i++) t += (p[i] = (rd() >> 7) & 1);
    for(int i=1; t>k; i++) t -= p[i], p[i]=0;
    for(int i=1; t<k; i++) t += !p[i], p[i]=1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    generateData();
    for(int i=1; i<=n; i++)
        if(t = (p[i] |= p[i]-1), p[i] += p[i-1], !~t)
            w[++cnt] = i, ++buf[p[i]+k];
    for(int i=1; i<=n; i++) buf[i] += buf[i-1];
    for(int i=cnt; t = w[i], i; --i) res[buf[p[t]+k]--] = t;
    cout << res[cnt] << '\n' << res[cnt-S] << '\n' << res[S+1] << '\n';
    return 0;
}