算法竞赛中的黑盒算法与奇淫技巧 By axuhongbo.

Presentation on theme: "算法竞赛中的黑盒算法与奇淫技巧 By axuhongbo."— Presentation transcript:

1 算法竞赛中的黑盒算法与奇淫技巧 By axuhongbo

2 BM 线性递推算法 随机化 拉格朗日插值法 手动加栈 快速读入 快速乘 FFT和NTT BITSET的使用 平板电视与rope 自带二进制函数

3 挑战算法竞赛程序设计 P201页

4 例题：2018ICPC 南京 G

5 快速读入

6 （#pragma comment(linker, “/STACK:1024000000,1024000000”)）
关闭流同步 注意不要混用

7

8 快速乘

9

10 首先用暴力快速乘O(n*logn)t了，取模一个long long范围内的数太耗时了，但是一直不知道怎 么优化取模，后来才知道有蒙哥马利算法优化 a*b%c，蒙哥马利算法适用于模数为奇数，入 门可参考 980

11 随机化算法

12 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次浇水操作后整个药田死了多少颗药?

13 HDU 6242 题意 给出n个点，找出经过一半点以上的圆。题目保证有解。

14 分析如果随机选择三个点，最差的情况下大 概要0. 5. 5. 5=0
分析如果随机选择三个点，最差的情况下大 概要0.5*0.5*0.5=0.125的概率选出正确的三 个点求出正确的圆心。也就是选错的概率是 7/8，那么重复实验一百次以上，错误率就会 下降到1e-6以上，除非特别黑，不然很快能 找到那个圆心的。判断一次要1e5的时间复杂 度，勉强能在时限内完成。

15 ①注意精度， ②n<=4要特判，这个时候直接取两个点求个圆 ③随机的三个点一定各不相同且不能在同一条直线上

16 PB_DS库 平板电视

17 Rope 可持久化平衡树

18 牛客网暑期ACM多校训练营（第三场）C Shuffle Cards

19 BZOJ 1269

20 高效位运算 __BUILTIN_系列函数

21 打表

22 分享两个牛客多校账号 （1）17853312640 （1）pojianchengdie （2）954241552 （2）asd954240
关于CSDN 下载

23 ACM常用网站：LOJ，BZOJ,UOJ,牛客网，计蒜客，TopCoder，Google Codejam，Project euler，EOJ,ZOJ,hihocoder，cf……

24 百度？ 谷歌 知乎 github CSDN 关键词 淘宝 QQ

25 集训队论文 Vjudge 哔哩哔哩 YouTube 微信：wanna_fly 微博

26 ACM常用的的QQ群：