正确答案

GitHub跳转原题关系图返回列表

由满分/零分人数反推候选答案串的出现次数,p=q=0 时在禁止集合上用前缀计数贪心构造字典序最小的可用串。

OJ: roj

题目 ID: 1693

难度:提高

标签:字符串哈希贪心python

创建: 2026-10-07 15:48

更新: 2026-10-07 15:48

形式化题目

给定 nn 个长度均为 mm 的字符串 a1,a2,…,ana_1, a_2, \dots, a_n,每个字符取 N 或 Y, 以及三个整数 p,qp, q(0⩽p,q0 \leqslant p, q 且 p+q⩽np + q \leqslant n)。 记 comp(s)\mathrm{comp}(s) 为把 ss 中每一位 N/Y 互换得到的串(m⩾1m \geqslant 1,所以始终有 comp(s)≠s\mathrm{comp}(s) \neq s)。

求长度 mm 的字符串 ss,使

#{ i:ai=s }=p,#{ i:ai=comp(s) }=q, \#\{\,i : a_i = s\,\} = p, \qquad \#\{\,i : a_i = \mathrm{comp}(s)\,\} = q,

在所有这样的 ss 中取字典序最小者;若一个都不存在则输出 -1。

题面里"其余神犇既非满分也非零分"不是额外约束:一旦 ss 定下来,每个人都按自己的答案自动 归入满分 / 零分 / 其他三类,p,qp, q 恰好就是上面两个计数。所以整个题目就是计数恰好匹配。

两个关键点:

  1. 字典序按字符的 ASCII 比较,即 N < Y。题面没有明说,但数据第 2 个测点 (n=2,m=2,p=q=0n = 2, m = 2, p = q = 0,输入 NN、YY,答案是 NY)正是这个顺序的证据: 若 Y < N 就该输出 YN 了。
  2. 因为 m⩾1m \geqslant 1,ss 与 comp(s)\mathrm{comp}(s) 必不相等,满分集合与零分集合不会有交叉。

正解

思路

先看 p>0p > 0。 满分的人写出的答案就是标准答案,所以 ss 必须是某个人写过的串; 又恰有 pp 个人满分,所以

cnt[s]=p,\mathrm{cnt}[s] = p,

其中 cnt[x]\mathrm{cnt}[x] 表示 xx 在输入中的出现次数(没出现则为 00)。零分条件同理写成 cnt[comp(s)]=q\mathrm{cnt}[\mathrm{comp}(s)] = q。于是做法很直接:把所有出现次数恰为 pp 的去重串当作候选, 逐个检查它的反串是不是恰出现 qq 次,在通过的候选中取字典序最小。输入里出现次数不是 pp 的串 一定当不了标准答案,全部直接排除。如果 p>0p > 0 却一个候选都没有,答案就是 -1。

再看 p=0p = 0 且 q>0q > 0。 此时 ss 一次都没在输入里出现过,但它的反串必须出现恰 qq 次。 反过来枚举输入中出现次数恰为 qq 的去重串 xx,则唯一的可能是 s=comp(x)s = \mathrm{comp}(x); 再补一个检查 cnt[s]=0\mathrm{cnt}[s] = 0。这个检查不能少:comp\mathrm{comp} 是自身的逆运算,若 xx 与 ss 都在输入里,则 cnt[comp(s)]=cnt[x]=q\mathrm{cnt}[\mathrm{comp}(s)] = \mathrm{cnt}[x] = q 看着像合法解,实际会让 cnt[s]>0=p\mathrm{cnt}[s] > 0 = p,必须排除。这里 ss 不必在输入里出现,所以候选不能再从输入里挑。

最后是 p=q=0p = q = 0。 此时 ss 与 comp(s)\mathrm{comp}(s) 都不能出现在输入里,候选从原本的 “输入里挑一个"变成了"在 2m2^m 个串里任挑一个”,量级上没法枚举。把约束统一成一个禁止集合

F=A∪comp(A),A={ a1,…,an } 去重,F = A \cup \mathrm{comp}(A), \qquad A = \{\,a_1, \dots, a_n\,\} \text{ 去重},

那么要求就是"挑一个不在 FF 里的长度 mm 串,且字典序最小"。这里 ∣F∣⩽2n|F| \leqslant 2n, 在 2m2^m 个串里只占极小一撮,所以解通常大量存在。

字典序最小可以逐位贪心:从空前缀 PP 出发,每一位先试 N 再试 Y,只要"以当前前缀开头的 串里还有没被禁的"就定下这一位。判断"还能延伸"只需要一个计数:

长度为 dd 的前缀 PP 之下共有 2m−d2^{m-d} 个长度 mm 的串。若 FF 中以 PP 为前缀的串有 bb 个,则还有 2m−d−b2^{m-d} - b 个可用,b<2m−db < 2^{m-d} 就等价于"这个前缀可行"。

因为 FF 已经排序,以 PP 为前缀的串恰好是 FF 里连续的一段——从 lower_bound(P) 到 upper_bound(P + "ZZZ…Z")(Z 比 N、Y 都大,补满 Z 就是该前缀的上界)。 而且这一段一定包含在上一层前缀对应的段里,所以二分时只要在当前 [lo,hi)[\mathrm{lo}, \mathrm{hi}) 区间内查找,区间越缩越窄。p=q=0p = q = 0 时第一层若连 N 和 Y 都走不通(等价于 ∣F∣=2m|F| = 2^m), 就是无解输出 -1。

三个分支各自用一个候选规则,合起来覆盖了 p,qp, q 的全部取值:

情况 ss 是否出现在输入中 候选怎么来 附加检查
p>0p > 0 必须出现 cnt=p\mathrm{cnt} = p 的去重串 cnt[comp(s)]=q\mathrm{cnt}[\mathrm{comp}(s)] = q
p=0<qp = 0 < q 必须不出现 cnt=q\mathrm{cnt} = q 的去重串取反 cnt[s]=0\mathrm{cnt}[s] = 0
p=q=0p = q = 0 必须不出现 前缀计数贪心现场构造 逐位确保 可用>0\text{可用} > 0

前两种情况的枚举在代码里合并成了一趟:对每个出现过的串 xx,把 s=xs = x 与 s=comp(x)s = \mathrm{comp}(x) 都放进候选池,再用 cnt[s]=p∧cnt[comp(s)]=q\mathrm{cnt}[s] = p \wedge \mathrm{cnt}[\mathrm{comp}(s)] = q 统一筛选。 合并不漏解,因为任何合法 ss 至少让 ss 与 comp(s)\mathrm{comp}(s) 之一在输入中出现过 (否则 ss 就落进 p=q=0p = q = 0 的情形了),于是它总会被某个 xx 生成出来; 而 p=q=0p = q = 0 时这个筛选会拒绝所有候选,正好交给贪心分支。

为什么每位的判断是充分的? 设当前前缀 PP 可行(即存在长度 mm 的不受禁串以 PP 开头)。 若 P+NP + \texttt{N} 不可行,说明以它开头的 2m−d−12^{m-d-1} 个串全部落在 FF 里; 那么所有以 PP 开头的不受禁串必然以 Y 开头,故 P+YP + \texttt{Y} 一定可行。 所以"先试 N,不可行再试 Y",只要还有解就绝不会走到两位都不可行的死路; 每一步都选了字典序更小的可行前缀,最终得到的正是全局字典序最小的串。 反过来若两位都不可行,则 PP 下方一个可用串都没有,与 PP 可行矛盾,说明一开始就无解。 实现里还额外检查了"两位都不可行就返回无解",这只是在第一层真正无解时给出 -1, 逻辑上不会误伤有解的情形。

再看题面样例 n=2,m=2,p=2,q=0n = 2, m = 2, p = 2, q = 0:两个人都写 YY,所以 cnt[YY]=2=p\mathrm{cnt}[\texttt{YY}] = 2 = p, 且 cnt[NN]=0=q\mathrm{cnt}[\texttt{NN}] = 0 = q,候选 YY 通过检查,输出 YY。 数据中的第 2 个测点是 n=2,m=2,p=q=0n = 2, m = 2, p = q = 0,输入 NN、YY:禁止集合是 {NN,YY}\{\texttt{NN}, \texttt{YY}\},第一位试 N(NN 被禁,但以 N 开头的可用串还有 NY,可行), 第二位试 N 得到 NN 被禁、改用 Y 得 NY,输出 NY,与数据一致。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:读入与计数 O(nm)O(nm)。p+q>0p + q > 0 时只需遍历去重串表,也是 O(nm)O(nm)。 p=q=0p = q = 0 时要把 ∣F∣⩽2n|F| \leqslant 2n 个长度 mm 的串排序,字符串比较最坏 O(m)O(m), 共 O(nmlog⁡n)O(nm\log n);构造时每一位做两次二分,字符串比较的代价累计 O(m2log⁡n)O(m^2\log n)。 取 n=30000n = 30000、m=500m = 500,实测 C++ 最大点 0.12 s(输入 15 MB,含进程启动)、 Python 最大点 0.04 s(限时 1000 ms)。
  • 空间:去重表 / 计数表最多 2n2n 个长度 mm 的串,O(nm)O(nm),即 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 风险。

总结

  • 把故事翻译成计数:满分人数就是"标准答案"这个串的出现次数,零分人数就是"标准答案的反串" 的出现次数,于是 p>0p > 0 时候选只能是输入里出现恰好 pp 次的串,问题从 2m2^m 的搜索空间 塌缩到 nn 个候选。
  • p=0p = 0 时不要把候选来源搞反:标准答案此时不在输入里,只能由"出现 qq 次的反串取反" 得到,还必须额外验证它本身出现 00 次,否则会漏掉这个隐含条件。
  • p=q=0p = q = 0 是构造而非枚举:把限制写成禁止集合 F=A∪comp(A)F = A \cup \mathrm{comp}(A), 判据"以 PP 为前缀的 FF 中串数 <2m−d< 2^{m-d}"把可行性压缩成一次二分计数, 逐位贪心(先 N 后 Y)即可得到字典序最小解。
  • 充分性来自补集大小:P+NP + \texttt{N} 不可行意味着它下面的 2m−d−12^{m-d-1} 个串全被禁, 那么所有可行解只能走 Y,所以"先试 N"的贪心不会错过解。
  • 先验证再相信 std.cpp:本题 std.cpp 在仓库内 10 个真实测点全部通过 (PASS 10/10),本文的推导与它一致;另外用枚举 2m2^m 个串的独立暴力做了约 3900 组 小规模交叉验证(m⩽6m \leqslant 6、pp 与 qq 遍历 p+q⩽np + q \leqslant n,包含输出 -1 的无解点), main.cpp 与 main.py 两个实现与暴力均无差异。