[语言月赛 202312] 打表过样例
题目背景
众所周知，一名负责人的出题人，不应当让如下的打表程序获得过多的分数。
#include<iostream>
int main() {
std::cout << "Specific Value\n";
}
这个程序的功能是，输出一个特定的内容，以尝试通过一些测试点而获得分数。
经典的例子是：https://www.luogu.com.cn/problem/P8819，输出无解可以获得 45 分的成绩。
题目描述
很不幸，你遇到了不负责任的出题人。
在某道试题里，共有 \(N\) 个测试点，组成了 \(k\) 个 Subtask，第 \(i\) 个 Subtask 包含 \(p_i\) 个测试点，第 \(j\) 个测试点的编号为 \(w_{i,j}\)。请注意，一个测试点可能属于多个 Subtask。
Subtask
每个 Subtask 包含多个测试点和一个分值，当且仅当通过全部这些测试点时，才能获得这个 Subtask 的分值。一道题目的得分为通过的所有 Subtask 分值之和。
这是一道输出仅有一个数的题目，编号为 \(i\) 的测试点，标准答案为 \(A_i\)。
很不幸，由于命题人不负责任，\(A_i\) 中出现了大量重复，让打表选手有了可乘之机。
现在，你通过某种手段获得了全部的数据，请问输出哪个数，可以得到最高的分数？最高的分数是多少？
如果有多个数均可得到最高的分数，你只需要任意给出一个。
输入格式
输入共 \(k+3\) 行。
输入的第一行为一个正整数 \(k\)。
接下来 \(k\) 行：
- 第 \(i\) 行的第一个数为 \(p_i\)，代表第 \(i\) 个 Subtask 包含的测试点数目。
- 接下来 \(p_i\) 个数，第 \(j\) 个代表测试点编号 \(w_{i,j}\)。
- 最后一个数为 \(S_i\)，代表这个 Subtask 的分值。
输入的第 \(k+2\) 行为一个正整数 \(N\)。
输入的第 \(k+3\) 行为 \(N\) 个非负整数，第 \(i\) 个代表 \(A_i\)。
输出格式
输出两行，每行一个整数。
第一行表示获得的最大分值。
第二行表示输出的数。
如果有多个数可以取到相同的最大分值，任意输出一个即可。
样例 #1
样例输入 #1
2
3 1 2 3 5
3 4 5 6 7
6
4 4 4 5 5 5
样例输出 #1
7
5
提示
数据规模与约定
- 对于 \(30\%\) 的测试数据，\(1 \le N \le 100\)，\(1 \le k,p_i \le 10\)，\(1 \le A_i \le 100\)。
- 对于 \(100\%\) 的测试数据，\(1 \le N \le 10^5\)，\(1 \le k,p_i \le 5000\)，\(1 \le w_{i,j} \le N\)，\(1 \le S_i \le 10^9\)，\(1 \leq A _ i \leq 10 ^ 9\)。
思路
模拟就可以解决这个问题，但是需要注意一些特殊地方
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int s[N];
int f[N];
int w[N];
void solve(){
int k;
cin>>k;
std::vector<int> a[k+1];
for(int i=1;i<=k;i++){
int p;
cin>>p;
for(int j=1;j<=p;j++){
int x;
cin>>x;
a[i].push_back(x);
}
cin>>s[i];//这个包的分数
}
int n;
cin>>n;
std::map<int, int> mp;
for(int i=1;i<=n;i++){
int x;
cin>>x;
mp[i]=x;
}
for(int i=1;i<=k;i++){
int c=mp[a[i][0]];
int j;
for(j=1;j<a[i].size();j++){
if(mp[a[i][j]]!=c){
break;
}
}
if(j>=a[i].size()){
w[i]=c;//第i个包的答案
}
else{
w[i]=-1;
}
}
for(int i=1;i<=k;i++){//f数组
int x=w[i];
if(x<0){
continue;//这个是不做求和的
}
for(int j=i;j<=k;j++){
if(i!=j){
if(w[j]==x){
s[i]+=s[j];
}
}
}
}
int maxn=-1;
int flag=-1;
for(int i=1;i<=k;i++){
if(w[i]!=-1){
if(maxn<s[i]){
maxn=s[i];
flag=w[i];
}
}
}
cout<<maxn<<endl;
cout<<flag<<endl;
return ;
}
signed main(){
int t;
t = 1;
while (t--)
{
solve();
}
return 0;
}