Hướng dẫn giải của VM 11 Bài 06 - Mã khóa bí mật 3


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.