Editorial for VOI 11 Bài 5 - Trò chơi chẵn lẻ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
int test,n,i,j,x,row[555][555],col[555][555],f[555][555];
int main()
{
 cin >> test;
 while (test--)
 {
  cin >> n;
  fr(i,1,n)
   fr(j,1,n)
   {
    scanf("%d",&x);
    x%=2;
    row[i][j]=(row[i][j-1]+x)%2;
    col[j][i]=(col[j][i-1]+x)%2;
   }
  fr(i,1,n)
   fr(j,1,n)
   {
    f[i][j]=0;
    if (!f[i-1][j] && !row[i][j]) f[i][j]=1;
    if (!f[i][j-1] && !col[j][i]) f[i][j]=1;
   } 
  if (f[n][n]) cout << "YES" << endl; else cout << "NO" << endl;
 }
}

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 505

int sr[N][N], sc[N][N], n, k;
bool f[N][N];

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    scanf("%d",&k); int t;
    while(k--) {
        scanf("%d",&n);
        fo(i,1,n) fo(j,1,n) {
            scanf("%d",&t);
            sr[i][j] = (sr[i][j-1] + t)&1;
            sc[j][i] = (sc[j][i-1] + t)&1;
        }
        fo(i,1,n) fo(j,1,n) {
            f[i][j] = (sr[i][j] == 0 ? !f[i-1][j] : 0)
                || (sc[j][i] == 0 ? !f[i][j-1] : 0);
            //f[i][j] = (sr[i][j] == 0 && ((i > 1 && sr[i-1][j] == 0) ? f[i-2][j] : 1) && (sc[j][i-1] == 0 ? f[i-1][j-1] : 1)) || (sc[j][i] == 0 && ((j > 1 && sc[j-1][i] == 0) ? f[i][j-2] : 1) && (sr[i][j-1] == 0 ? f[i-1][j-1] : 1));
        }
        printf(f[n][n] ? "YES\n" : "NO\n");
    }
    return 0;
}

Code mẫu của ladpro98

program parigame;
uses    math;
const   fi='';
        maxN=555;
var     a,sx,sy,win:array[0..maxN,0..maxN] of longint;
        n,t,tt:longint;
        inp:text;

procedure Enter;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,t);
end;

procedure input;
var     i,j:longint;
begin
        readln(inp,n);
        for i:=1 to n do
        for j:=1 to n do
        read(inp,a[i,j]);

end;

procedure dp;
var     i,j:longint;
begin
        for i:=1 to n do
        for j:=1 to n do
        begin
                sx[i,j]:=(sx[i-1,j]+a[i,j]) and 1;
                sy[i,j]:=(sy[i,j-1]+a[i,j]) and 1;
                win[i,j]:=0;
                if sx[i,j]=0 then win[i,j]:=max(win[i,j],win[i,j-1] xor 1);
                if sy[i,j]=0 then win[i,j]:=max(win[i,j],win[i-1,j] xor 1);
        end;
end;

procedure output;
begin
        if win[n,n]=1 then
        writeln('YES')
        else
        writeln('NO');
end;

begin
        Enter;
        for tt:=1 to t do
        begin
                input;
                dp;
                output;
        end;
end.

Code mẫu của RR

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

int a[502][502];
bool ret[502][502];
int T,n;

bool even(int x1,int y1,int x2,int y2)
{
    int sum = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
    sum %= 2;  sum = (sum + 2) % 2;
    return (sum == 0);
}

int main()
{
    //freopen("PARIGAME.INP","r",stdin);
    //freopen("PARIGAME.OUT","w",stdout);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        memset(a,0,sizeof(a));
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
          {
                int x;  scanf("%d", &x);  a[i][j] = (x % 2);
            }
        for (int i = 2; i <= n; i++)
          for (int j = 1; j <= n; j++) a[i][j] += a[i - 1][j];
        for (int j = 2; j <= n; j++)
          for (int i = 1; i <= n; i++) a[i][j] += a[i][j - 1];

        memset(ret,false,sizeof(ret));
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
          {
                if (even(i,1,i,j) && !ret[i - 1][j]) ret[i][j] = true;
                if (even(1,j,i,j) && !ret[i][j - 1]) ret[i][j] = true;
            }
        if (ret[n][n]) printf("YES\n"); else printf("NO\n");
    }
}

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>

int a[501][501],d[501][501],n;
bool f1[501][501],f2[501][501],F[501][501];

int main()
{
    //freopen("PARIGAME.in","r",stdin);
    int test;
    scanf("%d",&test);
    for(int ii = 1;ii<=test;ii++)
    {
         scanf("%d",&n);
         for(int i = 1;i<=n;i++)
             d[0][i] = 0;
         for(int i = 1;i<=n;i++)
         {
             int k = 0;
             for(int j = 1;j<=n;j++)
             {
                 scanf("%d",&a[i][j]);
                 a[i][j] = a[i][j]%2;
                 d[i][j] = (d[i-1][j] + a[i][j])%2;
                 k = (k+a[i][j])%2;
                 if(d[i][j]== 0) f1[i][j] = true;
                 else f1[i][j] = false;
                 if(k == 0) f2[i][j] = true;
                 else f2[i][j] = false;
             }
         }
         for(int i = 0;i<=n;i++)
         {
              F[i][0] = false;
              F[0][i] = false;
         }
         for(int i = 1;i<=n;i++)
             for(int j = 1;j<=n;j++)
             {
                 F[i][j] = false;
                 if(f1[i][j] && !F[i][j-1]) F[i][j] = true;
                 if(f2[i][j] && !F[i-1][j]) F[i][j] = true;
                // printf("%d %d %d\n",i,j,F[i][j]);
             }
         if(F[n][n]) printf("YES\n");
         else printf("NO\n");

    }
    //getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

int a[502][502];
bool ret[502][502];
int T,n;

bool even(int x1,int y1,int x2,int y2)
{
    int sum = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
    sum %= 2;  sum = (sum + 2) % 2;
    return (sum == 0);
}

int main()
{
//  freopen("PARIGAME.INP","r",stdin);
//  freopen("PARIGAME.OUT","w",stdout);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        memset(a,0,sizeof(a));
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
          {
                int x;  scanf("%d", &x);  a[i][j] = (x % 2);
            }
        for (int i = 2; i <= n; i++)
          for (int j = 1; j <= n; j++) a[i][j] += a[i - 1][j];
        for (int j = 2; j <= n; j++)
          for (int i = 1; i <= n; i++) a[i][j] += a[i][j - 1];

        memset(ret,false,sizeof(ret));
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
          {
                if (even(i,1,i,j) && !ret[i - 1][j]) ret[i][j] = true;
                if (even(1,j,i,j) && !ret[i][j - 1]) ret[i][j] = true;
            }
        if (ret[n][n]) printf("YES\n"); else printf("NO\n");
    }
}

Code mẫu của skyvn97



Comments

Please read the guidelines before commenting.


There are no comments at the moment.