Editorial for VM 11 Bài 06 - Mã khóa bí mật 3
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 <cstdio> #include <algorithm> #include <vector> using namespace std; int m,n,a[33][33]; vector <int> row[33],col[33]; int invalidRow(int x) { vector <int> b; int cnt=0; for (int y=1;y<=n+1;y++) if (a[x][y]) cnt++; else if (cnt) b.push_back(cnt), cnt=0; if (b.size()!=row[x].size()) return 1; for (int i=0;i<int(b.size());i++) if (b[i]!=row[x][i]) return 1; return 0; } int invalidCol(int y) { vector <int> b; int cnt=0; for (int x=0;x<=m+1;x++) if (a[x][y]) cnt++; else if (cnt) b.push_back(cnt), cnt=0; if (b.size()!=col[y].size()) return 1; for (int i=0;i<int(b.size());i++) if (b[i]!=col[y][i]) return 1; return 0; } int valid() { for (int i=1;i<=m;i++) if (invalidRow(i)) return 0; for (int i=1;i<=n;i++) if (invalidCol(i)) return 0; return 1; } int main() { int x,y,t; cin >> m >> n; for (int i=1;i<=m;i++) { row[i].clear(); cin >> y; while (y--) cin >> x, row[i].push_back(x); } for (int i=1;i<=n;i++) { col[i].clear(); cin >> y; while (y--) cin >> x, col[i].push_back(x); } cin >> t; while (t--) { for (int i=1;i<=m;i++) { string s; cin >> s; for (int j=1;j<=n;j++) a[i][j]=(s[j-1]=='1'); } cout << (valid()?"YES":"NO") << endl; } return 0; }
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; typedef long long LL; #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 35 vvi con; //constraint int m, n; char a[35][35], b[35][35]; void analysis(char a[35][35], int m, int n, vvi &ana) { rep(i,m) { ana.pb(vi()); for(char * st = strchr(a[i],'1'); st != NULL;) { char * en = strchr(st,'0'); if(en != NULL) { ana.back().pb(en-st); st = strchr(en,'1'); } else { ana.back().pb(n-(st-a[i])); st = NULL; } } } } bool ok() { vvi ana; //analysis analysis(a, m, n, ana); rep(i,m) rep(j,n) b[j][i] = a[i][j]; analysis(b, n, m, ana); return ana == con; } int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif scanf("%d%d",&m,&n); rep(i,m+n) { con.pb(vi()); int k; scanf("%d",&k); rep(j,k) { int x; scanf("%d",&x); con.back().pb(x); } } int t; scanf("%d",&t); while(t--) { rep(i,m) scanf("%s",a[i]); printf(ok() ? "YES\n" : "NO\n"); } return 0; }
Code mẫu của RR
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #include <sstream> #include <iomanip> using namespace std; const int MAXN = 100; int nRow, nCol; vector<int> row[MAXN], col[MAXN]; string solution[MAXN]; bool equal(vector<int> a, vector<int> b) { if (a.size() != b.size()) return false; for(int i = 0; i < a.size(); i++) { if (a[i] != b[i]) return false; } return true; } int get() { for(int i = 1; i <= nRow; i++) if (solution[i].length() != nCol + 1) return 0; for(int i = 1; i <= nRow; i++) { for(int j = 1; j <= nCol; j++) if (solution[i][j] < '0' || solution[i][j] > '1') return 0; } int res = 0; for(int i = 1; i <= nRow; i++) { string now = solution[i]; for(int x = 0; x < now.length(); x++) if (now[x] == '0') now[x] = ' '; istringstream sin(now); vector<int> cur; string u; while (sin >> u) { cur.push_back(u.length()); } if (equal(cur, row[i])) res++; } for(int j = 1; j <= nCol; j++) { string now = ""; for(int i = 1; i <= nRow; i++) now = now + solution[i][j]; for(int x = 0; x < now.length(); x++) if (now[x] == '0') now[x] = ' '; istringstream sin(now); vector<int> cur; string u; while (sin >> u) { cur.push_back(u.length()); } if (equal(cur, col[j])) res++; } return (res == nRow + nCol); } void read_input() { cin >> nRow >> nCol; int sumRow = 0, sumCol = 0; for(int i = 1; i <= nRow; i++) { int k; cin >> k; while (k--) { int u; cin >> u; row[i].push_back(u); sumRow += u; } } for(int j = 1; j <= nCol; j++) { int k; cin >> k; while (k--) { int u; cin >> u; col[j].push_back(u); sumCol += u; } } } bool read_output() { for(int i = 1; i <= nRow; i++) { string tmp; cin >> tmp; solution[i] = " "; for(int x = 0; x < tmp.length(); x++) { if (tmp[x] != '0' && tmp[x] != '1') { return false; } solution[i] += tmp[x]; } } return get(); } int main() { read_input(); int t; cin >> t; while (t--) { if (read_output()) puts("YES"); else puts("NO"); } return 0; }
Code mẫu của hieult
#include <stdio.h> #include <algorithm> #include <cstring> #include <vector> #include <cmath> //#include <conio.h> //double const PI=4*atan(1); int a[33],b[33],A[33][33],B[33][33],m,n,test,x[33],so; bool check; char s[33][33]; using namespace std; int main(){ // freopen("MAKHOA3.in","r",stdin); // freopen("A.out","w",stdout); scanf("%d %d",&m,&n); for(int i = 1;i<=m;i++){ scanf("%d",&a[i]); for(int j = 1;j<=a[i];j++) scanf("%d",&A[i][j]); } for(int i = 1;i<=n;i++){ scanf("%d",&b[i]); for(int j = 1;j<=b[i];j++) scanf("%d",&B[i][j]); } scanf("%d",&test); for(int itest = 1;itest<=test;itest++){ check = true; for(int i = 0;i<m;i++){ scanf("%s",s[i]); // printf("%s\n",s[i]); so = 0; //printf("***%d*** %d\n",s[0][3],s[i][0]=='1'); if(s[i][0]=='1'){ // printf("??\n"); x[++so]=1; } for(int j = 1;j<n;j++){ if(s[i][j]=='1'){ if(s[i][j-1]=='0') x[++so] = 1; else x[so]++; } } if(so!=a[i+1]) { check = false;} else{ for(int j = 1;j<=so;j++) if(A[i+1][j]!=x[j]){ check = false; } } } for(int i = 0;i<n;i++){ so = 0; if(s[0][i]=='1'){ x[++so]=1; } for(int j = 1;j<m;j++){ if(s[j][i]=='1'){ if(s[j-1][i]=='0') x[++so] = 1; else x[so]++; } } if(so!=b[i+1]){ check = false;} else{ for(int j = 1;j<=so;j++) if(B[i+1][j]!=x[j]){ check = false; } } } if(check) printf("YES\n"); else printf("NO\n"); } // getch(); }
Comments