2016-C21-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||
||291||4:58:52||8644||I||g++0x||Presentation error||
||283||4:50:04||8653||I||g++0x||Presentation error||
||282||4:48:45||8603||I||g++0x||Presentation error||
||269||4:34:43||6238||I||g++0x||Presentation error||
||264||4:28:21||4016||I||g++0x||Presentation error||
||263||4:22:09||3976||I||g++0x||Presentation error||
||262||4:16:44||3855||I||g++0x||Presentation error||
||259||4:09:45||1105||J||g++0x||OK||
||238||3:11:09||1299||J||g++0x||Wrong answer||
||232||2:49:58||1239||J||g++0x||Wrong answer||
||222||2:24:19||2527||A||g++0x||OK||
||216||1:46:25||1981||A||g++0x||Wrong answer||
||208||1:20:36||1877||E||g++0x||OK||
||197||0:42:10||424||G||g++0x||OK||
||195||0:34:53||1335||F||g++0x||OK||

== 流水账 ==
=== TsReaper ===
开场我们很快想到了F和G的做法，'''F1y34'''，'''G1y42'''。我写G的时候，学长们也想到了E的做法，'''E1y80'''。starve学长写E时，我和hzf学长讨论A。刚好starve学长做过一个A的弱化版，给我们讲了讲做法。一开始我的问题转换是错误的，之后才改对，'''A2y144'''。之后我和hzf学长讨论J，starve学长尝试I。J题我们一开始思路挺正确的，但是我们讨论到后面，一些符号的意义弄混了，导致出现了许多的错误，J题也拖延了比较久才答对，'''J3y249'''。

== 总结 ==
=== TsReaper ===
 * 做得不好的地方
   * 讨论做法的时候，数学符号的意义最好写明在草稿纸上，不然到后面很容易弄错。

== 题解 ==
F和G比较简单，略过...

=== A - The Carpet ===
如果要求没有#的最大面积矩形，有一个经典的做法：悬线法。可以搜索这篇文章来看看《浅谈用极大化思想解决最大子矩形问题》。

如果要求最多有一个#，我们可以分类讨论：(1)悬线上没有#，悬线左边可以容忍一个#，悬线右边不能有#；(2)悬线上没有#，悬线左边不能有#，悬线右边可以容忍一个#；(3)悬线上可以容忍一个#，悬线左右两侧都不能有#。对这三种情况分别求出最大子矩阵，再取最大值即可。写起来有点麻烦...

=== J - The Task ===
设size[v]表示以v为根的子树的有权大小，u是v的父亲，显然有b[u]-b[v] = size[1]-2*size[v]。也就是说size[v] = (size[1]-(b[u]-b[v]))/2。因为保证必然有解，我们可以先根据b[u]-b[v]的奇偶性，猜测size[1] = 0或size[1] = 1，然后算出我们猜测的所有size[v]的大小。

当然，现在我们猜测出来的size[v]很有可能是不正确的，怎么把它变成正确答案呢？我们看到，如果size[1]增加了2x，那么对于所有v != 1，size[v]都会增加x。也就是说，size[1]离真实答案差了2x，而其它的size离真实答案都差了x。

那么如何算出x呢？注意到b[1] = size'[2] + size'[3] + ... + size'[n]（这里的size'表示真实答案）。显然我们可以解方程b[1] = size[2] + x + size[3] + x + ... + size[n] + x算出x，那么我们就能得到size'，就能得到答案了。

== 补题 ==
=== TsReaper ===
C
Run IDTimeSizeProblemLanguageResult
2914:58:528644Ig++0xPresentation error
2834:50:048653Ig++0xPresentation error
2824:48:458603Ig++0xPresentation error
2694:34:436238Ig++0xPresentation error
2644:28:214016Ig++0xPresentation error
2634:22:093976Ig++0xPresentation error
2624:16:443855Ig++0xPresentation error
2594:09:451105Jg++0xOK
2383:11:091299Jg++0xWrong answer
2322:49:581239Jg++0xWrong answer
2222:24:192527Ag++0xOK
2161:46:251981Ag++0xWrong answer
2081:20:361877Eg++0xOK
1970:42:10424Gg++0xOK
1950:34:531335Fg++0xOK

流水账

TsReaper

开场我们很快想到了F和G的做法，F1y34，G1y42。我写G的时候，学长们也想到了E的做法，E1y80。starve学长写E时，我和hzf学长讨论A。刚好starve学长做过一个A的弱化版，给我们讲了讲做法。一开始我的问题转换是错误的，之后才改对，A2y144。之后我和hzf学长讨论J，starve学长尝试I。J题我们一开始思路挺正确的，但是我们讨论到后面，一些符号的意义弄混了，导致出现了许多的错误，J题也拖延了比较久才答对，J3y249。

总结

TsReaper

  • 做得不好的地方
    • 讨论做法的时候，数学符号的意义最好写明在草稿纸上，不然到后面很容易弄错。

题解

F和G比较简单，略过...

A - The Carpet

如果要求没有#的最大面积矩形，有一个经典的做法：悬线法。可以搜索这篇文章来看看《浅谈用极大化思想解决最大子矩形问题》。

如果要求最多有一个#，我们可以分类讨论：(1)悬线上没有#，悬线左边可以容忍一个#，悬线右边不能有#；(2)悬线上没有#，悬线左边不能有#，悬线右边可以容忍一个#；(3)悬线上可以容忍一个#，悬线左右两侧都不能有#。对这三种情况分别求出最大子矩阵，再取最大值即可。写起来有点麻烦...

J - The Task

设size[v]表示以v为根的子树的有权大小，u是v的父亲，显然有b[u]-b[v] = size[1]-2*size[v]。也就是说size[v] = (size[1]-(b[u]-b[v]))/2。因为保证必然有解，我们可以先根据b[u]-b[v]的奇偶性，猜测size[1] = 0或size[1] = 1，然后算出我们猜测的所有size[v]的大小。

当然，现在我们猜测出来的size[v]很有可能是不正确的，怎么把它变成正确答案呢？我们看到，如果size[1]增加了2x，那么对于所有v != 1，size[v]都会增加x。也就是说，size[1]离真实答案差了2x，而其它的size离真实答案都差了x。

那么如何算出x呢？注意到b[1] = size'[2] + size'[3] + ... + size'[n]（这里的size'表示真实答案）。显然我们可以解方程b[1] = size[2] + x + size[3] + x + ... + size[n] + x算出x，那么我们就能得到size'，就能得到答案了。

补题

TsReaper

C

附加文件