[BZOJ 1601]灌水

一定有人问我我死哪里去了……

这题挺简单的,但是对于zzs这种图论渣来讲,是巨大的困难……

这题可以造一个虚拟结点,所有点和它连该点点权长的边,其他边的正常造,然后剩下MST的就很简单了……

然而第一次写Prim……哎

代码:

继续阅读

[BZOJ 1699]排队

好久没写题解了……

净去颓颓颓了……

这题是ST裸题,顺便复习一下ST。

那个I/O优化提示就是赤裸裸的威胁,赤裸裸的威胁啊!

代码:

继续阅读

[洛谷 P1967]货车运输

倍增LCA经典题……

这题的做法就是求最大生成树,然后用倍增LCA法求瓶颈路……

注意一下,两点不连通时输出-1(其实这个用并查集判断不就行了……)!!!

代码:

继续阅读

[BZOJ 2588]Count on a tree

泥萌感觉我还能说什么……

这题就是DFS序套主席树,顺便带上倍增LCA,但有两大坑点:

  1. 存放数据不一定要用long long,但输入必须要。
  2. 输出数据蛋疼,最后一行行末没回车。

代码:

继续阅读

[BZOJ 2296]随机种子

现在才明白,我数论其实不好……

这题也不怎么难,需要一点灵感构造

代码:

继续阅读

[BZOJ 3211]花神游历各国

这题和3038几乎一样啊……

但是注意有的喜欢度可能为0,这种情况不处理的话时间效率duangduangduang……

代码:

继续阅读

[BZOJ 3038]上帝造题的七分钟2

这题也真是的……

其实也不难,开多了就成1了,成1了再怎么开也是1……所以暴力单点修改+配合标记乱搞搞就行了

代码:

继续阅读

[BZOJ 2243]染色

树剖好题……

2243记录

这能说明几个问题:

  1. 人傻自带大常数
  2. 不看题解难AC

继续阅读

[BZOJ 1355]Radio Transmission

KMP处女作……

然而这题只用得着失配函数= =

话说常见的OI考试中考KMP好像就只有考循环节问题的了= =

代码:

继续阅读

[BZOJ 4034]T2

这个题名字也真是……

思路和我以前提到过的NOI2015 D1T2的做法是相似的,不过这题貌似int会爆精度……我这SB开始没发现,后来改了还慢慢出错……然后慢慢改……终于AC了……

我本来以为这个YY思路只有我和诸位读者知道,结果发现是貌似是ydc发明的……比我早的高明的不知哪里去了……

代码:

继续阅读