由满分/零分人数反推候选答案串的出现次数,p=q=0 时在禁止集合上用前缀计数贪心构造字典序最小的可用串。
OJ: roj
题目 ID: 1693
难度:提高
标签:字符串哈希贪心python
创建: 2026-10-07 15:48
更新: 2026-10-07 15:48
形式化题目
给定 N 或 Y,
以及三个整数 N/Y 互换得到的串(
求长度
在所有这样的 -1。
题面里"其余神犇既非满分也非零分"不是额外约束:一旦
两个关键点:
- 字典序按字符的 ASCII 比较,即
N < Y。题面没有明说,但数据第 2 个测点 (,输入 NN、YY,答案是NY)正是这个顺序的证据: 若Y < N就该输出YN了。 - 因为
, 与 必不相等,满分集合与零分集合不会有交叉。
正解
思路
先看
其中 -1。
再看
最后是
那么要求就是"挑一个不在
字典序最小可以逐位贪心:从空前缀 N 再试 Y,只要"以当前前缀开头的
串里还有没被禁的"就定下这一位。判断"还能延伸"只需要一个计数:
长度为
的前缀 之下共有 个长度 的串。若 中以 为前缀的串有 个,则还有 个可用, 就等价于"这个前缀可行"。
因为 lower_bound(P) 到
upper_bound(P + "ZZZ…Z")(Z 比 N、Y 都大,补满 Z 就是该前缀的上界)。
而且这一段一定包含在上一层前缀对应的段里,所以二分时只要在当前 N 和 Y 都走不通(等价于 -1。
三个分支各自用一个候选规则,合起来覆盖了
| 情况 | 候选怎么来 | 附加检查 | |
|---|---|---|---|
| 必须出现 | |||
| 必须不出现 | |||
| 必须不出现 | 前缀计数贪心现场构造 | 逐位确保 |
前两种情况的枚举在代码里合并成了一趟:对每个出现过的串
为什么每位的判断是充分的? 设当前前缀 Y 开头,故 N,不可行再试 Y",只要还有解就绝不会走到两位都不可行的死路;
每一步都选了字典序更小的可行前缀,最终得到的正是全局字典序最小的串。
反过来若两位都不可行,则 -1,
逻辑上不会误伤有解的情形。
再看题面样例 YY,所以 YY 通过检查,输出 YY。
数据中的第 2 个测点是 NN、YY:禁止集合是
N(NN 被禁,但以 N 开头的可用串还有 NY,可行),
第二位试 N 得到 NN 被禁、改用 Y 得 NY,输出 NY,与数据一致。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:40
# update_at: 2026-10-07 15:48
import sys
from bisect import bisect_left, bisect_right
from collections import Counter
FLIP = bytes.maketrans(b'NY', b'YN') # 逐位取反的查表,用 bytes 比较省掉解码
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Counts = dict[bytes, int] # 答案串 -> 写出这份答案的人数
def flip(s: bytes) -> bytes:
"""逐位取反:N 变 Y、Y 变 N,得到与 s 完全不同的串(m ≥ 1)。"""
return s.translate(FLIP)
def pick_by_counts(cnt: Counts, p: int, q: int) -> bytes | None:
"""p + q > 0 时求标准答案:它本身出现恰 p 次,它的反串出现恰 q 次。
每个出现过的串 x 给出两个候选:s = x(p > 0,s 自己出现过)和 s = comp(x)
(p = 0 < q,此时 comp(s) = x 恰出现 q 次)。合法解至少让其中之一出现过,故不漏解。
"""
cands = [s for x in cnt for s in (x, flip(x))]
return min((s for s in cands if cnt.get(s, 0) == p and cnt.get(flip(s), 0) == q), default=None)
def smallest_free(forbid: list[bytes], m: int) -> bytes | None:
"""禁止集合之外的、长度 m 的字典序最小串;一个都不存在时返回 None。
前缀 `pref` 之下共有 2^rem 个长度 m 的串,只有在被禁的少于这么多时才能延伸下去。
`forbid` 已排序,以 pref 为前缀的串恰是连续一段,二分即可数出个数。
"""
prefix = b''
lo, hi = 0, len(forbid) # forbid[lo:hi] 恰好是以 prefix 为前缀的那些串
for d in range(m):
rem = m - d - 1 # 定下这一位后还剩几位
for ch in (b'N', b'Y'): # 先试 N,字典序最小
pref = prefix + ch
nlo = bisect_left(forbid, pref, lo, hi)
nhi = bisect_right(forbid, pref + b'Z' * rem, lo, hi) # 'Z' 比 'N'、'Y' 都大
blocked = nhi - nlo # 这个前缀下被禁掉的串数
if blocked < 1 << rem: # 还留着不受禁的延伸,这一位就定成 ch
prefix, lo, hi = pref, nlo, nhi
break
else:
return None # 两位都无路可走,这一层就断了
return prefix
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n, m, p, q = int(next(data)), int(next(data)), int(next(data)), int(next(data))
rows = [next(data) for _ in range(n)]
if p or q:
# 只需统计出现次数:满分人数与零分人数都直接读自计数表
cnt = Counter(rows)
ans = pick_by_counts(cnt, p, q)
else:
# 标准答案及其反串都不得出现,等价于避开禁止集合 A ∪ comp(A)
forbid = sorted({flip(s) for s in rows} | set(rows))
del rows # 15 MB 级输入,构造完限制集就释放
ans = smallest_free(forbid, m)
print(-1 if ans is None else ans.decode())
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 15:40
* update_at: 2026-10-07 15:48
*/
// main.cpp:正确答案。
// n 个人各写一份长度 m 的 N/Y 答案,其中恰有 p 人满分(答案 == 标准答案)、
// q 人零分(答案 == 标准答案逐位取反),求字典序最小的标准答案,无解输出 -1。
// 关键观察:满分人数就是"标准答案"这个串在输入中的出现次数,
// 零分人数就是"标准答案的反串"的出现次数;于是候选串可以由出现次数直接反推,
// 只有 p = q = 0 时候选有无穷多个,改用"前缀计数"贪心构造。
// 与 main.py 同一算法。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, p, q; // 题面数据(人数、判断题数、满分人数、零分人数)
vector<string> forbid; // p = q = 0 的禁止集合 A ∪ comp(A),排序去重后使用
unordered_map<string, int> appear; // 每个答案串被多少个人写出(只统计出现次数)
string ans; // 找到的标准答案
bool found; // 是否找到解
// 逐位取反:N 变 Y、Y 变 N。因为 m >= 1,comp(s) 永远不等于 s。
string comp(const string &s) {
string t = s;
for (size_t i = 0; i < t.size(); i++) {
t[i] = (t[i] == 'N') ? 'Y' : 'N';
}
return t;
}
// 串 s 在输入中的出现次数,没出现过就是 0
int count_of(const string &s) {
auto it = appear.find(s);
if (it == appear.end()) return 0;
return it->second;
}
// p + q > 0:标准答案 s 必须满足 cnt[s] == p 且 cnt[comp(s)] == q。
// 输入中每个出现过的串 x 都贡献两个候选:s = x(对应 p > 0,s 自己出现过)
// 和 s = comp(x)(对应 p == 0 < q,此时 cnt[comp(s)] == cnt[x] == q)。
// 任何合法 s 至少满足 cnt[s] > 0 或 cnt[comp(s)] > 0 之一,所以这样枚举一定不漏。
bool solve_by_counts() {
bool ok = false;
for (auto it = appear.begin(); it != appear.end(); ++it) {
for (ll k = 0; k < 2; k++) {
string s = (k == 0) ? it->first : comp(it->first);
if (count_of(s) != p) continue; // 满分人数必须正好是 p
if (count_of(comp(s)) != q) continue; // 零分人数必须正好是 q
if (!ok || s < ans) { // 多解时取字典序最小
ans = s;
ok = true;
}
}
}
return ok;
}
// p == q == 0:标准答案和它的反串都不得出现在输入中,候选有无穷多个,
// 用前缀计数贪心逐位构造字典序最小的合法串。
// 前缀 pref 之下共有 2^rem 个长度 m 的串;只要 forbid 中以 pref 为前缀的串
// 少于 2^rem 个,就必定存在一条不受禁的延伸,这一位就可以定下来。
// 每次都在"当前前缀对应的区间"里二分,所以区间只会越缩越窄。
bool solve_free() {
string s; // 已经确定下来的前缀
ll lo = 0, hi = forbid.size(); // forbid[lo, hi) 是以 s 为前缀的那一段
for (ll d = 0; d < m; d++) {
ll rem = m - d - 1; // 定下这一位后还剩多少位
// 禁止串总数至多 6e4 个,rem >= 20 时 2^rem 必然更大,用大常数代替避免溢出
ll limit = (rem >= 20) ? 1000000000000000000LL : (1LL << rem);
bool picked = false;
for (ll k = 0; k < 2 && !picked; k++) {
char ch = (k == 0) ? 'N' : 'Y'; // 先试 N,保证字典序最小
string pref = s + ch;
string up = pref;
up.append(rem, 'Z'); // 'Z' > 'Y',pref 后面补满 Z 就是该前缀的上界
ll nlo = lower_bound(forbid.begin() + lo, forbid.begin() + hi, pref) - forbid.begin();
ll nhi = upper_bound(forbid.begin() + lo, forbid.begin() + hi, up) - forbid.begin();
ll blocked = nhi - nlo; // 这个前缀下被禁掉的串数
if (blocked < limit) { // 还留着不受禁的延伸,这一位就定成 ch
s = pref;
lo = nlo;
hi = nhi;
picked = true;
}
}
if (!picked) return false; // 两位都走不通,说明这一层无路可走
}
ans = s;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> p >> q;
string s;
if (p > 0 || q > 0) {
// 只需要"每个答案串出现了几次":满分人数与零分人数都由此读出
for (ll i = 0; i < n; i++) {
cin >> s;
appear[s]++;
}
} else {
// p = q = 0:只需要禁止集合 A ∪ comp(A),不必统计次数
for (ll i = 0; i < n; i++) {
cin >> s;
forbid.push_back(s);
forbid.push_back(comp(s));
}
sort(forbid.begin(), forbid.end());
forbid.erase(unique(forbid.begin(), forbid.end()), forbid.end());
}
if (p > 0 || q > 0) found = solve_by_counts();
else found = solve_free();
if (found) cout << ans << "\n";
else cout << "-1\n";
return 0;
}复杂度
- 时间:读入与计数
。 时只需遍历去重串表,也是 。 时要把 个长度 的串排序,字符串比较最坏 , 共 ;构造时每一位做两次二分,字符串比较的代价累计 。 取 、 ,实测 C++ 最大点 0.12 s(输入 15 MB,含进程启动)、 Python 最大点 0.04 s(限时 1000 ms)。 - 空间:去重表 / 计数表最多
个长度 的串, ,即 15 MB 量级, 实测 C++ 峰值 35.9 MB;Python 把 15 MB 输入全部读进内存后峰值约 55 MB, 均在限定的 256 MB 内。 - 与 C++ 解法的关系:
main.cpp与main.py逐步对应, 区别只是 C++ 用unordered_map做计数、用lower_bound/upper_bound做前缀计数, Python 用Counter与bisect。同阶复杂度,都不存在 TLE 风险。
总结
- 把故事翻译成计数:满分人数就是"标准答案"这个串的出现次数,零分人数就是"标准答案的反串"
的出现次数,于是
时候选只能是输入里出现恰好 次的串,问题从 的搜索空间 塌缩到 个候选。 时不要把候选来源搞反:标准答案此时不在输入里,只能由"出现 次的反串取反" 得到,还必须额外验证它本身出现 次,否则会漏掉这个隐含条件。 是构造而非枚举:把限制写成禁止集合 , 判据"以 为前缀的 中串数 "把可行性压缩成一次二分计数, 逐位贪心(先 N后Y)即可得到字典序最小解。- 充分性来自补集大小:
不可行意味着它下面的 个串全被禁, 那么所有可行解只能走 Y,所以"先试N"的贪心不会错过解。 - 先验证再相信
std.cpp:本题std.cpp在仓库内 10 个真实测点全部通过 (PASS 10/10),本文的推导与它一致;另外用枚举个串的独立暴力做了约 3900 组 小规模交叉验证( 、 与 遍历 ,包含输出 -1的无解点),main.cpp与main.py两个实现与暴力均无差异。