并查集题型
并查集解决的是这样一个标准问题：动态维护若干个不相交的集合，支持合并两个集合与查询两个元素是否属于同一集合。但在实际问题中，很少会直接给出“请合并集合”的题目。更多时候，我们需要先从题意中找到“连通关系”或“等价关系”，再判断题目究竟需要这种关系的什么信息。 因此，并查集题型可以沿着两条主线展开： 怎样识别并查集模型：对象是什么，什么算“连通”或“属于同一集合”； 怎样询问：求连通块数量、集合大小、判断是否成环、带权关系推断，还是扩展域的分类问题。 一、怎样从原问题中找到并查集模型 1. 显式的连通性问题 问题直接描述“连通”、“相连”、“属于同一组”等概念，是最直接的并查集应用场景。 典型例题：P1551 亲戚 给定 n 个人、m 对亲戚关系，以及 p 个询问，每次询问两个人是否为亲戚。亲戚关系具有传递性。 解法思路：每个人初始是一个独立的集合。每读入一对亲戚关系，就将两人所在的集合合并。查询时只需判断两人是否在同一集合中。 1234567891011121314151617181920212223242526272829303132const int maxn=5000+...
19岁随笔
不知不觉19啦~~ 记录一下吧 时光倏忽而过，恍惚刚吹完十八岁的生日蜡烛，转眼便站在了十九岁的路口。 回望这一年，你成长了好多好多，从前的你会因为一次考试没有考好而崩溃落泪，会因为一些小事情反复陷入精神内耗，会因为别人的看法而伤心，现在呢，慢慢的你好像强大了起来，不会因为一点点小事就埋头痛哭，遇到事情不在依靠别人，而是自己慢慢尝试解决，解决了自己很多以前感觉不可能的事情，抗压能力真的强了好多好多。但是呢，其实你还是会因为未来而焦虑，还是会因为自己的选择而苦恼，你不知道自己的选择是不是正确的，只能在心里默默承受，纠结当下的选择对错，一遍遍劝慰自己：当下就是最好的。 这一年在忙碌充实又焦虑迷茫交织中度过，认识了好多朋友，遇到了很好很好的室友和朋友，收获了好多。这一年经历了高考，踏入崭新的大学校园，感觉整个人都不一样了。还去了好多好多地方玩，暑假和ysh去景德镇，买了好多好多东西。和家人去了马来西亚，第一次出国玩，很新奇的体验吧。寒假去了和cjj去了南昌，南昌拌粉还有瓦罐汤真的真的好好吃，也很好玩。去比赛浙江省省赛（虽然打铁了，但也是一次很好经历），在杭州和xxy见面吃饭。五一和大学朋...
洛谷P4180 严格次小生成树
P4180 严格次小生成树 - 洛谷 题意 要找一棵“严格大于最小生成树、且权值和最小”的生成树 思路 核心策略是“非树边替换树边”： 先用 Kruskal 算法求出最小生成树，记录其权值总和为 sum。 遍历每一条不在最小生成树中的非树边 $e(u, v, w)$。如果把这条边强行加到树中，树上就会形成一个环（即 $u$ 到 $v$ 的树上路径加上这条新边）。 为了重新变成一棵树，我们需要在这个环里删掉一条原本就在树上的边。 为了让新的树权值总和增加得最少（且严格大于 sum），我们需要在 $u$ 到 $v$ 的树上路径中，找到权值最大、且严格小于 $w$ 的那条树边替换掉。 我使用了Kruskal来求最小生成树，倍增lca来查找 $u$ 到 $v$ 的树上路径中的替换边 分块代码 看完思路后，我们一步一步来分块拆解代码 1.Kruskal 求最小生成树 123456789101112131415161718192021222324252627282930313233struct Edge{ int u,v,w; bool vis;//记录是不是树边...
ABC459
今天只写到D题，但是我还是来写题解了~ A和B感觉没什么好写的，略了。 C 题意 给你N个格子，进行Q次操作 1.在第x个格子里面加1，如果每个格子都大于1，每个格子都需要减去1 2.查询有几个格子大于x 思路 刚开始想着直接暴力，但是一看范围，嗯100%超时 每次所有格子大于1的时候都减掉1，如果暴力遍历所有格子好麻烦，那么！我们干脆不要减了，记录下需要减的次数cnt 在查询x的时候，因为我们没有给每个格子减cnt，所以我们需要给x加上tar是我们最后得出需要查询的值$tar=cnt+x$ 解决了减掉1的麻烦，还有什么麻烦呢？有没有感觉查询大于tar如果每次都遍历一次好麻烦，那么！如何快速的找到几个格子大于tar呢？我们直接开一个数组S[i]来记录累计次数>=i 的单元格数量，现在我们查询只要输出S[tar]即可 好了，问题又来了，我们如何看是否需要cnt++(所有格子减1)，其实思考完上面，这个解决非常简单，只有当所有单元格的次数都大于cnt*的时候，我们才要减掉1，我们已经记录了次数数组S，所以只要$S[cnt+1]==n$ 我们就需要cnt++ 代码 1234567...
图论整合
图的储存 1.邻接矩阵 使用条件：适合点数比较少的,注意处理重边时需取 $\min$。 1234567891011121314const int MAXN = 1005; // 最大顶点数const int INF = 0x3f3f3f3f; // 无穷大int g[MAXN][MAXN]; // g[u][v] 存储 u 到 v 的边权int n, m; // n个点，m条边int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u][v]=min( g[u][v], w ); // 防止重边，取最小权 g[v][u]=min( g[v][u], w );// 如果是无向图，加上这一行 } return 0;} P2245 星际导航 - 洛谷 2.邻接表 适合大部分场景，简...
ABC458
今天写到E题，来写个小小题解吧！ A 题意 给你一个字符串s，删除前面n个和后面n个字母，然后输出 思路 使用substr进行截取 代码 1234567891011void solve(){ string s; cin>>s; int n; cin>>n; s=s.substr(n); int len=s.size(); s=s.substr(0,len-n); cout<<s<<"\n";} B 题意 给你一个二维数组，问每一个单元格的相邻的单元格数 思路 超出范围的不算，我们可以假设都为4，然后如果有在边上的就剪掉 代码 123456789101112131415161718void solve(){ int n,m; cin>>n>>m; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) {...
ABC457
比赛时写到D题，比赛后补完了，记录一下第一次补完，以及第一次写题解 A 题意 给你一个序列A，和下标x, 问第x个元素是多少 思路 直接输出Ax，注意下标从1开始 代码 12345678910void solve(){ int n; cin>>n; vector<int> a(n+1); for(int i=1;i<=n;++i) cin>>a[i]; int x; cin>>x; cout<<a[x]<<'\n';} B 题意 给你N个长度不一样的序列A，和下标x，y，问Ax，y是多少 思路 使用vector的动态数组，注意x和y下标都从1开始 代码 1234567891011121314151617181920void solve(){ int n; cin>>n; vector<int> a[n+1]; for(int i=1;i<=n;++i) ...