Posts

弗洛伊德 Floyd // T must define < and + template<typename T,size_t V,bool Directed=true,T INF=T(0x3f3f3f3f)> struct Floyd { T g[V][V]; int n; void init(int n_) { n=n_; for(int i=0;i<n;i++) for(int j=0;j<n;j++) g[i][j]=INF; } void addedge(int u,int v,T w) // check multi-edges { g[u][v]=w; if(!Directed) g[v][u]=w; } void cmin(T &x,const T &y) { if(y<x) x=y; } void floyd(Upd =upd) { for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) cmin(g[i][j],g[i][k]+g[k][j]); } };

并查集 Union Find / Disjoint Set Union 路径压缩和按 size 合并 Union by Size // M: max number of set // id is in [0~M-1] template<size_t M> struct UF { int uf[M],sz[M]; int n; int ns; // number of set void init(int n_) { n=ns=n_; for(int i=0;i<n;i++) uf[i]=i,sz[i]=1; } int find(int x) { return x==uf[x]?x:uf[x]=find(uf[x]); } bool same(int x,int y) { return find(x)==find(y); } bool merge(int x,int y) { x=find(x); y=find(y); if(x==y) return false; if(sz[x]>sz[y]) swap(x,y); sz[y]+=sz[x]; uf[x]=y; ns--; return true; } }; Debug: void show() { cerr<<"UnionFind:----------------------\n"; cerr<<"id:"; for(int i=0;i<n;i++) cerr<<'\t'<<i; cerr<<'\n';

迪杰斯特拉 Dijkstra 模板（priority_queue） // T must define < and + // V: max number of vertex [0~V-1] template<typename T,size_t V,bool Directed=true, T INF=T(0x3f3f3f3f),T ZERO=T(0)> struct G { typedef pair<T,int> PTI; vector<PTI> g[V]; T dis[V]; int vis[V]; int n; void init(int n_) { n=n_; for(int i=0;i<n;i++) g[i].clear(); } void addedge(int u,int v,T w) { g[u].emplace_back(w,v); if(!Directed) g[v].emplace_back(w,u); } void dijkstra(int st,int ed=-1) // ed=-1 no destination { for(int i=0;i<n;i++) dis[i]=INF,vis[i]=0; priority_queue<PTI,vector<PTI>,greater<PTI> > qu; dis[st]=ZERO; qu.emplace(ZERO,st); while(!qu.empty()) { PTI p=qu.top(); qu.pop();

二叉堆 Binary Heap 模板：普通二叉堆 Heap // T must define < // min heap // M: max size of heap template<typename T,size_t M,typename Cmp=less<T>> struct Heap { static Cmp cmp; T h[M+1]; int n; void init() { n=0; } void init(T h_[],int n_) // h[0~n-1] { n=n_; for(int i=1;i<=n;i++) h[i]=h_[i-1]; for(int i=n/2;i;i--) sink(i); // O(n) } void push(T x) { h[++n]=x; swim(n); } T pop() { T res=h[1]; h[1]=h[n--]; sink(1); return res; } T top() { return h[1]; } // check n>=1 int size() { return n; } bool empty() { return

LCP 21. 追逐游戏 题目大意 给定一棵 $N$ 个点的基环树（环套树）。给定图上两个起始位置 $A$ 和 $B$ ($A \neq B$)。每一轮 $A$ 先移动，$B$ 后移动。每次移动可以移动到图上当前点的相邻点或者保持不动。任意时刻如果 $A$ 和 $B$ 处在同一位

第 1 章 开始 1.1 查看程序返回值 当一个程序运行结束时，我们想知道 main 函数的返回值可以使用以下命令。 Win > echo %ERRORLEVEL% Unix $ echo $? 1.2 标准库有四个输入输出对象 cin // 标准输入 cout // 标准输出 cerr // 标准错误 clog // 输出程序运行时的一般信息 字面

第 1 章 概率论导论 1.2 概率的不同类型 直观概率：基于直观来处理判断 古典概率：事件概率不是实验性的，通过预先计算事件 $E$ 可能发生的次数 $n_E$ 形成一个比值 $n_E / n$ 其中 $n$ 是所有可能的结果。此时需要所有的结果是等可能的。 古

1. 让自己习惯 C++ 条款 01：视 C++ 为一个语言联邦 C++ 是一个多重泛型编程语言（multiparadigm programming language）。 C++ 同时支持过程（procedural）形式、面向对象（object-oriented

实验 1 查看 CPU 和内存，用机器指令和汇编指令编程 想在 win10 上玩这个需要自己下载 DOSBox 和 debug.exe。 之后用 DOSBox 运行 debug 即可开始书中的实验。 R 命令：查看、修改寄存器 进入 debug 模式后输入 $r$ 回车后可以查看 CPU 寄存器内容。 输

P4588 [TJOI2018]数学计算 题目大意 给定 $x = 1$ 和某个模数 $MO$，有两种操作（共 $Q \le 10^5$ 次） 操作 $1$：把 $x = x*v % MO$ 操作 $2$：取消第 $k$ 次操作（取消的必为操作 $1$，且某个操作 $1$ 只会最多被取消一次） 每

第 2 章 寄存器 在 CPU 中： 运算器处理信息 寄存器储存信息 控制器控制各种器件 内部总线连接各种器件，在他们之间传输数据 对汇编程序员最重要的部件就是寄存器，寄存器是程序员可以用指令读写的部件，程序员通过改变寄存器中

第 1 章 基础知识 1.1 机器语言 CPU 提供机器指令集也就是机器语言。 早期卡片打孔就是使用的机器语言。 机器语言难于书写阅读查错于是产生了汇编语言 1.2 汇编语言的产生 汇编语言的主题是汇编指令。汇编指令采用了更便于人类书写

E - Bomber 题目大意 给出一个 $H \times W$ 的矩阵，上面有 $M$ 个点，选出一行一列使得覆盖到的点最多。问最多是多少。 其中 $H,W,M <= 3 \times 10^5$ 简要题解 注意到一定会贪心的选某个数量最多的行和列。设其行列数量分别 $mx$，$my$，则答

1575. Count All Possible Routes 题目大意 给定一些不同的位置 $(N \le 100)$，给定起点和终点位置的标号，给定起始油量 $(F \le 200)$。 每次可以选择从当前位置走到任意其他位置花费每单位距离 $1$ 单位油。油量不能为负。 问，从起点到终点总

E - Coprime 题目大意 给出数组 $A$ 如果其中数字两两互质则返回 “pairwise coprime”，如果整个数组 $gcd$ 为 $1$ 则返回 “setwise coprime”，其他情况返回 “not coprime” 简要题解 显然 setwise 很好判

比赛简述 ABC 中比较简单的一场，题目也都比较常规 AtCoder Beginner Contest 177 A - Don’t be late 代码实现 #include <bits/stdc++.h>using namespace std; int main() { int d,t,s; scanf("%d%d%d",&d,&t,&s); printf("%s\n",t*s>=d ? "Yes" : "No"); return 0; } B - Substring 题目大意 给出两个串 $S$ 和 $T$，问 $S$ 至少替换多少字符可以使 $T$ 是 $S$ 的子串。 Tag: 暴力 简要题解 $S$ $T$

F - I hate Shortest Path Problem 题目大意 给出一个 $(h+1) \times w$ 的二维矩阵，初始位置可以是第 $0$ 行的任意位置。 每一个格只能往右或下方向移动 每一行 $i$ 区间 $L_{i}$ 到 $R_{i}$ 的格子不能向下走，问到达每一行的最小可能步数 简要题解 $dp[i][j]$ 为到达 $(i,j)$ 位置的最小步

0 简介 Markdown 与 Typora 什么是 Markdown？ Markdown 是一种轻量级标记语言，可以通过格式标记把普通文本变成带有格式的富文本。 什么是 Typora？ Typora 是使用 Markdown 语言的一个编辑器。与其他 Markdown 编辑器不同的是，Markdown 的效

OTTFF 的新 Blog 很久之前我有一个 xxdn 的 Blog，但是随着自己越来越懒其广告等不重要的信息越来越多，于是弃坑多年。 读到一些大牛自建的博客之后，也萌生了自己搭建一个界面简单干净而又功能强大的 Blog 的想法。 经过研究，大概