[BZOJ 1370]团伙

哎……做了这题,我才敢说我真的会了点并查集

这是道很经典,很有意思的并查集题目

其实也不难,每个点记录敌人集合然后乱搞即可

代码:

继续阅读

[BZOJ 1053]反素数

终于A了……

此题坑点多~

据说只需要预处理12个素数,然而我预处理了4648个……so sad

然后DFS就可以了

我无力吐槽了……我就是智商感人啊

代码:

继续阅读

[BZOJ 3524]Couriers

这道题有了主席树,就是裸题了……

只要用主席树维护出现次数,然后二分求解即可

但是!数组一定要开大,开大,再开大,重要的事情说三遍!

代码:

继续阅读

[POJ 2104]K-th Number

我擦终于A了这题了!

主席树坑点多……

最好不要写指针主席树,不然容易TLE……(自带常数?

并且注意,一定要把数组开大,开大,再开大,重要的事情说三遍

代码:

继续阅读

[BZOJ 1001]狼抓兔子

终于A了!

再给大家欣赏一下zzs这个逗比百折不挠的卡评记录(一页半慎看):

这道题就是平面图转对偶图的恶心题~frown

zzs在此列出此题坑点,望后人警觉:

  1. 最好写一个定位函数,不然点的位置很容易混。
  2. 不要用SPFA,不然会被卡。
  3. m等于1或n等于1的情况需要特判!
  4. 不要用边表,内存开销太惊人……
  5. 用邻接表的话,不要像zzs这个逗比一样开小内存……

代码:

继续阅读

[BZOJ 3223]文艺平衡树

三大平衡树题中的第二道……

果然文艺啊,轻音体柔易推倒,果然是萝莉

很明显伸展树辣!

代码:

继续阅读

[BZOJ 1015]星球大战

这道题到现在才A……

其实……离线处理并不像我想的那样变态……

需要注意的是,离线处理过程中,在将被删除的点加入时,联通分量数可能增加(其他一个点都连不了)

代码:

继续阅读

做什么题都WA……混不下去了

[BZOJ 1192]鬼谷子的钱袋

这题真是interesting极了!

建议先在纸上实践一下,然后你会发现问题的解就是n的二进制长度!

让我偷着乐一会

[要证明?我这先挖个坑]

代码:

继续阅读

[BZOJ 4195]程序自动分析

看起来是道并查集水题……

可i和j最高可达1000000000,直接开个数组放注定会MLE,怎么办?

注意n最高为1000000,所以每组数据中出现的i和j最多会有2000000种,所以我们可以把i和j“映射”为不大于2000000的整数,这样就能避免MLE了!

这种技术,就是离散化

同时注意防卡常!

代码:

继续阅读