[BZOJ 1053]反素数
终于A了……
此题坑点多~
据说只需要预处理12个素数,然而我预处理了4648个……so sad
然后DFS就可以了
我无力吐槽了……我就是智商感人啊
代码:
[BZOJ 3524]Couriers
这道题有了主席树,就是裸题了……
只要用主席树维护出现次数,然后二分求解即可
但是!数组一定要开大,开大,再开大,重要的事情说三遍!
代码:
[POJ 2104]K-th Number
我擦终于A了这题了!
主席树坑点多……
最好不要写指针主席树,不然容易TLE……(自带常数?)
并且注意,一定要把数组开大,开大,再开大,重要的事情说三遍
代码:
[BZOJ 1001]狼抓兔子
终于A了!
再给大家欣赏一下zzs这个逗比百折不挠的卡评记录(一页半慎看):
这道题就是平面图转对偶图的恶心题~
zzs在此列出此题坑点,望后人警觉:
- 最好写一个定位函数,不然点的位置很容易混。
- 不要用SPFA,不然会被卡。
- m等于1或n等于1的情况需要特判!
- 不要用边表,内存开销太惊人……
- 用邻接表的话,不要像zzs这个逗比一样开小内存……
代码:
[BZOJ 3223]文艺平衡树
三大平衡树题中的第二道……
果然文艺啊,轻音体柔易推倒,果然是萝莉
很明显伸展树辣!
代码:
[BZOJ 1015]星球大战
这道题到现在才A……
其实……离线处理并不像我想的那样变态……
需要注意的是,离线处理过程中,在将被删除的点加入时,联通分量数可能增加(其他一个点都连不了)
代码:
[BZOJ 1192]鬼谷子的钱袋
这题真是interesting极了!
建议先在纸上实践一下,然后你会发现问题的解就是n的二进制长度!
让我偷着乐一会
[要证明?我这先挖个坑]
代码:
[BZOJ 4195]程序自动分析
看起来是道并查集水题……
可i和j最高可达1000000000,直接开个数组放注定会MLE,怎么办?
注意n最高为1000000,所以每组数据中出现的i和j最多会有2000000种,所以我们可以把i和j“映射”为不大于2000000的整数,这样就能避免MLE了!
这种技术,就是离散化
同时注意防卡常!
代码:
[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 4390]Max Flow
这明明不是道网络流题。
这就是道树剖题……
没有什么太难的地方,然而还是调试了几遍才过。
代码: