XUDJY

算法基础

C++(2) CF(32) CSP(3) ICPC补(3) QT(1) 动态规划(3) 数据结构(3) 数论(1) 树(9) 碎碎念(3) 题解(4)

/ 注册

全部文章 / 算法基础（共9篇）

矩阵基本性质

1，乘法结合律： (AB)C=A(BC) 2，乘法左分配律：(A+B)C=AC+BC 3，乘法右分配律：C(A+B)=CA+CB 4，对数乘的结合性k(AB）=(kA)B=A(kB）． 5，转置 (AB)T=BTAT． 6，矩阵乘法一般不满***换律 [3] 。 *注：可交换的矩阵...

2019-10-31

0 533

矩阵

网络赛使人自闭，目前为止还缺了好多知识点我哭了。 Matrix Power Series VJ链接：https://vjudge.net/problem/POJ-3233 难点在于推出Sk,Ak的递推式，将答案转换为常数矩阵的幂次方形式，还有可以在矩阵中补...

矩阵快速幂

2019-08-25

0 548

整体二分初识

菊苣是怎么一天学会CDQ和二分的啊我哭了（还不是自己太懒了）和CDQ分治相似，也有按照时间将修改与询问排序达到分治的操作。以后补详细理解（因为目前还没啥理解。。。。 K-th Number POJ链接：http://poj.org/prob...

整体二分

2019-08-13

0 519

CDQ分治初识

又是一个以前没接触过的东西我要疯啦。概述 CDQ分治被称为用时间（logn）降维的算法，与普通分治简单将问题分为一个个独立的子问题不同， CDQ分治中，每一次划分出来的两个子问题，前一个子问题用来解决后一个子问题，而不是其本身，即每次计算左区间对右区间的贡献，并...

CDQ 分治

2019-08-11

0 678

匹配问题

棋盘游戏（匈牙利算法，最大匹配） VJ链接：https://vjudge.net/problem/HDU-1281 由题目描述中的“不在这些格子上放车，也可以保证尽量多的“车”被放下。” 可以联想到这句话本意即为这条路存在于在增广路中，属于“翻转”增广路之前存在的匹配...

最大匹配匈牙利算法二分图

2019-08-09

0 632

LIS（最长递增子序列）

写到一道数位DP的题目，涉及LIS的nlogn解法，拿道LIS模板题复习一下。 BUY LOW, BUY LOWER （记录序列数，DP*2） VJ链接：https://vjudge.net/problem/POJ-1952 //打算把更新放在上面了 ...

LIS

2019-08-04

0 781

分块优化

今天码力不足还有点丧，不应该这样哦，学习新东西应该是一件很开心的事情。昨天学的一种优美的暴力方法，分块。找了个题试试这个方法，结果优化失败T掉了，主要就是最后没有想到逆序求f数组与to数组，因为前面的值可以通过后面的值推出的，简单加一就好。一开始只能想到直接顺序暴力求...

2019-08-02

0 596

数的整除特征

能被2整除的数的特征：个位上是0、2、4、6、8的整数。能被5整除的数的特征：个位上是0、5的整数。能被3（9）整除的数的特征：各个数位上数字之和能被3（9）整除的整数。能被4（25）整除的数的特征：末两位数能被4（25）整除的整数。能被8（125）整除的数的特征：末三位数能被8（125）整...

2019-07-29

0 509

差分与前缀和

求一维前缀和时：在（l，r）区间都加上q，维护一个差分数组b，b[l]加上q，b[r+1]减q即可。求前缀和时， a[i]+=a[i-1]+b[i];//其实很好理解啦，画图手模就行。 b[0]=a[0]; b[1]=a[0]+a[1]; ...

2019-07-25

0 427