转移自老blog 2018牛客总结

第一场

通过四题

两签到

两中等

目前赛后补三题

1.求解不定方程ax+by=c使得p2*x2+p1*x+q2*y2+q1*y最小

拓展欧几里得算法

二次函数的极值暴算

2.有个人要从一条直线走到另一条平行线,中间有几个圆,在直线和圆上走不消耗体力,其他消耗体力的与路程正比

计算几何及最短路模型转化

3.括号匹配,一个序列有很多很多不同括号,问你任意区间括号是否匹配

有两种做法,第一是记录括号入栈后栈顶元素

                      第二是根据括号唯一匹配,维护每个区间是否封闭匹配,即维护区间匹配对象的最值

4.构造一个矩阵使得每一行每一列都包含了所有的数字(1-N)且对于所有的 1 ≤ i < j ≤ n, 有 Ai,j ≠ Aj,i。

通过已有矩阵来构造未知矩阵

5.现有N个数a1,a2,...,aN。对于每一个ak,求有多少个有序二元组(i,j)满足,其中P为一给定质数。

根据原根性质将乘法转化为加法,再转化为fft

第二场

通过三题

签到两题

中等一题

目前赛后未补

1.计算一个矩阵与另一个01矩阵的积的所有元素的异或和

矩阵分块加速乘法,每八个元素预处理一次,乘时O1查询,共计加速八倍

 

第三场

通过两题

签到两题

赛后补四题

1.马走日

日了狗了

2.树上包含每个点的连通点集的数量

树上dp,两次dfs,第一次维护节点子孙数,第二次维护其他方向子孙数

第二次维护注意坑爹的逆元不存在情况

3.修修和栋栋轮流取石子,每人每次需要从任意一堆石子中取走个,修修先手。无法操作的人失败。此外,如果一个人取完了一堆石子,他会立即获胜。

sg函数,设定a-b是不可到达的状态,并发现循环节且特判a=1即可

4.二分图是否存在,不存在找奇环

一次dfs,或者镜像并查集+dfs

第四场

通过五题

五个签到题

第五场

通过一题

一个中等题

赛后补一题

1.中有多少不同的数,这些不同的数字里面第k大的是多少。

证明一下什么时候是2*sqrt(n)什么时候是2*sqrt(n)-1就行

2.an=m0an-1+m1an-2+c

蒙哥马利快速模乘 或者运气好的O1快速乘法

第六场

通过三题

三个找规律的题搞了半天

还用上了rmq二分。。。

第七场

通过三题

一签到

一中等找规律

一个模拟

1.记住log2的值,就可以做了

2.魔方展开