Recovery Kattis - recovery

淡淡的烟草味﹌ 2021-09-30 10:56 217阅读 0赞

[本题链接][Link 1]

题目大意：给两行01串，第一行长度代表行数，第二行长度代表列数，0表示在该行或列中1的个数为偶数，1表示1的个数为奇数，求该01矩阵，使得该矩阵转化的二进制数和字典序尽量小，1的数量要尽可能多，若构造不出输出-1。

当时训练赛上做这题完全没啥思路，还是看了学长的题解看了好久才勉强懂的。。

思路：若要使转化的二进制数尽量小，则存在的0应该尽量往左上角放（即存在0的话，0的位置应尽量在第一行或第一列）。因为（重点来了）：改变矩阵的一个元素，它所对应的行和列的奇偶性同时发生变化，对应到输入的串里，即行或列串里的1变0，0变1。可以先把矩阵看成全为1，然后求出奇偶性改变的行和列记录下来，排序后将这些位置变成0，然后输出就行了。

而对于输出-1的情况：两个串中1的个数为奇数的时候，矩阵是不存在的，因为你的操作不会改变1的个数的奇偶性，始终都是奇数个。

附上嫖来的AC代码(如果有不对的地方还请dl指出):

1 #include <iostream>
     2 #include <algorithm>
     3 #include <string>
     4 #include <cstring>
     5 #define INF 0x3f3f3f3f
     6 using namespace std;
     7 int main()
     8 {
     9     int a[110],b[110];
    10     char s[110][110];
    11     string s1,s2;
    12     memset(a,0,sizeof(a));
    13     memset(b,0,sizeof(b));
    14     cin>>s1>>s2;
    15     for(int i=0;i<s1.size();i++)
    16         for(int j=0;j<s2.size();j++)
    17             s[i][j]='1';//把整个矩阵看成全为1的矩阵
    18     int x1=s1.size()&1;
    19     int x2=s2.size()&1;
    20     int num=0,num1=0;
    21     for(int i=0;i<s1.size();i++)
    22         if(s1[i]-'0'!=x2)//如果不等于列的长度的奇偶的话，在该行肯定会有0的存在
    23             a[num++]=i;//记录该行的位置
    24     for(int i=0;i<s2.size();i++)
    25         if(s2[i]-'0'!=x1)//如果不等于行的长度的奇偶的话，在该列肯定有0的存在
    26             b[num1++]=i;//记录该列的位置
    27     if((num+num1)&1){
        //如果和为奇数，无法构造出矩阵来
    28         cout<<"-1";
    29         return 0;
    30     }
    31     while(num1>num)//num是行中有0的行数量，num1是列中有0的列数量
    32         a[num++]=0;//直到有0的行数=列数，添加的位置在第一行或第一列(让转化的二进制数尽量小)
    33     while(num>num1)
    34         b[num1++]=0;
    35     sort(a,a+num);
    36     sort(b,b+num1);
    37     int maxn=max(num,num1);
    38     for(int i=0;i<maxn;i++)
    39         s[a[i]][b[i]]='0';
    40     for(int i=0;i<s1.size();i++){
    41         for(int j=0;j<s2.size();j++)
    42             cout<<s[i][j];
    43         cout<<endl;
    44     }
    45     return 0;
    46 }

转载于:https://www.cnblogs.com/shangqing/p/11274223.html

[Link 1]: https://open.kattis.com/problems/recovery