题解 P8254 【[NOI Online 2022 入门组] 王国比赛（官方数据）】

· · 题解

思路

蒟蒻想到了一种只需要 10^3 的空间的算法，加了快读之后时间可以跑 180ms 。

在输入的时候预处理（快读是后面加上去的）：

int t;
t=Read();
if(t)b[j]++;//"判断值"+1
else b[j]--;//"判断值"-1

我们设答案为对的大臣会将该题的“判断值” +\,1 ，答案为错的大臣会将该题的“判断值” -\,1 ，易得

由于 m 为奇数，所以可以排除“判断值” =0 的情况。

根据这些，我们可以写出如下代码：

if(i==m){
    if(b[j]>=1)b[j]=1;//预测为对
    else b[j]=0;//预测为错
}

在最后一次循环中，读入时便可以将最终预测结果求出。

在输入每题答案的时候，我们在输入时累加结果：

int t;
t=Read();
if(t==b[i])s++;//预测正确答案+1

最后输出 s ，结束。

坑点

本题坑点不多，唯一的坑就是读入的时候，不是习惯性的“先x后y”，而是“先y后x”。

核心代码

for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        int t;
        t=Read();
        if(t)b[j]++;//"判断值"+1
        else b[j]--;//"判断值"-1
        if(i==m){
            if(b[j]>=1)b[j]=1;//预测为对
            else b[j]=0;//预测为错
        }
    }
}
for(int i=1;i<=n;i++){
    int t;
    t=Read();
    if(t==b[i])s++;//预测正确答案+1
}