分类： ACM题解

发布于

[带权并查集] HDU5441 Travel

扯淡的就是我们队训练赛两个队友一个过了一个一人题一个过了一个5人题，然后我这边有两个通过率90%+的卡住没过，呵呵了真的是，怀疑人生。

这个后来补题也是wa，计数并查集合并公式推错（这么简单卧槽我小学数学没学好），然后最愚蠢的是排序的时候把m写成了n，wa到哭。

其实当时第一眼看就大概想到是用计数的并查集做，但是没想到自己能写这么挫，而且当时主要是被那个二叉树卡住（怀疑人生+2），那个真的只要简单粗暴就好我却想多了，唉

继续阅读“[带权并查集] HDU5441 Travel”

发布于

[强连通分量][DAG][DP] UVa11324

算是学到了缩点构造新图的方法吧emm有点笨

有环的图一般都有点难倒腾，所以这种都是遇见了先求scc，变成DAG以后再想办法求解。

分析题意后可以发现，对于DAG，求出来的其实是一条路径，因为如果有分叉的话分叉的不同子树之间就没有办法互通了。令每个缩点的权值为含点的个数，这样就转化成了DAG上的最长路问题了。

错误：scc每次都会出现漏初始化错误。。。还有就是缩点之后的节点标记与原来的节点意义不同，要注意。

  继续阅读“[强连通分量][DAG][DP] UVa11324”

发布于

[割点][强连通分量] POJ1523 SPF

这题略坑。。。输入的可以是不连续的点，我一开始都从1开始dfs，WA了n发发现数据里可能没1这个点。。。GG

求割点的话本身倒是很裸，但是还要求出生成的子集个数，也是试了各种奇怪的方法。。。。后来发现把low[v]>=pre[u]的子节点v的数量记下来就可以了，至于证明。。。直觉证明法吧
继续阅读“[割点][强连通分量] POJ1523 SPF”

发布于

[CF][思维][预处理][枚举] CF1016C Vasya And The Mushrooms

这场CF也是崩了。。AB太慢而且wa了n发，C知道正确做法然后wa了3发剩20min放弃了。然后今天手算了五分钟ac emmmmm

这个要做到每个格子都只走一次，就必须先蛇形然后转圈，只不过中间从哪一点开始转圈决定了最后的答案大小。样例给的就是两种极端情况，一种是从一开始就开始转圈，另一种是一直蛇形直到最后。

预处理的话左边的从左往右推，右边的从右往左推，主要是右边的计算有点绕（其实也不是很绕主要是当时心态崩了emmm 继续阅读“[CF][思维][预处理][枚举] CF1016C Vasya And The Mushrooms”

发布于

[暑期集训][数学][数论][组合数学] SPOJ Square-free integers

（其实一开始想的是错的，实际上就是mu[i]^2的前缀和S

先考虑对立面，2到n之间有多少个数可以被平方数整除？可以枚举从2到sqrt(n)，然后把可以被这些数字的平方整除的算上，也就是n/(i^2)个对于每个来说。但是这里会有重复的，比如i分别为2，3，6时，算上了4，9，36，其中36被算了两遍，所以要加加减减。（好吧其实我也还没自己证明出来但是今天有点疲回头填坑ooorz
继续阅读“[暑期集训][数学][数论][组合数学] SPOJ Square-free integers”