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.

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

Please read the guidelines before commenting.


There are no comments at the moment.