传送门: 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 850 DefectiveAddition
topcoder 罕见的水题啊!
如果我们已知了每个数相与原数不同的最高的二进制位,(设 ta 为 pi)
那么对于第 k 位, 如果有 x 个数满足 pi>k, 由于这些位的异或值确定,
所以, 当 x>0 时, 有 2^(x-1) 种方案.
由于当 x=0 时会有意想不到的事情发生, 所以稍微 dp 一下就好了.
Topcoder SRM 565 Div 1 - Problem 1000 UnknownTree
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 1000 Mountains
一道很妙的题哇.
一个显而易见的结论是, 一座山的可见范围, 一定是一段连续的区间.
考虑编号从大到小的放置山.
如果当前山可见, 并且可见范围不是从最左边到最右边.
那么又有一个很显然的结论, 当前山只有两个合法位置.
考虑如果当前山不可见, 那么这座山对之后要放的山没有丝毫影响. 直接乘上这座山合法的位置数即可.
如果这座山到处都可见? 这是个较严重的问题,
我们考虑, 把所有这样的到处都可见的山全部拿出来.(按照编号从小到大)(我们称之为大山)
相邻两座大山之间夹着若干个小山.
对于大山 L 和大山 R,(L
所以可以枚举相邻两个大山的位置, 对之间的小山位置进行 dfs.
dfs 的复杂度是 2 的幂次, 可以接受.
Topcoder SRM 568 Div 1 - Problem 1000 DisjointSemicircles
异常兴奋! 又一道喜闻乐见的分情况讨论题!
我们设有 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 1000 MegaFactorial
我真是个爱学习的孩子, 在秋游的时候还在想这道题~~
简单来说, 由于 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 900 CurvyonRails
谁来治一治我普及组级别的网络流水平啊 o(﹏)o
复杂地来说, 黑白染色, 每个格子拆成两类点: 横方向点和纵方向点,
由于两份流量都流入横方向点或都流入纵方向点都会产生 1 的费用,
所以将方向点拆点, 连两条边, 一条流量为 1, 费用为 0; 另一条流量为 1, 费用为 1.
Topcoder SRM 571 Div 1 - Problem 1000 CandyOnDisk
Topcoder 也会出这种无脑题?
若 a 能到达 b, 那么 b 也能到达 a.
如果从一个圆到达另一个圆, 其可到达范围是两个圆环.
每个圆环当作一个点, 就可以建图跑 spfa.
需要特判一些特殊情况 (*/ω\*)
Topcoder SRM 572 Div 1 - Problem 1000 NextAndPrev
枚举分界点, 贪心求最小代价就行了?
由于口胡我可能没想清细节..
Topcoder SRM 573 Div 1 - Problem 850 WolfPack
以我的智商看来是做不动这种脑洞题啊.
每次 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 - Problem 900 CharacterBoard
Topcoder 罕见的放松题啊.
我们考虑给你的矩阵中两个元素 x 和 y, 若它们在字符串中的位置相同才可能发生冲突.
位置相同当且仅当 x 和 y 的位置差能被 Len 整除, 这样的 len 最多只有 i0*j0*sqrt(i0*W) 种
对于这样的每一种 len, 暴力判断是否合法以及计算方案数,
如果不存在这样的冲突, 方案数为 26^(Len - i0*j0). 所以等比数列求和即可.
TopCoder SRM 577 Div 1 - Problem 1000 BoardPainting
又是网络流.﹏
好难哇, 怎么做啊..
在此给出周欣的算法:
如果把相邻两个格子之间新建一个虚点, 选择这个虚点, 就表示这两个格子在一次染色中完成.
由于染色过程不能转弯, 这限制了一个格子横放向上的虚点和纵方向上的虚点不能同时选.
这就是二分图最大独立集问题, 可以用网络流解决
TopCoder SRM 578 Div 1 - Problem 1000 DeerInZooDivOne
看到题目描述中的鹿角, 莫名想到乔巴~~
简单地说, 可以枚举两个联通块之间的分界边, 然后进行 dp,
考虑 f[a][b] 表示以 a 为根节点, b 为根节点, a 联通块与 b 联通块同构的最大大小.
a 的若干个儿子和 b 的若干个儿子一一匹配, 其 f 值的和 + 1 就是 f[a][b].
这就是二分图最大权匹配
TopCoder SRM 579 Div 1 - Problem 1000 RockPaperScissors
如果当前我们知道了对手之前扔出 a 个剪刀, b 个石头, c 个布, 我们可以通过 dp 预处理求出下一次对手扔剪刀, 扔石头, 扔布的概率.
然后我们当前做出最优决策, 使这一回合的期望得分尽可能的大. 这也是一个 dp.
TopCoder SRM 580 Div 1 - Problem 1000 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 了此题? 说不定那也是对的喔..
来源: http://www.bubuko.com/infodetail-2485258.html