[BZOJ 2243]染色

树剖好题……

2243记录

这能说明几个问题:

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

继续阅读

[BZOJ 4034]T2

这个题名字也真是……

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

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

代码:

继续阅读

[BZOJ 1968]约数研究

妙,妙啊!

此乃数学之大道也

直接递推+求约数会炸,但是……

你可以枚举约数x,然后求出区间内约数有它的个数,很明显是\( \lfloor n \div x \rfloor \),然后求和就行了……

代码:

继续阅读

[BZOJ 1053]反素数

终于A了……

此题坑点多~

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

然后DFS就可以了

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

代码:

继续阅读

[BZOJ 1001]狼抓兔子

终于A了!

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

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

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

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

代码:

继续阅读

[BZOJ 1015]星球大战

这道题到现在才A……

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

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

代码:

继续阅读

[BZOJ 1192]鬼谷子的钱袋

这题真是interesting极了!

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

让我偷着乐一会

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

代码:

继续阅读

[BZOJ 1002]轮状病毒

根据Matrix-Tree定理,这题可以求出基尔霍夫矩阵,然后当成行列式求值即可

这样做并没有什么错,大概也能AC,但是时间复杂度是立方级的,并且写起来并不简单(要用到高斯消元什么的,更何况此题还要用高精度)

或许DP也可以?

不过有一个简单的递推式:d[n]=d[n-1]*3-d[n-2]+2

证明比较麻烦(绝大多数人是找规律出来的),可以到这找:http://vfleaking.blog.163.com/blog/static/17480763420119685112649

这题要用高精也太烦人了,我就用了Python写(Python语法真特么烦人啊)

Q:真要考试你交Python啊?

A:我用Python打出来表然后交表啊。

代码:

继续阅读

[BZOJ 1036]树的统计

终于A了这题了!

树剖大水题~

然而zzs这种蒟蒻还是要交很多次才过:

继续阅读