题解 | 阅读理解

阅读理解

https://www.nowcoder.com/practice/199904c4134b48ffbc48032a5373fb7c

噗嗤——这种连幼稚园小朋友都能秒杀的题目，居然还有人需要看题解？真是逊毙了！你们这群杂鱼平时写代码难道都不动脑子的吗？****************************

既然你们求而不得，本天才少女加藤翔子就大发慈悲地给你们写一篇吧。好好盯着看，这可是为了救赎你们那可怜的智商才写的！

📚 杂鱼也能懂的题解：英语老师的阅读理解

🧐 核心槽点：题面是用来骗笨蛋的！

听好了，笨蛋杂鱼们！这道题最坑的地方就在于——题面说单词只由“小写英文字母”组成，但实际的数据里可能藏着各种奇怪的非字母字符。

如果你在处理字符串时想当然地去过滤或者只考虑小写字母，你就等着吃红色的 WA 吧！这种基础中的基础，只有没用的杂鱼才会中招呢，呵呵~

💡 翔子的天才思路

这种题目的本质就是建立一个倒排索引（Inverted Index）。

数据结构：用一个映射表（C++ 里的 map 或 Python 里的 dict）。键（Key）是单词字符串，值（Value）是一个存储短文编号的动态数组（vector 或 list）。
去重处理：同一篇短文里某个单词可能出现好几次。为了不输出重复的编号，每次往数组里加编号前，先看看最后加进去的是不是当前这篇。如果已经加过了，就别再加了，这种逻辑对杂鱼来说应该不难理解吧？
读入技巧：

直接把单词当成字符串读进去就行了。
千万不要管它里面有什么字符，原封不动地存起来就是唯一的标准！

💻 毫无难度的 C++ 代码

这种的复杂度，简直是在浪费本天才的 CPU 时间。

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

// 只有杂鱼才会写出一堆没用的宏定义...
void solve() {
    int n;
    cin>>n;
    map<string ,vector<int>>mp;
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=1;j<=m;j++){
            string s;
            cin>>s;
            if(mp.count(s)){
                if(mp[s].back()!=i){
                    mp[s].push_back(i);
                }
            }else{
                mp[s].push_back(i);
            }
        }
    }

    int q;
    cin>>q;
    while(q--){
        string s;
        cin>>s;
        for(auto id:mp[s]){
            cout<<id<<" ";
        }
        cout<<'\n';// 即使没出现也要输出空行，这都不懂可以回炉重造了
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    // cin >> t;

    while (t--){

        solve();
    }

    return 0;
}

🐍 连笨蛋都能跑通的 Python 代码

Python 的处理速度虽然像杂鱼一样慢，但在写起来确实省事呢。

import sys
import math
import queue
import itertools
import heapq
from collections import deque
from array import array
from bisect import bisect_right

# from dataclasses import dataclass
sys.setrecursionlimit(1145141919)
input = sys.stdin.readline


def read():
    line = sys.stdin.readline()
    if not line:
        return []
    return list(map(int, line.split()))


def readf():
    line = sys.stdin.readline()
    if not line:
        return []
    return list(map(float, line.split()))


mod = 10**9 + 7
inf = 10**18
MOD = 998244353
N = 2 * (10**5) + 5

def solve():
    n = read()[0]
    mp = {}
    for i in range(n):
        a = sys.stdin.readline().split()
        m = int(a[0])
        for j in range(1, m + 1):
            if a[j] not in mp:
                mp[a[j]] = [i + 1]
            else:
                if mp[a[j]][-1] != i + 1:
                    mp[a[j]].append(i + 1)

    q = read()[0]
    for i in range(q):
        s = input().strip()
        if s in mp:
            print(' '.join(map(str, mp[s])))
        else:
            print()# 找不到就输出空行，杂鱼听懂了吗？


def main():
    t = 1
    # t = int(sys.stdin.readline())
    for _ in range(t):
        solve()


if __name__ == "__main__":
    main()