[题解] Recovery-The North American Invitational Programming Contest 2018

[TOCM]

# 原题

Consider an n \times mn×m matrix of ones and zeros. For example, this 4 × 4:

1111
0111
0111
0110

We can compute even parity for each row, and each column. In this case, the row parities are [0, 1, 1, 0][0,1,1,0] and the column parities are [1, 0, 0, 1][1,0,0,1] (the parity is 11 if there is an odd number of 11s in the row or column, 00 if the number of 11s is even). Note that the top row is row 11, the bottom row is row nn, the leftmost column is column 11, and the rightmost column is column mm.
Suppose we lost the original matrix, and only have the row and column parities. Can we recover the original matrix? Unfortunately, we cannot uniquely recover the original matrix, but with some constraints, we can uniquely recover a matrix that fits the bill. Firstly, the recovered matrix must contain as many 11’s as possible. Secondly, of all possible recovered matrices with the most 11’s, use the one which has the smallest binary value when you start with row 11, concatenate row 22 to the end of row 11, then append row 33, row 44, and so on.

Input Format
Each input will consist of a single test case.

Note that your program may be run multiple times on different inputs.

Each test case will consist of exactly two lines.

The first line will contain a string R (1 \le |R| \le 50)R(1≤∣R∣≤50), consisting only of the characters 00 and 11. These are the row parities, in order.

The second line will contain a string C (1 \le |C| \le 50)C(1≤∣C∣≤50), consisting only of the characters 00 and 11. These are the column parities, in order.

Output Format
If it is possible to recover the original matrix with the given constraints, then output the matrix as |R|∣R∣ lines of exactly |C|∣C∣ characters, consisting only of 00’s and 11’s. If it is not possible to recover the original matrix, output -1−1.

样例输入1
0110
1001
样例输出1
1111
0111
1110
1111
样例输入2
0
1
样例输出2
-1
样例输入3
11
0110
样例输出3
1011
1101
题目来源

The North American Invitational Programming Contest 2018

# 简要概括 #

题目的意思是，一开始有一个矩阵，每一行的 1 的个数如果是偶数个，记为0，奇数个记为1,所以这样会根据矩阵行列中的 1 的个数 来形成两个10字符串。现在已知这个最终的字符串，要我们还原出原先的矩阵，两点额外的要求：
+ 使矩阵中 1 的数目尽可能的多
+ 最后的矩阵的每一行连接起来形成的二进制数最小

# 思路 #

这样一来我们可以分析得到，我们要在满足尽可能多的 1 的数目的前提下，把 1 往矩阵的右下角扔，这样可以保证，得到的二进制数最小。然后就是另一个问题，我们如何保证当前是尽可能多的 1 。
一开始想把 1 先往右下角放，然后遍历上去，最后检查，但是后来发现这个做法不可取，因为最后一行有可能并不一定都能通过改动变化成合法的，所以后期就把策略改成了

这个时候要注意 ，对于下面这一种情况的特判，当时找了好久的BUG
00
11
答案应该是
00
11

如果根据我们的算法，x 和 y 的坐标数不对等的话，还要根据二者的差值是否是偶数，来判断能否更改成合法矩阵，二者差值为奇数的情况始终不可能修改成合法的矩阵，应该输出 -1.

# Code Share #

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = (int)50 + 1;
int dic[maxn][maxn];

int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string a, b;
    while(cin >> a >> b){
        memset(dic,0,sizeof(dic));
        vector<int> cmda,cmdb;
        bool have = false;
        int lena = a.size(), lenb = b.size();
        for(int i = 0;i < lena; i++){
            if(lenb & 1 && a[i] == '0'){
                cmda.push_back(i);
            }
            else if(a[i] == '1' && !(lenb&1)){
                cmda.push_back(i);
            }
        }
        for(int i = 0;i < lenb; i++){
            if(lena & 1 && b[i] == '0'){
                cmdb.push_back(i);
            }
            else if(b[i] == '1' && !(lena&1)){
                cmdb.push_back(i);
            }
        }
        if((cmda.size()-cmdb.size()) & 1){
            cout << -1 << endl;
            have = true;
        }
        else if(cmda.size() == cmdb.size()){
            int sl = cmda.size();
            for(int i = 0;i < sl; i++){
                dic[cmda[i]][cmdb[i]]++;
            }
        }
        else{
            if(cmda.size() < cmdb.size()){
                int i = 0,j = 0;
                for(i = 0;i < (int)cmdb.size() - (int)cmda.size(); i++){
                    dic[0][cmdb[i]]++;
                }
                for(;j < (int)cmda.size();){
                    dic[cmda[j++]][cmdb[i++]]++;
                }
            }
            else{
                int i = 0,j = 0;
                for(i = 0;i < (int)cmda.size() - (int)cmdb.size(); i++){
                    dic[cmda[i]][0]++;
                }
                for(;j < (int)cmdb.size();){
                    dic[cmda[i++]][cmdb[j++]]++;
                }
            }
        }
        for(int i = 0;i < lena && !have; i++){
            for(int j = 0;j < lenb; j++){
                cout << 1 - dic[i][j];
            }
            // cout << "     " << i+1;
            cout << endl;
        }
    }
    return 0;
}

代码应该很容易懂，也没加上啥巧办法，就是生写的。

                                                            -- 2018.08.12