洛谷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。

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

输出格式：

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

即：

第一个数表示当 $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;
}