算法竞赛中的黑盒算法与奇淫技巧 By axuhongbo
BM 线性递推算法 随机化 拉格朗日插值法 手动加栈 快速读入 快速乘 FFT和NTT BITSET的使用 平板电视与rope 自带二进制函数
挑战算法竞赛程序设计 P201页
例题:2018ICPC 南京 G
快速读入
(#pragma comment(linker, “/STACK:1024000000,1024000000”)) 关闭流同步 注意不要混用
快速乘
首先用暴力快速乘O(n*logn)t了,取模一个long long范围内的数太耗时了,但是一直不知道怎 么优化取模,后来才知道有蒙哥马利算法优化 a*b%c,蒙哥马利算法适用于模数为奇数,入 门可参考 https://blog.csdn.net/zgzczzw/article/details/52712 980
随机化算法
Farm(牛客多校) 题意:给出一个N. M的矩阵药田,药田中每个格子都种有一种编号的为1~N Farm(牛客多校) 题意:给出一个N*M的矩阵药田,药田中每个格子都种有一种编号的为1~N*M的药,随后一个T表示有T次浇水操作,之后先是给出N行M列的矩阵(药田),再给出T行,每行有5个数,X1,Y1,X2,Y2和W,表示这次操作会在左上角为(X1,Y1),右下角为(X2,Y2)的矩阵中浇W这种药水,若是该某个药格中的药编号与被浇到的药水不同,则死亡,问你T次浇水操作后整个药田死了多少颗药?
HDU 6242 题意 给出n个点,找出经过一半点以上的圆。题目保证有解。
分析如果随机选择三个点,最差的情况下大 概要0. 5. 5. 5=0 分析如果随机选择三个点,最差的情况下大 概要0.5*0.5*0.5=0.125的概率选出正确的三 个点求出正确的圆心。也就是选错的概率是 7/8,那么重复实验一百次以上,错误率就会 下降到1e-6以上,除非特别黑,不然很快能 找到那个圆心的。判断一次要1e5的时间复杂 度,勉强能在时限内完成。
①注意精度, ②n<=4要特判,这个时候直接取两个点求个圆 ③随机的三个点一定各不相同且不能在同一条直线上
PB_DS库 平板电视
Rope 可持久化平衡树
牛客网暑期ACM多校训练营(第三场)C Shuffle Cards
BZOJ 1269
高效位运算 __BUILTIN_系列函数
打表
分享两个牛客多校账号 (1)17853312640 (1)pojianchengdie (2)954241552 (2)asd954240 关于CSDN 下载
ACM常用网站:LOJ,BZOJ,UOJ,牛客网,计蒜客,TopCoder,Google Codejam,Project euler,EOJ,ZOJ,hihocoder,cf……
百度? 谷歌 知乎 github CSDN 关键词 淘宝 QQ
集训队论文 Vjudge 哔哩哔哩 YouTube 微信:wanna_fly 微博
ACM常用的的QQ群: