思路  树的模拟  #include <bits/stdc++.h> //#define int long long const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; using namespace std; struct node { int win, lose; }tree[1 << 19]; int k; int dfs(int v) { if(v >= (1 << k)) return 1; if(tree[v].win < tree[v].lose) return 0; tree[v...

思路  判断连通块的个数，直接用dfs(), 把连通块全部标记为访问过，枚举从某个点出发 坑点，如果我们从宝藏的进入dfs()，宝藏应该提前判断  #include <bits/stdc++.h> //#define int long long const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; using namespace std; string g[N]; string st[N]; int n, m, ff; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; void ...

思路  模拟整个过程 用优先队列保证，每次处理的是人数最少的学校 注意一个点，当第二种情况发生的时候，此时这个赛场不可能又当前学校的队员，所以对当前学校来说，这个教室也是新开的  #include <bits/stdc++.h> //#define int long long const int N = 1e3 + 10; const int INF = 0x3f3f3f3f; using namespace std; map<string, int> ans; vector<int> room; // 记录每个赛场剩余位置 vector<string...

思路  题目定义的两个人之间的距离是最小距离并且是可以传递的。所以用Floyd求出任何两个人之间的最小距离 异性缘说的是，异性对本人的距离。所以在枚举的时候，如果评女性（x）的异性缘, 对于每个男性(y)， 我们找的是g[y][x]的最大值, 而不是g[x][y]。 有一个坑点是，如果两个人之间没有距离，我们初始化为正无穷，在考虑异性缘的时候这样的人不能直接不考虑，如代码63和91行 上述情况距离正无穷说明，异性缘1/d，是负无穷，这是符合题意的 对于男女分别讨论的题我们一般，直接把男生和女生分别存起来。 男女的处理一般相同，所以我们尽量把处理操作写成函数，增加阅读性，减上代码的重复  #in...

思路  超绝恶心题 最大的坑点，正零和负零。因为cin读入负零和正零都是零，所以直接用int读入是不可以的 封装整合的应用，因为存在大量的相似操作，所以我们写成函数，减少重复的代码，使得思路更加清晰  #include <bits/stdc++.h> //#define int long long const int N = 1e3 + 10; using namespace std; double g[N][N]; vector<int> man; vector<int> woman; int st[N]; void get_max(int x, int ...

思路  超级模拟 存好结构体之后，直接按照两条排序要求进行排序即可  #include <bits/stdc++.h> //#define int long long const int N = 1e3 + 10; using namespace std; struct node { string name, id; int state, idx; string time; // 构造函数 node(string name, string id, int state, string time, int idx) { this->name = name; this->id...

#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e5 + 10, M = N * 2; const int INF = 0x3f3f3f3f3f3f3f3f; int dad[N], mom[N]; map<int, char> mp; void up(int u, int d, map<int, int>& st)...

非常折磨的维京人 思路  理解题意最重要 这里定义的五代之内和之前愿天下有情人都是失散多年的兄妹这题的五代之内不太一样，本题要求如过A的10代祖先和B的3代祖先相同，那也不能结婚。 假设A、B的共同祖先为C，那么对A来说C是五代之外的祖先，对B来说C五代之外的祖先，同时满足才说明A和B五代之内没有共同祖先。这主要是因为题目没有说给出的两个人是同辈关系。  注意  对于非维京人祖先的处理，可以都相同，但是要特判。或者直接处理为他们的祖先都不同，这样就不同特判了 当枚举A、B两个人的祖先都超过五代的时候，直接结束，他俩一定可以结婚，否则会超时 记录祖先的时候用代数映射祖先姓名，这样遍历才能保证第一...

思路1  dfs 解决连通块问题  #include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e3 + 10, M = N * 2; const int INF = 0x3f3f3f3f3f3f3f3f; int g[N][N]; int n, m; int st[N]; // 访问以u为跟的连通块，并且都设为已经访问 void dfs(int u) { f...

思路  多起点最短路 好像对于多起点的最短路，都是反着搜索。即从终点向起点搜索，这样搜索一次就可以了 这题的坑点：坐标反着给 注意是同时到达大本营的队伍成绩不算，不要看到火拼理解成在路上相遇的队伍（-_-）  #include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e3 + 10, M = N * 2; const int INF = 0x3f3f3f3f...

思路  暴力搜索加剪枝 搜索过程中行或者列的和大于sum剪掉 搜索到(x,y)，假设剩下的都取最大值sum，能否满足要求，如果不能剪掉  #include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e3 + 10, M = N * 2; const int INF = 0x3f3f3f3f3f3f3f3f; int a[N][N]; int srow[N], ...

#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e5 + 10, M = N * 2; const int INF = 0x3f3f3f3f3f3f3f3f; int h[N], e[M], ne[M], idx; int depth[N], dad[N], st[N]; // 当前访问过的所有节点中的最大深度 // 当前访问过的节点的个数 int...

#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e3 + 10, M = N * 2; const int INF = 0x3f3f3f3f3f3f3f3f; void print(stack<int>& tree) { stack<int> tmp; while(tree.size()) { tmp.push(tr...

题目传送门 思路  字符串处理 注意替换词可能再次被替换从而造成错误 注意删除字符之后，要控制指向字符串的指针  #include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N = 1e5 + 10, M = N * 2; const int INF = 0x3f3f3f3f3f3f3f3f; // 判断是不是字母或者数字 bool is_word(char c) { ...