题目描述：给n个矩形二维容器(xi×yi)，求面积最大的矩形块A×B，使得两个这样的矩形块能塞进容器里。
塞法有两种：塞在同一个容器；塞在两个不同的容器。前一种情况很水，后一种也不难。枚举矩形块的较小边A，这个较小边也必然是某个容器的较小边。所以只要枚举容器的较小边就行了，这样确定第一个容器；然后在第一条边大于A的容器中，找第二条边的最大值。该值与第一个容器的较大边的较小值，就是矩形块的较大边B。
于是问题转换成求区间最大值，方法很多，这里采取排序后倒序枚举解决。
注意double(精度仅52位)存不下答案，要用long double，或者手动处理long long来输出答案。
1 | /* |
依次模拟最长公共子串的匹配过程，每到一个状态，标记最长不可用后缀的长度countAns。全部跑完后，树形dp更新祖先的countAns，因为祖先是后缀，长度小于子孙的匹配部分的子串也不可用了。最后累加可用部分的数量得到答案。
1 | /* |
鄙校又有两人合体账号上紫了，引起了一些同学的不满。我倒觉得这无所谓，大不了此号不再表示个人实力，而是代表两人合作形成的小队伍有上紫的实力……（然后ljr发奖时就说：恭喜xxx和xxx组成的小队达到2000分，赠送该队耳机（咕咕咕～）一副）
但抛开这个不论，组队训练还是非常重要的。虽然这种操作让cf的分有点“虚”，但无形之间增加了大量组队训练的机会。我觉得这正是我们现在迫切需要的东西。
下午做了个梦，梦见啥忘了，但就是让人不想爬起来……
也许在梦境世界有另一个我们……
梦醒了，继续起来刷题。今天又是阳光灿烂的一天呢。
说到刷题。可能有些同学觉得鄙人有啥天赋，或者某些题莫名其妙的就会做。其实没有的事。
本人高中时很菜，高二搞了两个月oi，结果考下来还不如高一。高三搞了一天，结果莫名其妙省一（其实名次还是不如高一，但那年名额放水）。后来大学决定弥补遗憾（？），没上大一的暑假就在边搞项目边刷luogu。项目半黄不黄了，洛谷倒刷了不少。
另外就是大一上的时候，丝雨学姐的project，每周刷多少题，写题解报告。刚进队的同学可能都刷萌新题啥的，我就找nwpu练着玩系列，那时候就刷了一堆dp、二分、stl啥的。虽然并不很多，但很明显对之后的cf涨分起到了作用。
（那时候可能是成长力的巅峰时期，会分数规划，会图论，会数据结构，会stl骚操作，还有各种莫名其妙的贪心和脑洞题……）
现在已经好久没刷那里的题了，也好久没写啥题解，却沉沦于一堆乱七八糟的专题和新算法中，该会的也都不会了，学一个新东西还要好长时间（成长力A->E）。
当年wdl靠着刷水题熬过了瓶颈期，我也必须找到我自己的方法，来度过这最艰难的时期。
关于学习和ACM。冲突是必然的，关键在平衡。这都是废话。
但是，舍弃平时的上课来搞算法，这值得吗？
上大学究竟为了什么？我认为，被ACM束缚住自己的一切大学生活，很亏。
而我自己却正处于这样的状态。
很多人叫我金爷，我也知道我不配。这个名字是wdl起的。出处我大概能猜到，当年他们称金策为策爷。wdl给我起这个，半是讽刺，半是激励。
作为报复，我也继续叫他wdl。
我最怕听到的，却正是wdl常说的一句话：这道题liu总肯定把它秒了……
于是我就知道我又要背锅了。
我在团队中的定位，还是偏思维，偏脑洞，正经的题常常不会，说明仍然缺知识基础。为了弥补，我曾经刷了一些线段树，耗费了很多时间，但是不仅没有用，而且得不偿失。
结果就变成现在这样脑洞也不行，算法也不会的状态。
我感觉我学算法似乎陷入了一个误区，只是知道这玩意是什么，怎么用这玩意，却没有真正理解这个东西是怎么来的，为什么这么来。原因很简单：新的算法和以前学的相比，难了，不好理解了，要追求和以往一样的学习的速度，做不到。暑假的时候自学SAM，对着博客盯了三天，还是没有彻底理解构造的原理。现在要是不给板子，还是不行。
其实仔细回想，当年学dp还要费劲……但是那时候年轻，容错空间很大。现在根本不可能给你一个学期去理解dp到底是啥。即使是SAM，也是如此。你要学新算法，必然大量占用刷题时间，而且学了还不一定考，考了也不一定做得出。
再说思维题，对于大部分人，没有啥天生有脑洞的事，都是刷题刷出来的（lcw裸题除外= =）。
wdl说他去刷div2的E题，那时候我其实非常想说，让我去刷吧，你好好搞数据结构和数学。
但那句话还是没有说出口。我还有计算几何、字符串的大锅，搞这俩玩意已经焦头烂额。马上还有复变期末，才刷了三分之一套题，就来写这个文章。
要是再等半年就好了……
但是，之前那些玩游戏、刷新闻和破站的时间呢，不是白白流逝了么……
计算几何这个东西，之前已经付出了大量的精力，效果却不怎么好，现在板子有没有锅都不知道。有一道水题，老早就过了，结果把板子的template去掉，就过不了了。根本不知道为什么。
计算几何这玩意，题目要是水，就是瞎暴力，大家都能过；要是难，你也过不了。代码量大不说，还难调，精度还随时有可能爆炸。我不知道计算几何是不是应该就此收手，希望能和队友商量一下。
马上就是区域赛了。虽然时间不多，但仍能临阵磨枪。共勉。
忘了一件事。刷题绝对不能只追求量，一定要彻底参透刷过的题，不然等于白刷。
大部分人都知道这个道理，可是一看周围的人刷题量都蹭蹭蹭往上涨，又不知不觉地继续堆刷题量了……
题目描述：n个串，两两连接，有多少种方案形成回文串
枚举每个串作为连接后较长的串，找到所有回文前缀，剩余的后缀部分的反串连在当前串前面可得回文串，跑字典树即可。再找到所有回文后缀，剩余的前缀部分的反串连在当前串后面也可得回文串，跑反串字典树即可。还有一种是两个串长度相等，放入之前的任意一种情况都行。本题卡常，用string会T，建立两棵字典树会mle，所以要用一个字符数组模拟n个串，并先做第一种，然后清空字典树并重建反串字典树再做第二种。
1 | /* |
【题面描述】
求由字典集T（仅包含小写字母）生成的长度为m，且不包含子串S（|S|≤50）的字符串总数量，对$2^{32}$取模。m不超过${10}^9$。
神烦的dp套KMP= =看数据规模容易以为是CTA算法题(Contribute To the Answer)，但居然是矩阵快速幂优化dp= =感觉没见过的话很不可做，但据说已经是经典老题了，还有AC自动机版本……
取模就是两眼一闭，自然溢出。
首先得迅速解决n比较小时的问题，否则就会想偏。
f[i][j]表示第i位文本串匹配到第j位模式串的合法方案数，其中规定j尽可能大。初值为f[0][0]=1，转移时对每个模式串的位置j枚举下一个字母k，遍历j的next祖先，找到能成功匹配到k的最大位置，这就是应当转移到的目标；如果匹配完成，那么不计入答案。显然这一步与i无关，所以可以预处理mtx数组，其中mtx[j][k]表示第j位模式串后接上k应当转移到的位置，对每个j和k暴力跑next即可。这样在跑dp时，对每一对(j,k)，可以$O(1)$地找到要转移到的位置，将方案数累加即可（刷表法）。答案就是$\displaystyle\sum_{i=0}^{|S|-1}f[m][i]$。dp时间复杂度为$O(m|S||T|)$，预处理时间复杂度为$O(|S|^2|T|)$。其实可以通过进一步预处理，使预处理时不用枚举k，复杂度下降为$O(|S|^2)$，但由于时间复杂度瓶颈不在这里，所以意义不大= =
转移方程伪代码：
1 | /* |
然后可以发现，$f[i][j]$只由$f[i-1][j]$转移而来。所以可以用填表法表示转移方程：
莫名其妙多了一维？但可以发现，对于每对(p,j)，我们只关心有多少个k，使得mtx[p][k]==j，也就是说可以再次预处理m0[p][j]表示满足条件的k的数量。
于是修改转移方程（顺便重新命名了一些字母）:
初值还是f[0][0]=1。
我们发现了什么？如果把f[i]写成行向量，那么这就是矩阵乘法的形式！那么就变成矩阵快速幂的板子了。
但本人习惯写方阵×列向量的形式，所以dp方程（强行）改为：
由于初值只有f[0][0]=1，所以乘完后答案就是第0列的和，不必再进行一次矩阵乘法了。
另外，两步预处理可以合成一步，还是省略k的信息，比较容易就不再赘述了。
1 | /* |
今年暑假，我参加了西北工业大学的大学生程序设计创新实践基地（ACM基地）的培训。我认为，但凡参加这个培训的同学们，都或多或少怀揣了摘金夺银的梦想。三伏盛夏，谁愿意顶着酷暑，每日早起赶到机房打卡，听课，刷题，敲代码，调试，敲代码，调试，调试呢？既然大家愿意牺牲大量玩的时间（培训时长为一个暑假，中间只有两周的休息时间），必然对收获有着一份向往。本人也是如此，打codeforces到24:35几乎成了常态，希望能以此稍微提升自己的实力，进而能在比赛中取得至少还能说得过去的成绩。
然而，“行百里者，半于九十”。一些同学参加了初级培训，后续的高级培训却没有参加。如果确实是水平的问题，还可以理解；但即使是初级培训，不少同学仍然觉得困难。有一次，我们吃完饭回机房时，偶尔听到路上有同学对当天讲课的内容疯狂吐槽，嫌讲课的同学只讲题目的大体思路，没有讲任何基础算法；不巧的是，那位讲课的同学就在我们中间，听得一清二楚。事实上，他之前准备讲课时，考虑到部分同学没有算法基础，特意选择了不需要会任何算法的题目；没想到反而因此被吐槽，于是非常郁闷。正好我几天后负责讲解一个基础算法，于是我想，既然大家这么想听算法课，那到时候大家总会认真听了吧？没想到到了那一天，还是有不少同学在狂戳手机……我讲完一段，提出一个问题下去，反馈寥寥无几。当然也有一些同学相当积极，即使回答并不够非常正确，但仍然给我留下了较为深刻的印象。后来我想，也许平时为我们上课的老师，也是这样的想法呢？但就学习而言，基地的培训和平时的上课有本质上的不同。在基地培训，从来不会有人督促学什么内容、哪些是重点、交什么作业……一切都是为了自己实力的提升，最终也只能靠自己提升实力。那些为数不多，坚持到底的同学，水平也因此突飞猛进。
就我个人而言，水平的提升也得靠自己。原本我以为，个人赛综合rank1，codeforces一度名列西工大在役选手rank1，再稍微下点功夫，就还算说得过去了。现在看来，“不仅天真的令人发笑，而且幼稚的不可理喻”。好多真正的巨佬，一直偷偷拼命努力。不仅是高中就有基础的巨佬，平时非常低调，实力却远超一般人的想象；还有大学开始接触编程、零基础的新巨佬，勤奋刻苦，疯狂刷题，从芸芸众生中脱颖而出。而我却几乎还在原地踏步，该不会的还是不会。现如今，基地里人均杜教筛、人均后缀数组、人均主席树，cf人均紫名，可是我还在被各种水题卡，稍微高级一点的算法（现在都称不上“高级”）又不会。以前为了督促自己刷题写题解，还专门开了github的博客，结果整整一个暑假都没有更新。不敢突破舒适圈，只能安于现状；偶尔想学一个算法，刷了一点题，结果直接被新学的东西“洗脑”，遇到啥题都往那上面想，反倒连本来应该轻松解决的问题都不会了。模拟比赛时还犯各种低级错误，什么忘开long long、忘记清零，本来不会犯的错都犯了。原本指望一个暑假cf能上100+的分，结果只成功了负百分之一。
前路依旧漫漫。几个月前，我还可以用“才大一，还有时间”安慰自己，可如今，一切已然没有退路。以前区域赛卡题也没关系，反正还有时间可以练；然而今年区域赛的网络赛（相当于预选赛）已经悄然而至。
The sound of footsteps became louder every day,
Then I noticed the fact there was no time.
我不希望成为这首《why, or why not》中的悲剧。现在还剩下最后一点时间，能否取得理想的成绩，成败就在此一举。往年的区域赛的可做题有很多，该练的都必须练。cf，网络复现赛，能不落下就尽量不能落。还有，及时写题解，脑洞题可以试着积累一下小结论。除此之外，早睡早起，减少浪费的时间，都是可以做而应当做的。
丈夫生世会几时？安能蹀躞垂羽翼！不管是为了自己，还是为了重要的人，只有比别人付出更多，才有可能收获更多（更何况对于我这种菜逼，还得加倍的多）。漂亮话是无济于事的，只有行动和成果才能证明一切。今年年底，一切拭目以待。
热身赛，下雨。似乎大家都选择性无视了志愿者小姐姐发消息提醒的“南昌天气多变”，木有带伞，只有一件便携的雨披……总之三个人被淋成落汤鸡，鞋子还湿透了。中午到食堂买了雨伞，但又不熟悉体育馆位置，绕了好多路。总算到热身赛赛场，大家都精疲力尽（而且没法睡午觉）……热身赛题目来了个surprise：除了标配三分英文题面，还有一份中文题面。主办方信誓旦旦告诉我们，只有热身赛有中文，正式赛就没有了。（吃显示器预定）
D题输出5个数(wyh式裸送，后来碰到了wyh大佬，果然是他主持的比赛QAQ)，A题也很简单，虽然有一点小意外但很快解决了。B题模拟题，C题需要一点思考，但在我敲B题时被两个大佬队友推出来了。抬头一看榜，BC两题一片大红，我交了一发B也RE，故怀疑数据出锅，C题敲完后随便提交了一下,WA完走人。主办方及时承认了数据出锅，但又信誓旦旦的保证明天正式赛绝对没问题。(你拿啥保证啊，就连之前的$#TT$#@#G&@#$#^$#……)
热身赛回来，洗了个澡，浪了一晚上早早睡觉了，可不幸的是，凌晨4点又醒了过来……折腾到估计5点多才睡着，7点强制起来时感觉比较疲惫，吃完早饭 (质量很一般) 又是退房又是寄放行李……因为这么多琐事又消耗了很多体力(没有领队像根草QAQ)。到了赛场，WC还要排队，找另一个还是要排队，再找一个又要排队……
刚解决了私人问题，就听到赛场一片惊呼，原来正式赛也有一份中文题面！！！(不过幸好正式赛数据似乎确实没有出锅，不然就成了说啥啥打脸……)我们盯着倒计时，比赛刚开始，迅速刮分了中文题目，我看到最后一张纸上的L题又是wyh式裸送题，于是随手写了一发，居然WA了！原来不知道是太急了还是太困了，我竟然手残地在第二个数前面多敲了一个1。当时我连弄死自己的心都有了。特别感谢队友，提醒我：WA这一次损失不大，但要是因为这个影响了后面的心态，就很糟糕了。于是我尽力地调整，尽量在后面的比赛中忘掉这件事，好在心态没有受到太大的影响。(当然免不了赛后被队友的疯狂吐槽，估计回去后也没脸见大家了QAQ)
然后继续看题，注意到K题是个比较简单的贪心题，于是1A。此时队友在研究F(F是网络赛题的改编，奇偶项前缀和+单点修改)，我交完K后和geh学长开G，ACoder开始敲F。我们稍微想了一段时间的G题，考虑了建图的做法，所有可以成为第一名的队员之间一定能互相到达，因此找到一个最大值之后，bfs一遍就解决了。ACoder的F似乎出了点问题，换我上去敲G，稍微调试后1A了。此时队友打印了F题疯狂研究，发现公式推错了……然后改公式，还是WA。然后我和geh看别的题目，ACoder继续调F，geh学长写了F的暴力做法进行对拍。我注意到很多队伍过了J，于是看了一下J，认为是字典树裸题，于是和ACoder交流后，考虑让他先写J。ACoder想出了遍历tries维护权值树状数组的做法，但我认为暴力就可以了……考虑到ACoder比较熟悉字典树，还是让他写。(赛后认为ACoder的做法应该是标准解法，但很多队伍用map水过去了……)J写到一半，geh注意到了F题的锅(只是一个手残错误……)，迅速修改后AC。很快ACoder也1A了J。
此时我们碰到了铜墙铁壁————5题(铜墙铁壁：从比赛结果来看，5题经历了从银牌到打铁)。由于F题3WA，L题1WA，我们的罚时已经非常高了，要想确保拿银必须继续A题。在ACoder敲J时，geh学长在推B，我也看了别的题，感觉都不好做。H题看起来很有希望，别的部分都可以解决，但卡在了第一步的两个1e5数组两两取或的操作。(赛后得知是FWT卷积，然而本菜逼并没有听说过= =)A题感觉有点像某种生成树，但还是完全没有思路。(赛后得知是斯坦纳树，本菜逼仍然没有听说过= =)C题没有特别能理解题意，给了一个莫名其妙的式子，然后改变数组的顺序？？？(赛后得知是递归降幂+归并，数论是个啥玩意……)E题像树形dp，但处理起来会TLE+MLE(赛后得知是防AK的长链剖分，我TM……)。D题是大搜索，还没人AC。剩下的只有B和I了，过B、H队伍的比较多，A、C、I很少。于是geh学长还在B题苦苦挣扎……(赛后得知是牛顿差值/拉格朗日差值，学长表示很可惜差点就做出来了，本彩笔：喵喵喵？)ACoder认为I题可能可做，怀疑榜被带歪了。ACoder想出了修改排列方式简化问题，我以此为基础，想到了预处理k较小的情况，询问时暴力求出k较大的情况，修改时只需根据对修改点周围的影响，修改预处理结果的做法。ACoder提出根据均值不等式，大小界限为√kmax时，时间复杂度均摊最小，为Θ(n+q)√kmax。经过了一番波折，在ACoder大测试数据的帮助下，封榜后我终于把I调对了。这样我们终于确保了6题银奖。
(其实如果L、F、I不手残，而且再做得快一点，甚至拿金都有希望……)
比赛结束后，由于解决了I题，还是很高兴的，但一想到L题一WA赛神仙，我tm就……
(其实从罚时上看对结果影响确实不算大……但果然还是摧残心态啊)
吐槽一下考前几乎一个月都在研究计算几何，结果一道题都没遇到……
但该学的还是得学。这次5题以上(歪榜的I除外)大多是非常不常见的算法和数据结构，因此广泛的学习是很必要的。伟大的ACoder教导我们：学会各种算法+大量的刷题=success。(制定一个5(个)月计划吧。)
希望今年下半年，中美合拍……哦不，南昌区域赛，再次来到这里时，我们都能变得更强吧。
刚刚从卧铺火车上醒来，写下了这篇反思。早晨天气晴好，也是别有一番特色呢。
这次CF最终还是unrated了。虽然A题无限WApoint3（包括本菜在内）很容易让大家心态爆炸，但个人认为，B、C题做的好坏更为关键（这次的B和C都不是特别简单，需要仔细思考一下，否则很容易出错）。B题我采用的判断方法是奇偶字母分开，再把整个奇数序列放在偶数序列的前面或者后面，判断两序列交界的两个字母是否不相邻，如果两种方法都不可行就说明无解。C题主要是二分的策略问题，数值小的作为左端点优，数值大的作为右端点优，所以把序列一分为二，二分答案求分界点即可。（等等这篇好像是DE的题解来着？）
D题是一个比较典型的树形dp，但很遗憾本菜在比赛完之后才解决……首先读题要准确，节点对是相对有序的，所以全0序列和全1序列要算两次(因为x到y，y到x各算一次)，而先0后1序列只算一次。首先读图，随便找根节点建树，对于每一个节点，要记录它的子孙节点到它为止的全0、全1、先0后1、先1后0四种序列的数量(分别记为f00,f11,f01,f10)，由它的每一个儿子转移过来：如果儿子连向当前节点的边为0，那么更新f00和f10 （坑点：注意f00要加上儿子直接连接自己的、只有一条边的路径，f10除了由儿子的f10转移，还要由f11转移）；类似处理边为1的情况。然后就是儿子两两组合了（当然真的两两枚举肯定T，所以用当前儿子方案数×(总方案数减去当前儿子方案数)）：设以当前节点为路径中最高节点的路径集合为ans，那么ans要包括00+00，11+11，00+11，00+01，01+11这么多种情况，还要加上当前节点是路径端点、也即只用到一个儿子的情况。细节很 丰富 ，不知不觉，时间就在调试中消逝了~
1 |
|
E:蛇皮做法。老规矩，先用单调栈预处理每个点作为最大点的的覆盖范围；注意到输入数据是1~n的一个排列，所以预处理每一个数所在的位置。然后枚举每个点(不妨叫它x)，求出x作为最大点可以满足条件的区间数量，求法很暴力：选取左边区间和右边区间中较短的那个区间，对这个区间的每一个元素y，求出x-y，判断它的位置是否在x覆盖的另一个区间内。累计总数量得到答案。
这个算法显然是正确的，但神奇之处在于它的时间复杂度不是看上去的$Θ(n^2)$，实际上非常快。具体的证明比较难(本菜并不会)，但也许可以这么理解：
x为最大值n时，位置最差时为区间中点，此时需要枚举答案区间端点的数量最多，为n/2，相当于x把区间分成等长的两部分；然后x取n-1和n-2，位置最差时分别为各个部分的中点，此时各自分别需要枚举最多的n/4个端点，总共数量为n/2，相当于区间被分为4等分；再取x为n-3到n-6……这样相当于构造了树形结构，共有$log_2n$层，每层枚举数量为n/2，总共枚举数量为$(nlog_2n)$，对于题目给的数据范围可以接受。
伪证毕。
1 |
|
以上。
为什么总有人喜欢拿出”被害者有罪论”这一看似荒谬的命题？实际上，这是给自己看的。
“因为被害者犯了xxx错，所以才会……”
一方面，这是为了安慰自己，维护”不犯错就不会遭殃”之说。另一方面，也是在为防止遭殃而迷信般地寻找方法。前者是理论基础，后者是方法实现。
但事实上，现实就是这么不讲道理。许多受害者本无罪，但祸害偏偏降临到他们身上。无罪的他人也是如此，不知哪天，灾厄就会无故地降临到他们头上。过去的许多人就这样莫名其妙地成为了牺牲者，未来也是。
除非非要认为，人天生就是有罪——可平等的有罪竟得到完全不同的下场，仍是荒谬。
但这不是人类社会的错；与之相反，人类社会的稳定存在反而在全力阻止现实的”不讲理”，当然即使如此，不合理的事情仍然很多很多。相比而言，自然反倒才是不合理的根基。或者说，对有意识的生命而言，自然本身就是不合理的。优胜劣汰、适者生存合理吗？先天疾病合理吗？如果更基础一点，细胞凋亡之类最基础的生理现象，都是不合理的。在这样不合理的世界中，非要找因果报应之论，岂不可笑？
于是茫茫宇宙中，剩下的只有——
——澄清透明的黑白色的绝望。
（也许这就是我喜欢幻想乡的理由吧。）
题目描述：给n×m的01矩阵，每次操作可以把某一行或者某一列的每一个数翻转。问是否可以经过若干次操作，使矩阵从左到右、从上到下数值不下降。
题目的数据范围为1≤n,m≤200，但完全可以用O(nm)时间完成。
显然一个数值不下降的矩阵，可以由这样一个矩阵转换得到：它仅有至多一行不全为0，且如果这一行存在，那么这一行的元素必须满足前i项为0，而i+1到n项为1$( 0 < i ≤ n)$。不妨将这一行称为特殊行。
根据定义，一个矩阵可以转换为前述矩阵的必要条件是非特殊行全部能转换为0。不妨设第一列不翻转(翻转第一列等价于翻转每一行和第2~m列)，因此先翻转所有a[i][1]=1的第i行。然后分两种情况：如果特殊行不是第一行，那么翻转所有a[1][i]=1的第i列，然后判断当前矩阵是否满足条件，满足条件就说明找到答案了。如果特殊行是第一行，那么随意取另外一行为非特殊行，类似翻转即可。实际翻转和判断时，并不需要对每一个元素进行操作，只要对一行或者一列进行标记操作，而求某元素数值只要与所在行列的标记进行异或运算即可。
注意输出时，还要把所得矩阵转换回不下降矩阵。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
int a[330][330],r[200],c[200];
int n,m;
bool check(){
int flag=0;
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j+=1){
if(a[i][j]^r[i]^c[j]){
if(flag)return 0;
flag=1;
for(int k=j+1;k<=m;k+=1){
if(!(a[i][j]^r[i]^c[j]))return 0;
}
break;
}
}
}
return 1;
}
void print(){
cout<<"YES\n";
int flag=0;
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j+=1){
if(a[i][j]^r[i]^c[j]){
for(int k=i+1;k<=n;k+=1){
r[k]^=1;
}
flag=1;break;
}
}
if(flag)break;
}
for(int i=1;i<=n;i+=1){
cout<<r[i];
}
cout<<endl;
for(int i=1;i<=m;i+=1){
cout<<c[i];
}
cout<<endl;
}
int main (/*int argc, char const* argv[]*/){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j+=1){
cin>>a[i][j];
}
}
c[1]=0;
for(int i=1;i<=n;i+=1){
r[i]=a[i][1];
}
for(int i=2;i<=m;i+=1){
c[i]=a[n][i]^r[n];
}
if(check()){print();return 0;}
for(int i=2;i<=m;i+=1){
c[i]=a[1][i]^r[1];
}
if(check()){print();return 0;}
cout<<"NO\n";
return 0;
}
以上。