Aurouki

G.Horse Drinks Water（模拟，数学）时间复杂度：$O(t)$题意    将军饮马问题：马处于点$(x_G,y_G)$，将军处于点$(x_T,y_T)$，河水位于x轴正半轴与y轴的正半轴上，求将军饮马的最短距离. 数据范围 $ 0$ $\le x_G,y_G,x_T,y_T \le 10^9$ 思路    签到题，由数据范围知，将军和马一定同处于第一象限，所以将任一点的坐标转换到第二象限，求 直线两点的距离 即可。注意浮点数输入输出。 Code:12345678910111213141516171819202122#include <bits/stdc++.h>#define endl '\n'using i64 = long long;using namespace std;signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); int t; cin > ...

L.Sudoku and Minesweeper(简单构造)题意    有一个$9 \times 9$大小的经典数独，进行 扫雷 游戏，可以将数字替换成$’‘$表示地雷,请构造出一个合法方案，使得剩下的数字*相邻的地雷数量等于该数字，注意，不能将整张地图全部填充地雷. 思路    签到题，从最后一句话入手，不能将全部地图更换为地雷，那整张地图 只安排一个数字 ，因为一个数字相邻的数量最多为8，所以只选择一个非边界的8即可。 Code:123456789101112131415161718192021222324252627#include <bits/stdc++.h>#define endl '\n'using i64 = long long;using namespace std;signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); vector<string> s ...

图(Graph)的相关应用连通图题目链接：https://ac.nowcoder.com/acm/contest/86373/E题意    有一张$n$个点$m$条边组成的无向图，每个节点的权值为$a_i$;现在通过加边将这个图连成连通图，每次连边的代价是新形成的连通块的 最大元素值 ，请问 连通整张图 的最小代价是多少？ 数据范围 $1 \le n \le 10^5,0 \le m \le 10^5$ 题解    从贪心的考虑出发，我们连通图的时候希望代价最小，那么各个连通块应该尽量选择小的连接，不难想到，若起始是$n$个孤立的点进行连接，那么只需要对权值进行 升序排序 ，最终的答案应该是$\sum\limits_{i=2}^{n} w_i$.    回到本题，原始给定的这几条边，我们通过建图可以将连通的边分别统计出最大值，以此缩成一个点，再通过无向图遍历或者并查集维护最大值的方式得到各个连通图的最大权值，将这些点与孤立的点放入一个vector内进行排序，最终遍 ...

E. GCD VS XOR(位运算)时间复杂度：$O(n)$题意    $t$组数据，每组给定一个$x$，求出严格小于$x$的正整数$y$，使得$gcd(x,y)=x \oplus y$；若不存在，则输出“-1”. 数据范围 $1 \le t \le 10^4$ $1 \le x \le 10^{18}$ 思路    签到题，结论就是$y=x-lowbit(x)$或者更为直接的写法$y=x \& (x-1)$,当$x$恰为2的幂次方时，也就是x二进制(从低位往高位)的第一个1就是其本身，即$x=lowbit(x)$，此时答案无解。    从结论出发，不难发现，当$y=x-lowbit(x)$时，即y等于x减去二进制的第一个1时，$lowbit(x)$与$x$一定成倍数，恰好满足gcd的要求，同时两者异或值等于$lowbit(x)$。如二进制数$(1011100)_2$，其$lowbit(x)=(100)_2$,显然，$(1011100)_2=(1000000 ...

树的直径定义    一棵树中最长的简单路径，简单路径是指两点间只被访问一次.    通俗来讲，就是树上的 最长链的长度. 解一：两次DFS遍历  首先，对任意结点(默认为节点1)开始进行第一次DFS，到达距离最远的点一定是直径的一个端点；再次从该端点开始DFS，第二次到达的最远的点必为直径的另一个端点,故两点之间的距离就是树的直径。12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;int n, c;vector<vector<int>> e(n + 1);signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); vector< ...

基环树的定义条边个点的连通图 基环树是一棵”伪树“ 如若不保证连通，它就会成为基环树森林. 基环树的形成 无向图 在一棵基于无向图的无根树上加一条边，构成基环树 去掉环上的任意一条边，基环树变为一棵真正的树 有向图 一个DAG(有向无环图)，如果能在图中加一条边能形成一个自联通的环，则形成一棵基环树. 基础问题找环1.无向图    使用拓扑排序(BFS)实现。 计算所有点的度数，并将度为1的点入队列； 从队列中弹出度为1点，并将其边去掉(相邻点度数减一)，若此时相邻点度为1，则放进队列中； 反复执行，直到队列为空     操作结束后统计所有度数大于1的点，即为环上的点.

核心思路    对于DAG（有向无环图）的有序序列，每次应找到所有入度为零的点存入队列，并将该点的出度清空（“剪断”对应的边）；易知，最终队列中元素出现的次数为n时，拓扑排序完成，否则图中一定出现了环.    PS:拓扑序列并不唯一 Code:123456789101112131415161718auto toposort=[&]() -> bool{ queue<int>q; int tot = 0; for(int i = 1; i <= n; i++) if(!in[i]) q.push(i),tot++; while(!q.empty()){ int temp = q.front(); q.pop(); for(auto it:e[temp]){ in[it]--; if(!in[it]) ...

倍增法Code:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int n, m, s; cin >> n >> m >> s; vector<vector<int>> e(n + 1); vector<vector<int>> fa(n + 1, vector<int>(30)); //fa[u][i]表示以u为根结点，往上2^i层次的父亲编号 vector<int>d ...

1.数星星(二分)题意    天上有n颗星星，每颗星星从第秒（包含边界）开始闪烁，闪烁周期是秒，天上每颗星星每闪烁一次，小度便会记一次数。    假设小度今晚从第l秒开始数，第r秒天就亮了，当数到c颗星星的时候，小度便会睡着。    请问小度今晚是否能睡着？如果能，将在第几秒睡着，反之则输出“-1”。 数据范围 思路    答案具备单调性，且范围极大，正解显然是二分答案！设小度第x秒睡着，显然答案下界为l，上界为r，也就是从l秒开始数直到第x秒结束，判断计数值是否不小于c。    假设星星在第x秒开始闪烁并计数，第y秒结束，闪烁周期为w,则闪烁次数为;如若在第x秒开始闪烁，但从第l秒才开始计数，第y秒结束，则严格大于第l秒的第一次开始计数的时间t为，易知，当y-x能被w整除时，边界点l也需计数一次，同理，之后的计数为. Code:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>#define e ...

A. Creating Words（模拟）使用swap函数对两个字符串第一位交换即可. Code:123456789101112131415#include<bits/stdc++.h>#define int long long#define endl '\n' using namespace std;signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t; while(t--){ string sx, sy; cin >> sx >> sy; swap(sx[0], sy[0]); cout << sx << ' ' << sy << endl; } return 0;} B.Maximum Multiple Sum(模拟)因为n的范围极小，直接遍历找最大值并更新答案即可. Code:12345678910111 ...