7-1 懂的都懂（raicom睿抗机器人CAIP编程技能赛）_睿抗caip编程设计常考算法

7-1 懂的都懂

众所周知，在互联网上有很多话是不好直接说出来的，不过一些模糊的图片仍然能让网友看懂你在说什么。然而对这种言论依然一定要出重拳，所以请你实现一个简单的匹配算法。

现在我们采集了原图的一些特征数据，由 N 个小于 255 的非负整数组成，假设对于给定的若干张由 M_i 个同样小于 255 的非负整数组成的新图的特征数据，每个数据都可以由原图中任意四个不同数据的平均值计算而来，则称新图为原图的相似图片。对于给出的数据，请你判断是不是相似图片。

注意，不同数据指的并非是数据的值不同，而是不能取同一个数据多次。对于两个相同值的数据，如果给出两次，则可以取两次。

输入格式:
输入第一行是两个整数 N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原图的特征数据个数和新图的张数。

接下来一行为 N 个小于 255 的非负整数，表示原图的特征数据。

最后的 K 行，每行第一个数是 M_i (1 ≤ M_i）
​
≤ 200)，表示新图的特征数据个数。然后是 M_i 个小于 255 的非负整数，表示新图的特征数据。

输出格式:
对于每一张新图，如果为相似图片，则在一行中输出 Yes，否则输出 No。

输入样例:

5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11
1
2
3
4
5

输出样例:

Yes
No
Yes
1
2
3

暴力+哈希表

#include<bits/stdc++.h> // 包含STL库
using namespace std;

// 定义全局变量
int yuan[51]; // 存储原图的特征数据
int ans[1000]; // 用于标记所有可能的特征数据平均值
int n,k,m; // 分别表示原图的特征数据个数，新图的张数，新图的特征数据个数

int main()
{
    cin>>n>>k; // 读入原图的特征数据个数和新图的张数
    for(int i=0;i<n;i++)
        cin>>yuan[i]; // 读入原图的特征数据
    
    // 计算原图中任意四个不同数据的平均值，并标记到ans数组中
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                for(int l=k+1;l<n;l++)
                {
                    int sum=yuan[i]+yuan[j]+yuan[k]+yuan[l];
                    ans[sum]=1; // 标记这个和的平均值（乘以4）为可能的特征数据
                }
            }
        }
    }
    
    // 针对每张新图进行检查
    for(int i=0;i<k;i++)
    {
        int m;
        cin>>m; // 读入新图的特征数据个数
        int flag=0; // 标记变量，用于判断新图是否为相似图片
        for(int j=0;j<m;j++)
        {
            int t;
            cin>>t; // 读入新图的一个特征数据
            if(ans[t*4]!=1) // 检查这个特征数据是否能由原图的四个数据的平均值计算而来
                flag=1; // 如果不可以，则将flag标记为1
        }
        if(flag==1) printf("No\n"); // 如果flag为1，说明至少有一个特征数据不匹配，输出“No”
        else        printf("Yes\n"); // 如果所有特征数据都匹配，输出“Yes”
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

踩到的坑

• 这道题对相似的算法应该是4数之和/4，但如果用int会出现浮点数向下取整，导致答案错误，所以我使用了yuan[i]+yuan[j]+yuan[k]+yuan[l]==t*4来判断，避免出现该问题
• 运行超时，我把下面输入新图片的for循环放进了4数之和的for循环中，并一起判断，导致了运行超时