お前はどこまで見えている

1. 简介 BSGS 算法也称为大小步算法，主要用来解决 Ax≡Bmod  p\begin{array}{c} A^x \equiv B \mod{p} \end{array} Ax≡Bmodp​ 的问题，其中 ppp 为质数。 2. 算法 令 x=i⋅m−jx = i \cdot m -jx=i⋅m−j，其中 m=⌈p ⌉m = \lceil \sqrt{p} \,\rceilm=⌈p​⌉。此时原式等价于 Ai⋅m−j≡Bmod  p⇒Ai⋅m≡Aj⋅Bmod  p\begin{array}{c} A^{i \cdot m - j} \equiv B \mod{p} \\ \Rightarrow A^{i \cdot m} \equiv A^{j} \cdot B \mod{p} \end{array} Ai⋅m−j≡Bmodp⇒Ai⋅m≡Aj⋅Bmodp​ 然后枚举 j∈[0,m]j \in [0,m]j∈[0,m]，将 Aj⋅BA^{j} \cdot BAj⋅B 存入哈希表；再枚举 i∈[1,m]i \in [1,m]i∈[1,m]，从哈希表中寻找第一个满足 Ai⋅m≡Aj⋅B ...

1. 点、线、凸边形 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199 ...

1. 思想 矩阵树定理：对于一个无向图 GGG，它的生成树个数等于其基尔霍夫矩阵任何一个 N−1N - 1N−1 阶主子式的行列式的绝对值。 度数矩阵 DDD：是一个 N×NN \times NN×N 的矩阵，其中 D[i][j]=0(i≠j)D[i][j]=0 (i \neq j)D[i][j]=0(i=j)，D[i][i]=iD[i][i]=iD[i][i]=i 号点的度数。 邻接矩阵 AAA：是一个 N×NN \times NN×N 的矩阵，其中 A[i][i]=0A[i][i]=0A[i][i]=0，A[i][j]=A[j][i]=i,jA[i][j]=A[j][i]=i,jA[i][j]=A[j][i]=i,j 之间的边数。 然后 Kirchhoff（基尔霍夫）矩阵 K=D−AK = D-AK=D−A 。 【注】行列式计算方法：将矩阵转为三角矩阵进行行列式计算。 2. 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...

1. 简介 最大流算法主要分为两大类，一类为增广路算法，一类为预流推进算法。最大流算法解决的是在有向网路图 G=(V,E) G = (V,E) G=(V,E) 中计算从源点 sss 到汇点 ttt 的最大流量问题，以及最小割容量问题。 最小割最大流定理 s−ts-ts−t 最大流的值等于 s−ts-ts−t 的最小割容量。 2. 增广路算法 剩余容量 剩余容量 cf(u,v)=c(u,v)−f(u,v) c_f(u,v) = c(u,v) - f(u,v) cf​(u,v)=c(u,v)−f(u,v) 表示边 (u,v)(u,v)(u,v) 的容量与流量之差。 增广路 对于一个网络图 G=(V,E) G = (V,E) G=(V,E)，从图 G 中找到一条从源节点 sss 到目标节点 ttt 的路径，且路径上所有边的剩余容量都大于 0 ，则这条路径称为增广路 。 残量网络 对于网络图 GGG，残量网络定义为网络 G 中所有节点和剩余容量大于 0 的边构成的子图，即 Gf=(Vf=V,Ef=(u,v)∈E,cf(u,v)>0)\begin{array}{c} G ...

1. 题目 题目链接：PAT「1003 Universal Travel Sites (35分)」 。 Description After finishing her tour around the Earth, CYLL is now planning a universal travel sites development project. After a careful investigation, she has a list of capacities of all the satellite transportation stations in hand. To estimate a budget, she must know the minimum capacity that a planet station must have to guarantee that every space vessel can dock and download its passengers on arrival. Input Specification: Each input file ...

1. 题目 题目链接：PAT「1002 Business (35分)」 。 Description As the manager of your company, you have to carefully consider, for each project, the time taken to finish it, the deadline, and the profit you can gain, in order to decide if your group should take this project. For example, given 333 projects as the following: Project[1] takes 333 days, it must be finished in 333 days in order to gain 666 units of profit. Project[2] takes 222 days, it must be finished in 222 days in order to gain 333 units of ...

1. 题目 题目链接：PAT「1001 Battle Over Cities - Hard Version (35分)」 。 Description It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city. Given the map of cities which have ...

1. 简介 并查集是一种高效的数据结构，常用来解决集合的合并和查找问题，常见于图论问题中。 2. 操作 2.1 构建 并查集一般构建为初始时每个节点所属的集合编号即为自己的节点编号。 1234567// 初始化int father[MAXN]; // father[i] 即为节点 i 所属的集合编号void init(int n) { for(int i = n; i; --i) { father[i] = i; }} 2.2 查找 并查集的高效之处在于在查找过程中压缩路径，从而实现压缩路径后查找的效率变为 O(1) 。 1234// 寻找并查集的根节点int findfather(int x) { return x == father[x] ? x : (father[x] = findfather(father[x]));} 2.3 合并 每次合并时只需将一个集合的根节点的 father 设为另一个集合的根节点。 1234// 合并并查集void mergefather(int x, i ...

1. 题目 题目链接：Spring Outing 。 题目描述   You class are planning for a spring outing. N people are voting for a destination out of K candidate places.   voting progress is below:   First the class vote for the first candidate place. If more than half of the class agreed on the place, the place is selected. The voting ends.   Otherwise they vote for the second candidate place. If more than half of the class agreed on the place, the place is selected. The voting ends.   Otherwise they vote for the third c ...

1. 题目 题目链接：P2418「yyy loves OI IV」 。 题目背景 某校 2015届有两位 OI 神牛，yyy 和 c01。 题目描述 全校除他们以外的 NNN 名学生，每人都会膜拜他们中的某一个人。现在老师要给他们分宿舍了。但是，问题来了： 同一间宿舍里的人要么膜拜同一位大牛，要么膜拜 yyy 和 c01 的人数的差的绝对值不超过 MMM。否则他们就会打起来。 为了方便，老师让 NNN 名学生站成一排，只有连续地站在一起的人才能分进同一个宿舍。 假设每间宿舍能容纳任意多的人，请问最少要安排几个宿舍？ 输入格式 第一行，两个正整数 NNN 和 MMM。 第 2⋯N+12 \cdots N+12⋯N+1 行，每行一个整数 111 或 222，第 iii 行的数字表示从左往右数第 i−1i-1i−1 个人膜拜的大牛。 111 表示 yyy，222 表示c01。 输出格式 一行，一个整数，表示最少要安排几个宿舍。 输入输出样例 输入 #1 1234565 111221 输出 #1 11 说明/提示 难度题，做好心理准备～ 测试点编号 N的范围 M的范围 1~3 ≤ ...

1. 地址翻译 地址翻译由 MMU(Memory Management Unit) 内存管理单元进行。 1.1 基本参数 符号 描述 N=2nN = 2^nN=2n 虚拟地址空间的地址数量 M=2mM = 2^mM=2m 物理地址空间的地址数量 P=2pP = 2^pP=2p 页的大小（字节） 1.2 虚拟地址（VA） 符号 描述 VPO 虚拟页面偏移量（字节） VPN 虚拟页号 TLBI TLB 索引 TLBT TLB 标记 TLB(Translation Lookaside Buffer)：翻译后背缓冲区/快表，是一个小的虚拟内存地址 VP 的缓存。 1.3 物理地址（PA） 符号 描述 PPO 物理页面偏移量（字节） PPN 物理页号 CO 缓冲块内的字节偏移量 CI 高速缓存索引 CT 高速缓存标记 PT(Page Table)：页表是一个页表条目(PTE)数组，将虚拟页映射到物理页。 1.4 页面命中 1.5 缺页异常 2. 内存管理 在磁盘和内存之间的页面 ...

1. 信息的表示和处理 MSB：most significant bit（最高有效位） LSB：least significant bit（最低有效位） 1.1 进制表示 二进制数用后缀字母 B 十六进制数用后缀字母 H C 语言常量数字默认为有符号数，无符号数用后缀字母 U 1.2 进制转换 整数转换 除法——除基取余法 小数转换 乘法——乘基取整法 1.3 数值范围 无符号数值 UMin=0UMax=2w−1 UMin = 0 \\ UMax = 2^w - 1 \\ UMin=0UMax=2w−1 补码数值 TMin=−2w−1TMax=2w−1−1 TMin = -2^{w-1} \\ TMax = 2^{w-1} - 1 \\ TMin=−2w−1TMax=2w−1−1 1.4 类型转换 有符号数和无符号数的转换规则： 位模式不变、数值可能改变（按不同编码规则重新解读） 隐式转换 有符号数隐式转换为无符号数 当表达式中有符号和无符号数混用时，包括比较运算符连接的表达式 符号扩展 对于给定 w 位的有符号整型数 x ...