谁会啊

走不出的回忆

2025-06-11 14:41:11

发布于：浙江

13阅读

0回复

0点赞

重合字符串
时间限制：1000ms
内存限制：128MB

Yuilice给出 N 个长度为 6 的字符串，每个字符串由数字组成，其中S
i

代表其中第i个字符串。

你现在另外还拥有 M 个长度为 3 的字符串，每个字符串都由数字组成。其中T
i

代表其中第i个字符串。

现在你需要求出 S
1

,S
2

,…,S
N

中有多少个字符串最后三个字符与 T
1

,T
2

,…,T
M

中的一个或多个重合。

数据约束
1≤N,M≤1000
N 和 M 都是整数。
S
i

是长度为 6 的字符串，由数字组成，适用于所有 i=1,2,…,N 。
T
j

(1≤j≤M) 必然为长度为 3 的由数字组成的字符串。
输入格式
输入内容由标准输入法提供，格式如下

N M
S
1

S
2

⋮
S
N

T
1

T
2

⋮
T
M

输出格式
打印一个整数代表答案

样例组
输入#1
复制
3 3
142857
004159
071028
159
287
857
输出#1
复制
2
输入#2
复制
5 4
235983
109467
823476
592801
000333
333
108
467
983
输出#2
复制
3
输入#3
复制
4 4
000000
123456
987111
000000
000
111
999
111
输出#3
复制
3
提示说明
样例一解释
S
1

的最后三个字符是 857，与 T
3

重合。
S
2

的最后三个字符是 159，与 T
1

重合。
S
3

的最后三个字符是 028，与 T
1

、 T
2

或 T
3

不重合。

因此，答案为 2 。

有帮助，赞一个

去预览

0/2000

全部评论 6

复仇者_帅童
看到大家都写了，我也口糊一个吧（
用哈希表（就是桶）记录数 $i$ 有没有出现在 $T_i$ 内（hash[t[i]] = 1）
然后再枚举 $S_i$ ，只要看 $S_i$ 后三位有没有在哈希表里出现过，即 hash[s[i] % 1000] 的值是不是 1 即可。时间复杂度 $O(N+M)$

2天前来自广东
0
亚洲卷王 AK IOI
set<string>存一下Ti是否出现过，然后枚举所有S，截取后三个字符g，使用set.count(g)==1判断是否在set里就行。时间 $O((n+m) \log m)$

3天前来自北京
0

复仇者_༺ཌༀ皴·泰ༀད༻

我的代码：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    vector<string> T(M);
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
    }
    int count = 0;
    for (int i = 0; i < N; ++i) {
        string lastThree = S[i].substr(3, 3);
        for (int j = 0; j < M; ++j) {
            if (lastThree == T[j]) {
                count++;
                break;
            }
        }
    }
    cout << count;
    return 0;
}

3天前来自浙江

复仇者_༺ཌༀ皴·泰ༀད༻
回复复仇者_༺ཌༀ皴·泰ༀད༻
虽是AI写的，但也不是正规题目。

3天前来自浙江
0

椰蓉莉
nb

3天前来自浙江
0
椰蓉莉
给伞哥你真敢啊

3天前来自浙江
0
椰蓉莉
哇塞

3天前来自浙江
0

全部评论 6

我的代码：

热门讨论