解题思路 1.除了最长的路径,所有的路径均需要走两遍,使用转化思想,将问题转化为两遍路径(2 * (n - 1))-最长路径(step)即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n; while(cin >> n){ unordered_map<int, vector<int>> f; //n-1条边无向连通图,不可能有环 int u, v; for(int i = 0; i <...

解题思路 1.使用广度优先搜索分别计算当前节点的S值和T值,S值即为以当前节点i为起始点所有能访问的节点数,T值则为对所有节点执行广度优先搜索,当前节点i被访问的次数; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n, m; while(cin >> n >> m){ int u, v; unordered_map<int, unordered_set<int>> f; //第二维使用set的原因在...

解题思路 1.注意走的是网格点,直接使用动态规划即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int m, n; while(cin >> m >> n){ vector<vector<int>> f(m + 2, vector<int>(n + 2)); //注意走的是网格点 f[1][1] = 1; for(int i = 1; i <= m + 1; i++){...

解题思路 1.同条路线的站点互通只需要一辆公交车即可,建立虚拟节点连接同条公交路线的各个站点,以此建图;每条公交路线的虚拟节点不一样,且不能与实际节点重合,虚拟节点编号可考虑在一个基础值之上递增;从source到target的路径数除以2即为最小代价; 代码 #include <bits/stdc++.h> using namespace std; int bfs(unordered_map<int, vector<int>>& g, vector<bool>& isVisited, int t){ //返回最小代价,不能到达...

解题思路 1.遍历每个节点,使用广度优先搜索验证当前点是否符合条件,简单模拟即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n, m; while(cin >> n >> m){ unordered_map<int, unordered_set<int>> f; //保存图(节点,相邻节点) 去掉重边 int u, v; for(int i = 0; i < m; i++)...

解题思路 1.根据题意模拟,字符串s每增加一个元素算出其最大字典序子序列,新增元素与ans中元素对比,寻找s[i]第一次大于ans[j]的位置,新的ans等于ans.substr(0, j) + s[i]; 代码 #include <bits/stdc++.h> using namespace std; int main(){ string s; while(cin >> s){ string ans; ans += s[0]; for(int i = 1; i < s.size(); i++){...

解题思路 1.使用前缀和统计满足条件的选择个数,一组测试用例可能包含多组数据注意输入输出; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n, t, c; while(cin >> n >> t >> c){ //一组测试用例可能包含多组数据 vector<long long> f(n); //前缀和 看数据范围 for(int i = 0; i < n; i++){ in...

解题思路 1.使用栈存储未匹配的左右括号,当当前括号为右括号,栈顶元素为左括号时,两括号匹配,将栈顶元素出栈;否则,将当前括号入栈;遍历完字符串后,遍历栈,统计栈中左右括号的数量,即为需要在字符串开头或结尾添加的右左括号数量; 代码 #include <bits/stdc++.h> using namespace std; int main(){ string s; while(cin >> s){ stack<char> sk; for(auto& ch : s){ if(c...

解题思路 寻找最小点(x1,y1)和最大点(x2,y2),取最大边长即为最小正方形边长;注意输入输出,简单模拟即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n; while(cin >> n){ //注意题目,同时输入多组数据 int x1 = INT_MAX, y1 = INT_MAX, x2 = INT_MIN, y2 = INT_MIN; while(n){ int x0, y0; ...

解题思路 1.可证明任意合并顺序所获得分均一样,简单模拟即可; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> w(n); for(int i = 0; i < n; i++){ cin >> w[i]; } int score = 0, sum = w[0]; for(int i = 1; i < n; i++){ //任意合并顺...

解题思路 1.枚举[1:1000]区间的素数,统计素数对时需要去重(定义第一个数小于等于第二个数即可); 代码 #include <bits/stdc++.h> using namespace std; bool check(int t){ //校验i是否为质数 i > 1 if(t < 4) return true; for(int i = 2; i * i <= t; i++){ if(t % i == 0) return false; } return true; } int main(){ in...

解题思路 1.数组所有点横坐标不一样,按横坐标升序排列,最大点其实就是横坐标或纵坐标大于等于其他所有点的点;当前i位置点能成为最大点的条件是,i的纵坐标大于等于[i+1:n-1]区间位置点的纵坐标,故逆序遍历数组,x保存[i+1:n-1]区间最大纵坐标值,当i的纵坐标大于等于x时,当前点即为最大点,保存当前点的坐标,最后逆序输出坐标值; 代码 #include <bits/stdc++.h> using namespace std; int main(){ int n ; cin >> n; vector<pair<int, in...

解题思路 1.使用无序哈希表unordered_map<int,vector>存储(喜好值, 用户编号),使用二分查找的方法确定用户边界; 代码 #include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; int main(){ int n ; cin >> n; unordered_map<int, vector<int>&gt...

解题思路 1.遍历数组,依次枚举第一名特工的位置i,使用二分查找找出第三名特工的最远位置pos,则第二第三名特工的位置可在[i+1:pos]区间任意选择,累加所有选择即可,注意防止整形溢出; 代码 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n, d; cin >> n; cin >> d; vector<int> v(n); int ...