[Algo Beat Contest 017 A] 串哈希

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

按 kirai、daishuki、shuki 的优先级检查子串并顺序模拟气压变化。

OJ: luogu

题目 ID: P17232

难度:入门

标签:字符串模拟

日期: 2026-08-11 07:37

目录

  1. 形式化题目
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定一个初始整数和一个字符串序列。依次处理每个字符串时，根据它是否包含若干固定子串，按指定优先级改变当前整数。全部处理后，根据最终整数是否为正输出数值差或固定字符串。

思路

这题的核心是“规则优先级”，不是哈希。每个字符串只需要判断是否包含三个固定子串：kirai、daishuki、shuki。

判断顺序必须和题面优先级一致：

  1. 先判断 kirai。一旦出现，就忽略另外两条加分规则。
  2. 再判断 daishuki。因为 daishuki 自身包含 shuki，所以它必须排在 shuki 前面。
  3. 最后判断 shuki。
  4. 都不包含时，气压减一。

遇到 kirai 时还要注意当前气压的符号：若当前气压非负，就把它设为 0；若已经为负，则保持不变。

处理完所有字符串后，设最终气压为 tt。若 t>0t>0，输出 t−st-s；否则输出 shuki。

代码

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-08-11 07:37
 * update_at: 2026-08-11 11:03
 */
#include <bits/stdc++.h>
using namespace std;

int n;
long long s, now_value;

bool has_substr(const string &word, const string &pat) {
    return word.find(pat) != string::npos;
}

bool has_substr2(const string &word, const string &pat) {
    if (pat.size() > word.size()) return false;

    // 手动枚举起点，再逐字符比较，等价于判断 pat 是否为 word 的连续子串。
    for (int i = 0; i + (int)pat.size() <= (int)word.size(); i++) {
        bool same = true;
        for (int j = 0; j < (int)pat.size(); j++) {
            if (word[i + j] != pat[j]) {
                same = false;
                break;
            }
        }
        if (same) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    now_value = s;
    for (int i = 1; i <= n; i++) {
        string word;
        cin >> word;

        // 题面规则有优先级：kirai 最高，daishuki 高于 shuki。
        if (has_substr2(word, "kirai")) {
            if (now_value >= 0) now_value = 0;
        }
        else if (has_substr2(word, "daishuki")) {
            now_value += 2;
        }
        else if (has_substr2(word, "shuki")) {
            now_value += 1;
        }
        else {
            now_value -= 1;
        }
    }

    if (now_value > 0) cout << now_value - s << '\n';
    else cout << "shuki\n";
    return 0;
}

复杂度

设所有字符串长度总和为 LL。每个字符串做常数次固定模式串查找，时间复杂度为 O(L)O(L)。

除读入字符串外，只维护当前气压，空间复杂度为 O(1)O(1)。

总结

这题容易错在 daishuki 包含 shuki，以及 kirai 的优先级最高。只要严格按题面顺序模拟，每一步气压变化就和定义一致。