[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 先往右下角放,然后遍历上去,最后检查,但是后来发现这个做法不可取,因为最后一行有可能并不一定都能通过改动变化成合法的,所以后期就把策略改成了

先把一个矩阵全部假设为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


题意

题目中的意思是,给出一个由 0 和 1 组成的矩阵块,每次按压之后,按压的那一块,其上下左右四面的块的状态都会改变状态,问哪一种按压方法,可以在按压的次数最少的情况下使得矩阵全部为 0,最后输出矩阵。

思路

这个在操作的时候,每一个块一定要尽可能的少操作,因为操作偶数次会恢复初始状态,并且由题意知道,操作的顺序对解结果没有影响,所以我们可以先给定第一行的状态,再由第一行去逐一判断下一行,直到最后看一看是不是合法就好了。


这里的第一行的操作的枚举,可以使用二进制来进行,快速方便,简记做如下代码:

for(int i = 0;i < (1<<n); ++i){
    memset(jge,0,sizeof(jge));
    for(int j = 0;j < n; ++j){
        jge[0][n-j-1] = i>>j&1;
    }
}

有这几行代码给出的数组的第一行,就是不同的操作状态,也就是每一种我们都去模拟一下,最后看看哪一个最小。


  • find 函数用于查询和合法性检验,给出经过当前所有已有的操作后,此块是否变为 0 的检验。
  • js 函数用于计算,给出某一个 块 是否按压的记录,并且检查当前的操作是否合法,不合法就输出 IMPOSSIBLE ,否则累加当前状态的操作数,看看是不是当前最优操作。
  • filp 函数是主体函数,给出模拟状态,判断最优解是否存在,输出结果。
    大体就这么个思路,下面给出代码。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <functional>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <climits>
typedef long long ll;
using namespace std;
const int maxn = 100;
const int dx[5] = {-1,0,0,0,1};
const int dy[5] = {0,-1,0,1,0};
int org[maxn][maxn], jge[maxn][maxn], ans[maxn][maxn];
//origin / judge / answer
int n, m;

inline int find(int x, int y){
    int res = org[x][y];
    for(int i = 0;i < 5; ++i){
        int nx = x + dx[i],ny = y + dy[i];
        if(nx >= 0 && nx < m && ny >= 0 && ny < n){
            res += jge[nx][ny];
        }
    }
    return (res&1);
}

inline int js(){
    for(int i = 1;i < m; ++i){
        for(int j = 0;j < n; ++j){
            if(find(i-1, j)){
                jge[i][j] = 1;
            }
        }
    }
    for(int i = 0;i < n; ++ i){
        if(find(m-1,i))
            return -1;
    }
    int rs = 0;
    for(int i = 0;i < m; ++i){
        for(int j = 0;j < n; ++j){
            rs += jge[i][j];
        }
    }
    return rs;
}

inline int flip(){
    int res = -1;
    for(int i = 0;i < (1<<n); ++i){
        memset(jge,0,sizeof(jge));
        for(int j = 0;j < n; ++j){
            jge[0][n-j-1] = i>>j&1;
        }
        cout << endl;
        int num = js();
        if(num >= 0 && (res < 0 || res > num)){
            res = num;
            memcpy(ans,jge,sizeof(jge));
        }
    }
    if (res < 0){
        cout << "IMPOSSIBLE" << endl;
    }
    else {
        for(int i = 0;i < m; ++i){
            cout << ans[i][0];
            for(int j = 1;j < n; ++j){
                cout << " " << ans[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}


int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin >> m >> n){
        memset(org,0,sizeof(org));
        for(int i = 0;i < m; ++i){
            for(int j = 0;j < n; ++j){
                cin >> org[i][j];
            }
        }
        flip();
    }
    return 0;
}

  • Sublime Text 3 折腾笔记(C/C++)

    • 写在前面
    • 获取

      • 下载链接
    • 配置
  • 插件
  • 总结

写在前面

  • 不得不说,生在中国,有时候安装一个软件还真是学习的好“机会”
  • Good Good Study, Day Day Up!

获取

这个,笔者一开始是在官网下载的,十分顺利,然而下载下来误删之后,官网就打不开了!!!也 `ping` 不通了!笔者实在是不想在国内一堆乱七八糟的网站下载,就飞出去到了官网下载。
不知道什么时候还会再打开或者打不开,相信笔者的童鞋可以下载我安装的版本。百度网盘吧,不是很大
Sublime Text 3 3143 x64&32 PC(上传日期:2018。02.27)

下载链接

官方网站
百度云盘: https://pan.baidu.com/s/1o9AsINK 密码: 3e2d

配置

Sublime不是一个具体的IDE,要使用它要经过一些配置

  • 首先,你要确保能够编译程序,就要有一个编译器,一般的编译器有MinGw和TDM-Gcc

    • 有的电脑安装过IDE,比如Dev-c++/Code Blocks(带编译器版本)/VS··· ···,这个时候,不再需要去下载编译器了,
      找到你的软件安装目录,你会发现里面就有MinGw的呢!
      如果有的话,你就可以跳过安装编译器这一步了!跳转到下一步
    • 对于TDM,有个安装包,一路NEXT就好啦,要记住安装路径哦!
    • 对于MinGw,有一些不一样的地方。安装过程需要联网,而且安装完成后,记得勾选下面截图中的选项,
      然后 Installation->Apply Changes

  • 配置Windows系统环境变量

    • 此电脑->属性->高级系统设置->环境变量->系统变量中的path ****添加****你的编译器路径下的bin目录。
      添加,不要删了或者是重新新建一个Path,不然的话,你的cmd命令就失效了,只有后面再一条一条恢复了。
      我恢复的时候,网上的办法完全行不通,注册表自己就改了,最后看了同学的电脑恢复成了系统初始的Path@#@
      如果记不住或者拿捏不准的话,可以打开那个MinGw\bin看看,里面是不是有gcc和g++的应用程序,有的话您就放心吧!

  • 测试

    • 测试一下是不是路径是对的,并且文件起作用了。
      打开cmd,输入gcc,如果识别了,恭喜你,进入下一步吧!如果失败了,请您先重启一下电脑(部分电脑系统需要重启生效),
      如果依然不正确,请您想一下,是下载的编译器不全呢,还是您路径没有添加正确呢?别放弃,再来一次,会成功的!
  • 配置Sublime Text

    • 不详细介绍Build System了,求知欲强的朋友搜一下吧,或者移步Link_1\ Link_2 \ CSDN<-感觉很全面的

      • 打开Sublime,点击 Tools->Build System -> New Build System ,
        输入下方配置文件,ctrl+s保存,我这里保存的名字是C++
        文件位置C:\Users\Fancyking\AppData\Roaming\Sublime Text 3\Packages\User,那个以.sublime-build为后缀的,
        用Sublime打开就可以修改

C++11配置文件

    {
    "encoding": "utf-8",
    "working_dir": "$file_path",
    "shell_cmd": "g++ -Wall -std=c++11 \"${file}\" -o \"${file_path}/${file_base_name}\"",
    "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
    "selector": "source.c++",

    "variants":
    [
        {   
        "name": "Run",
            "shell_cmd": "g++ -Wall -std=c++11 \"${file}\" -o \"${file_base_name}\" && start cmd /c \"\"${file_path}/${file_base_name}\" & pause\""
        }
    ]
}
一般这个时候Build System选择刚才新创建的文件的话,直接ctrl+B就可以运行了,不行的话,请重启电脑,
如果还是错误,请检查步骤和文件整体是否完全。(请在英文输入法状态下操作)
  • Snippets

    Sublime还带有一个功能,嗯,你是不是对每次打开新的CPP输入的那一堆头文件感到厌倦了呢,这里帮你解决!
    先来看看效果


    • 设置:
      Tools-New Snippet

      文件格式是这样的

<snippet>
    <content><![CDATA[
Hello, ${1:this} is a ${2:snippet}.
]]>//在这里输入内容,${1:}表示按完快键键后按光标所在位置
${2:}表示,按完快捷键后,按第一下tab光标转移到的位置。
</content>
    <!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
    <!-- <tabTrigger>hello</tabTrigger> -->//快捷键开关,你要把注释取消掉,像
    <tabTrigger>hello</tabTrigger>//我的图中就是把hello改成了'#init'
    <!-- Optional: Set a scope to limit where the snippet will trigger -->
    <!-- <scope>source.python</scope> -->
</snippet>

我的配置是这样的

由于里面有解析标签,显示不完全,所以换成图片了
Conf


  • 使用

    • What? 你说你不会用?来来来,按照上面的,你输入#init再按一下Tab,哇,是不是会了!
      改变tabTrigger的内容,可以改变快捷键哦!

  • Just Enjoy It!

    下面,你就可以使(rou)用(lin)他了,快用他去码字吧!


    插件

    插件有好多啊,大家搜一搜估计就好了,我说我的主题吧。

    主题我是BoxyAFileIcon
    感觉ConvertToUTF8不错



  • 强大的插件管理包

    • package control

      • 安装
        按下键盘上的 ctrl+`, Console(也可以是菜单栏 View -> Show Console
        输入下面的内容(来自官方啦,不过根据官方说,会不定时更新) Link ,回车
        Sublime 3


      import urllib.request,os,hashlib; h = '6f4c264a24d933ce70df5dedcf1dcaee' + 'ebe013ee18cced0ef93d5f746d80ef60'; pf = 'Package Control.sublime-package'; ipp = sublime.installed_packages_path(); urllib.request.install_opener( urllib.request.build_opener( urllib.request.ProxyHandler()) ); by = urllib.request.urlopen( 'http://packagecontrol.io/' + pf.replace(' ', '%20')).read(); dh = hashlib.sha256(by).hexdigest(); print('Error validating download (got %s instead of %s), please try manual install' % (dh, h)) if dh != h else open(os.path.join( ipp, pf), 'wb' ).write(by)
      


      Sublime 2

      import urllib2,os,hashlib; h = '6f4c264a24d933ce70df5dedcf1dcaee' + 'ebe013ee18cced0ef93d5f746d80ef60'; pf = 'Package Control.sublime-package'; ipp = sublime.installed_packages_path(); os.makedirs( ipp ) if not os.path.exists(ipp) else None; urllib2.install_opener( urllib2.build_opener( urllib2.ProxyHandler()) ); by = urllib2.urlopen( 'http://packagecontrol.io/' + pf.replace(' ', '%20')).read(); dh = hashlib.sha256(by).hexdigest(); open( os.path.join( ipp, pf), 'wb' ).write(by) if dh == h else None; print('Error validating download (got %s instead of %s), please try manual install' % (dh, h) if dh != h else 'Please restart Sublime Text to finish installation')
      

  • 输入完成。然后在Preference,如果看到了Package Control就完成了。
    英文输入法下按下 ctrl+shift+P 输入 pcic ,就可以安装你找到的插件了,只需要输入名字哦!

  • 意外
    正常情况下,以上操作之后就可以愉快的享受了,但是,你在CN_Zh不是,还有着奇奇怪怪的错误。
    > 如果你选中了 Package Control Install Package ,但是弹出来一个对话框,说:
    Package Control:There are no packages available for installation
    那是因为有一个文件,他没有在网上预定好的地方下载到,
    我的解决方法是,翻出去下载下来(网页右键单击另存为),放到本地,然后改一下设置的文件获取路径。
    下载到本地之后,找到文件 PackageControl.sublime-settings
    (在文件夹里找或者是Preference->Package Setting->Settings Default)
    改掉第一个channels,将里面的网址对应的部分改成 C:\\Users\\Fancyking\\Documents\\Sublime\\channel_v3.json
    最终指向channel_v3.json文件就好啦。你就可以看见搜索框了!
  • 高兴太早
    + 有的时候,下载还是不成功,是为什么呢,哎,你还在CN_Zh,如果打开Package Control的Debug的话,
    你会发现,网站链接有时候会失败,哎,我是找了一个ipv4的地址放在了hosts文件里,
    50.116.33.29 sublime.wbond.net 50.116.34.243 packagecontrol.io
    谁知道起不起作用,还是一会儿行一会儿不行的!
    反正也不是插件狂,找个好的时候下载完了就好啦,也不是很用愁。
    对了,要是这玩意一直不能用的话,你可以搜到插件以后,手动安装,麻烦是会有的,还有依赖等着你,/xk。
  • 不服输
    我说,你不让我简简单单的安装,我就会放弃吗,醒醒吧,像咱们这么勤劳奋斗热爱祖国的少年,当让是另外想办法啦!
    另一条路就是,下载源码,解压到 Package Control 文件夹下,注意哦,GitHub上的Zip,解压之后,不要忘了删除最后的 -master 哦,不然是会报错的!
    只要想搞,总是会搞出来的!
  • 总结

    折腾了好久,安装了满意的Sublime,这个我觉得兼具好看,快速,体积小,内存小的优点,就是在中国要折腾一下。
    写这篇笔记也写到了深夜,希望可以帮到需要的人吧,反正当时我安装的时候,找了好多资料!
    
    

    The World Is Not Enough!
    — —This is what I believe forever!
    — —This is my belief

    2018.02.28初稿
    2018.02.30第一次修改