C++博客-Mato is No.1

论人类智慧与机器智慧的关系

Mato_No1 — Sat, 25 Oct 2014 07:30:00 GMT

人类智慧，指人类所具有的智能和各方面的思维能力，尤其是目前人类具有而机器不具有的创造（发明新事物）和改进（提高现有事物的性能）的能力。人类智慧的水平由全人类的平均智商和知识水平决定，并且在不断地提高。与机器智慧（机器所具有的智能和“思维能力”）相比，人类智慧最典型的特点是它能够超越经验，即能在已经掌握的知识（经验）的基础上进行创新思维，从而自主发现一些尚未掌握的知识，有时人们甚至可以通过“直觉”（或“凭空想象”）得到一些有用的东西，而目前的机器只能从存储器中的内容（经验）中得到知识，不能自主获取存储器中没有的东西。因此，目前的人工智能只能机械地模仿人类的行为，“掌握”（其实是由人类灌输）人类已经掌握的知识，而不可能自主发现人类尚未掌握的知识，因为机器根本不具有学习和创新的能力。

目前的世界处于“人类控制机器”（机器智慧受制于人类智慧）的状态。然而，理论上人脑可以被电子元件完全模拟，所以人类所具有的创造和改进的能力，机器也是可以拥有的。一旦这种拥有超越经验的创造和改进能力的人工智能（即所谓的“强人工智能”）出现，机器智慧就会独立于人类智慧自主发展，很快机器就会凭借它的高速运算的特点，掌握比人更多的知识，从而超越人类智慧。因此最后的人机关系可能走向两种结果：一是机器在独立发展其智慧直至赶上人类的过程中，没有出现明显的敌视人类的倾向，最终人类和机器互相向对方灌输自己掌握的知识，人机差异基本消失（除了硬件），人机和谐共处，此为好结果；二是机器在独立发展的过程中被某些反人类的邪恶势力控制或者自主产生了反人类倾向，最终人机大战爆发，人类由于速度和性能劣势被机器消灭，此为坏结果。

显然，我们每个人都希望看到最终人机和谐共处的好结果，而不想被自己制造出来的机器杀死。所以，我们现在就要学习尽可能多的知识，发挥人类智慧的创造和改进的能力，同时保持对机器的控制，避免其出现反人类倾向，从而在强人工智能出现后等待好结果的到来。

Mato_No1 2014-10-25 15:30 发表评论

关于本blog转型的说明

Mato_No1 — Fri, 02 May 2014 14:41:00 GMT

我的OI生涯已结束，所以这个blog以后就不会有多少关于OI的内容了囧……

-----Human intelligence is really terrible-----

将会变为各种有关人类智慧的东西（乱搞内容+各种非传统题+一些实用内容+0x5B25...）

Mato_No1 2014-05-02 22:41 发表评论

CTSC2014题目的各种乱搞方法 && 感想

Mato_No1 — Wed, 30 Apr 2014 15:25:00 GMT

@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css); Day1 random：
首先基本方法是矩乘……xor可以转化为mod 2意义下的加法操作……
直接矩乘O(N³logK)，需要优化……
由于mod 2，矩阵中所有的元素都是0或1，于是可以压位，设压w位，则时间复杂度变为O(N³logK/w)……
其实还可以继续优化。
在mod 2意义下，乘法相当于and，加法相当于xor……假设某次待乘的两个N*N矩阵分别为A和B……
先对A的每一行进行分段，每w位一段，然后这一段在进行矩乘的时候，实际上是对B的每个w*32的块，都将该块对应的若干行（这一段值为1的位置对应的那些行）取出并整体xor……
因此可以一开始就对B进行分块，每块大小为w*32，每块计算出对于每个w位二进制数对应行的xor和……
这样两个矩阵相乘的总时间就是O(N³/w/32)了囧……（A中一共N²/w段，每段在B中乘N/32块，每段和每块的相乘结果可以直接在预处理记录的xor和里面调，是O(1)的）
预处理时间显然是O(N²/w/32*2^w)，w=logN时两者平衡……
这样很明显可以卡过去N=1000，K=10⁹的那些点（w取10），N=2000的或许也可以卡过去囧……

Day2 crypto：
N=50的，由于p大，直接随机53~58个方程，解方程组，有解的就认为是答案囧……
N=60的，基本思想是通过碰撞（两个方程xor）消去某些未知数，然后当未知数个数较小时暴力枚举验证……
@fanhq666 在讲题的时候，说进行两轮碰撞，第一轮消去第41~60个未知数，第二轮消去第21~40个，然后暴枚……
优化：这样在两轮之后其实是对4个方程合并后的结果，正确率严重降低，可以直接取3个方程碰撞消去40个（也可能>40个，减少枚举量）未知数，这样正确率就木有那么惨不忍睹了囧……

Day2 numbers：
基本方法：手打前若干个数字，后面的进行比对，选那个最像的（其实这样正确率并不能达到最高，可以取前10像的，看哪个数字最多，或者加入其它的一些估价……）
这样正确率可以达到约0.9……
为了进一步提高正确率，可以找出那些出错的数字，看都是将什么判成了什么……
结果是，4和9、7和9、3和5、某些1和8、某些1和2等易出错……
因此可以针对这些继续优化……比如对4和9设计更精细的估价函数，按每列拆分，可以确定上方的开口大小，然后取开口前若干小的为9，其它为4……

（未完待续）
———————————————————————————————————————————————————
一些感想：

我的OI生涯就这么结束了……
没能参加IOI，真的很遗憾……
但是像我这样的沙茶，除了提交答案和某些乱搞题外几乎木有任何优势，要是进了队，很明显是给中国丢脸啊囧……

CTSC的这几天，我和HN、ZJ的神犇进行了充分细致的交流……毕竟这是大学前最后一次和他们见面的机会了……
从这个交流当中感受到了很多东西……
首先当然是和他们讨论各种问题的过程中，他们告诉我的那些新思想和新方法……当然在他们的论文中也有体现……
真是太神了……我为什么就一直没想起来这些呢囧……
还有就是他们在一起讨论问题时的热烈的场景……原来那些新思想都是在这里出现的，只要一人想出来，大家都知道了囧……
想起我平时有多么孤独……这样的场景只能在比赛时经历……
众多神犇在一起，每人都可以从别人那里获得动力，以及获得各种有用的资料……
而我这样的沙茶，本来就很弱，被神犇们鄙视，又木有好的资料来源，自然也缺乏动力了……

这些因素加在一起的效果，就是我进步的速度明显比他们慢，明显跟不上时代……
回想起从2008年7月以来的这些日子……
前两年不用说了，学习的都是最基础的东西（这些东西在强省都是几个月解决的事，而我用了两年，已经明显落后）……
后面，虽然各位神犇给我提供了一些榜样作用，但是这种作用效果还是太差……
我仍然需要几乎完全靠自己的努力来解决那些巨可怕的问题……
当2011年LCT、各种分块开始烂大街的时候，我还在写线段树、splay tree的模板……
当2012年SAM出现的时候，我还在写一般的SA……
当2013年cdq-gyz分治等各种诡异的思想出现的时候，我还在写动态树的模板……
总是跟不上时代，以至于我相对于其他人变得越来越弱……
用比他们更多的时间，收益却远远小于他们……
每一次听到一道题是ZJ、HN等的资料题、模拟赛题等原题时，就有一种想哭的冲动……

我曾经不止一次地想过，假如我生在ZJ或HN，或者小时候转移到了那里……
这几年的生活会肿么样呢……现在会是什么样呢囧……
不用为了需要一篇论文或者一道题，在google、baidu、citeseerx等上面到处找，找了很久无果……
不用在看知识点或题解时，面对无论如何也搞不懂的部分，急得想撞墙，也木有用……
不用为了一道难题的解决折腾几天，可能几分钟讨论一下就完事了……
不会在比赛后讨论时，别人说到一种很熟悉的方法，自己却从未想到过也从未听说过……
不会每天都在痛苦中度过，却一直跟不上时代，越来越弱……
弱省之所以弱，也就是因为这些原因吧囧……

（听说AH已经连续6年无国家队了，各科国家队都木有……这不奇特，看看AH这环境，将来要有，只能说那个人太高能了囧……至少现在还木有这么神的人……）
当然，我不能改变自己所处的环境，只能在这种环境下选择尽可能优的行动……

我希望能有一个更加精彩的人类智慧时代……

cong 国家队：一出现就能使人吓傻的鼎爷、xyz大爷；压位帝+乱搞帝+人类智慧之神 sy菊苣；几何帝花神。
今年中国队应该可以延续辉煌了囧……
Orz @法法塔 @vfleaking @matthew99等神犇

Mato_No1 2014-04-30 23:25 发表评论

WC2014总结

Mato_No1 — Fri, 14 Feb 2014 08:59:00 GMT

（0）人类智慧是可怕的……

（1）我们要充分发挥人类智慧，探索、测试、改进解决方案的能力……

（2）有些喜闻乐见的题目，和游戏好像木有什么区别囧……

（3）随机和近似是很有力的工具……

（4）尽可能发散思维，想到乱搞办法，是更有力的工具……

（5）学会利用机器和系统的bug和其它有用特点进行乱搞，是(更^*)有力的工具（前面的那个括号内是个正则表达式）……

（6）传统题可能有许多非传统做法，这是很坑的囧……

（7）做题时，不要忘了计算机科学最基本的理论……

（8）有时候，玩也是很有用的囧……

（9）任何时候，永远不要对自己丧失信心和希望，即使在考挂的时候囧……

（10）营员交流和表演节目是可以救命的囧（不知谁还记得@huyuanming11和@lhm_m两位神犇的故事……）

（11）给人类智慧的化身@lemon_workshop（@false_sillycross)跪了……

（12）给提出数据结构最前沿研究内容Retroactive DS，同时在比赛里出人道数据，最终成功保佑了本沙茶的@WJMZBMR跪了……

（13）给虐爆全集训队的@xudyh、@vfleaking、@jcvb跪了……

（14）给比赛前一天玩游戏（当然后来也开始刷CF了……表示神犇为什么都喜欢刷CF囧……），然后在比赛里虐场的@法法塔、@Vensinte跪了……

（15）给一年集训队、一年半候选队的@formyfamily(kzf)跪了……

（16）给下N个法法塔：@ydc、@pyx1997、@matthew99……跪了……

（17）给各位被本沙茶偷来资料的神犇，以及所有虐掉本沙茶的神犇跪了……

（18）其实上面的所有人都叫一个名字：杨芳斐……（顺便剧透一下：本沙茶其实是杨芳斐的第10086个小号……）

（19）没什么可说的，都是蒟蒻的借口罢了……自己果然还是半吊子水平啊囧……

最终总结，用两个字形容本次WC：,b

Mato_No1 2014-02-14 16:59 发表评论

hw1-1 题目提交地址

Mato_No1 — Sun, 27 Oct 2013 04:10:00 GMT

这是我的hw1-1的三道题在Tsinsen上的提交地址：

WF 2003D_Eurodiffusion
WF 2008C_Conveyor Belt
WF 2013G_Map Tiles

各位神犇如果有更好的做法，麻烦把题解或标程发到mato_no1[at]yeah.net（在这里回复也行），3x。

Mato_No1 2013-10-27 12:10 发表评论

统计的力量

Mato_No1 — Fri, 13 Sep 2013 05:29:00 GMT

摘要: Orz zkw！！！最近看完了《统计的力量》……觉得这实在是太神了……原来线段树可以这么写……zkw线段树的思想：先将线段长度N变为2的整数次方，使线段树成为满二叉树，然后就可以通过各种位运算直接链接到某个结点，不必递归了，因此大大减小了常数……本沙茶利用zkw线段树在BZOJ1756和1798上都刷到... 阅读全文

Mato_No1 2013-09-13 13:29 发表评论

关于树分治的问题

Mato_No1 — Sat, 31 Aug 2013 15:39:00 GMT

摘要: （从NOI以后一直在各网站上做水题……谁叫我这么弱做不动难题呢……）（最近实在感觉到弱得令人吃惊……这样下去还混什么集训队啊……于是只好去挑难题了……中间对某些知识点有一些见解……就总结在这里了囧……）（最近见到了比较多的树分治的题... 阅读全文

Mato_No1 2013-08-31 23:39 发表评论

NOI2013 题解&&总结

Mato_No1 — Sat, 20 Jul 2013 15:43:00 GMT

@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css); @import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css); 【Day0】
不说了囧……

【Day1】
meow：
k=2：先将这N个d维向量组成一个N*d的矩阵A，则A*A^T&e1;i&e3;&e1;j&e3;(mod 2)就是向量i•向量j(mod 2)，因此问题有解当且仅当A*A^T不是全1。
随机1*N的向量v，看(v*A)*A^T是否等于v*(N*N的全1矩阵)，如果A*A^T不是全1那么期望试两次就可以得到不等的结果。（如果试了10次都是相等，就视为无解）
如果两边的乘积不等，则找到那个不等的列，设为第i列，则必然存在一个解包含向量i，枚举另一个即可。时间复杂度O(Nd)
k=3：计算(A*A^T)&e1;i&e3;&e1;j&e3;²(mod 3)，即(Σ(x_ik*x_jk))²，即Σ(x_ik1*x_ik2*x_jk1*x_jk2)(mod 3)，对每个向量构造一个d²维向量，为之前的每个向量各维两两相乘的结果，则转化为k=2的情况（只不过将mod 2改为mod 3），时间复杂度O(Nd²)，常数小一点（比如少算mod）可以卡过去。

count：
（正解需要某些很奇怪的性质，本沙茶看不出来，只会85分的）
递推，设F&e1;i&e3;&e1;j&e3;和G&e1;i&e3;&e1;j&e3;表示某层是BFS序列的&e1;i..j&e3;这一段，树的总高度和树的棵数（所求平均值即为F&e1;i&e3;&e1;j&e3; / G&e1;i&e3;&e1;j&e3;）。
则枚举k，若k满足一定条件，则F&e1;j+1&e3;&e1;k&e3;+=F&e1;i&e3;&e1;j&e3;+G&e1;i&e3;&e1;j&e3;，G&e1;j+1&e3;&e1;k&e3;+=G&e1;i&e3;&e1;j&e3;。
问题是这个“一定条件”是什么（最难搞的地方囧）
第零，BFS&e1;j+1..k&e3;这一段的各个结点在DFS序列中的位置递增（这个很显然）。
第一，BFS&e1;j+1..k&e3;这一段的各个结点在DFS序列中的位置之前都必须有在BFS&e1;i..j&e3;范围内的结点，作为它的父结点（这个也很显然）；
第二，DFS序列中，所有在BFS&e1;i..j&e3;范围内的结点的下一个位置如果不是在BFS&e1;0..i-1&e3;范围内的，就必须是BFS&e1;j+1..k&e3;范围内的，因为这表示它的第一个子结点（这个灰常难想到！！！！！！！！！！！！！！！本沙茶就挂在这里了囧……）
对于第零和第一，实际上是给出了k的上限，枚举k时不符合这个条件则退出，而第二则是给出了k的下限（所有的“下一个位置”要填满才能算）；
此外，F和G要用long double（double也会爆，不用担心精度，本沙茶当时还在如何维护平均值的问题上纠结了很久……）
这个做法是O(N³)的，但加上那些优化就可以85分了囧……
（本沙茶当时想到这个做法了，也想到了第零和第一，但木有想到第二，结果挂了……要是真得到85分，总分254，稳的rank1了……真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧，真悲剧……）

train：
史上最水的提交答案……整个就是个NOIP普及组难度的题……
首先分析数据就不难发现这10个点其实是一种模型：
一开始有若干元钱（用变量v 2表示）。
有若干个大块，每个大块可以选择进或者不进，如果进，就要付出一些钱，如果不进，就自动跳转到后面的某个大块。
在每个大块里有若干个（不超过25个）小块，有1或10个变量，每个小块也可以选择要或者不要，如果要，就对所有的变量各加上一个效果值（可正可负）。
目标是所有变量的绝对值之和最大（每个大块末尾会结算一次，然后将所有变量的值清零）
首先每个大块内选哪些小块可以暴力枚举，然后得到最大的总绝对值，设为val&e1;i&e3;（i为大块编号），设如果不进第i个大块，跳到的大块编号为B&e1;i&e3;，第i个大块付出的钱为V&e1;i&e3;。
而大块之间就是一个类似于01背包的模型，设F&e1;i&e3;&e1;j&e3;表示到达第i个大块（尚未作出选择）时，用掉了j元钱的最大总效果值，用F&e1;i&e3;&e1;j&e3;更新F&e1;B&e1;i&e3;&e3;&e1;j&e3;，若不超过一开始的总钱数则用F&e1;i&e3;&e1;j&e3;+val&e1;i&e3;更新F&e1;i+1&e3;&e1;j+V&e1;i&e3;&e3;，要实时保存最优决策。
输出的时候注意一下，那里面有几个点，当钱不够时会自动选择不进当前大块，木有必要作出选择了。

至此Day1完挂。

【Day2】
matrix：
矩阵乘法，十进制快速幂。没了。

penman：
比较猥琐的DP题……
重点是这个：所有的图形都可以拆成单列，一列一列地弄（本沙茶太弱了，这个都木有想起来），然后就是三维DP。
N：设F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列，上下边界分别为j、k行，状态为第st个部分（第0部分为最左边一竖，第1部分为中间若干块，第2部分为最右边一竖）的最优解，计算好一列之后求出一大堆辅助值，就可以使下一列O(1)算出了。
I：设F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列，上下边界分别为j、k行，状态为第st个部分（第0部分为那一竖的左边，第1部分为那一竖，第2部分为那一竖的右边）的最优解，不需要辅助值，直接求即可；
O：可以DP，但更好的办法是枚举左、右、上边界，然后扫描，说它更好是因为知道了左右边界，可以直接引出左边的N和右边的I的最优解。
具体实现的时候细节很多……真折磨人。还有要注意为节省空间，F数组要对i这一维滚动。

foodshop：
首先这是个无向环套树（关于这方面的总结见这里）
枚举开店的那条边，如果是树边，求出该边的较下结点往下的最大长度dist1，以及往其它结点的最远距离dist2，则结果即为min{dist1+x, dist2+L-x}，满足0<=x<=L，L为该边长度。dist1求法不说了，dist2分为两部分，树内的，可以转化为经典DP模型“树的中心点”；树外的，先求出环上的每个结点往树中走的最大长度，作为这个结点的权值，然后就转化为一个带边权和点权的环，对于每个点i，求出max{i、j距离+j的权值}（j为环上的点）的值，这个值可以通过在环上扫描的方法求出：设G&e1;i&e3;为第i个点出发，逆时针走更优的位置最远到哪里。逆时针扫描这个环，然后所有的G就可以在线性时间内求出，求出G后，对每个点分别求出其逆时针更优区与顺时针更优区内的最大值（可以在扫描过程中用线段树维护），即可解决这个问题。
如果开店的边在环上，设其两端点为i、j（i->j为逆时针方向）。很容易发现，如果在这条边上开店，则j的逆时针更优区内的所有点一定是逆时针到这个店更近，i的顺时针更优区内的所有点一定是顺时针到这个店更近，而其它的点则需要额外判断一下是顺时针更近还是逆时针更近（总判断次数为线性）。这样也可以借助线段树在扫描过程中求出每条环边的顺、逆时针更优区，从而转化为与树边的问题一样的模型。时间复杂度O(NlogN)。
不过，对于环边，还有一种更简单的做法（Orz @hza）：
二分最远距离（即结果）D，然后对于环上的所有点，找到这个环上到这个点距离大于（D-这个点树里的最大深度）的点集合（显然是连续的一段弧），对所有点的这种弧求并，如果能覆盖整个环，则最优解=D。

本沙茶Day2全暴力，只拿了暴力分……对付繁琐题的能力太弱了，代码量一大就悲剧……
（后来发现，foodshop的暴力都写疵了囧……枚举开店的边后应该用SPFA求最短路，因为删掉的可能是树边，剩下的不是树……不过数据弱，木有出现这种情况囧……）

至此NOI2013完挂。
———————————————————————————————————————————————————
【总结 && 一些感想】
从上面可以看出，本沙茶在NOI2013中使用的算法都是NOIP普及组以内难度的囧（matrix的矩阵乘法可能略高级一些，但显然也不能超过NOIP难度）……
这些算法都是本沙茶在2009年以前就搞懂的，也就是说，后4年掌握的所有算法，这次都木有用上……
最后一次NOI，竟如此富有戏剧性……居然只考普及组算法……
图论、高级数据结构、字符串、几何、数论、组合……这次都木有考，这也是NOI历史上的一个“创举”了囧……
但尽管如此，本沙茶在此次NOI中仍然暴露出了诸多问题……并不是比赛技巧问题，而是平时埋下的祸根……
想题不够灵活，找不出题目隐藏的特殊性质，特殊情况考虑不清楚，写代码速度太慢……这些都是平时不好好做题，天天颓废的结果……
因此，这次挂掉，也是理所应当的事……

遗失了过去，因此，现在后悔了…………………………………………………………………

不过，不管肿么讲，还是混进了集训队……集训队是一个新的开始，每天都面临巨大的挑战，同时每天都能得到巨大的提高……
虽然本沙茶现在很弱，应付难题的能力还远远不够，但经过这一年的训练，相信可以改变这一切，尽快脱菜……
希望这能是一个转折点。
50，12，6，4，1。

———————————————————————————————————————————————————

膜拜本次虐场神犇
@鼎爷
@xudyh
@xyz111
@hzaskywalker(FFT)
@hzhwcmhf
@zhj
@鱼丸
@sunzhouyi
以及众多虐掉count、penman、foodshop的神犇……

Mato_No1 2013-07-20 23:43 发表评论

【复仇之战】AHOI2013 Round2 总结

Mato_No1 — Mon, 17 Jun 2013 14:37:00 GMT

前言：
从2006年的全国第一，到2012年的全国第二十；
从国家队每年必有，到正式选手NOI Ag都拿不到；
时间可以改变一切，仅仅几年，我们共同见证了一个省从强省变成弱省；
而无比奇(keng)特(die)的省选题，又使得许多难以想象的事情发生了；
不知现在，还有谁记得一年前的那场风波，两年前的那场风波，三年前的那场风波；
不知现在，还有谁记得那些被奇(keng)特(die)的省选题和谐掉的众神；
相关链接0
相关链接1
相关链接2
———————————————————————————————————————————————————
今年，安徽省选终于不再是一场闹剧。
希望这能成为一个转折点。下面进入正题。
———————————————————————————————————————————————————

本沙茶还是考废了……6题有3题被卡常数，而且卡到和暴力差不多的得分……
不过毕竟复仇成功了……好像还进了A队……
不过像我这么弱到NOI也是被虐的份……

下面上题解：
【Day1】
coin：
首先那个贪心性质是比较好看出来的囧……就是如果每个面值都是上一个面值的正整数倍，则要得到一个价格的最小张数，总是先用最大的，不够了再用第二大的……以此类推。
（证明：假设价格为s，某个方案(a1, a2...am)(ai为第i大的面值使用张数)对于最大的面值不是按照这样的，则有s-a1*v1>=v1；若a2*v2>=v1，则将(v1/v2)张第二大的换成一张第一大的显然更优，若a2*v2=v1-a2*v2>=v2，可以对第三大的继续分类讨论，这样一直到第m大的，必然会有一个出现可换成更大面值的情况，也就是该方案必然不是最优方案；如果最大的面值按照这样，后面的面值不按照这样，仍然如此）
这样只要所有面值确定，配成任何一种价格的最优方案也就确定了，且可以随着面值从大到小的一一确定，不断更新最优方案；
由于本题价格<=100000，所以考虑搜索。一开始搜最大的面值，然后在搜后面的面值的时候，只能枚举其因数。优化：
（1）初始定界：根据样例2+简单分析可以得出，使用2的幂的面值是一种比较优的方案，因此用它进行初始定界，可以大大方便后面的卡界；
（2）容易证明，如果所有价格中最大的为maxw，则最大的面值必然在[maxw/2, maxw]之间；
（3）很重要的剪枝：容易证明在最优方案中，相邻两个面值的比值必然是质数（否则设vi/v(i+1)不是质数，存在>1的因数d，则加入vi/d这个面值以后……）。因此，只需要预处理出2~100000间所有数的质因数即可；
（4）一些启发式优化（卡界）；
（5）卡时；
综合使用以上方法可以得到85~100分；注意搜索中的数组分层问题；

cube:
被卡常数了，真悲剧……
本题的猥琐之处在于它的时空限制，时限1s，空限64M……给跪了！！！
只要求出(0, 0, 0)-(200, 200, 200)间的每个格子是否被覆盖，然后再做一次floodfill就行了囧……
实现方法有很多，最好的是三维树状数组（改段求点，一个数组即可，且可以用short）。
问题是，本题的floodfill如何实现？递归DFS，爆栈；人工栈DFS，MLE；BFS，在压位的情况下可以勉强卡过空间，但常数被卡了……
（求神犇好的解决办法囧……）

square：
首先两个不相交子矩形要么在X方向上不相交，要么在Y方向上不相交，要么在X、Y方向上都不相交……（废话）
因此结果等于(X方向上不相交的全黑子矩形个数)+(Y方向上不相交的全黑子矩形个数)-(X、Y方向上都不相交的全黑子矩形个数)；
前两个显然灰常好求，第三个，只要求出每个点左上、右上、左下、右下四个方向里面的全黑子矩形个数，也灰常好求……
不过有一个细节：如何求出以某行/列为最下行/最右列的全黑子矩形个数？
一种方法是往左/右（或上/下）第一个比它矮的地方不断迭代，但这样遇到阶梯状的会被卡掉；
正确方法是找到往左/右（或上/下）第一个比它矮的地方，然后以这里为右下角的全黑子矩形个数=以那个地方为右下角的全黑子矩形个数+这里的高度*两个位置的距离；
然后就是严格的O(N²)了（不过数据很弱，本沙茶使用会被阶梯状的卡掉的办法也AC了囧）；

至此Day1完挂。

【Day2】
（全DS题什么心态？？？？？？）
homework：
第一问……是人都会吧囧……
第二问……傻眼了囧……
其实看到第二问这种不能合并的东东就应该想到分块……这里说一种时间复杂度为O(N^5/3)的分块方法
注意本题的两问都满足区间减性质，即“A[l1..r1]中关于[l2..r2]范围内的数的结果=A[l1..r1]中关于[0..r2]范围内的数的结果- A[l1..r1]中关于[0..l2-1]范围内的数的结果”。
因此，可以先对[l2..r2]这一维离线，然后按照值递增的顺序逐个加入A数组中的所有元素（一开始A数组为空），每加入一个数，就对l2或r2等于这个数的所有询问计算结果，这样原题就转化为了这个问题：
一个长为N的序列，一开始所有位置都为空，现在有两个操作：（1）在某个空位置插入一个数；（2）询问目前某区间内的数的总数，以及不相同的数的总数；
这两个问题都可以分块解决：设S1[i][j]和S2[i][j]分别表示目前第i块到第j块中数的总数以及不相同的数的总数，同时维护bool FF[i][j][k]表示第i块到第j块是否出现数k。插入一个数时直接维护S1，根据FF维护S2即可。显然块大小sz应取N^2/3，总的时间、空间复杂度均为O(N^5/3)。
这样……本题时限10s应该能过了吧囧……但是常数……万恶的常数啊！！！！！（事实上后5个点在本机上都是8.5s左右的，只有第4、5个点T，但在那里不知为什么几乎全T了……）

disconnected：
这个……本沙茶真心不会搞囧……
@drcrow神犇说有一种按询问分块的办法，其思想具体见他今年CTSC的论文……但本沙茶智硬理解不了……
求各位神犇解释……

diff：
（很水的题，很坑爹的常数……本题真是推广SAM的利器……）
本题的核心在于算任意两个后缀的LCP之和，其它的很容易推导出来……
后缀的LCP，“正常人”的第一反应是SA……
求出SA及height后，转化为线段树问题……然后就直接搞定了……
但是……………………………………………………………………………………………………
本题N<=500000，时限2s！！！！！！！！！！！！！！！！！！！！！！！！！！！！
如果求SA，不管是倍增还是DC3都会T（把SA求出来就T了）
因此，正解其实是SAM，把这个串的SAM求出来之后，直接用DFS求次序，再求height……这里的时间复杂度就是线性的了。
（WJMZBMR：现在SA早就过时了，要用SAM！！！不，其实SAM也过时了，现在是Suffix BST以及2^K Substring BST，但考虑到AH太弱了，同情一下，降低一点难度……）

至此AHOI Round2完挂。
（不过许多人都放水了囧……他们说我去年滚粗，太可怜了，要照顾我……于是我这样的弱智就A队了……）
（HSAAHNU进了6个……太可怕了，坐等NOI组团虐场……）

Mato_No1 2013-06-17 22:37 发表评论

【AHOI2013复仇】带插入区间第K小的“动态标号”做法

Mato_No1 — Wed, 29 May 2013 13:52:00 GMT

首先，Orz @vfleaking！！！出此神题！！！
原题地址
@vfleaking神犇空间里的N多主流解法：3 0 6 5

这里讲的是本沙茶乱搞出的一种解法——“动态标号”（神犇不要鄙视）。
首先，如果没有插入，这题是裸题，按值建线段树套平衡树即可，O(Nlog²N)；
然后，如果有插入，但可以离线，这题也是裸题，只要找到所有插入操作插入的位置，得到最终的序列，然后从头处理操作，一开始将中途插入的所有位置都设为无效值，插入就成了修改。
问题是，又有插入，又强制在线，肿么办？？？

注意到在求解区间第K小的按值建线段树套平衡树做法中，是对线段树的每个结点[l, r]都建一棵平衡树，表示值在[l, r]范围内的所有位置，然后，通过找某一区间内值的个数，就可以得到这一区间内值在[l, r]范围内的位置的个数。事实上，如果平衡树结点的权值，也就是位置，不用0到(N-1)的整数表示，而用任意的递增序列表示，也是可以的，只不过此时需要维护一棵这个递增序列的平衡树，找到第K小的值，也就表示第K个位置。也就是说，这些平衡树结点的权值其实只表示相对位置，即“标号”。

因此，可以得到这样的做法：一开始设置一个递增的标号序列，第i个标号表示第i个位置，并且用它建立线段树套平衡树。然后，每次要插入的时候，就找到待插入位置，为它申请一个新的标号，在它两个相邻位置标号之间即可。一般来说，标号都是整数，在申请新标号时，如果它左右两边相邻位置的标号分别是a、b，若a+1
接下来的问题就是如何设置标号使得尽可能少的重新分配标号。本沙茶在多次尝试之后得出了比较好的办法（神犇肯定有更好的办法，不要鄙视），一开始第i个位置的标号为i*2*10⁹（显然标号是个long long），然后，每次如果a+1s, a+K1*2^s]（K1是个预先得知的值）范围内的标号全部重新分配，使得它们等间距，并且在所有涉及这些标号的平衡树里面对应的标号也要改掉，这里要特别注意，不能找到一个改一个，而要在所有涉及到的标号全部找到后一起改！！（否则会出现改过的后面又被改的情况，本沙茶就是在这里卡了很久……）此外，这里可以加入优化，即记录每个标号对应的值（注意，是实际的值，不是位置），这样在线段树里面就可以定向而不用试了囧……

@vfleaking神犇的第1、2个点纯随机，结果不会出现a+1=b的情况，也就是根本没有重新分配……（囧），但3、4个点则是特殊构造的，它总是在开头、正中间、结尾这三个位置插入，结果经常出现标号挤在一起然后重新分配……实测结果为总共重新分配了40~50W个结点……最后这两个点本机测18s……

代码

后记：
事实上这种动态标号是可以被卡掉的，有一种方法能让它每logK0次操作就将所有的标号全部重新分配一次，从而总的重新分配次数变为O(NM/logK0)。因此，需要更好的动态标号算法，使得它在任何情况下都可以保证总的重新分配标号的次数在一个可接受的范围内。在N<=10⁵的时候（再大就不能动态标号了，稳T），这个“可接受的范围”可以控制在大约O((N+M)*N^1/3)，这是肿么搞的呢……以后再说囧。

Mato_No1 2013-05-29 21:52 发表评论