P8254 [NOI Online 2022 入门组] 王国比赛

ShanCreeperPro · 2022-04-01 18:49:38 · 题解

P8254 [NOI Online 2022 入门组] 王国比赛

update：

2022.4.5 更新了~~大家好奇~~的 TLE 做法和突然~~心血来潮~~的 Go 语言做法。

这道题有一个坑：

题目中为 n 题 m 人，可是输入数据是 m 行 n 列。

还不理解？看看这个样例就知道了：

以正常的想法，应该是 1 0 1，0 1 1，0 1 0 这三个数据为一题大臣的判断，可是由于是 n 行 m 列，导致了你需要“竖”着看，即 1 0 0，0 1 1，1 1 0 为三道题的判断。

新手容易上当（包括我都蒙了一会）。

TLE 做法：

inline void part2(){
    fore(i,1,m){
        fore(j,1,n){
            if(a[i][j]==0) b[j].x++;
            else if(a[i][j]==1) b[j].y++;
        }   
    }
    fore(i,1,m){
        if(b[i].x>z) pd[i]=0;
        else pd[i]=1;   
    }
    fore(i,1,n){
        if(pd[i]==ans[i]) sum++;
    }
    write(sum); 
}

这个 TLE 的原因非常明显。

所以我们要尽可能把他们放在一起处理。

接着讲正解。

我们可以定义一个二维数组 a 来存每道题大臣的答案，用 b 存正确的答案，并读入，读入时记得外层循环终止条件为 m，内层为 n：

（C++）：

#define fore(i,x,n) for(int i=x;i<=n;i++)
int n,m,a[MAXX][MAXX],b[MAXX];
fore(i,1,m)
    fore(j,1,n)
        a[i][j]=read();
fore(i,1,n) b[i]=read();

（Go）：

var i,j int
fmt.Scan(&n,&m)
for i=1;i<=m;i++{
    for j=1;j<=n;j++{
        fmt.Scan(&a[i][j])
    }
}
for i=1;i<=n;i++{
    fmt.Scan(b[i])
}

定义 x 为单个问题猜测正确的人数，y 为猜测错误的人数，如果 x>y 则猜测为对，否则为错：

（C++）：

fore(j,1,n){
    x=0; y=0;
    fore(i,1,m){
        if(a[i][j]==1) x++;
        else y++;
    }
    if(x>y) sum=1;
    else sum=0;

（Go）：

for j=1;j<=n;j++{
    x=0
    y=0
    for i=1;i<=m;i++{
        if a[i][j]==1{
            x++
        } else {
            y++
        }
        if x>y{
            sum=1
        } else {
            sum=0
        }

（这里记得将外层循环设为 n，内层为 m。）

最后进行判断，如果判断对了 ans 增加 1，最后输出：

（C++）：

    if(sum==b[j]) ans++;
}
write(ans);

（Go）：

        if sum==b[j]{
            ans++
        }
    }
}
fmt.Println(ans);

时间复杂度 O(mn)，可以通过本题。

AC 代码：

（C++）：

#include<bits/stdc++.h>
#define int long long
#define fore(i,x,n) for(int i=x;i<=n;i++)
using namespace std;
const int MAXX=1005;
int n,m,a[MAXX][MAXX],b[MAXX];
int x,y,c=1,sum,ans;
const int mod=1;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read();
    m=read();
    fore(i,1,m)
        fore(j,1,n)
            a[i][j]=read();
    fore(i,1,n) b[i]=read();
    fore(j,1,n){
        x=0; y=0;
        fore(i,1,m){
            if(a[i][j]==1) x++;
            else y++;
        }
        if(x>y) sum=1;
        else sum=0;
        if(sum==b[j]) ans++;
    }
    write(ans);
}

（Go）：

package main
import "fmt"
var n,m,x,y,sum,ans int
var a[1005][1005] int
var b[1005] int
var c=1
func main(){
    var i,j int
    fmt.Scan(&n,&m)
    for i=1;i<=m;i++{
        for j=1;j<=n;j++{
            fmt.Scan(&a[i][j])
        }
    }
    for i=1;i<=n;i++{
        fmt.Scan(b[i])
    }
    for j=1;j<=n;j++{
        x=0
        y=0
        for i=1;i<=m;i++{
            if a[i][j]==1{
                x++
            } else {
                y++
            }
            if x>y{
                sum=1
            } else {
                sum=0
            }
            if sum==b[j]{
                ans++
            }
        }
    }
    fmt.Println(ans);
}

后记：

比赛时脑抽写了个 TLE 的代码气死我了呜呜呜。