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.
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"); } }
Comments