Topcoder口胡记 SRM 562 Div 1 ~ SRM 592 Div 1
跨越美利坚面试创业技术培训 2018-02-02
传送门：https://284914869.github.io/AEoj/index.html
Topcoder SRM 562 Div 1 - Problem 1000 InducedSubgraphs
当K*2<=N的时候，显而易见的是编号为i（K<=i<=N-K+1）的点一定会形成一条链。
枚举合法的这样的链，剩下的暴力dp吧。
当K*2>N的时候，显而易见的是编号为i（N-K+1<=i<=K）的点一定会形成一个联通快。
如果把这个联通块去掉，树会形成若干个不相交、不接触的小联通块，且这些联通块的大小之和一定。
如果把树的一个点提根，进行上下dp，就能很方便地进行统计答案。
Topcoder SRM 563 Div 1 - Problem 950 CoinsGame
好惨惨啊！这么简单的题竟然没有自己想出来~~
我们称棋子A和棋子B等价，当且仅当它们只会同时在这个棋盘上，或同时离开棋盘。
一个显然的结论就是，若A和B等价，B和C等价，那么A和C等价（即具有传递性）
所以可以通过bfs求出所有等价点对，通过并查集合并。用总情况数减去不合法情况数就好了。
Topcoder SRM 564 Div 1 - Problem 850DefectiveAddition
topcoder罕见的水题啊！
如果我们已知了每个数相与原数不同的最高的二进制位，（设ta为pi）
那么对于第k位，如果有x个数满足pi>k，由于这些位的异或值确定，
所以，当x>0时，有2^(x-1)种方案。
由于当x=0时会有意想不到的事情发生，所以稍微dp一下就好了。
Topcoder SRM 565 Div 1 - Problem 1000UnknownTree
topcoder罕见的无思维难度码农题。。
分两种情况讨论：A、B、C在同一条链上。以及A、B、C不在同一条链上。
Topcoder SRM 566 Div 1 - Problem 1000 FencingPenguins
http://www.cnblogs.com/Blog-of-Eden/p/7852426.html
Topcoder SRM 567 Div 1 - Problem 1000Mountains
一道很妙的题哇。
一个显而易见的结论是，一座山的可见范围，一定是一段连续的区间。
考虑编号从大到小的放置山。
如果当前山可见，并且可见范围不是从最左边到最右边。
那么又有一个很显然的结论，当前山只有两个合法位置。
考虑如果当前山不可见，那么这座山对之后要放的山没有丝毫影响。直接乘上这座山合法的位置数即可。
如果这座山到处都可见？这是个较严重的问题，
我们考虑，把所有这样的到处都可见的山全部拿出来。（按照编号从小到大）（我们称之为大山）
相邻两座大山之间夹着若干个小山。
对于大山L和大山R，（L<R），很显然1到L-1和R+1到n的山对这之间的山的放置没有影响。
所以可以枚举相邻两个大山的位置，对之间的小山位置进行dfs。
dfs的复杂度是2的幂次，可以接受。
Topcoder SRM 568 Div 1 - Problem 1000DisjointSemicircles
异常兴奋！又一道喜闻乐见的分情况讨论题！
我们设有m对连线已经确定。（m<=n）
当m比较大的时候，暴力似乎行。O(2^(2n-2m-1)*C(2n-2m,n-m))
当m比较小的时候，枚举这些连线分别在上方还是在下方。
方案合法当且仅当这个半圆里面与它同向的点的数量是偶数。
设向上为1，向下为0，一个半圆相当于限制了这个半圆之中的变量的xor值为1或者是0.
对于前缀xor数组，相当于限制了两个位置上的数xor为1或者是0。
这个用并查集来检查一下是否合法即可。
Topcoder SRM 569 Div 1 - Problem 1000MegaFactorial
我真是个爱学习的孩子，在秋游的时候还在想这道题~~
简单来说，由于B<=10，我们只关心的是B的最小质因子p以及它的指数q。
简单的说，我们只要统计N!K的值中，质因子p的指数Q，计算Q div q就好了。
由于对1e9+7取模，div比较麻烦，所以：Q div q = (Q - Q mod q) / q
再由于K比较小，所以矩乘一下就行了。
Topcoder SRM 570 Div 1 - Problem 900CurvyonRails
谁来治一治我普及组级别的网络流水平啊o(╥﹏╥)o
复杂地来说，黑白染色，每个格子拆成两类点：横方向点和纵方向点，
由于两份流量都流入横方向点或都流入纵方向点都会产生1的费用，
所以将方向点拆点，连两条边，一条流量为1，费用为0；另一条流量为1，费用为1。
Topcoder SRM 571 Div 1 - Problem 1000CandyOnDisk
Topcoder也会出这种无脑题？
若a能到达b，那么b也能到达a。
如果从一个圆到达另一个圆，其可到达范围是两个圆环。
每个圆环当作一个点，就可以建图跑spfa。
需要特判一些特殊情况(*/ω＼*)
Topcoder SRM 572 Div 1 - Problem 1000NextAndPrev
枚举分界点，贪心求最小代价就行了？
由于口胡我可能没想清细节。。
Topcoder SRM 573 Div 1 - Problem 850WolfPack
以我的智商看来是做不动这种脑洞题啊。
每次x可以+1,-1,不变，y也可以+1,-1,不变，且x,y至少有一个变，这个很烦啊。
根据题解的做法，我们把坐标轴旋转45°，题目变成了：
每次x可以+1或-1，y也可以+1或-1，且x,y独立！这一步转化好妙啊！
接下来就好做了，对于一个终点Z，
对于Zx，可以求出x方向上的方案数；对于Zy，可以求出y方向上的方案数。
答案是sigma Zx,Zy [Fx(Zx)*Fy(Zy)] = sigmaZx[Fx(Zx)] * sigmaZy[Fy(Zy)]
TopCoder SRM 574 Div 1 - Problem 1050 Tunnels
对于给出矩形中的非从左边连到右边的地道，这些地道会形成括号序列，
对于从左边穿到右边的地道，可能是从左往右，也可能是从右往左？
从上往下进行dp？
似乎怎么想也想不清啊。。反正是口胡，放弃思考了。。
TopCoder SRM 575 Div 1 - Problem 1000 Tunnels
每次想网络流题都要想好久好久~~。。
先进行黑白染色，由于L字形角落的格子一定黑色，两端的格子一定白色，
两端的格子，一定有一个在奇数行，一个在偶数行。
源点流向奇数行，偶数行流向汇点就行了。
TopCoder SRM 576 Div 1 - Problem900 CharacterBoard
Topcoder罕见的放松题啊。
我们考虑给你的矩阵中两个元素x和y，若它们在字符串中的位置相同才可能发生冲突。
位置相同当且仅当x和y的位置差能被Len整除，这样的len最多只有i0*j0*sqrt(i0*W)种
对于这样的每一种len，暴力判断是否合法以及计算方案数，
如果不存在这样的冲突，方案数为26^(Len - i0*j0)。所以等比数列求和即可。
TopCoder SRM 577 Div 1 - Problem1000 BoardPainting
又是网络流。┭┮﹏┭┮
好难哇，怎么做啊。。
在此给出周欣的算法：
如果把相邻两个格子之间新建一个虚点，选择这个虚点，就表示这两个格子在一次染色中完成。
由于染色过程不能转弯，这限制了一个格子横放向上的虚点和纵方向上的虚点不能同时选。
这就是二分图最大独立集问题，可以用网络流解决
TopCoder SRM 578 Div 1 - Problem1000 DeerInZooDivOne
看到题目描述中的鹿角，莫名想到乔巴~~
简单地说，可以枚举两个联通块之间的分界边，然后进行dp，
考虑f[a][b]表示以a为根节点，b为根节点，a联通块与b联通块同构的最大大小。
a的若干个儿子和b的若干个儿子一一匹配，其f值的和+1就是f[a][b]。
这就是二分图最大权匹配
TopCoder SRM 579 Div 1 - Problem1000 RockPaperScissors
如果当前我们知道了对手之前扔出a个剪刀，b个石头，c个布，我们可以通过dp预处理求出下一次对手扔剪刀、扔石头、扔布的概率。
然后我们当前做出最优决策，使这一回合的期望得分尽可能的大。这也是一个dp。
TopCoder SRM 580 Div 1 - Problem1000 WallGameDiv1
简单博弈，我们可以证明，Rabbit不会将棋子向上移，
当Rabbit在某一行，且下方有障碍时，Eel不会放障碍，
以此我们得出一个结论，Rabbit在一行中的运动是，左，右，左，右，左，......最后下。
我们还可以得出一个结论，当Rabbit在某一行某一列上，且此时Eel没有在它下方放上障碍，那么Rabbit也一定会往下走了（往左右走之后还一定会回到这里）。
所以可以用区间dp。f[i][L][R][0 or 1]表示第i行，已经放了L到R的障碍（即Rabbit已经走过了L到R），此时Rabbit在L-1还是在R+1。
每次Eel决定Rabbit下方是否有障碍，如果有障碍，则Rabbit决定往左或往右。
据说cwy用奥妙重重的骗分方法A了此题？说不定那也是对的喔。。
累了。。
还有581到592。。下次回来再写吧
