比较水
第一题是求一个最小割点数,首先想到的是贪心
搞了十分钟发现不对,再搞搞图论
搞了五分钟发现也不对,只会求单个割点
再看看题,画个方格子….
然后发现
mdzz最多不就两个就可以了吗,肯定有一个水会被逼在墙角上
第二题是求一个在唯一最短路径上的点数
一开始在纠结floyed怎么求最短路条数的问题,然后发觉不是有spfa么(笑)
做着做着又发现一种特殊情况,
有个点是两条最短路径的共有点,想了5分钟发现
只要i~k与k~j的路径数乘一下,看看够不够i~j的路径数就可以了
第三题特™眼熟,又是一个维护位的问题
xor就直接前缀和然后拆位求01个数相乘
and就是求拆位连续一
or是总数减去连续0
想完开打,发现有biao…
(嘿嘿嘿)
成功拿下第二个AK
300300
100100
100100
100100