题解：P14782 [NERC 2025] Alphabet City

shy__lzy · 2025-12-18 20:18:09 · 题解

P14782 题解

思路

对每个字符串 \ell，计算能用其他字符串的 m 份字母拼出 k 份其他字符串和 1 份 s_\ell 的最大 k。

方法：

对每个字母 c：

• 设 A = s_\ell 中 c 的数量，B = 其他字符串中 c 的总数
• 若 B=0 但 A>0，则不可行（输出 -1）
• 否则，计算 t = \lceil A/B \rceil，更新 k \le m - t

取所有字母限制的最小值即为答案。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, m;
string s[N];
int cnt[N][26];
int sum[26];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin >> n >> m;
    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < n; i++) {
        cin >> s[i];
        memset(cnt[i], 0, sizeof(cnt[i]));

        // 统计当前字符串的字母
        for (char ch : s[i]) {
            cnt[i][ch - 'A']++;
        }

        // 累加到总数
        for (int c = 0; c < 26; c++) {
            sum[c] += cnt[i][c];
        }
    }

    for (int l = 0; l < n; l++) {
        int ans = m;
        bool ok = true;

        for (int c = 0; c < 26; c++) {
            int A = cnt[l][c];
            int B = sum[c] - A;

            if (B == 0 && A > 0) {
                ok = false;
                break;
            }
            if (B > 0) {
                int t = (A + B - 1) / B;
                ans = min(ans, m - t);
            }
        }

        if (ok && ans >= 0) {
            cout << ans << " ";
        } else {
            cout << -1 << " ";
        }
    }

    cout << endl;
    return 0;
}