爆零后的感受外加一道强联通分量HDU 4635的题解

今天又爆零了,又是又,怎么又是又,爆零爆多了,又也就经常挂嘴边了,看到这句话,你一定很想说一句””,弱菜被骂傻,也很正常啦

如果你不开心,可以考虑往下看。

翻到E(HDU 4635 Strongly connected)题,这么短的题目,肯定要先看啦。然后D(LightOJ 1229),然后C(ZOJ 2243),然后F(HDU 4711),然后B(CodeForces 385D),然后看A(HDU 3889)好吧,我承认,A题看了一眼就不看了,B题一看是线段什么有点几何的味道就果断放弃,然后C题,傻傻的理解错题意,提交一直WA,然后没办法,看E题,想到只要保证最后至少两个连通分量,就可以满足题意,然后要求最大值,那就保证有且仅有两个连通分量就可以了,对于一个连通分量最多只能有x(x-1)边, x表示顶点数 ,然后得出一个式子,边数f = n*n-n-1+x*x-(n+1)x;当x更(n+1)/2的差值越大,f越大,换句话说,只要把一个连通分量顶点个数最小的独立出来,把其它的连通分量都合并成一个连通分量就可以了,

可是我没考虑下面这种情况

 

这时候如果把3独立出来,5、9、7弄成一个连通分量,那么3也会跟5,9,7合并成一个连通分量,所以不能选3,

最小的不能选,那就选5吧,把3、7、9合并,可以。

也就是说是要把顶点个数尽量小且入度或者初度为零(一个连通分量看成一个点)的连通分量独立出来。

view code

红色部分就是思维漏洞

 

。差一点,不过acm没有差一点,只有ac或者没ac.

下面再来总结一下题目吧
Problem A
HDU 3889(水题,不会做)

Problem B
CodeForces 385D(dp,题意尚不明确)

Problem C
ZOJ 2243(什么treap,被坑)

笛卡尔树:

  每个节点有2个关键字key、value。从key的角度看,这是一颗二叉搜索树,每个节点的左子树的key都比它小,右子树都比它大;从value的角度看,这是一个堆。

题意:以字符串为关键字key,数字为关键字value,构造一个二叉搜索大堆,最后按要求中序遍历 笛卡尔树的构造。

view code

//[a-z]表示读取的字符串由a-z中的字符组成,其余的字符为定界符scanf/fscanf 的%[]和%n使用方法



Problem D
LightOJ 1229(博弈,不会)

Problem E
HDU 4635(。。。。。。。。。。。。。。。。。,此处省略一万字)

Problem F
HDU 4711 。。

爆零后的感受外加一道强联通分量HDU 4635的题解,,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。