90分的你距离一百分差了什么(测试点#1WA的进来)

P2704 [NOI2001] 炮兵阵地

羊摆摇 @ 2022-10-13 13:34:18

省流:得用cin

以下是我的90分代码和100分代码:

90分code:

#include <bits/stdc++.h>
using namespace std;

#define LL long long
typedef const int Int;

Int N=105,M=150;

int B[N];

int dp[N][M][M];

int n,m;

int sta[M],cnt[M],siz;

void dfs(int i,int stat,int cont){
    if(i>=m){
        sta[++siz]=stat,cnt[siz]=cont;
        return;
    }
    dfs(i+1,stat,cont);
    dfs(i+3,stat+(1<<i),cont+1);
}

bool checkPH(int k,int r){
    if(sta[k]&B[r])return false;
    return true;
}

bool check(int a,int b){
    if(sta[a]&sta[b])return false;
    return true;
}

int main(){
    char c;
    scanf("%d%d",&n,&m);
    for(int k=1;k<=n;k++){
        for(int k1=0;k1<m;k1++){
            c=getchar();
            if(c=='\n')c=getchar();
            if(c=='H'){
                B[k]+=(1<<k1);
//              cout<<k1<<endl;
            }
        }
    }
    dfs(0,0,0);
//  cout<<siz<<endl;
//  for(int k=1;k<=siz;k++){
//      cout<<sta[k]<<" "<<cnt[k]<<endl;
//  }
//  cout<<endl;
//  for(int k=0;k<=n;k++)cout<<B[k]<<endl;
    for(int k=1;k<=n;k++){
        for(int k1=1;k1<=siz;k1++){
            for(int k2=1;k2<=siz;k2++){
                if(!check(k1,k2)||!checkPH(k1,k)||!checkPH(k2,k-1))continue;
                for(int k3=1;k3<=siz;k3++){
                    if(!check(k1,k3))continue;
                    dp[k][k1][k2]=max(dp[k][k1][k2],dp[k-1][k2][k3]+cnt[k1]);
                }
            }
        }
    }
//  return 0;
    int ans=INT_MIN;
    for(int k=1;k<=siz;k++){
        for(int k1=1;k1<=siz;k1++)ans=max(ans,dp[n][k][k1]);
    }
    printf("%d",ans);
    return 0;
}

100分code:

#include <bits/stdc++.h>
using namespace std;

#define LL long long
typedef const int Int;

Int N=105,M=150;

int B[N];

int dp[N][M][M];

int n,m;

int sta[M],cnt[M],siz;

void dfs(int i,int stat,int cont){
    if(i>=m){
        sta[++siz]=stat,cnt[siz]=cont;
        return;
    }
    dfs(i+1,stat,cont);
    dfs(i+3,stat+(1<<i),cont+1);
}

bool checkPH(int k,int r){
    if(sta[k]&B[r])return false;
    return true;
}

bool check(int a,int b){
    if(sta[a]&sta[b])return false;
    return true;
}

int main(){
    char c;
    scanf("%d%d",&n,&m);
    for(int k=1;k<=n;k++){
        for(int k1=0;k1<m;k1++){
            cin>>c;
            if(c=='\n')cin>>c;
            if(c=='H'){
                B[k]+=(1<<k1);
//              cout<<k1<<endl;
            }
        }
    }
    dfs(0,0,0);
//  cout<<siz<<endl;
//  for(int k=1;k<=siz;k++){
//      cout<<sta[k]<<" "<<cnt[k]<<endl;
//  }
//  cout<<endl;
//  for(int k=0;k<=n;k++)cout<<B[k]<<endl;
    for(int k=1;k<=n;k++){
        for(int k1=1;k1<=siz;k1++){
            for(int k2=1;k2<=siz;k2++){
                if(!check(k1,k2)||!checkPH(k1,k)||!checkPH(k2,k-1))continue;
                for(int k3=1;k3<=siz;k3++){
                    if(!check(k1,k3))continue;
                    dp[k][k1][k2]=max(dp[k][k1][k2],dp[k-1][k2][k3]+cnt[k1]);
                }
            }
        }
    }
//  return 0;
    int ans=INT_MIN;
    for(int k=1;k<=siz;k++){
        for(int k1=1;k1<=siz;k1++)ans=max(ans,dp[n][k][k1]);
    }
    printf("%d",ans);
    return 0;
}

显而易见,除了getchar输入改为cin输入外几近没有任何区别-

但是!就是这一个小小的区别,我调试了一个中午QAQ(后来是翻讨论区才知道要改的)

下载了测试点,#1就是样例,大家肯定是样例过了才敢交的,可是用getchar#1就会莫名返回一个7,而不是本地输出的6。

想问一下有没有人知道为什么这道题cin就能过,而getchar就会使输出值改变


by 5k_sync_closer @ 2022-10-13 13:53:22

@羊摆摇 没用 cin,过了啊

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, c;long long q, g[150], s[350], w[350], f[150][350][350];char v;
void D(int p, int q, int x)
{
    if(x > m) {s[++c] = p;w[c] = q;return;}
    D(p, q, x + 1);D(p ^ (1 << x), q + 1, x + 3);
}
bool C(int x, int y) {return !(s[x] & s[y]);}
bool P(int x, int l) {return !(s[x] & g[l]);}
int main()
{
    scanf("%d%d", &n, &m);D(0, 0, 1);
    for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j)
    {scanf(" %c", &v);if(v == 'H') g[i] ^= 1 << j;}
    for(int i = 1;i <= c;++i) if(P(i, 1)) f[1][i][0] = w[i];
    for(int i = 1;i <= c;++i) if(P(i, 2)) for(int j = 1;j
    <= c;++j) if(C(i, j) && P(j, 1)) f[2][i][j] = w[i] + w[j];
    for(int i = 3;i <= n;++i) for(int j = 1;j <= c;++j) if(P(j, i))
    for(int x = 1;x <= c;++x) if(C(j, x) && P(x, i - 1))
    for(int y = 1;y <= c;++y) if(C(j, y) && C(x, y) && P(y, i - 2))
    f[i][j][x] = max(f[i][j][x], f[i - 1][x][y] + w[j]);
    for(int i = 1;i <= c;++i) for(int j = 0;j <= c;++j) q = max(q, f[n][i][j]);
    return printf("%lld", q), 0;
}

省流:换行符


by qwasd @ 2022-10-13 13:55:35

省流:\r\n


by 羊摆摇 @ 2022-10-13 17:35:05

@5k_sync_closer 谢谢说明 ,您这压行是真的强


|