Ptilopsis_w's little blog

v1.0 用法 通过 read() 和 print() 进行输入输出， 也可以用 cin , cout (我已经define了)。 千万不要快读快写和 cstdio 混用！！！！ read() 可以传入任意c++关键字类型和string(小数也可以)。 read() 和 print() 也可以传入多个参数，即使不同类型也可以。(c++98不支持) int a; char b;read(a, b); // OK, no problem 输出小数时，使用setpcs(x)来保留精度(四舍五入)。 double x;print(setpcs(5), x);cout << setpcs(5) << x; 读入 char 类型时，会自动过滤掉空格(读入第一个不是空格的字符)，效果跟cin一样。 如果想要读入一整行，可以用getline(cin, string)(字符数组的我懒得写了)。 根据使用习惯也可以用 a = read<int>() 的方式读入。 read() 函数会返回成功读入了几个数据，可以用来判断是否到达读入文件结尾。 cin >> a ...

有向图强连通分量 简介 强连通分量定义: 在有向图 GGG 中，任意两个节点可以互相到达。 强连通分量（SCC）定义: 极大的强连通子图。 Tarjan 算法 我们先要学习一下 DFS 生成树： 有向图的 DFS 生成树主要有四种边：树边，返祖边，横叉边，前向边。 考虑 DFS 生成树与强连通分量的关系：如果节点 xxx 是某个强联通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其他节点肯定在搜索树中以 xxx 为根的子树中。 Tarjan 算法求强连通分量需要维护两个数组： dfnxdfn_xdfnx​ ：DFS 时节点 xxx 被遍历的次序。 lowxlow_xlowx​ ：在 xxx 的子树中能回溯到的最早的在栈里的节点。 使用 DFS 对图中的所有节点进行搜索，维护每个节点的 dfndfndfn 和 lowlowlow 变量，且让搜索到的节点入栈。每找到一个强连通分量，就让这个强连通分量里所有节点出栈。在搜索过程中，对于节点 xxx 和 xxx 能直接到达的节点 yyy 考虑 333 中情况： yyy 未被访问：继续对 yyy 进行搜索。在回溯过程中，用 lowyl ...

听着名字高大上，其实就是 kruskal MST 多加了一步而已。 构建方法 我们还是维持原来跑 kruskal MST 的过程： 首先新建 nnn 个集合，代表图上的每个点，点权都是 000。 每一次加边会合并两个集合，合并方法是新建一个点，点权为这次加入的边的边权，同时将两个集合的根节点分别设为新建点的左右儿子，然后合并成一个集合，根为新建点。 在进行 n−1n-1n−1 轮合并后，我们得到了恰有 nnn 个叶子的二叉树，同时每个非叶子节点都有两个儿子，这棵树就叫 kruskal 重构树。 这里套用一下 OI-Wiki 的图： 这张图的 kruskal 重构树为: 性质 原图中两点之间所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = kruskal 重构树上两点间 LCA 的权值。 例题 LOJ137 最小瓶颈路 题目求的就是两点间简单路径上最大边权的最小值，直接敲一个 kruskal 重构树再敲个 LCA 就行了。 NOI2018 归程 首先每条边有两个属性: 长度，海拔；因为这两个属性互不影响，而且家固定在节点 111，也就是终点固定， ...

鸽子要跑路 Description 鸽子一开始位于平面直角坐标系上的整点 (a,b)(a, b)(a,b)，每次可以上下左右走一个单位(保证坐标非负)。鸽子的家在 (c,d)(c,d)(c,d)。 鸽子的疲劳值初始值为 000。如果鸽子当前位置 (x,y)(x,y)(x,y) 满足 x and⁡ y>0x \, \operatorname{and} \, y > 0xandy>0，鸽子的疲劳值就要加 111，否则疲劳值不增加。and⁡\operatorname{and}and 是按位与。起点与终点的疲劳值不计入答案。 求鸽子回家的最小疲劳值。 Input 第一行数据组数 TTT。 接下来 TTT 行，每行四个整数 a,b,c,da, b, c, da,b,c,d。 Output TTT 行，每行一个整数表示答案。 Hint T≤105,a,b,c,d≤1018T \le 10^5, a,b,c,d \le 10^{18}T≤105,a,b,c,d≤1018。 Solution 打个表可以发现，xand⁡y=0x \operatorname{and} y = 0xand ...

PolarSea 与边割集 Description 给定一棵 nnn 个点的无向树，边带权，树上每个点有三种状态：无归属、属于 SolarPea、属于 PolarSea。 SolarPea 和 PolarSea 想要断掉一些边，使得对于每一对点 (x,y)(x,y)(x,y)，若 xxx 属于 SolarPea，yyy 属于 PolarSea，则 x,yx,yx,y 不连通。 求断掉的边的最小权值和。 Input 第一行包含一个整数 nnn。 接下来 n−1n-1n−1 行，每行包含三个数 u,v,wu,v,wu,v,w， 表示一条连接 u,vu,vu,v，权值为 www 的边。保证给出的是一棵树。 接下来一行，首先包含一个数 sss，表示属于 SolarPea 的点数。接下来 sss 个不同的数 a1,⋯ ,asa_1,\cdots,a_sa1​,⋯,as​，表示所有属于 SolarPea 的点。 接下来一行，首先包含一个数 ppp，表示属于 PolarSea 的点数。接下来 ppp 个不同的数 b1,⋯ ,bpb_1,\cdots,b_pb1​,⋯,bp​，表示所有属于 Polar ...

序列 Description 小 Y 酷爱的接龙游戏正是这样。玩腻了成语接龙之后，小 决定尝试无平方因子二元合数接龙，规则如下： 现有 nnn 个不超过 10610^6106 的合数，每个均可表示为 a=pqa=pqa=pq ( p,qp,qp,q 为两个互异素数)。 若 a=p1q1(p1<q1)a=p_1 q_1 (p_1 < q_1)a=p1​q1​(p1​<q1​) , b=p2q2(p2<q2)b=p_2 q_2(p_2 < q_2)b=p2​q2​(p2​<q2​) ，当且仅当 q1=p2q_1 = p_2q1​=p2​ 时 bbb 能接在 aaa 后面。 请问从给定的这 nnn 个数中选数接龙，最长可以形成一个包含多少数的接龙序列？ Input 第一行输入一个正整数 nnn, 意义如题干所述。 第二行输入 nnn 个不超过 10610^6106 的合数。 Output 输出一个整数表示答案。 Hint n≤5×104n \le 5 \times 10^4n≤5×104。 Solution 把一个数 a=pqa = p qa=pq 看成 ...

GCD 和 LCM Description TTT 个询问，每次询问给出三个整数 n,m,an, m, an,m,a，求： ∑i=1n∑j=1mlcm⁡(i,j)[gcd⁡(i,j)≤a]\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i,j) [\gcd(i,j) \le a] i=1∑n​j=1∑m​lcm(i,j)[gcd(i,j)≤a] Input 第一行读入 TTT。 接下来 TTT 行，每行三个整数 n,m,an, m, an,m,a。 Output TTT 行，表示每个询问的答案。 Hint T≤104,n,m,a≤105T \le 10^4, n,m,a \le 10^5T≤104,n,m,a≤105 Solution 套路莫比乌斯反演，下面设 n≤mn \le mn≤m。 ∑i=1n∑j=1mlim⁡(i,j)[gcd⁡(i,j)≤a]=∑d=1min⁡(n,a)1d∑i=1n∑i=1mij[gcd⁡(i,j)=d]=∑d=1min⁡(n,a)d∑i=1⌊nd⌋∑j=1⌊md⌋ij[gcd⁡(i,j)=1]=∑d=1m ...

精神焕发 Description 给出一棵 nnn 个点的树，点从 111 至 nnn 编号。每个点 uuu 上有足够多瓶加血 wuw_uwu​ 的药水，如果原来你的血量为 xxx*，那么喝下这瓶药水后你的血量会变为 x+wux+w_ux+wu​。 有 qqq 次询问。每次询问给出数 xxx 与两个点的编号 sss、ttt。 这次询问中，你的初始血量为 xxx，一开始在 sss，想要走到 ttt。每次走到一个点，你就会喝下这个点上的药水（一开始来到点 sss 时会喝下 sss 上的药水）。你可以多次经过一个点，每次经过时都会喝下一瓶这个点上的药水。如果某个时刻你的血量小于 000，那么你就死了。你想知道你是否可以在不死的情况下从 sss 走到 ttt。 更形式化地，你需要判断是否存在一个点的编号组成的序列 p1…kp_{1 \dots k}p1…k​，满足： p1=sp_1=sp1​=s，pk=tp_k=tpk​=t； 对于任意 i∈[1,k−1]i \in [1,k-1]i∈[1,k−1]，树上的点 pip_ipi​ 与 pi+1p_{i+1}pi+1​ 之间有一条边。 对于任意 ...

环 Description 对于一个长度为 nnn 的 010101 串，下标从 000 到 n−1n-1n−1 。定义两种类型的操作： A类型：选择一个 xxx，将序列循环右移 xxx 位，也就是新序列的第 (i+x) mod n(i+x) \bmod n(i+x)modn 位对应原序列的第 iii 位。 B类型：选择一个 xxx ，满足序列的第 xxx 个位置位 111 ，且第 (x+1) mod n(x+1) \bmod n(x+1)modn 位不为 111 ，交换序列的第 xxx 个位置和第 (x+1) mod n(x+1) \bmod n(x+1)modn 个位置的字符。 给定 n,k,ln,k,ln,k,l 。请构造一个由 lll 个长度为 nnn 的 010101 串构成的序列 SSS，下标从 000 开始。使得序列中每个串恰好有 kkk 个 111 。且对于 0≤i<l−10 \le i < l-10≤i<l−1，SiS_iSi​ 既可以通过一次A类型的操作，也可以通过一次B类型的操作，变为 Si+1S_{i+1}Si+1​。 Input 第一行一个整 ...

军训 Description 起点 (0,0)(0,0)(0,0) ，每次只能走恰好曼哈顿距离为 kkk 的点，构造一种到达 (x,y)(x,y)(x,y) 且步数最小的方案，无解输出 -1。 Input 一行三个整数 k,x,yk, x, yk,x,y 。 Output 若无解，一行一个整数 -1。 否则第一行一个整数 sss, 代表最小操作次数。 接下来 sss 行，第 iii 行两个整数 xi,yix_i, y_ixi​,yi​, 表示第 iii 次操作后的坐标，若多组解任意输出一组。 Hint 1≤k≤109,−105≤x,y≤105,(x,y)≠(0,0)1 \le k \le 10^9, -10^5 \le x,y \le 10^5, (x,y) \not = (0,0)1≤k≤109,−105≤x,y≤105,(x,y)=(0,0) Solution 因为 x,yx,yx,y 可正可负，不如先将 x,yx,yx,y 取绝对值，输出时判符号。 如果 kkk 是奇数，那么所有坐标都可达(存在一种方案从 (x,y)(x,y)(x,y) 走到 (x+1,y)(x+1,y)(x ...