4.28总结

反正今天考的很糟

看到第一题的第一眼,就发现好像是我之前写过的一道题,瞬间兴奋,匆匆看了一眼题面,感觉就是它了,就先走了。

然后看t2,想了一会,并没有很长时间,仍没有想好暴力,8点多一点就走了,看t3,第一眼又感觉是之前做的一道题,但那道题现在还不会,估计不行,仔细看了看题面,不是,吓死了

40分很简单,想到二次离线莫队,想到快9点,感觉应该可以,直接就写了,写到该离线的时候,发现之前想的有问题,不能这样做,时间上过不去了,这时候9.30了,于是赶紧开始打暴力,结果看错了要输出的量,一直调,还不对,10多的时候,还没发现看错了要输出的量,赶紧回去看第一题,哦,不是原题,但是很像,想套一个回滚,但是不知道怎么合并,边数太多,实在不会,莫队不行,当时也没想到分块,70分也不知道怎么删边,拿了暴力就走了,

终于到了第二题,看完题以后,就觉得今天彻底凉了,一看就是暴力+打表,但是不知道时间够不够,结果连暴力都模模糊糊不确定,打了一下也没过样例,就剩下一个小时了,答案也有点离谱,回去看第三题,终于发现,输出的量不是要求的量,11.00终于过样例了,回去看t2,一直到考试结束终于过了样例

总结:看到有相似的题,更应该静下心思考,log的不行,上莫队,分块,二分判定,思考的时候,多往题目性质上思考,数据结构上思考,还有位运算

题解:

t1: 分块+倍增+Kosaraju

 考试的时候没有往分块上想,太不行了,不过还是不知道_Find_first到底能不能用

t2:

dp

这个不会也不亏了,从一开始理解的题意就是错的,竞赛图这个东西应该也不会考,就不学了吧。

f[i]表示i个点的带标号竞赛图个数,g[i]=表示i个点的带标号强连通竞赛图个数.

题解:

 f[i]=2^[i*(i-1)/2]

g[i]=f[i]-不合法的

枚举1所在的连通块的大小i,1所在的连通块后面的点数之和j : ans[i+j]+=C(n-1,i-1)*g[i]*C(n-i,j)*f[j]*f[n-i-j];

t3:

算了吧,太难了,要自闭了

原文地址:https://www.cnblogs.com/xsm098/p/14715973.html