牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共11篇）

远古杂题 1

基因匹配Match（数据结构优化dp）题意 1~n 每个数一定出现五次在s1，s2中。求两个字符串的最长公共子序列。考虑n²的暴力写法，对于每一个i，与他相等的一定只有五个。所以可以记录相等的位置优化，分别查询该位置之前的最大值+1转移，Ans记录即可。对于1~n的带修改RMQ，可以...

线段树 dp 状压字符串矩阵

2019-07-17

0 465

矩阵求逆

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

数学矩阵线性代数

2019-07-23

0 578

模拟9 题解

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

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

2019-07-27

0 338

模拟28 题解

A. 虎比较显然的贪心。儿子中存在偶数个不符合条件的，直接全部连在一起。存在奇数个，最后剩下的一个能上传则上传，否则也撞死在这里。容易证明，将更多的不符合条件的情况上传，不会使答案更优。 B. 阴阳观察题目两个性质： 0/1为联通块同行同列1之间...

容斥贪心 dp 矩阵

2019-08-21

0 344

模拟52 题解

A. 平均数刚开始没想到。突然想到二分判定。然后想到平衡树，想着这题也太难了。然后想到树状数组离散一下就好打了。然后忘了开longlong，被搞成了60分。其实精度确实有问题，和暴力拍千组左右数据会出错。所以其实问题是求逆序对，打归并排序或许常数会小一点。 ...

二分答案矩阵 dp 线段树

2019-09-27

0 338

模拟80 题解

A. 贝尔数这个数据范围，似乎显然是矩阵快速幂。对模数质因数分解就会发现每个质因子只出现一次且很小。所以考虑求出$mod$每个质因子的结果并$crt$合并。题中已经给出了贝尔数在模$p$意义下的一个公式，所以直接保存$p$个贝尔数，矩阵快速幂转移就可以了。 B...

线性代数矩阵 AC自动机 dp 二分图网络流

2019-10-20

0 368

数学专题测试2 题解

A. B $[n=1]=\sum \limits_{d|n} \mu(d)$ 于是考虑用莫比乌斯函数容斥出题意中的$[gcd=1]$。设$f_n$表示$gcd$为$n$的倍数的答案。 $g_n$表示$gcd$为$n$的答案。 $g_1=\sum \limits_{i=1}^n\mu(i)...

矩阵线性代数莫比乌斯函数多项式数列

2020-01-05

0 441

省选模拟47 题解

A. 老夫发现这个问题有点类似二维偏序。所以考虑类似扫描线的做法，枚举第一个维度，同时在第二个维度上用一个数据结构维护答案。所以枚举 $c$ 的取值，然后发现每次的操作是插入一个点。以值域为下标建立一个数据结构，对应的操作就是前缀加下标，询问操作就是全局查询最大值。所以用一个简单...

凸包扫描线分块 dp 矩阵线性代数

2020-03-16

0 378

省选模拟62 题解

A. Fable 虽然没打 noi online，但是大概看了一眼题。其中 T2 就用到了一个结论是：设 $p_{i,k}$ 表示 $i$ 次冒泡排序之后，第 $k$ 个点与之前的点形成的逆序对个数。则有每次冒泡排序之后，$p_{i+1,k}=\max{p_{i,k+1},0}$。 ...

结论题高斯消元多项式 set 矩阵平衡树启发式合并树状数组线性代数

2020-04-04

0 415

省选模拟80 题解

A. 数字如果枚举 $x\ and \ y$ 的取值，可以进行一个简单的dp。 $dp_{i,0/1,0/1,0/1,0/1}$ 表示从高到低到第 i 位，最高的几位分别是否与 $lx,rx,ly,ry$ 相同，然后这个 dp 数组的取值也只有0/1。所以可以 dp 套 dp。在考虑过...

分块多项式 dp套dp dp 根号分治矩阵数位dp

2020-04-25

0 408