0%

Bus System

  • 一道究极简单的最短路
  • floyd可以过,dij应该也行
  • 注意cin解绑后不可与stdin混用
    阅读全文 »

畅通工程再续

prim模板题,读入时不合法就不建边


流程

  • 建邻接矩阵
  • 选第一个点,写dis为0,vis为true,用第一个点更新dis
  • 循环n-1次
    • 先求vis为false的最小边,得到val和pos
    • 用pos更新dis
    • 判断val,更新ans或跳出
  • 输出结果

阅读全文 »

Jungle Roads

原题

一道最小生成树模版题,我想写prim却概念不清最后写成了kruskal


思路

就是最小生成树,用kruskal,用并查集处理集合

阅读全文 »

乘法逆元


定义 : 若$ax\equiv1modb$,即a,x之即对b的模为1,则ax为乘法逆元,表示为$a=x^-1mod b$

在运算中逆元作为在mod下除法的等效

参考


模运算中的一个问题

模运算有三条性质:

$$\begin{cases}
(a+b)%n = (a%n + b%n)% n\
(ab)%n = ( (a%n)(b%n) ) % n\
(a-b)%n = (a+(-b) )%n = ( (a%n) + ((-b)%n) )% n
\end{cases}$$

于是,在加减乘运算中为了防止溢出,我们可以步步取模,其结果”封闭”.

然而,此性质对除法并不成立.于是我们使用乘法逆元(inv(a)),代替除法.

阅读全文 »

序列自动机


通过一个预处理,
对子序列实现$O(n)$的查询

注意,使用getchar()时必须清空缓冲

阅读全文 »

线性同余方程


辗转相除法

求gcd的基本方法是辗转相除法,即欧几里得算法

用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

阅读全文 »

我一直在做的一个智障操作


如:n个点,求两两距离之和

我:

1
2
3
4
5
6
7
8

int ans=0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
ans+=abs(num[i]-num[j]);
}
}
num/=2;//每条边都算了两次

但是:每个点要干什么,不就是和前面所有点作一次差,和后面所有点作一次差

阅读全文 »

快速幂


乘方操作十分耗时,需要一种乘方的快速求法,
一个数的7次方,显然我们可以拆分为二次方乘五次方,而二进制中,可以更加方便的拆分之…

阅读全文 »

广度优先搜索


利用queue的BFS
基本组成: node结构, clear(), queue<node>, 存图(一维,二维,三维), 与地图一致的vis访问控制, BFS(), main(), 路径记录

阅读全文 »