20220826猿辅导研发第二轮笔试(得分2/3)

好难啊……得分2/3。

T1 题目名称忘记了 100%

搜索引擎会统计各搜索词的词频即出现次数，但是对一些简单词汇会自动被过滤，这些词称为停用词。某搜索引擎为适应词汇形态变化，停用词可能使用"？"代替某个字符。
搜索引擎是不区分大小写的，故IT/It/it会被视为一个词汇。
现在给出这个搜索引擎的搜索词列表和停用词表，请给出词频最高的词出现次数。

输入t，代表t组数据。(t<=10)
每组数据有2行，第一行先输入一个整数n（n<1e5），然后输入n个词。
第二行输入一个k（k<=200），代表停用词数量，然后输入k个词。
对于每组数据，输出出现频次最高的单词。

input:
2
2
12 A tidy tiger tied a tie tighter to tidy her tiny tail
1 a
16 A big black bug bit a big black bear made the big black bear bleed blood
2 b?? b???

output:
2
3

正解好像是Trie树。但是我Trie树只过了10%，不知道哪儿错了。最后用了优化的暴力通过了。

正常暴力：对每个词语遍历所有停用词，看是否能匹配。优化思路：使用一个map存储某长度的停用词，只遍历某长度的词语。

from collections import Counter, defaultdict


def match(s,p):
    for i in range(len(s)):
        if s[i]!=p[i] and p[i]!='?':
            return False
    return True


for _ in range(int(input())):
    ws = list(map(lambda x:x.lower(),input().split()[1:]))
    cc = list(map(lambda x:x.lower(),input().split()[1:]))
    mp=defaultdict(list)
    for c in cc:
        mp[len(c)].append(c)

    ct = Counter()
    for w in ws:
        w = w.lower()
        for c in mp[len(w)]:
            if match(w,c):
                break
        else:
            ct[w] += 1

    print(ct.most_common(1)[0][1])

T2 题目名字忘记了 100%

给定整数K和一个数组A，现需要在A中寻找子数组，使其包含整数K的所有质因子，相同数字要求收集足够个数。请输出满足条件的最小子数组长度（如果没有满足条件的子数组，输出0即可）。

输入T，代表T组数据。（T<=5）
每组数据输入k和n（k<1e6, n<5e5），n为数组长度。然后输入n个整数。(a[i]<2147483647)
对于每组数据，输出满足条件的最小子数组长度

input:
2
20 8
1 2 3 2 6 5 2 1
17 10
1 4 5 7 10 8 7 17 2 8

output:
4
1

暴力获取k的所有质因数。得到一个map，比如k=20，我们可以得到它的质因数序列：{2:2,5:1}。只有相当于在数组中找到最小长度的子数组使得覆盖这个map，同题型原题：leetcode 76，直接滑窗解决即可。

输入数据太大了，用cpp写。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int inf = 0x7fffffff;
const ll INF = 1e18;
#define L 500010
#define mp make_pair
#define pii pair<int,int>
#define mii map<int,int>
int n, m;
int T;
int a[L];
int k;

mii f(int x) {
    mii ans;
    int i = 2;
    while (x > 1) {
        if (x % i == 0) {
            ans[i]++;
            x /= i;
        } else {
            i++;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> k >> n;
        for (int i = 0; i < n; i++)cin >> a[i];

        int ans = n + 1;
        mii mp = f(k);
        int need = mp.size();
        int l = 0;
        for (int r = 0; r < n; r++) {
            if (mp.count(a[r])) {
                mp[a[r]]--;
                if (mp[a[r]] == 0)need--;
            }
            while (need == 0) {
                ans = min(ans, r - l + 1);
                if (mp.count(a[l])) {
                    mp[a[l]]++;
                    if (mp[a[l]] == 1)need++;
                }
                l++;
            }
        }
        if (ans == n + 1)cout << 0 << endl;
        else cout << ans << endl;
    }
}

T3 题目名字忘记了完全不会

一个游乐园，有n个项目。初始有一些积分，可以在任意一个项目开始游玩。当完成一个项目时，会存在若干条道路通往其他项目。
但是游乐园里的道路有一些限制，对于第i条道路，完成项目xi；后可以单向通往项目yi，同时需要至少ai的积分才能选择走这条道路（并不会消耗积分），并且经过后会得到bi积分。
如果想游乐园里无限地玩下去，那么初始分数最少是多少？如果无论如何都无法在游乐园中无限地玩下去，则输出-1。

输入项目书n和道路数m。接下来输入m行，每行分别是x y a b（变量意义看题描述）
n,m<=2000， a,b<=1e9

input:
5 5
4 2 4 0
3 2 3 0
2 4 1 1 
4 3 3 1
5 3 0 2

output:
1

解释：
选择5为起点，初始最少1个积分。
从5到3，需要0积分，得到2分，目前共3积分。
从3到2，需要3积分，得到0分，目前共3积分。
从2到4，需要1积分，得到1积分，目前共4积分：
从4到3，需要3积分，得到1积分，目前共5积分。
随后在3->2->4->3中便可以无限地游玩下去。

没思路，只能看出来是需要在图中找一个环，然后彻底不会了。

#猿辅导##猿辅导笔试##笔试#