每日一题5.30

XinyuLin

2024icpc圣彼得堡St. Petersburg
试试国外的

银牌题Nhttps://qoj.ac/contest/1696/problem/8794

Fengyj

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define int long long
mt19937_64 rnd(1);
void solve(){
    int n,m;
    cin>>n>>m;
    int sz = max(n, m);
    vector<vector<int>> a(sz, vector<int>(sz));
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            char k;
            cin >> k;
            a[i][j] = k - '0';
        }
    }
    
    vector<vector<int>> b(m, vector<int>(m));
    if(n<m){//encoder 0~n-1 n~m-4 m-3~m-1
        //主体，还原
        // for (int i = 0; i < n;i++){
        //     for (int j = 0; j < m;i++){
        //         b[i][j] = a[i][j];
        //     }
        // }
        //比特点，连比特
        int num = m - n - 3;
        for (int i = 0; i < n;i++){
            for (int j = 0; j < num;j++){
                if(i>>j&1){
                    a[i][j + n] = a[j + n][i] = 1;
                }
            }
        }
        //哨兵点，连主体
        for (int i = 0; i < n;i++){
            for (int j = m - 1; j >= m - 3;j--){
                a[i][j] = a[j][i] = 1;
            }
        }
        //连比特
        for (int i = n; i < m - 4;i++){
            a[i][i + 1] = a[i + 1][i] = 1;
        }
            // 最后一个哨兵连第一个比特
            a[m - 1][n] = a[n][m - 1] = 1;
        for (int i = 0; i < m;i++){
            for (int j = 0; j < m;j++){
                cout << a[i][j];
            }
            cout << '\n';
        }
    }
    else{//decoder
       
        vector<u64> s(n), r(n);
        for (int i = 0; i < n;i++){
            r[i] = rnd();
        }
        for (int i = 0; i < n;i++){
            for (int j = 0; j < n;j++){
                if(a[i][j]){
                    s[i] += r[j];
                }
            }
        }
        map<u64, int> mp;
        for (int i = 0; i < n;i++){
            mp[s[i]]++;
        }
        int x=-1, y=-1;
        u64 w=0;
        for(auto [p,q]:mp){
            if(q==2){
                w = p;
                break;
            }
        }
       
        vector<int> tp(n);
        for (int i = 0; i < n;i++){
            if(s[i]==w){
                x = i;//x为2哨兵点之一
                tp[i] = -1;
                break;
            }
        }
        assert(x != -1);
        for (int i = 0; i < n;i++){
            if(a[x][i])
                tp[i] = -2;
        }

        for (int i = 0; i < n;i++){
            if(i!=x&&s[i]==w){
                tp[i] = -1;//另一个2哨兵点
                break;
            }
        }
        //此时仅比特点,3哨兵为0
        for (int i = 0; i < n;i++){
            if(!tp[i]){
                int ok = 1;
                for (int j = 0; j < n;j++){
                    if(!a[i][j]&&tp[j]==-2)
                        ok=0;
                }
                if(ok){
                    y = i;
                    break;
                }
            }
        }
        assert(x != -1 && y != -1);
        int ls = -1;
        vector<int> v;
        int now = y;
        while(1){
            int ok = 0;
            for (int i = 0; i < n;i++){
                if(i!=now&&tp[i]==0&&i!=ls&&a[now][i]==1){
                    v.push_back(i);
                    ls = now;
                    now = i;
                    ok = 1;
                    break;
                }
            }
            if(!ok)
                break;
        }
        vector<int> id(n);
        for (int i = 0; i < n;i++){
            if(tp[i]==-2){
                for (int j = 0; j < (int)v.size();j++){
                    if(a[i][v[j]]){
                        id[i] |= 1 << j;
                    }
                }
            }
        }
        for (int i = 0; i < n;i++){
            for (int j = 0; j < n;j++){
                if(tp[i]==-2&&tp[j]==-2){
                    b[id[i]][id[j]] = a[i][j];
                }
            }
        }
        for (int i = 0; i < m;i++){
            for (int j = 0; j < m;j++){
                cout << b[i][j];
            }
            cout << '\n';
        }
    }
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}