B3912题解

_Leehom_ · 2024-01-13 23:17:19 · 题解

很多人做的是排序啊，其实这一题不用排序也能做。

我们观察到题目中说了这样一句话：

编号为 i 的测试点，标准答案为 A_i 。

这说明什么？说明这题是一个标记题啊。还记得 STL 里面有个啥吗，map 啊！

我们开一个结构体储存每一个测试点里面的答案，也就是结构体里面再开一个数组。然后使用 map 标记编号为 i 的测试点标准答案是啥，然后遍历结构体，如果该测试点里面有一个的标准答案不等于第一个的标准答案，就不加，负责就加，最后遍历一遍 A_i，但注意，这里要访问 map，所以总复杂度还要乘上 A_i，有些大，但通过此题完全没问题，更新最终答案，总复杂度 O( \displaystyle \sum_{i = 1}^{i \leq k} p_i \times k \times \displaystyle \sum_{i = 1}^{i \leq n} \log A_i + \displaystyle \sum_{i = 1}^{i \leq n}\log S_i+N \times \displaystyle \sum_{i = 1}^{i \leq n} \log A_i)，可以通过这道题。

代码

#include <bits/stdc++.h>

#define int long long // 懒，也可能是这个导致的常数 boom！ 

using namespace std;

struct mep{ // 定义结构体 
    int n, m, a[5005]; // 长度，分数，和结构体里的子测试点 
}p[5005];

int tans = -1, n, m, trans, x[100005]; // 编号数组，两个答案 
map<int, int>ans; // 记录每个选项最多获得多少分 
map<int, int>bh; // 记录编号 

signed main(){ // define 之后主函数加 signed 
    cin >> n;
    for(int i = 1; i <= n; i++){ // 输入 
        cin >> p[i].n;
        for(int j = 1; j <= p[i].n; j++){ // 存结构体里 
            cin >> p[i].a[j];
        }
        cin >> p[i].m;
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> x[i];
        bh[i] = x[i]; // 标记编号 i 
    }
    for(int i = 1; i <= n; i++){
        int u = bh[p[i].a[1]]; // u 是为了确定整个测试点答案相同，以及这个答案叫啥 
        for(int j = 2; j <= p[i].n; j++){ // 从 2 开始，因为已经 1 是初始化的 
            if(u != bh[p[i].a[j]]){ // 不相同，说明这个测试点骗不到分了 
                u = 0;
                break;
            }
        }
        ans[u] += p[i].m * !(u == 0); // 如果相同就加起来，不相同就不加，需要表达式的基础 
    }
    for(int i = 1; i <= m; i++){
        if(ans[x[i]] > tans){ // 每次更新选的数字与最终答案，注意，最终要输出两个答案 
            tans = ans[x[i]]; 
            trans = x[i];
        }
    }
    cout << tans << '\n' << trans; // 输出答案 
    return 0; // 好习惯 
}