牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟14 题解

A. 旋转子段对于位置i上的数$a_i$，易知有且仅有一个旋转点使它旋转到$a_i$，这个旋转点是$\frac{i+a_i}{2}$ 因为旋转点分落在点上的旋转点和两点之间的旋转点，除2不易处理。不妨将位置i上的数存放在$i+a_i$处。设1~i的原本固定点为$pre_i$个，后缀同理...

模拟退火搜索图论树状数组

2019-08-08

0 474

模拟13 题解

A. 矩阵游戏　　通过前40%的部分分，我们发现程序复杂度不能为$O(nk)$。　　设$h(i)$表示第$i$行最终乘的总系数，$l(i)$表示第$i$列。　　考虑每个点$(i,j)$，它对最终答案的贡献是$((i-1)*m+j)*h(i)*l(j)$。　　发现可以拆分为$(i-1)...

线段树映射分块 ST表

2019-08-06

0 409

模拟12 题解

A. 斐波那契(fibonacci) 首先想到a,b<=1e6的暴力：建树，直接向上标记求lca。建树的过程中发现一个性质。斐波那契第n代兔子，是n-2代及以前的兔子的儿子。因为编号连续且与父亲编号大小有关，设该节点的编号为$x$，在第$k$代，则$f(x)=x-fib(...

数列线段树 dp 单调队列贪心拓展域并查集

2019-08-03

0 399

模拟11 题解

A. string 类似 HEOI2016排序。排序这道题因为只询问单点最终答案，二分答案，将小于和大于等于答案的数分别设为0 1，用线段树维护0 1的排序即可。算法一：本题中的1～n变成了0～25（即a～z），单点询问变成了全体询问。仿照排序那道题的做法，线段树优...

线段树 dp trie树组合计数

2019-08-02

0 442

模拟10 题解

A. 辣鸡(ljh) 模拟。对于同一块内的答案，直接统计。对于不同块内的，枚举i和大于i的$j=i+1～n$，一个有效的剪枝：以$x_1$为第一维排序，当$x_{1j}>x_{2i}+1$时break退出循环。然而如果用纵向链状的数据还是会被卡成$O(n^2)$，然而...

数学期望启发式合并线段树模拟

2019-07-30

0 344

模拟9 题解

A. 随 (rand) 尽量不要重载乘法，真的很慢。 50分算法因为重载乘法被卡常卡成20分，真的很伤。 $void$函数，传入希望存储答案的指针，使用$memcpy$快速传递。 1 void mult(const matrix &a,const matrix &...

组合计数 dp 数学期望矩阵线性代数树上差分原根

2019-07-27

0 338

线段树/莫队杂题

高速公路(road) 如果直接维护一个点到其它点的距离，维护起来很困难。不妨转换思路，考虑每个点对答案的贡献，设询问区间为$l,r$，则点$i$的贡献为$(i-l)*(r-i)*w[i]=(-i^2+(l+r)*i-l*r)*w[i]$。对于$i^2*w[i],i*w[i],w[i...

线段树莫队分块

2019-07-26

0 420

模拟8 题解

A. 匹配 $Hash$直接搞。如果使用$KMP$，注意B字符串与A完全匹配，这是原本的$KMP$无法处理的问题。 B. 回家刚开始以为是割点，打完后仔细一想发现不对。于是打了圆方树，没有什么技巧。另一种简单的做法：只判断割点，但修改判断割点的方法。 ...

Hash KMP 字符串 tarjan 图论三分

2019-07-25

0 308

矩阵求逆

设逆矩阵为$P$，该矩阵为$A$，单位矩阵为$E$ 则有$P*A=E$ $P*E=P$ 因为做初等行变换等价于被对应的初等矩阵左乘。在$A$化为$E$过程中，对$E$做相同操作，就可以得到$P$。初始化另一个矩阵为单位矩阵，将本矩阵用高斯消元尝试消为单位矩阵。注意该过程不...

数学矩阵线性代数

2019-07-23

0 578

模拟7 题解

A. 方程的解 a，b均为正整数，exgcd求出x最小和最大的解。作差后除公差再加一，就是方程的解的数量。对于a，b，c中存在0或负数的情况，疯狂加特判。 B. visit 共走t步，要求到达坐标$(n,m)$。即总共向上走了n步，向右走了m步。设u为向上走步数，d为向下...

exgcd 数学组合计数 lucas定理中国剩余定理模拟 set

2019-07-22

0 414