[NOI Online 2022 普及组] 王国比赛题解

CyaNgw_DyG · 2022-04-01 12:58:53 · 题解

先声明一下：比赛开始的一段时间里第二个样例的 n , m 的位置反了，恰好第一个样例 n , m 相同，不存在顺序问题，导致很多选手在一二个样例过了之后在第三个样例上挨了很久（包括我）。

但后来官方把这个bug改了。

思路：模拟

先用一个数组 a_m 统计每个题目的大臣的答题情况

我这里判断的是如果第 i 个题大臣给的 0 ，那么就 a_i -1 ，

反之，第 i 个题大臣给的 1 ,那么就 a_i+1 。

到了最后如果 a_i>0 ，那么就表示第 i 个题的认为是正确的大臣多，即国王也会认为是正确的。反之，如果 a_i<0 ，则认为是错误的大臣多，国王就会认为是错误的。

见代码：

#include<bits/stdc++.h>
using namespace std;
int rd(){int Q;scanf("%d",&Q);return Q;}//假装快读->压行 
int n=rd(),m=rd(),ans,a[1005];
int v(){return rd()==0?-1:1;};//输入1或者0，如果是0的话就返回-1，是1的话就返回1 
int main(){
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)//这里一定是先m再是n
    a[j]+=v();
    return 0;
} 

接下来输入正确答案，与上面的处理方式一样，如果 b_i=0 ，就 b_i \gets -1 ，如果 b_i=1 ，那么就不用变 。

赋值完了过后，如果 b_i=-1 \land a_i<0 或者 b_i=1 \land a_i>0 ，才能算这道题国王答对。

总结一下，a_i 和 b_i 必须是同号才能算答对，则它们的积是正数，同号相乘得正，保证不会出现 0 。

代码十分简短，不用上述的 b_m 数组。

#include<bits/stdc++.h>
using namespace std;
int rd(){int Q;scanf("%d",&Q);return Q;}//假装快读->压行 
int n=rd(),m=rd(),ans,a[1005];
int v(){return rd()==0?-1:1;};//输入1或者0，如果是0的话就返回-1，是1的话就返回1 
int main(){
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)a[j]+=v();//这里一定是先m再是n
    for(int i=1;i<=n;i++)if(v()*a[i]>0)ans++;//积为正数
    cout<<ans;
    return 0;
}