[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
这明明不是道网络流题。
这就是道树剖题……
没有什么太难的地方,然而还是调试了几遍才过。
代码:
[BZOJ 2456]mode
原来这就是BT众数题的始祖啊~
首先讲一下方法(这种方法其实叫摩尔投票法):
[BZOJ 4196]软件包管理器
终于A了!
在CodeVS,洛谷甚至UOJ上各种A
但是在BZOJ上各种TLE。BZOJ评测姬自带10倍常数?
这题处理安装很简单,一直溯到根。
删除……注意一下树剖的一些神奇性质。
[BZOJ 1036]树的统计
终于A了这题了!
树剖大水题~
然而zzs这种蒟蒻还是要交很多次才过: