首页 > 代码库 > 初赛第五场B

初赛第五场B

2024-10-02 02:07:02   218人阅读

每个 UCloud 用户会构造一个由数字序列组成的秘钥，用于对服务器进行各种操作。作为一家安全可信的云计算平台，秘钥的安全性至关重要。因此，UCloud 每年会对用户的秘钥进行安全性评估，具体的评估方法如下：

首先，定义两个由数字序列组成的秘钥 a 和 b 近似匹配（≈\approx≈） 的关系。a和 b 近似匹配当且仅当同时满足以下两个条件：

  • ∣a∣=∣b∣，即 aaa 串和 bbb 串长度相等。
  • 对于每种数字 c，c 在a中出现的次数等于 c 在b 中出现的次数。

此时，我们就称 a和 b近似匹配，即 a≈b。例如，(1,3,1,1,2)≈(2,1,3,1,1)(1,3,1,1,2)≈(2,1,3,1,1)。

UCloud 每年会收集若干不安全秘钥，这些秘钥组成了不安全秘钥集合 TTT。对于一个秘钥 sss 和集合 TTT 中的秘钥 ttt 来说，它们的相似值定义为：sss 的所有连续子串中与 ttt 近似匹配的个数。相似值越高，说明秘钥 sss 越不安全。对于不安全秘钥集合 TTT 中的每个秘钥 ttt，你需要输出它和秘钥 sss 的相似值，用来对用户秘钥的安全性进行分析。

输入格式

第一行包含一个正整数 n，表示 s 串的长度。

第二行包含 n 个正整数 s1,s2,...,sn(1≤si≤n)1??,s?2??,...,s?n??(1≤s?i??≤n)，表示 sss 串。

接下来一行包含一个正整数 m，表示询问的个数。

接下来 m个部分：

每个部分第一行包含一个正整数 k(1≤k≤n)，表示每个 t 串的长度。

每个部分第二行包含 k 个正整数 t1,t2,...,tk(1≤ti≤n)?1??,t?2??,...,t?k??(1≤t?i??≤n)，表示 TTT 中的一个串 ttt。

输入数据保证 TT中所有串长度之和不超过 200000。

对于简单版本：1≤n,m≤1001

对于中等版本：1≤n≤50000,1≤m≤5001

对于困难版本：1≤n≤50000,1≤m≤100000

输出格式

输出 m 行，每行一个整数，即与 T 中每个串 t 近似匹配的 s 的子串数量。

样例解释

对于第一个询问，(3,2,1,3)≈(2,3,1,3)(3,2,1,3)≈(3,1,3,2)(3,2,1,3)；

对于第二个询问，(1,3)≈(3,1),(1,3)≈(1,3)；

对于第三个询问，(3,2)≈(2,3),(3,2)≈(3,2)。

样例输入

5
2 3 1 3 2
3
4
3 2 1 3
2
1 3
2
3 2

样例输出

2
2
2

思路：B暴力就可以了，貌似我又写崩了
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int c[103][103];
 4 int d[103];
 5 map<int ,int >a,b;
 6 int main(){
 7     int n,m;
 8     scanf("%d",&n);
 9     int x;
10     int MMax=0;
11     for(int i=1;i<=n;i++){
12        scanf("%d",&d[i]);
13        MMax=max(MMax,d[i]);
14     }
15     int q;
16     scanf("%d",&q);
17     for(int ii=1;ii<=q;ii++){
18         int Max=MMax;
19         scanf("%d",&m);
20         a.clear();b.clear();
21         for(int i=1;i<=m;i++){
22             scanf("%d",&x);
23             b[x]++;
24             Max=max(Max,x);
25         }
26         int sum=0;
27         int t;
28         for(int i=1;i<=m;i++) a[d[i]]++;
29         for(int i=m;i<=n;i++){
30             if(i!=m) {
31                     a[d[i]]++;
32                     a[d[i-m]]--;
33             }
34             t=0;
35             for(int j=0;j<=Max;j++){
36                 if(a[j]!=b[j]){
37                     t=1;break;
38                 }
39             }
40             if(!t) sum++;
41         }
42         printf("%d\n",sum);
43     }
44     return 0;
45 }

 

初赛第五场B


联系
我们