IO流 （附带算法竞赛模板）
主要是BufferedReader + StringTokenizer（很快） 算法竞赛模板:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import java.io.*; import java.math.BigDecimal; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { public static void solve() { } public static void main(String[] args) throws Exception { try (PrintWriter out = new PrintWriter(new...
Educational codeforceRound 173 题解
A1 BC123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151#include<bits/stdc++.h>using namespace std;using i64 = long long;constexpr i64 inf = 1e9 + 7;template<typename T>tuple<T, T, T>...
线段树
对于一个数组，如果想要动态的管理它，就使用线段树把 区间加 & Sum 区间修改， 区间加和求和 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071template<typename T>struct Segment { vector<T> f; vector<T> tag; int n; Segment() {} Segment(int n) : n(n) { f.assign(n << 2 + 1, 0); tag.assign(n << 2 + 1, 0); } void update(int l, int r, T c, int s, int t, int p)...
TCP / UDP
OSI七层网络模型 从下往上 ： 物理层， 数据链路层，网络层，运输层， 会话层，表示层，应用层 TCP/ IP 网络协议是什么 在计算机网络要做到井井有条的交换数据，就必须遵守一些事先约定好的规则，比如交换数据的格式、是否需要发送一个应答信息。这些规则被称为网络协议。 为什么要对网络协议分层 简化问题难度和复杂度。由于各层之间独立，我们可以分割大问题为小问题。 灵活性好。当其中一层的技术变化时，只要层间接口关系保持不变，其他层不受影响。 易于实现和维护。 促进标准化工作。分开后，每层功能可以相对简单地被描述![[OSI.png]] 1、UDP 和 TCP 的特点与区别 用户数据报协议 UDP（User Datagram Protocol） 是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。 传输控制协议 TCP（Transmission Control...
Tarjan
强连通分量1234567891011121314151617181920212223242526272829303132vector<int> dfn(n + 1), low(n + 1), f(n + 1);int dfncnt = 0, flag = 0;stack<int> st;auto tarjan = [&](auto self, int u) -> void { dfn[u] = low[u] = ++dfncnt; st.push(u); for (auto v : e[u]) { if (!dfn[v]) { self(self, v); low[u] = min(low[u], low[v]); } else if (f[v] == 0) { low[u] = min(low[u], low[v]); } ...
基环树
图中只存在一个环的图就是基环树，分为有向图和无向图 无向图求基环树可以使用bfs ： 先统计入度，然后每次对队列中元素删边，把删后度数为1的点入队，bfs结束后，所有度数 > 1的点就是环上的点，如果只需要求一个点，可以使用dfs，出现了两次的点说明必然有环。 想法1 ： 可以通过先找出基环树的环， 之后分别对除了环以外的每个点的子树进行操作，把信息合并到环上，之后问题就集中为处理一个环上问题， 想法2 ： 可以先找出基环树的环， 之后删掉基环树上某一条边， 将基环树变成一个树，处理树上问题 寻找环的办法1 ： 对于无向图， 使用拓补排序，最后剩下的度数 > 1 的点就是环上的点1 2 : 对于有向图， 使用dfs 寻找，出现了vis两次的点就是环上一个点123456auto check_c = [&](auto self, i64 u) -> int { vis[u] = 1; int now = fa[u]; if (vis[now]) return now; else...
欧拉回路
欧拉回路是这样一个东西（个人理解） ： 从图上某个点出发，每条边不能重复经过，然后从这个点开始把所有的点和边走一遍（同时满足每条边不能重复）后回到这个点。 怎么求？ 一种办法是Fluery , 即每次只找不是桥的边bfs， 当每个点和边都进队后再处理桥， 如果图不连通或者经过桥之后无法遍历整个图，则没有欧拉回路，否则就找到了欧拉回路， 由于这样实现需要先tarjan缩强连通分量后记录桥的位置，之后再每个点遍历，需要时间复杂度大约是O(n ^ 2), 太不牛，我们换下一个算法 Hierholzer算法 （不是这什么鬼名字也太长……）我直接把函数名字写成dfs了，板子如下（自己实现的用起来自己舒服）123456789vector<int> now(n + 1);stack<int> s;auto dfs = [&](auto self, int u) -> void { for (int i = now[u]; i < e[u].size(); i = now[u]) { now[u]++; ...