机试day12动态规划：用于求解最优解问题，算法与分治法类似，基本思想也是将待求解问题分解成若干字问题，先求解子问题，然后从这些子问题的解得到原问题的解与分治法不同在于适合用动态规划求解的问题，经分解得到的子问题往往不是相互独立的，若用分治法来解决这类问题，则分解得到的子问题数目太多，有些子问题会被重复计算多次eg：斐波那契数列递归求解，如果用原来的递归方法会产生很多不必要的运算，例如Fibonacci(7)=F(6)+F(5)，而计算F(6)又会再计算F(5)为了避免重复计算，可以用一个数组dp来记录计算的中间结果N阶楼梯上楼问题N阶楼梯上楼问题_牛客题霸_牛客网 (nowcoder.com)描述N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）输入描述：输入包括一个整数N,(1<=N<90)。输出描述：可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。#include <iostream> using namespace std; const int MAXN = 90; int dp[MAXN]; void get_upstair() { dp[0] = 1, dp[1] = 2; for (int i = 2; i < MAXN; i++) dp[i] = dp[i-1] + dp[i-2]; } int main() { get_upstair(); int N; while (cin >> N) cout << dp[N-1] << endl; }dp最好使用long long类型，因为结果可能十分大最大连续子序列：在一个给定序列中找出一个连续的子序列，使得这个连续的子序列的和最大，输出最大的序列和最大序列和最大序列和_牛客题霸_牛客网 (nowcoder.com)描述给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。输入描述：第一行为一个正整数N，第二行为N个整数，表示序列中的数。输出描述：输入可能包括多组数据，对于每一组输入数据， 仅输出一个数，表示最大序列和。思路：还是用dp数组存储每个位置当前最大的序列和，每次取max(当前值，上一个最大序列和值+当前值)#include <iostream> #include <algorithm> using namespace std; int main() { int N; while (cin >> N) { long long S[N]; for (int i = 0; i< N; i++) cin >> S[i]; long long dp[N]; dp[0] = S[0]; for (int i = 1; i < N; i++) dp[i] = max(S[i], dp[i-1] + S[i]); sort(dp, dp + N); cout << dp[N-1] << endl; } };最大子矩阵最大子矩阵_牛客题霸_牛客网 (nowcoder.com)描述已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 1)子矩阵。 比如，如下4 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。输入描述：输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。输出描述：输出最大子矩阵的大小。思路：挺复杂的，比一行的要难得多在输入时顺便计算sum数组，存储该数上方（包括自己）一列的和接着使用三个嵌套循环该数+上方1行、2行。。。的值，这样就可以转换为一行的矩阵，然后就按照上一题做法写#include <iostream> #include <algorithm> using namespace std; int main() { int N; while (cin >> N) { int S[N][N], sum[N][N]; for (int i = 0; i< N; i++) { for (int j = 0; j < N; j++) { cin >> S[i][j]; if (i != 0) sum[i][j] = sum[i-1][j] + S[i][j]; else sum[i][j] = S[i][j]; } } int dp[N], arr[N]; int maxn = sum[0][0]; for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { for (int k = 0; k < N; k++) { if (i == 0) arr[k] = sum[j][k]; else arr[k] = sum[j][k] - sum[i-1][k]; } int current = arr[0]; for (int p = 0; p < N; p++) { if (p == 0) dp[p] = arr[p]; else dp[p] = max(arr[p] + dp[p-1], arr[p]); current = max(dp[p], current); maxn = max(current, maxn); } } } cout << maxn << endl; } };法2：更简单，复杂度$O(n^3)$#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<vector<int>> v(n, vector<int>(n)); for(int i = 0; i< n; ++i){ for(int j = 0; j < n; ++j){ cin>>v[i][j]; } } int ans = INT_MIN; for(int i = 0; i < n; ++i){//开始下标i vector<int> sum(n, 0); for (int j = i; j < n; ++j){//结束下标j int b = -32767;//注意此处不要初始化过小导致溢出会出现无厘头结果 for(int k = 0; k < n; ++k){//第k行 sum[k] += v[k][j]; b = max(b+sum[k], sum[k]);//空间优化后的状态方程 ans = max(ans, b);//记录递推过程中的最大值即是最后的结果 } } } cout<<ans<<endl; return 0; }最大连续子序列最大连续子序列_牛客题霸_牛客网 (nowcoder.com)描述给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。输入描述：测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K< 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。输出描述：对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。思路：在原有求最大序列和基础上增加了难度，要求存储该序列的首部尾部元素值我存储的是下标，可以直接取值设置flag，判断输入是否全是负数，如果是直接输出不能再用max了，无法判断哪个是更大的，因此用if比较head、tail变量存储的是最大序列和对应的序列首部尾部元素下标，tmp_head、tmp_tail变量存储的是上一个元素所在序列首部尾部元素下标，每次都要更新#include <iostream> #include <algorithm> using namespace std; int main() { int K; while (cin >> K) { if (K == 0) break; long long S[K]; int flag = 1; for (int i = 0; i < K; i++) { cin >> S[i]; if (S[i] >= 0) flag = 0; } if (!flag) { long long dp[K]; dp[0] = S[0]; long long maxn = S[0]; int head = 0, tail = 0; int tmp_head = 0, tmp_tail = 0; for (int i = 1; i < K; i++) { if (S[i] > dp[i-1] + S[i]) { dp[i] = S[i]; tmp_head = i, tmp_tail = i; } else { dp[i] = dp[i-1] + S[i]; tmp_tail++; } if (maxn < dp[i]) { maxn = dp[i]; head = tmp_head, tail = tmp_tail; } } cout << maxn << " " << S[head] << " " << S[tail] << endl; } else { cout << 0 << " " << S[0] << " "<< S[K-1] << endl; } } };改进：不需要tmp变量，tmp_tail其实就是当前循环的i，只需更新head即可，改进后代码如下long long dp[K]; dp[0] = S[0]; long long maxn = S[0]; int head = 0, tail = 0, tmp_head = 0; for (int i = 1; i < K; i++) { if (S[i] > dp[i-1] + S[i]) { dp[i] = S[i]; tmp_head = i; } else { dp[i] = dp[i-1] + S[i]; } if (maxn < dp[i]) { maxn = dp[i]; head = tmp_head, tail = i; } }最长递增子序列（LIS）：在一个已知序列中，取出若干元素（不必连续）组成一个新的序列，新序列中各个数依旧保持原序列中先后顺序，若此时下标递增，则称此子序列为原序列的一个递增子序列拦截导弹拦截导弹_牛客题霸_牛客网 (nowcoder.com)描述某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。输入描述：每组输入有两行， 第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25）， 第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。输出描述：每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。思路：状态转移方程为$dp[i] = max\{1,dp[j]+1|j\lt i\&\& A_j\ge A_i\}$#include <iostream> using namespace std; int main() { int k; while (cin >> k) { int S[k]; for (int i = 0; i < k; i++) { cin >> S[i]; } int dp[k], answer = 0; for (int i = 0; i < k; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (S[i] <= S[j]) dp[i] = max(dp[i], dp[j] + 1); } answer = max(answer, dp[i]); } cout << answer << endl; } }最大上升子序列和最大上升子序列和_牛客题霸_牛客网 (nowcoder.com)描述一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。输入描述：输入包含多组测试数据。 每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。输出描述：对于每组测试数据，输出其最大上升子序列和。思路：上一题改编即可，确保是大于而不是大于等于，同时dp取得是最大上升子序列和而不是最长上升子序列长度，只需在满足大于条件后，取==上一个最大上升子序列和==、==前面每个数对应最大上升子序列和+当前值==中的最大值#include <iostream> using namespace std; int main() { int N; while (cin >> N) { int S[N]; for (int i = 0; i < N; i++) { cin >> S[i]; } int dp[N], answer = 0; for (int i = 0; i < N; i++) { dp[i] = S[i]; for (int j = 0; j < i; j++) { if (S[i] > S[j]) dp[i] = max(dp[i], dp[j]+S[i]); } answer = max(answer, dp[i]); } cout << answer << endl; } }合唱队形合唱队形_牛客题霸_牛客网 (nowcoder.com)描述N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK， 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入描述：输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。 第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。输出描述：可能包括多组测试数据，对于每组数据， 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。思路：分成两组，一组从前往后，一组从后往前，最后按照从前往后求数组和并减一，得到最大序列数，总数减它即可#include <iostream> using namespace std; int main() { int N; while (cin >> N) { int T[N]; for (int i = 0; i < N; i++) { cin >> T[i]; } int dp1[N], dp2[N], answer = 0; for (int i = 0; i < N; i++) { dp1[i] = 1, dp2[N-i-1] = 1; for (int j = 0; j < i; j++) { if (T[i] > T[j]) dp1[i] = max(dp1[i], dp1[j] + 1); } } for (int i = N-1; i >= 0; i--) { for (int j = N-1; j > i; j--) { if (T[i] > T[j]) dp2[i] = max(dp2[i], dp2[j] + 1); } } for (int i = 0; i < N; i++) { answer = max(answer, dp1[i]+dp2[i]-1); } cout << N - answer << endl; } }最长公共子序列（LCS）：给定两个字符串，求一个最长公共子串，同时为两者的子串，且长度最长思路：dp[i][j]表示以s1[i]作为结尾和以s2[i]作为结尾的最长公共子序列长度两两字符比较，如果一个为空串，dp直接赋0如果俩字符相等，那么就是dp[i-1][j-1] + 1如果俩字符不等，取上一个最大值（i-1和j-1）CoincidenceCoincidence_牛客题霸_牛客网 (nowcoder.com)描述Find a longest common subsequence of two strings.输入描述：First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.输出描述：For each case, output k – the length of a longest common subsequence in one line.#include <bits/stdc++.h> using namespace std; int main() { string s1, s2; while (cin >> s1 >> s2) { int n = s1.size(), m = s2.size(); int dp[n+1][m+1]; // dp[i][j]表示以s1[i]作为结尾和以s2[i]作为结尾的最长公共子序列长度 memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } cout << dp[n][m] << endl; } }背包问题0-1背包：n件物体，每件物体重$w[i]$，价值$v[i]$，现有容量为m的背包，如何选择使得装入背包价值最大dp[i][j]表示前i个物体装进容量为j的背包能获得的最大价值，dp[n][m]即为所求对于容量为j的背包，如果不放入第i件物体，问题转换为将前i-1个物体放入容量为j的背包，即dp[i][j]=dp[i-1][j]对于容量为j的背包，如果放入第i件物体，问题转换为将前i-1个物体放入容量为j-w[i]的背包，即dp[i][j]=dp[i-1][j-w[i]]+v[i]因此取两者最大值为状态转移方程需要注意j-w[i]不小于0，边界价值dp为0优化：去除i-1，因为结果只与二维数组的上一行相关，但必须保证每次更新中确认dp[j]时，dp[j-w[i]]尚未被本次更新修改，因此需要采用倒序遍历j的值（从大到小）完全背包：0-1背包的扩展，每种物体不止可以取一件对于容量为j的背包，如果不放入第i件物体，问题转换为将前i-1个物体放入容量为j的背包，即dp[i][j]=dp[i-1][j]对于容量为j的背包，如果放入第i件物体，此时仍可以取第i个物体，因此dp[i][j]=dp[i][j-w[i]]+v[i]优化后和0-1一样，但是需要正序遍历j多重背包：0-1背包和完全背包之间的折中，即每种物体既不是只能取一件，也不是能取无穷件，而是最多k件点菜问题点菜问题_牛客题霸_牛客网 (nowcoder.com)描述北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。 注意：由于需要营养多样化，每种菜只能点一次。输入描述：输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。输出描述：输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。#include <iostream> #include <cstring> using namespace std; int main() { int C, N; while (cin >> C >> N) { int Pi[N], Vi[N]; for (int i = 0; i < N; i++) { cin >> Pi[i] >> Vi[i]; } int dp[C+1]; memset(dp, 0, sizeof(dp)); for (int i = 0; i < N; i++) { for (int j = C; j >= Pi[i]; j--) { // 剩余的价格要大于等于当前物体的价格 dp[j] = max(dp[j], dp[j-Pi[i]] + Vi[i]); } } cout << dp[C] << endl; } }最小邮票数最小邮票数_牛客题霸_牛客网 (nowcoder.com)描述有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。输入描述：有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。输出描述：对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。思路：本题是0-1背包问题的扩展，原来是求最大值，现在是求能放下的最小邮票数目只需max改为min，v[i]改为1，需要注意初始化赋值不是0而是一个较大的数（题中可以大于20），这时不能用memset赋值，而是要用循环赋值（不然会出现奇怪的数值，是由于memset是对内存值修改）#include <iostream> #include <cstring> using namespace std; int main() { int M, N; while (cin >> M >> N) { int p[N]; for (int i = 0; i < N; i++) { cin >> p[i]; } int dp[M+1]; // memset(dp, 100, sizeof(dp)); for (int i = 0; i <= M; i++) { dp[i] = 100; } dp[0] = 0; for (int i = 0; i < N; i++) { for (int j = M; j >= p[i]; j--) { dp[j] = min(dp[j], dp[j-p[i]] + 1); } } if (dp[M] == 100) cout << 0 << endl; else cout << dp[M] << endl; } }珍惜现在，感恩生活题目：共有资金n元，有m中大米，每种大米价格不等，问最多能采购多少输入：先输入C，表示C组测试案例；每组测试用例第一行两个整数n、m（1<=n,m<=100），分别表示经费金额和大米种类，然后是m行数据，每行包含三个数p、h、c（1<=p<=20 1<=h<=200 1<=c<=20），分别表示每袋大米的价格、每袋大米的质量、大米的袋数输出：能够购买的最大质量思路/原理：降低每种物体的数目可以降低计算复杂度，因此可以将原物品分组，每组个数为$2^0、2^1...2^{c-1}、k-2^{c}+1$，这样可以通过组合得到0到k之间任意件物体价值重量和，即可转化为0-1背包问题#include <bits/stdc++.h> using namespace std; int main() { int caseNumber; cin >> caseNumber; while (caseNumber--) { int n, m; cin >> n >> m; int p[m], h[m], c[m]; vector<int> v, w; int number = 0; for (int i = 0; i < m; i++) { cin >> p[i] >> h[i] >> c[i]; // 开始分解！！关键 for (int j = 1; j <= c[i]; j<<=1) { v.push_back(j * h[i]); w.push_back(j * p[i]); number++; c[i] -= j; } if (c[i] > 0) { v.push_back(c[i] * h[i]); w.push_back(c[i] * p[i]); number++; } } int dp[n+1]; memset(dp, 0, sizeof(dp)); for (int i = 0; i < number; i++) { for (int j = n; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } } cout << dp[n] << endl; } }The Triangle题目：输入一个数字三角形，计算从顶部到底部选取的路径数字和最大值（类似二叉树从根结点到某个叶子节点）输入：输入N，代表N行，然后输入数字三角形输出：路径最大值样例：输入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出： 30从底部开始，直到根结点（逆向思维），dp[i][j]表示从(i, j)出发到底部路径所有值之和最大值#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int dp[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < i + 1; j++) { cin >> dp[i][j]; } } for (int i = N - 2; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]); } } cout << dp[0][0] << endl; }
机试day11最短路径：求图G中两个特定顶点之间最短路径长度应用包括：求两个城市间最短行车距离等经典算法：Dijkstra算法，将顶点集合V分成两个集合S和TS：已确定的顶点集合，初始只含源点sT=V-S：尚未确定的顶点集合算法反复从集合T中选择当前源点s最近的顶点u，将u加入集合S，然后对所有从u发出的边进行松弛操作（贪心策略）畅通工程续题目：已知起点终点，计算最短行走距离，每组第一行包含两个正整数N和M（0<N<200，0<M<1000），分别代表城镇数目和已修建道路数目。接下来是M行道路信息，每行A、B、X表示AB间一条道路距离X。再接下来一行有两个整数S、T代表起点终点#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> #include <climits> using namespace std; const int MAXN = 200; const int INF = INT_MAX; // 无穷大 struct Edge { int to, length; Edge(int t, int l): to(t), length(l) {} }; struct Point { int number, distance; Point(int n, int d): number(n), distance(d) {} bool operator< (const Point& p) const { return distance > p.distance; } }; vector<Edge> graph[MAXN]; // 邻接表实现的图 int dis[MAXN]; // 源点到各点距离 void Dijkstra(int s) { priority_queue<Point> myPriorityQueue; dis[s] = 0; myPriorityQueue.push(Point(s, dis[s])); while (!myPriorityQueue.empty()) { int u = myPriorityQueue.top().number; myPriorityQueue.pop(); for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i].to; int d = graph[u][i].length; if (dis[v] > dis[u] + d) { dis[v] = dis[u] + d; myPriorityQueue.push(Point(v, dis[v])); } } } } int main() { int n, m; while (cin >> n >> m) { memset(graph, 0, sizeof(graph)); fill(dis, dis + n, INF); // 距离初始化为无穷 while (m--) { int from, to, length; cin >> from >> to >> length; graph[from].push_back(Edge(to, length)); graph[to].push_back(Edge(from, length)); } int s, t; cin >> s >> t; Dijkstra(s); if (dis[t] == INF) dis[t] = -1; cout << dis[t] << endl; } }最短路径问题描述给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。输入描述：输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)输出描述：输出 一行有两个数， 最短距离及其花费。思路：在上一题的基础上增加cost，因此需要改变小于号的重载，先比较距离，如果相等再比较花费同时需要注意有俩种满足最小路径的条件，一种是距离更小，一种是距离相等但花费更少#include <iostream> #include <vector> #include <climits> #include <queue> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 1000; const int INF = INT_MAX; struct Edge { int to, length, cost; Edge(int t, int l, int c): to(t), length(l), cost(c) {} }; struct Point { int number, distance, cost; Point(int n, int d, int c): number(n), distance(d), cost(c) {} bool operator< (const Point& p) const { if (distance != p.distance) return distance > p.distance; else return cost > p.cost; } }; vector<Edge> graph[MAXN]; int dis[MAXN], cost[MAXN]; void Dijstra(int s) { priority_queue<Point> myPriorityQueue; dis[s] = 0, cost[s] = 0; myPriorityQueue.push(Point(s, dis[s], cost[s])); while (!myPriorityQueue.empty()) { int u = myPriorityQueue.top().number; myPriorityQueue.pop(); for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i].to; int l = graph[u][i].length; int c = graph[u][i].cost; if (dis[v] > dis[u] + l || (dis[v] == dis[u] + l && cost[v] > cost[u] + c)) { dis[v] = dis[u] + l; cost[v] = cost[u] + c; myPriorityQueue.push(Point(v, dis[v], cost[v])); } } } } int main() { int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; memset(graph, 0, sizeof(graph)); fill(dis, dis + n + 1, INF); fill(cost, cost + n + 1, INF); int a, b, d, p; while (m--) { cin >> a >> b >> d >> p; graph[a].push_back(Edge(b, d, p)); graph[b].push_back(Edge(a, d, p)); } int s, t; cin >> s >> t; Dijstra(s); cout << dis[t] << " " << cost[t] << endl; } }
机试day10畅通工程畅通工程_牛客题霸_牛客网 (nowcoder.com)描述某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。输出描述：对每个测试用例，在1行里输出最少还需要建设的道路数目。输入： 4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0 输出： 1 0 2 998法1：计算集合数目思路：初始每个城镇都是孤立的，读入建成的道路，将道路连接的城镇所在集合合并，表示两个集合中的结点都已连通。最后只需计算有多少集合即可#include <iostream> using namespace std; const int MAXN = 1000; int father[MAXN]; // 父亲结点 int height[MAXN]; // 结点高度 void Initial(int n) { // 初始化 for (int i = 0; i <= n; i++) { father[i] = i; // 每个结点的父亲为自己 height[i] = 0; // 每个结点的高度为0 } } int Find(int x) { // 查找根结点 if (x != father[x]) { // 如果相等，说明此时是父结点 father[x] = Find(father[x]); // 否则继续找父结点的父结点 } return father[x]; } void Union(int x, int y) { // 合并集合 x = Find(x); // 首先找到集合的根结点 y = Find(y); if (x != y) { // 若根结点不同，说明是两个集合，需要进行合并，合并原理是尽可能使树高增加较少 if (height[x] < height[y]) { father[x] = y; // 高度低的集合树根结点的父结点指向另一个集合的根结点 } else if (height[x] > height[y]) { father[y] = x; } else { father[y] = x; // 若高度相等把y加到x的子结点，同时x的高度+1 height[x]++; } } } int main() { int n, m; while (cin >> n) { if (n == 0) break; cin >> m; Initial(n); while (m--) { int x, y; cin >> x >> y; Union(x, y); } int answer = -1; for (int i = 1; i <= n; i++) { if (Find(i) == i) { // 如果不相等，说明此结点不是集合的根结点，反之是根结点，集合数+1（答案） answer++; } } cout << answer << endl; } return 0; }注！！！记住此模板，可以用到很多图论题目中法2：更简单的法使用向量#include<iostream> #include<vector> using namespace std; int main(){ int n, m; while(cin >> n >> m){ int t = n; vector<int> v(n + 1,-1); while(m--){ int x,y; cin>>x>>y; int a = x, b = y; while (v[a] != -1) //一直找到集合的根结点 a = v[a]; while (v[b] != -1) b = v[b]; if(a==b) // 根结点相同 continue; else v[b] = x, t -= 1; //合并集合 } v.clear(); cout<<t-1<<endl; } }连通图连通图_牛客题霸_牛客网 (nowcoder.com)描述给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。输入描述：每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。输出描述：对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。思路：直接套用上一题的模板即可，最后集合数大于0，说明图没有连通#include <iostream> using namespace std; const int MAXN = 1000; int father[MAXN]; // 父亲结点 int height[MAXN]; // 结点高度 void Initial(int n) { // 初始化 for (int i = 0; i <= n; i++) { father[i] = i; // 每个结点的父亲为自己 height[i] = 0; // 每个结点的高度为0 } } int Find(int x) { // 查找根结点 if (x != father[x]) { father[x] = Find(father[x]); } return father[x]; } void Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) { father[x] = y; } else if (height[x] > height[y]) { father[y] = x; } else { father[y] = x; height[x]++; } } } int main() { int n, m; while (cin >> n) { if (n == 0) break; cin >> m; Initial(n); while (m--) { int x, y; cin >> x >> y; Union(x, y); } int answer = -1; for (int i = 1; i <= n; i++) { if (Find(i) == i) { answer++; } } if (answer == 0) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }Is It A Tree?Is It A Tree?_牛客题霸_牛客网 (nowcoder.com)描述A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties. There is exactly one node, called the root, to which no directed edges point. Every node except the root has exactly one edge pointing to it. There is a unique sequence of directed edges from the root to each node. For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.输入描述：The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero and less than 10000.输出描述：For each test case display the line "Case k is a tree." or the line "Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).输入： 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1 输出： Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.思路：仍然使用图来解决，但需要使用有向图，设置入度#include <iostream> using namespace std; const int MAXN = 10000; int father[MAXN]; int height[MAXN]; int inDegree[MAXN]; bool visit[MAXN]; void Initial() { for (int i = 0; i < MAXN; i++) { father[i] = i; height[i] = 0; inDegree[i] = 0; visit[i] = false; } } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } void Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } } } bool isTree() { bool flag = true; int component = 0; int root = 0; for (int i = 0; i < MAXN; i++) { if (!visit[i]) continue; if (father[i] == i) component++; if (inDegree[i] == 0) root++; else if (inDegree[i] > 1) flag = false; } if (component != 1 || root != 1) flag = false; if (component == 0 && root == 0) flag = true; return flag; } int main() { int p, q; Initial(); int caseNumber = 0; while (cin >> p >> q) { if (p == -1 && q == -1) break; if (p == 0 && q == 0) { if (isTree()) cout << "Case " << ++caseNumber << " is a tree." << endl; else cout << "Case " << ++caseNumber << " is not a tree." << endl; Initial(); } else { Union(p, q); inDegree[q]++; visit[p] = true; visit[q] = true; } } }第一题第一题_牛客题霸_牛客网 (nowcoder.com)描述该题的目的是要你统计图的连通分支数。输入描述：每个输入文件包含若干行，每行两个整数i,j，表示节点i和j之间存在一条边。（请使用循环输入，可以参考该网址：https://www.nowcoder.com/discuss/276）输出描述：输出每个图的联通分支数。输入： 1 4 4 3 5 5 输出： 2思路：并查集，检查最终集合数目即可#include <iostream> using namespace std; const int MAXN = 1000000; int father[MAXN]; int height[MAXN]; bool visit[MAXN]; void Initial() { for (int i = 0; i < MAXN; i++) { father[i] = i; height[i] = 0; visit[i] = false; } } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } void Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } } } int main() { int i, j; Initial(); while (cin >> i >> j) { Union(i, j); visit[i] = true, visit[j] = true; } int answer = 0; for (int k = 0; k < MAXN; k++) { if (k == father[k] && visit[k]) answer++; } cout << answer; }改进：本代码有缺陷，由于题目没有说明输入范围，因此最好使用map<int, int> father替换int father[MAXN]，这样就不用设置MAXNHead of a GangHead of a Gang_牛客题霸_牛客网 (nowcoder.com)描述One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A "Gang" is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threthold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.输入描述：For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format: Name1 Name2 Time where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.输出描述：For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.思路：仍然是并查集，设置了一堆数据结构来处理调用的函数和之前无区别，分别是初始化、找根结点、合并集合新设置了两种结构体，分别是Node和GraphNode的i表示name首字母-'A'的数字值，weight表示该结点的权值Graph的total_w表示集合所有结点的权值和（最后会除以2，因为所有结点权值算了两次）、num表示集合中结点数接下来的思路，看注释#include <iostream> #include #include <vector> #include <cstring> using namespace std; const int MAXN = 1000; int father[MAXN]; int height[MAXN]; int weight[26]; void Initial() { for (int i = 0; i < MAXN; i++) { father[i] = i; height[i] = 0; } memset(weight, 0, sizeof(weight)); } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } void Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } } } struct Node { int i, weight; Node(int a, int b): i(a), weight(b) {} }; struct Graph { int total_w, num; Graph(int a, int b): total_w(a), num(b) {} }; int main() { int N, K; while (cin >> N >> K) { Initial(); string name1, name2; int time, flag; for (int i = 0; i < N; i++) { // 本方法缺陷在这里，虽然题目说了name由三个大写字母，但提交发现有的只有一个大写字母，甚至不确定有没有可能给的三个大写字母都不同，如果这样的话本方法失败 cin >> name1 >> name2 >> time; weight[name1[0]-'A'] += time; // 每个结点值唯一值，并增加权重值 weight[name2[0]-'A'] += time; Union(name1[0]-'A', name2[0]-'A'); // 把首字母和A的数字差作为结点值构建并查集 } flag = name1.size(); // 记录name长度 map<int, int> myMap; // 根值和集合id vector<Graph> graph; // 图，存储集合所有结点权值和、结点数目 vector<Node> G_max; // 结点，存储所有集合权值最大的结点信息 int g_num = 0; for (int i = 0; i < 26; i++) { if (weight[i] == 0) // 该字母未出现 continue; int root = Find(i); // 获取该集合根结点值 if (myMap.count(root) == 0) { // 遇到新的集合 myMap[root] = g_num; graph.push_back(Graph(weight[i], 1)); // 集合总权值加入到vector中 G_max.push_back(Node(i, weight[i])); // 结点加入到vector中 g_num++; } else { // 之前就遇到过，则权值和增加，结点数目+1，最大权值更新 int j = myMap[root]; graph[j].total_w += weight[i]; // 更新加上权值 graph[j].num++; if (G_max[j].weight < weight[i]) // 更新修改为该集合的最大权值 G_max[j] = Node(i, weight[i]); } } int gang_num = 0; for (int i = 0; i < g_num; i++) { // 先获取可以视为gang的集合数目并打印 if (graph[i].total_w / 2 > K && graph[i].num> 2) gang_num++; } cout << gang_num << endl; for (int i = 0; i < g_num; i++) { if (graph[i].total_w / 2 > K && graph[i].num> 2) { string name; name += ('A' + G_max[i].i); // 获取name首字母的大写字母 for (int j = 0; j < flag; j++) cout << name; // 循环输出 cout << " " << graph[i].num << endl; // 打印集合结点数目 } } } }改进：对于字符串可能不同可以考虑使用map映射name和id（看的他人代码）知识点最小生成树（MST）：在一个无向连通图中，若存在一个连通子图，它包含原图中的所有顶点和部分边，且子图不存在回路，则称子图为原图的一棵生成树。在带权无向连通图中，所有生成树中边权和最小的那棵被称为最小生成树构造方法：Kruskal算法和Prim算法，其中Kruskal算法更简单且效率非常高Kruskal原理：在要求解的连通图中，任意选择一些点属于集合A，剩余属于集合B，最小生成树必定存在一条权值最小的边，并且这条边两个顶点分别属于A、B的边【反证法证明】算法步骤：初始时所有顶点属于孤立的集合按照边权递增顺序遍历所有边，若遍历到的边的两个顶点分属不同的集合，则确定该边为最小生成树上的一条边，并将该边两个顶点分属的集合合并遍历完所有边后，若原图连通，则被选取的边和所有顶点构成最小生成树，若不连通则最小生成树不存在还是畅通工程还是畅通工程_牛客题霸_牛客网 (nowcoder.com)描述某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。输出描述：对每个测试用例，在1行里输出最小的公路总长度。思路：仍然使用并查集，只不过Union返回的是两个结点是否同为一个集合的bool值，同时定义了Edge结构接收结点值和距离，并使用sort+自定义比较函数Compare来从小到大排列，并依次遍历边本题结果必定有最小生成树，因此不必检查图是否连通#include <iostream> #include <algorithm> #include using namespace std; const int MAXN = 100; int father[MAXN]; int height[MAXN]; struct Edge { int node1, node2, dist; }; bool Compare(Edge x, Edge y) { return x.dist < y.dist; } void Initial(int n) { for (int i = 0; i < n; i++) { father[i] = i; height[i] = 0; } } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } bool Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } return true; } else return false; } int main() { int N; while (cin >> N) { if (N == 0) break; Initial(N); int relation = N * (N - 1) / 2; Edge all[relation]; for (int i = 0; i < relation; i++) { cin >> all[i].node1 >> all[i].node2 >> all[i].dist; } sort(all, all + relation, Compare); int min_len = 0; for (int i = 0; i < relation; i++) { if (Union(all[i].node1-1, all[i].node2-1)) { min_len += all[i].dist; } } cout << min_len << endl; } }继续畅通工程继续畅通工程_牛客题霸_牛客网 (nowcoder.com)描述省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。 当N为0时输入结束。输出描述：每个测试用例的输出占一行，输出全省畅通需要的最低成本。思路：在上一题基础上结构体Edge增加新的isBuild变量表示路是否修建，Compare重新编写，使得为1的排前面注意：做这道题时发现测试报错，原因在Union里输入的数字应该-1，因为初始化是从0~N-1#include <iostream> #include <algorithm> #include using namespace std; const int MAXN = 100; int father[MAXN]; int height[MAXN]; struct Edge { int node1, node2, cost, isBuild; }; bool Compare(Edge x, Edge y) { if (x.isBuild != y.isBuild) return x.isBuild > y.isBuild; else return x.cost < y.cost; } void Initial(int n) { for (int i = 0; i < n; i++) { father[i] = i; height[i] = 0; } } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } bool Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } return true; } else return false; } int main() { int N; while (cin >> N) { if (N == 0) break; Initial(N); int relation = N * (N - 1) / 2; Edge all[relation]; for (int i = 0; i < relation; i++) { cin >> all[i].node1 >> all[i].node2 >> all[i].cost >> all[i].isBuild; } sort(all, all + relation, Compare); int min_cost = 0; for (int i = 0; i < relation; i++) { if (Union(all[i].node1-1, all[i].node2-1)) { if (all[i].isBuild == 0) min_cost += all[i].cost; } } cout << min_cost << endl; } }另外一种思路是，如果遇到isBuild为1，把对应边的长度设置为0也可以FrecklesFreckles_牛客题霸_牛客网 (nowcoder.com)描述In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.输入描述：The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.输出描述：Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.思路：题目大意是给出多个坐标，求出连接所有坐标的最小距离我是把Node转为Edge来做，还是并查集，需要注意数据类型使用double#include <iostream> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; const int MAXN = 100; int father[MAXN]; int height[MAXN]; struct Edge { int node1, node2; double dist; }; struct Node { double x, y; }; bool Compare(Edge x, Edge y) { return x.dist < y.dist; } void Initial(int n) { for (int i = 0; i < n; i++) { father[i] = i; height[i] = 0; } } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } bool Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } return true; } else return false; } int main() { int N; while (cin >> N) { Initial(N); Node nodes[N]; for (int i = 0; i < N; i++) cin >> nodes[i].x >> nodes[i].y; int relation = N * (N - 1) / 2; Edge all[relation]; int k = 0; // 计算边 for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { all[k].node1 = i; all[k].node2 = j; all[k].dist = sqrt(pow(nodes[i].x-nodes[j].x, 2)+pow(nodes[i].y-nodes[j].y, 2)); k++; } } sort(all, all + relation, Compare); double min_len = 0; for (int i = 0; i < relation; i++) { if (Union(all[i].node1, all[i].node2)) { min_len += all[i].dist; } } cout << fixed << setprecision(2); cout << min_len << endl; } }Jungle Roads描述The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.（ps:如果不是连通图的话，最后的结果输出不用包含不在连通图里的那些点）输入描述：The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.输出描述：The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.思路：题目大意就是给了一堆边，让你找最小连通图做法完全和前面相同，无非是换了数据结构来存储数据，本方法使用了vector来存储边#include <iostream> #include <algorithm> #include #include <vector> using namespace std; const int MAXN = 26; int father[MAXN]; int height[MAXN]; struct Edge { int node1, node2, dist; Edge(int a, int b, int c): node1(a), node2(b), dist(c) {} }; bool Compare(Edge x, Edge y) { return x.dist < y.dist; } void Initial(int n) { for (int i = 0; i < n; i++) { father[i] = i; height[i] = 0; } } int Find(int x) { if (x != father[x]) father[x] = Find(father[x]); return father[x]; } bool Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] < height[y]) father[x] = y; else if (height[x] > height[y]) father[y] = x; else { father[y] = x; height[x]++; } return true; } else return false; } int main() { int n; while (cin >> n) { if (n == 0) break; Initial(n); vector<Edge> e; for (int i = 0; i < n-1; i++) { char start; int k; cin >> start >> k; for (int j = 0; j < k; j++) { char village; int dist; cin >> village >> dist; e.push_back(Edge(start-'A', village-'A', dist)); } } sort(e.begin(), e.end(), Compare); int min_len = 0; for (int i = 0; i < e.size(); i++) { if (Union(e[i].node1, e[i].node2)) { min_len += e[i].dist; } } cout << min_len << endl; } }
C++数据结构2二叉树相关知识二叉树递归定义：二叉树要么为空，要么由根节点、左子树、右子树构成遍历方法：前序遍历、中序遍历、后序遍历题目二叉树遍历1二叉树遍历_牛客题霸_牛客网 (nowcoder.com)描述编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。输入描述：输入包括1行字符串，长度不超过100。输出描述：可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。输入： abc##de#g##f### 输出： c b e g d f a 思路：记死二叉树遍历模板就行了#include <iostream> using namespace std; struct TreeNode { char data; TreeNode *leftChild; TreeNode *rightChild; TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {} }; TreeNode* build_tree(int& position, string s) { char node = s[position++]; if (node == '#') return NULL; TreeNode* root = new TreeNode(node); root->leftChild = build_tree(position, s); root->rightChild = build_tree(position, s); return root; } void InOrder(TreeNode* t) { if (t) { InOrder(t->leftChild); cout << t->data << " "; InOrder(t->rightChild); } } int main() { string tree_s; while (cin >> tree_s) { int position = 0; TreeNode* t = build_tree(position, tree_s); InOrder(t); cout << endl; } }二叉树遍历2二叉树遍历_牛客题霸_牛客网 (nowcoder.com)描述二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。输入描述：两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。输出描述：输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。输入： ABC BAC FDXEAG XDEFAG 输出： BCA XEDGAF思路：本题同上一题，都是根据二叉树某种遍历结果求出二叉树，进而求另一种遍历结果本题给出前序遍历和中序遍历，因此能够得到唯一的二叉树；前序的第一个字符肯定是root，而此root必然在中序中，因此可以不断拆分得到二叉树#include <iostream> using namespace std; struct TreeNode { char data; TreeNode *leftChild; TreeNode *rightChild; TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {} }; TreeNode* Build(string str1, string str2) { if (str1.size() == 0) return NULL; char c = str1[0]; TreeNode* root = new TreeNode(c); int position = str2.find(c); root->leftChild = Build(str1.substr(1, position), str2.substr(0, position)); root->rightChild = Build(str1.substr(position+1), str2.substr(position+1)); return root; } void PostOrder(TreeNode* t) { if (t) { PostOrder(t->leftChild); PostOrder(t->rightChild); cout << t->data; } } int main() { string str1, str2; while (cin >> str1 >> str2) { TreeNode* root = Build(str1, str2); PostOrder(root); cout << endl; } }二叉排序树相关知识二叉排序树特征：若左子树非空，则左子树上所有结点关键字的值均小于根结点关键字的值若右子树非空，则右子树上所有结点关键字的值均大于根结点关键字的值左右子树本身也是一棵二叉排序树题目二叉排序树1二叉排序树_牛客题霸_牛客网 (nowcoder.com)描述二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。输入描述：输入包含多组测试数据，每组测试数据两行。 第一行，一个数字N（N<=100），表示待插入的节点数。 第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。输出描述：输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。思路：还是得多练下，二叉树数据结构学的只会概念，代码啥的基本没掌握住，方法是#include <iostream> using namespace std; struct TreeNode { int val; TreeNode *leftChild; TreeNode *rightChild; TreeNode(int v): val(v), leftChild(NULL), rightChild(NULL) {} }; TreeNode* Insert(TreeNode* root, int x, int father) { if (root == NULL) { root = new TreeNode(x); cout << father << endl; } else if (x < root->val) root->leftChild = Insert(root->leftChild, x, root->val); else root->rightChild = Insert(root->rightChild, x, root->val); return root; } int main() { int N; while (cin >> N) { TreeNode* root = NULL; int x; for (int i = 0; i < N; i++) { cin >> x; root = Insert(root, x, -1); } } }二叉排序树2二叉排序树_牛客题霸_牛客网 (nowcoder.com)描述输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。输入描述：输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。输出描述：可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个换行。 输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。思路：先实现Insert，在前序、中序、后序遍历，背住就好#include <iostream> using namespace std; struct TreeNode { int data; TreeNode *leftChild; TreeNode *rightChild; TreeNode(int data): data(data), leftChild(NULL), rightChild(NULL) {} }; TreeNode* Insert(TreeNode* root, int x) { if (root == NULL) root = new TreeNode(x); else if (x < root->data) root->leftChild = Insert(root->leftChild, x); else if (x > root->data) root->rightChild = Insert(root->rightChild, x); return root; } void PreOrder(TreeNode* root) { if (root) { cout << root->data << " "; PreOrder(root->leftChild); PreOrder(root->rightChild); } } void InOrder(TreeNode* root) { if (root) { InOrder(root->leftChild); cout << root->data << " "; InOrder(root->rightChild); } } void PostOrder(TreeNode* root) { if (root) { PostOrder(root->leftChild); PostOrder(root->rightChild); cout << root->data << " "; } } int main() { int n; while (cin >> n) { TreeNode* root = NULL; int x; for (int i = 0; i < n; i++) { cin >> x; root = Insert(root, x); } PreOrder(root); cout << endl; InOrder(root); cout << endl; PostOrder(root); cout << endl; } }二叉搜索树二叉搜索树_牛客题霸_牛客网 (nowcoder.com)描述判断两序列是否为同一二叉搜索树序列输入描述：开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。输出描述：如果序列相同则输出YES，否则输出NO输入： 2 567432 543267 576342 0 输出： YES NO思路：insert函数和之前一样，主要是写compare函数来比较两棵树，从根节点开始若根节点都为空，返回true若只有一个为空，肯定不同，返回false若都不为空，先比较当前节点值，不同返回false，相同再去比较左子树和右子树，从头开始比较#include <iostream> using namespace std; struct TreeNode { char data; TreeNode *leftChild; TreeNode *rightChild; TreeNode(int data): data(data), leftChild(NULL), rightChild(NULL) {} }; TreeNode* Insert(TreeNode* root, char x) { if (root == NULL) root = new TreeNode(x); else if (x < root->data) root->leftChild = Insert(root->leftChild, x); else if (x > root->data) root->rightChild = Insert(root->rightChild, x); return root; } bool compare(TreeNode* base_root, TreeNode* root) { if (base_root == NULL && root == NULL) return true; if (base_root == NULL || root == NULL) return false; if (base_root->data != root->data) return false; bool left_same = compare(base_root->leftChild, root->leftChild); bool right_same = compare(base_root->rightChild, root->rightChild); return left_same && right_same; } int main() { int n; while (cin >> n) { if (n == 0) break; TreeNode* root[n+1]; string s[n+1]; for (int i = 0; i < n + 1; i++) { root[i] = NULL; cin >> s[i]; for (int j = 0; j < s[i].size(); j++) { root[i] = Insert(root[i], s[i][j]); } } for (int i = 0; i < n; i++) { if (compare(root[0], root[i+1])) cout << "YES" << endl; else cout << "NO" << endl; } } }优先队列相关知识#include <queue> priority_queue<typename> name;优先队列：将数据按照事先规定的优先级次序进行动态组织的数据结构，访问元素时，只能访问当前队列中优先级最高的元素，最高级先出题目复数集合复数集合_牛客题霸_牛客网 (nowcoder.com)描述一个复数（x+iy）集合，两种操作作用在该集合上： 1、Pop 表示读出集合中复数模值最大的那个复数，如集合为空 输出 empty ，不为空就输出最大的那个复数并且从集合中删除那个复数，再输出集合的大小SIZE； 2 Insert a+ib 指令（a，b表示实部和虚部），将a+ib加入到集合中 ，输出集合的大小SIZE； 最开始要读入一个int n，表示接下来的n行每一行都是一条命令。输入描述：输入有多组数据。 每组输入一个n(1<=n<=1000)，然后再输入n条指令。输出描述：根据指令输出结果。 模相等的输出b较小的复数。 a和b都是非负数。思路：要设置个结构体，并重载小于号（因为类无法直接比较）#include <iostream> #include <queue> using namespace std; struct Complex { int real, imag; Complex(int a, int b): real(a), imag(b) {} bool operator< (Complex c) const { return real * real + imag * imag < c.real * c.real + c.imag * c.imag; } }; int main() { int n; while (cin >> n) { string str; priority_queue<Complex> myPriorityQueue; for (int i = 0; i < n; i++) { cin >> str; if (str == "Pop") { if (myPriorityQueue.empty()) cout << "empty" << endl; else { Complex current = myPriorityQueue.top(); cout << current.real << "+i" << current.imag << endl; myPriorityQueue.pop(); cout << "SIZE = " << myPriorityQueue.size() << endl; } } else if (str == "Insert") { int a, b; scanf("%d+i%d", &a, &b); myPriorityQueue.push(Complex(a, b)); cout << "SIZE = " << myPriorityQueue.size() << endl; } } } }哈夫曼树在一棵树中，从任意一个节点到达另一个节点的通路称为路径，该路径上所需经过的边的个数被称为该路径的长度。如果过树中结点带有表示某种意义的权值，那么从根节点到该节点的路径长度再乘以该节点的权值被称为该节点的带权路径长度。树中所有叶子节点的带权路径长度之和为该树的带权路径长度和。给定n个带有权值的节点，以他们为叶子节点构造一颗带权路径长度和最小的二叉树，该二叉树为哈夫曼树，也称最优树哈夫曼树求法：所有节点放入集合K若集合K剩余节点数大于1，取出其中权值最小的两个节点，将他们构造成某个新节点的左右子节点，设这个新节点权值为两个子节点的权值和，并放入集合K若集合K仅剩一个节点，则该节点为哈夫曼树的根节点。构造过程中，所有中间节点的权值和，几位该哈夫曼树的带权路径和哈夫曼树_牛客题霸_牛客网 (nowcoder.com)描述哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和的最小值。输入描述：输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。输出描述：输出权值。思路：优先队列处理，需要重新定义优先队列priority_queue<int, vector<int>, greater<int>> myPriorityQueue;#include <functional> #include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n; while (cin >> n) { priority_queue<int, vector<int>, greater<int>> myPriorityQueue; for (int i = 0; i < n; i++) { int x; cin >> x; myPriorityQueue.push(x); } int sum = 0; while (myPriorityQueue.size() != 1) { int a = myPriorityQueue.top(); myPriorityQueue.pop(); int b = myPriorityQueue.top(); myPriorityQueue.pop(); sum = sum + a + b; myPriorityQueue.push(a+b); } cout << sum << endl; } }查找第K小数查找第K小数_牛客题霸_牛客网 (nowcoder.com)描述查找一个数组的第K小的数，注意同样大小算一样大。 如 2 1 3 4 5 2 第三小数为3。输入描述：输入有多组数据。 每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。输出描述：输出第k小的整数。输入： 6 2 1 3 5 2 2 3 输出： 3思路：可以使用优先队列来做#include <functional> #include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n, k; while (cin >> n) { priority_queue<int, vector<int>, greater<int>> myPriorityQueue; for (int i = 0; i < n; i++) { int x; cin >> x; myPriorityQueue.push(x); } cin >> k; int a = 0; while (--k) { a = myPriorityQueue.top(); while (myPriorityQueue.top() == a) myPriorityQueue.pop(); } cout << myPriorityQueue.top() << endl; } }搬水果搬水果_牛客题霸_牛客网 (nowcoder.com)描述在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。 假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。例如有 3 种水果，数目依次为 1，2，9。可以先将 1，2 堆合并，新堆数目为3，耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆，耗费体力为 12。所以小明总共耗费体力=3+12=15，可以证明 15 为最小的体力耗费值。输入描述：每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类数。第二行包含 n 个整数，用空格分隔，第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。输出描述：对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。思路：和哈夫曼树那题一模一样散列表相关知识散列表是一种根据关键字（key）直接进行访问的数据结构，通过简历关键字和存储位置的直接映射关系（map），便可利用关键码直接访问元素，加快查找标准库中提供映射模板map，map是一个将关键字和映射值形成一对映射后进行绑定存储的容器。map底层使用红黑树实现，内部仍然是有序的，其查找效率为$O(logn)$标准库中还有一个无序映射unordered_map，其底层使用散列表实现，期望的查找效率为$O(1)$#include map<typename T1, typename T2> name;map元素的添加或删除：insert()和erase()map元素的访问：[key]at()迭代器map元素操作：find()查找特定元素、clear()清空映射题目查找学生信息查找学生信息_牛客题霸_牛客网 (nowcoder.com)描述输入N个学生的信息，然后进行查询。输入描述：输入的第一行为N，即学生的个数(N<=1000) 接下来的N行包括N个学生的信息，信息格式如下： 01 李江 男 21 02 刘唐 男 23 03 张军 男 19 04 王娜 女 19 然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下： 02 03 01 04输出描述：输出M行，每行包括一个对应于查询的学生的信息。 如果没有对应的学生信息，则输出“No Answer!”思路：使用线性表会很耗时，因此使用映射查找法1：使用结构体接受，比较清晰#include <iostream> #include #include <string> using namespace std; struct Student { string name, gender; int age; }; int main() { int N, M; while (cin >> N) { map<string, Student> myMap; string student_num; Student x; while (N--) { cin >> student_num >> x.name >> x.gender >> x.age; myMap.insert(pair<string, Student>(student_num, x)); } cin >> M; while (M--) { cin >> student_num; if (myMap.find(student_num) != myMap.end()) { x = myMap.at(student_num); cout << student_num << " " << x.name << " " << x.gender << " " << x.age << endl; } else cout << "No Answer!" << endl; } } }法2：每行看作一个字符串（getline()），输入输出较为简单需要注意第一次输入N后需要用getchar()吃掉回车#include <iostream> #include #include <string> using namespace std; int main() { int N, M; while (cin >> N) { getchar(); map<string, string> myMap; string key; while (N--) { string str; getline(cin , str); int pos = str.find(" "); string key = str.substr(0, pos); myMap[key] = str; } cin >> M; while (M--) { cin >> key; string answer = myMap[key]; if (answer == "") answer = "No Answer!"; cout << answer << endl; } } }魔咒词典魔咒词典_牛客题霸_牛客网 (nowcoder.com)描述哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。 给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”输入描述：首先列出词典中不超过100000条不同的魔咒词条，每条格式为： [魔咒] 对应功能 其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束，这一行不属于词典中的词条。 词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。输出描述：每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”输入 [expelliarmus] the disarming charm [rictusempra] send a jet of silver light to hit the enemy [tarantallegra] control the movement of one's legs [serpensortia] shoot a snake out of the end of one's wand [lumos] light the wand [obliviate] the memory charm [expecto patronum] send a Patronus to the dementors [accio] the summoning charm @END@ 4 [lumos] the summoning charm [arha] take me to the sky 输出： light the wand accio what? what?思路：我是使用了两个map来分开存储，需要注意的是不能使用cin直接获取输入，因为中间有空格，要使用getline来获取整行，然后对字符串进行分割#include <iostream> #include #include <string> using namespace std; int main() { string str, magic, function; map<string, string> m2f; map<string, string> f2m; while (getline(cin, str)) { if (str == "@END@") break; int pos = str.find("]"); magic = str.substr(1, pos-1); function = str.substr(pos + 2); m2f[magic] = function; f2m[function] = magic; } int N; cin >> N; string query; getchar(); while (N--) { getline(cin, query); string answer; if (query.find("[") == 0) { query = query.substr(1, query.size()-2); answer = m2f[query]; if (answer == "") answer = "what?"; } else { answer = f2m[query]; if (answer == "") answer = "what?"; } cout << answer << endl; } }可以改进的：题目中说了没有重复的魔咒、功能，因此放在一个映射里也可以子串计算子串计算_牛客题霸_牛客网 (nowcoder.com)描述给出一个01字符串（长度不超过100），求其每一个子串出现的次数。输入描述：输入包含多行，每行一个字符串。输出描述：对每个字符串，输出它所有出现次数在1次以上的子串和这个子串出现的次数，输出按字典序排序。思路：由于map底层采用的红黑树，因此内部会将元素按照关键字字典序排序#include <iostream> #include using namespace std; int main() { string str; while (cin >> str) { map<string, int> myMap; for (int i = 0; i < str.size(); i++) { for (int j = 1; j <= str.size() - i; j++) { string key = str.substr(i, j); if (myMap.find(key) != myMap.end()) myMap[key]++; else myMap[key] = 1; } } map<string, int>::iterator it; for (it = myMap.begin(); it != myMap.end(); it++) { if (it->second > 1) cout << it->first << " " << it->second << endl; } } }统计同成绩学生人数统计同成绩学生人数_牛客题霸_牛客网 (nowcoder.com)描述读入N名学生的成绩，将获得某一给定分数的学生人数输出。输入描述：测试输入包含若干测试用例，每个测试用例的格式为 第1行：N 第2行：N名学生的成绩，相邻两数字用一个空格间隔。 第3行：给定分数 当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。输出描述：对每个测试用例，将获得给定分数的学生人数输出。思路：直接映射map，很好用的，相当于python的字典了#include <iostream> #include using namespace std; int main() { int N; while (cin >> N) { map<int, int> myMap; if (N == 0) break; int score, query; while (N--) { cin >> score; myMap[score]++; } cin >> query; if (myMap.find(query) != myMap.end()) cout << myMap[query] << endl; else cout << 0 << endl; } }注：也可以用countmap.find返回的是迭代器，成功指向要查找的元素，失败指向endmap.count返回整数，1表示有这个元素，0表示无开门人和关门人开门人和关门人_牛客题霸_牛客网 (nowcoder.com)描述每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录，请根据记录找出当天开门和关门的人。输入描述：每天的记录在第一行给出记录的条目数M (M > 0 )，下面是M行，每行的格式为 证件号码 签到时间 签离时间 其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。输出描述：对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。 注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况。思路：使用map可以直接帮我们自动比较字符串的字典序并排列好，很方便需要注意的点：map.begin()或end()属于迭代器，不能+1或-1，要用++或--#include <iostream> #include #include <string> using namespace std; int main() { int M; while (cin >> M) { map<string, string> in; map<string, string> out; string num, in_t, out_t; while (M--) { cin >> num >> in_t >> out_t; in[in_t] = num; out[out_t] = num; } cout << in.begin()->second << " " << (--out.end())->second << endl; } }谁是你的潜在朋友描述“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。 首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。输入描述：每个案例第一行两个整数N,M，2 <= N ，M<= 200。接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1<=P<=M)输出描述：每个案例包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^ ^）思路：分别设置一个数组接收每个读者喜欢的书的编号，一个map接收每本书的喜欢人数#include <iostream> #include using namespace std; int main() { int N, M; while (cin >> N >> M) { map<int, int> myMap; int readers[N]; int p; for (int i = 0; i < N; i++) { cin >> p; myMap[p]++; readers[i] = p; } for (int i = 0; i < N; i++) { if (myMap[readers[i]] == 1) cout << "BeiJu" << endl; else cout << myMap[readers[i]] - 1 << endl; } } }
机试day9鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。输入描述：每组测试数据占1行，每行一个正整数a (a < 32768)输出描述：输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开 如果没有满足要求的答案，则输出两个0。思路：最少时要么全是兔子要么1只鸡剩下全是兔子；最多时全是鸡。出现奇数说明不满足#include <iostream> using namespace std; int main() { int a; while (cin >> a) { int min = 0, max = 0; if (a % 2 == 0) { min = a / 4 + a % 4 / 2; max = a / 2; } cout << min << " " << max << endl; } }代理服务器代理服务器_牛客题霸_牛客网 (nowcoder.com)描述使用代理服务器能够在一定程度上隐藏客户端信息，从而保护用户在互联网上的隐私。我们知道n个代理服务器的IP地址，现在要用它们去访问m个服务器。这 m 个服务器的 IP 地址和访问顺序也已经给出。系统在同一时刻只能使用一个代理服务器，并要求不能用代理服务器去访问和它 IP地址相同的服务器（不然客户端信息很有可能就会被泄露）。在这样的条件下，找到一种使用代理服务器的方案，使得代理服务器切换的次数尽可能得少。输入描述：每个测试数据包括 n + m + 2 行。 第 1 行只包含一个整数 n，表示代理服务器的个数。 第 2行至第n + 1行每行是一个字符串，表示代理服务器的 IP地址。这n个 IP地址两两不相同。 第 n + 2 行只包含一个整数 m，表示要访问的服务器的个数。 第 n + 3 行至第 n + m + 2 行每行是一个字符串，表示要访问的服务器的 IP 地址，按照访问的顺序给出。 每个字符串都是合法的IP地址，形式为“xxx.yyy.zzz.www”，其中任何一部分均是0–255之间的整数。输入数据的任何一行都不包含空格字符。 其中，1<=n<=1000，1<=m<=5000。输出描述：可能有多组测试数据，对于每组输入数据， 输出数据只有一行，包含一个整数s，表示按照要求访问服务器的过程中切换代理服务器的最少次数。第一次使用的代理服务器不计入切换次数中。若没有符合要求的安排方式，则输出-1。输入： 3 166.111.4.100 162.105.131.113 202.112.128.69 6 72.14.235.104 166.111.4.100 207.46.19.190 202.112.128.69 162.105.131.113 118.214.226.52 输出： 1思路：这题真的好烧脑啊啊啊啊啊啊，但我做出来了啊啊啊啊啊啊本题的贪心策略体现在尽可能是连续多个被访问的服务器IP地址都不和代理服务器IP相同，思路逆向来说就是找到最后一个代理服务器前，其他代理服务器均和已访问过的服务器IP地址相匹配。结合测试案例分析来说：在访问第五个服务器时（162.105.131.113），它的IP地址和其中一个代理服务器IP相同，但是另外两个都已在先前访问过，此时162.105.131.113这个IP的代理服务器是最晚出现的（最贪心的），因此改变次数+1#include <cstring> #include <iostream> using namespace std; int main() { int n, m; while (cin >> n) { // 输入代理服务器IP string proxy_s[n]; for (int i = 0; i < n; i++) { cin >> proxy_s[i]; } // 输入访问服务器IP cin >> m; string access_s[m]; for (int i = 0; i < m; i++) { cin >> access_s[i]; } // 定义bool类型数组，true表示改代理服务器被访问过；初始化全为false bool is_accessed[n]; memset(is_accessed, false, sizeof(is_accessed)); int result = 0, access_n = n; // result是改变代理服务器的次数，access_n表示还未被访问过的代理服务器数目，初始为n // 遍历要访问的服务器IP，和代理服务器IP比较 for (int i = 0; i < m; i++) { int j = 0; // 记录下来哪个代理服务器IP被匹配了 for (; j < n; j++) { if (access_s[i] == proxy_s[j] && !is_accessed[j]) { // IP匹配且该代理服务器之前没被访问过 is_accessed[j] = true; // 该代理服务器已被访问 access_n--; //还未被访问过的代理服务器数目-1 break; // 直接退出比较，以记录下该代理服务器下标 } } if (!access_n) { // 如果所有的代理服务器均已被访问，表示需要换一次代理，result++ if (n == 1) { // 特殊情况，只有一个代理服务器，且还被匹配了，直接输出-1 result = -1; break; } result++; access_n = n - 1; // 当前还在使用代理服务器，因此未被访问过的代理服务器数目应为n-1 memset(is_accessed, false, sizeof(is_accessed)); // 全置false is_accessed[j] = true; // 当前的代理服务器设置为true } } cout << result << endl; } }memset要善用，虽然容易写错（溢出之类的？），但是不需要循环初始化值，很方便看了下其他人的解题思路，发现有用二分法（先sort代理服务器IP）加快匹配的，也行，不过既然能pass了，那就没必要再多此一举了To Fill or Not to Fill描述With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.输入描述：For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.输出描述：For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print "The maximum travel distance = X" where X is the maximum possible distance the car can run, accurate up to 2 decimal places.思路：本人除了会写结构体、排序、写输入输出，对于算法设计完全是懵逼的，看了其他人思路只能自叹不如正确做法是将每个距离设置一个bool变量，即bool数组，走过即设置为true；贪婪策略需要我们以最小油价走最长距离，因此排序按照油价排，从最小的装满油箱开始走，直到走完最长距离或者到达终点#include <iostream> #include <algorithm> #include <cstring> using namespace std; struct GasStation { double price; int distance; }; bool stationCompare(GasStation x, GasStation y) { return x.price < y.price; } int main() { int Cmax, D, Davg, N; while (cin >> Cmax >> D >> Davg >> N) { GasStation S[N]; bool tag[D+1]; memset(tag, false, sizeof(tag)); for (int i = 0; i < N; i++) { cin >> S[i].price >> S[i].distance; } sort(S, S+N, stationCompare); double total_price = 0; for (int i = 0; i< N; i++) { int currentdistance = 0; for (int j = S[i].distance + 1; j <= S[i].distance + Cmax * Davg; j++) { if (!tag[j]) { tag[j] = true; currentdistance++; } if (j == D || j == S[i].distance + Cmax * Davg) { total_price += S[i].price * currentdistance / (Davg * 1.0); break; } } } int fill = 1; double max_distance = 0; for (int i = 1; i <= D; i++) { if (!tag[i]) { fill = 0; break; } else max_distance++; } if (fill) printf("%.2f\n", total_price); else printf("The maximum travel distance = %.2f\n", max_distance); } }n的阶乘使用递归实现#include <iostream> using namespace std; long long Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n-1); } int main() { int n; while (cin >> n) { cout << Factorial(n) << endl; } }杨辉三角形打印某一行#include <iostream> using namespace std; int Yanghui(int n, int i) { if (i == 0 || n == i + 1) return 1; else return Yanghui(n-1, i-1) + Yanghui(n-1, i); } int main() { int n; while (cin >> n) { for (int i = 0; i < n; i++) { cout << Yanghui(n, i); if (i != n -1) cout << " "; } } }全排列全排列_牛客题霸_牛客网 (nowcoder.com)描述给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。输入描述：输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。输出描述：输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义： 已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得 s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。 每组样例输出结束后要再输出一个回车。思路：最简单的直接STL（标准库）里algorithm的next_permutation正常思路：递归#include <iostream> #include <algorithm> using namespace std; string str; void swap(int x, int y) { char tmp = str[x]; str[x] = str[y]; str[y] = tmp; } void func(int i, int j) { if (i == j) cout << str << endl; else { for (int m = i; m < str.size(); m++) { string s = str; swap(i, m); sort(str.begin() + i + 1, str.end()); func(i+1, j); str = s; } } } int main() { while (cin >> str) { sort(str.begin(), str.end()); func(0, str.size()-1); } }Fibonacci求第n个Fibonacci数，思路就是递归（分而治之）#include <iostream> using namespace std; int Fibonacci(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return Fibonacci(n-1) + Fibonacci(n-2); } int main() { int n; while (cin >> n) { cout << Fibonacci(n) << endl; } }二叉树二叉树_牛客题霸_牛客网 (nowcoder.com)描述如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。 比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。输入描述：输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。输出描述：对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。输入： 3 12 0 0 输出： 4思路：分别求左子树和右子树节点个数【分治法】#include <iostream> using namespace std; int get_children(int m, int n) { if (m <= n) return 1 + get_children(2 * m, n) + get_children(2 * m + 1, n); else return 0; } int main() { int m, n; while (cin >> m >> n) { if (m == 0) break; cout << get_children(m, n) << endl; } }2的幂次方2的幂次方_牛客题霸_牛客网 (nowcoder.com)描述Every positive number can be presented by the exponential form.For example, 137 = 2^7 + 2^3 + 2^0。 Let's present a^b by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0). Since 7 = 2^2 + 2 + 2^0 and 3 = 2 + 2^0 , 137 is finally presented by 2(2(2)+2 +2(0))+2(2+2(0))+2(0). Given a positive number n,your task is to present n with the exponential form which only contains the digits 0 and 2.输入描述：For each case, the input file contains a positive integer n (n<=20000).输出描述：For each case, you should output the exponential form of n an a single line.Note that,there should not be any additional white spaces in the line.思路：需要先用while循环不断除2求出指数，在递归求指数的2次幂表示；其中如果指数为0或1的，直接s拼接即可#include <iostream> #include <vector> using namespace std; string func(int n) { string s; vector<int> exp; int i = 0; while (n != 0) { if (n % 2 == 1) exp.push_back(i); // vector中添加指数值 n /= 2; i++; } for (int j = exp.size() - 1; j >= 0; j--) { if (exp[j] == 0) // 指数为0直接+2的0次方 s += "2(0)"; else if (exp[j] == 1) // 指数为1直接+2 s += "2"; else s += "2(" + func(exp[j]) + ")"; if (j != 0) // 除了最后一个都添加一个加号 s += "+"; } return s; } int main() { int n; while (cin >> n) { cout << func(n) << endl; } }Catch That Cow题目大意：给定农夫位置N，奶牛K，农夫可以行走：1min从X到X-1或X+1；传送：1min从X到2X，问需要最少时间抓到奶牛思路：使用BFS（宽度优先搜索），从搜索起点开始，不断优先访问当前节点邻居，然后按照访问邻居的顺序去访问每个邻居的所有邻居（已访问的除外）对于本题来说，可以设置二元组状态(n, t)，从(n, t)到下一分钟可能转为三种状态(n-1, t+1)、(n+1, t+1)、(2n, t+1)，因此可使用BFS不断扩展，直到第一次访问到奶牛位置#include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; const int MAXN = 100001; struct Status { int n, t; Status(int n, int t): n(n), t(t) {} }; bool visit[MAXN]; int BFS(int n, int k) { queue<Status> myQueue; myQueue.push(Status(n, 0)); visit[n] = true; while (!myQueue.empty()) { Status current = myQueue.front(); myQueue.pop(); if (current.n == k) return current.t; for (int i = 0; i < 3; i++) { Status next(current.n, current.t + 1); if (i == 0) next.n += 1; else if (i == 1) next.n -= 1; else if (i == 2) next.n *= 2; if (next.n < 0 || next.n > MAXN || visit[next.n]) continue; myQueue.push(next); visit[next.n] = true; } } } int main() { int n, k; cin >> n >> k; memset(visit, false, sizeof(visit)); cout << BFS(n, k); return 0; }Find The Multiple给出一个正整数n，找到n的倍数m，使得m的十进制只包含0和1两种数字思路：BFS找，此处不用担心被访问过的，因为数字始终增大，每次找10*i、10*i+1，这样保证了所有数均含0、1#include <iostream> #include <cstring> #include <queue> using namespace std; int BFS_search(int n) { long long i = 1; queue<long long> myQueue; myQueue.push(i); while (!myQueue.empty()) { i = myQueue.front(); myQueue.pop(); if (i % n == 0) return i; myQueue.push(10 * i); myQueue.push(10 * i + 1); } } int main() { int n; while (cin >> n) { if (n == 0) break; cout << BFS_search(n) << endl; } return 0; }小结：BFS：搜索求解最优解问题DFS：查找问题是否有解A Knight's Journey思路：使用DFS从A1开始遍历，需要使用递归这里需要理解题意：pxq，行是字母，列是数字，如上图我写了个简单的格式。对于字典序，字母小的先访问，然后数字小的先访问#include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; const int MAXN = 30; int p, q; bool visit[MAXN][MAXN]; int direction[8][2] = { {-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2} }; bool DFS(int x, int y, int step, string ans) { if (step == p * q) { cout << ans << endl << endl; return true; } else { for (int i = 0; i < 8; i++) { int nx = x + direction[i][0]; int ny = y + direction[i][1]; char col = ny + 'A'; char row = nx + '1'; if (nx < 0 || nx >= p || ny < 0 || ny >= q || visit[nx][ny]) continue; visit[nx][ny] = true; if (DFS(x, y, step+1, ans + col + row)) return true; visit[nx][ny] = false; } } return false; } int main() { int n; cin >> n; int casenumber = 0; while (n--) { cin >> p >> q; memset(visit, false, sizeof(visit)); cout << "Scenario #" << ++casenumber << ":" << endl; visit[0][0] = true; if (!DFS(0, 0, 1, "A1")) cout << "impossible" << endl << endl; } return 0; }Square题目：木棍拼正方形输入： 3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 3 5 4 4 输出： yes no yes思路：三元组(sum, number, position)，sum表示当前拼凑的木棍总长，number表示已经拼凑成边长的数量，position表示当前木棍的编号首先要按照从大到小排序木棍长度，一个边一个边的拼凑#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 25; int side; int m; int sticks[MAXN]; bool visit[MAXN]; bool DFS(int sum, int number, int position) { if (number == 3) // 剩下的绝对可以凑 return true; int sample = 0; for (int i = position; i < m; i++) { if (visit[i] || sum + sticks[i] > side || sticks[i] == sample) // 加起来超过边长跳过，之前已经试过不可以的跳过（sample接收） continue; visit[i] = true; if (sum + sticks[i] == side) { //直接开始下一条边 if (DFS(0, number + 1, 0)) return true; else sample = sticks[i]; } else { if (DFS(sum + sticks[i], number, i + 1)) // 接着拼凑 return true; else sample = sticks[i]; } visit[i] = false; } return false; } bool Compare(int x, int y) { return x > y; } int main() { int N; cin >> N; while (N--) { cin >> m; int len = 0; for (int i = 0; i < m; i++) { cin >> sticks[i]; len += sticks[i]; } if (len % 4 != 0) // 不能被4整除，直接no cout << "no" << endl; memset(visit, false, sizeof(visit)); sort(sticks, sticks+m, Compare); side = len / 4; if (sticks[0] > side) // 最长木棍超出边长，直接no cout << "no" << endl; if (DFS(0, 0, 0)) cout << "yes" << endl; else cout << "no" << endl; } return 0; }神奇的口袋神奇的口袋_牛客题霸_牛客网 (nowcoder.com)描述有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。输入描述：输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。输出描述：输出不同的选择物品的方式的数目。思路：DFS#include <iostream> #include <algorithm> using namespace std; const int MAXN = 21; int weight[MAXN]; int n, res; void DFS(int w, int index) { for (int i = index; i < n; i++) { int cal = w + weight[i]; if (cal > 40) continue; else if (cal < 40) DFS(cal, i+1); else res++; } } int main() { while (cin >> n) { int total = 0; res = 0; for (int i = 0; i < n; i++) { cin >> weight[i]; total += weight[i]; } if (total < 40) { cout << 0 << endl; continue; } sort(weight, weight+n); if (weight[0] > 40) { cout << 0 << endl; continue; } DFS(0, 0); cout << res << endl; } }八皇后八皇后_牛客题霸_牛客网 (nowcoder.com)描述会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。 给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。输入描述：每组测试数据占1行，包括一个正整数b(1 <= b <= 92)输出描述：输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。法1：思路：这道题花了我很长时间去做，写好代码后一直报栈溢出的错误，debug了快一个小时才发现queen==7那个条件没有return，一直在DFS遍历具体解题方法：首先以第一个queen 1-8 for循环，每次重置use二维布尔数组为falseDFS传入三元组(col_num, queen, queen_s)，col_num表示当前queen的列数，queen表示第几行queen，queen_s表示已经排好的queen串每次进入DFS后，使用for循环根据col_num和queen值，设置该列和所在对角线的所有use布尔值为true，表示会被其他queen吃掉如果遇到一个位置不是true，则queen_s+当前数，并进入下一个DFS，需要注意使用tmp_use和new_queen_s来缓存，这样如果进入DFS没有找到结果，返回后还可以恢复原来的状态#include <cstring> #include <iostream> using namespace std; string s[92]; bool use[8][8]; int num = 0; void DFS(int col_num, int queen, string queen_s) { if (queen == 7) { s[num] = queen_s; num++; return; } for (int i = 1; i + queen < 8; i++) { use[i+queen][col_num] = true; if (col_num+i < 8) use[i+queen][col_num+i] = true; if (col_num-i >= 0) use[i+queen][col_num-i] = true; } for (int i = 0; i < 8; i++) { bool tmp_use[8][8]; memcpy(tmp_use, use, sizeof(use)); string new_queen_s = queen_s; if (use[queen+1][i]) continue; else { new_queen_s.push_back('0'+i+1); DFS(i, queen+1, new_queen_s); memcpy(use, tmp_use, sizeof(tmp_use)); } } } int main() { for (int i = 0; i < 8; i++) { memset(use, false, sizeof(use)); string queen_s = ""; queen_s.push_back('0' + i + 1); DFS(i, 0, queen_s); } int b; while (cin >> b) { cout << s[b-1] << endl; } return 0; }法2：别人的DFS，更简单/* DFS * 行从0到7逐层增加，不会存在重复放到同一行的情况 * 列需要用bool col[8]记录某行是否已经放置 * 对角线则需要用一个bool matrix[8][8](代码里用到矩阵名是djx)，并放到Judge(int x,int y)中判断 * 然后思路就比较简单了，按照DFS对可扩展的状态进行递归 * 每层的可扩展状态满足： * （1）列上没有其它棋子 * （2）对角线上没有棋子 * 好像把DFS中的now换成row更容易理解？ */ #include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxN = 8; bool djx[maxN][maxN] = {false}; bool col[maxN] = {false}; vector<int> vi; //可以用string bool Judge(int x,int y){ //用于判断当前条件下（djx数组目前的状态下）对角线上是否已经有棋子了 int y2 = y; for(int i=x;i>=0;i--){ if(y>=0 && djx[i][y--]==true) return false; if(y2<8 && djx[i][y2++]==true) return false; } return true; } void DFS(int now,int ans){ if(now==8){ vi.push_back(ans); return ; } for(int j=0;j<8;j++){ //完全的DFS思路 if(!col[j] && Judge(now,j)){ col[j] = true; djx[now][j] = true; //注意：题目里的所有数字都是从1开始计数，所以使用j+1记录answer DFS(now+1,ans*10+j+1); //可以用string，由于最长8为十进制数，所以用int了 col[j] = false; djx[now][j] = false; } } } int main(){ DFS(0,0); sort(vi.begin(),vi.end()); //对answer进行排序 int index; while(cin>>index){ cout<<vi[index-1]<<endl; //注意题目中所有数字均为从1计数 } return 0; }
机试day8最大公约数最大公约数_牛客题霸_牛客网 (nowcoder.com)描述输入两个正整数，求其最大公约数。输入描述：测试数据有多组，每组输入两个正整数。输出描述：对于每组输入,请输出其最大公约数。思路：辗转相除法，也可以写个递归的取模函数#include <iostream> using namespace std; int main() { int a, b; while (cin >> a >> b) { int tmp; while (b) { tmp = a % b; a = b; b = tmp; } cout << a << endl; } }最简真分数最简真分数_牛客题霸_牛客网 (nowcoder.com)描述给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。输入描述：每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。输出描述：每行输出最简真分数组合的个数。思路：转换为求最大公约数，如果不为1，则为最简真分数#include <iostream> using namespace std; int is_zuijian(int a, int b) { int tmp; while (b) { tmp = a % b; a = b; b = tmp; } if (a != 1) return 0; else return 1; } int main() { int n; while (cin >> n) { if (n == 0) break; int num[n]; for (int i = 0; i < n; i++) { cin >> num[i]; } int m = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { m += is_zuijian(num[i], num[j]); } } cout << m << endl; } }素数判定素数判定_牛客题霸_牛客网 (nowcoder.com)描述给定一个数n，要求判断其是否为素数（0,1，负数都是非素数）。输入描述：测试数据有多组，每组输入一个数n。输出描述：对于每组输入,若是素数则输出yes，否则输入no。思路：对于大于1的数遍历取模，若余数为0，说明存在银子，不是质数【巧妙方法：比到根号n即可，数论知识】#include <iostream> #include <math.h> using namespace std; int is_prime(int n) { int prime = 1; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { prime = 0; break; } } return prime; } int main() { int n, prime; while (cin >> n) { if (n <= 1) prime = 0; else { prime = is_prime(n); } if (prime) cout << "yes" << endl; else cout << "no" << endl; } }素数素数_牛客题霸_牛客网 (nowcoder.com)描述输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。输入描述：输入有多组数据。 每组一行，输入n。输出描述：输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。思路：本题无非就是多了个要求素数个位为1，直接for循环从11每次加10，每个循环内做一次上一题的is_prime判断#include <iostream> #include <math.h> using namespace std; int is_prime(int n) { int prime = 1; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { prime = 0; break; } } return prime; } int main() { int n, has_prime; while (cin >> n) { has_prime = 0; for (int i = 11; i < n; i += 10) { if (is_prime(i)) { has_prime++; cout << i << ' '; } } if (!has_prime) cout << "-1"; cout << endl; } }瞅了眼题解，发现个搞笑的：他的做法和id很搭配Prime NumberPrime Number_牛客题霸_牛客网 (nowcoder.com)描述Output the k-th prime number.输入描述：k≤10000输出描述：The k-th prime number.思路：本题依然很简单，为了应对不同可能的k值，我们可以提前先找好10000个素数存入vector，直接下标k取值就好做了一个加速【感觉不明显】，首先已经存好2，剩下的只检查奇数#include <iostream> #include <vector> #include <math.h> using namespace std; int is_prime(int n) { int prime = 1; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { prime = 0; break; } } return prime; } int main() { vector<int> prime_number; prime_number.push_back(2); int i = 3; while (prime_number.size() <= 10000) { if (is_prime(i)) prime_number.push_back(i); i += 2; } int k; while (cin >> k) { cout << prime_number[k-1] << endl; } }额外学习下：埃氏筛法埃氏筛法：用已经筛选出的素数去过滤所有能整除它的数，但是只能在给定范围内快速筛选，所需时间少很多const int maxn = 10000000; int prime[maxn]; bool IsPrime[maxn];//0代表都是素数 void Find_Prime(){ IsPrime[1] = 1;//1不是素数 int pNum = 0; for(int i = 2; i <= maxn; i++){ if(!IsPrime[i]){ prime[pNum++] = i; } for(int j = 0; j < pNum && i * prime[j] <= maxn; j++){ IsPrime[i * prime[j]] = 1; if(i % prime[j] == 0){ break; } } } }质因数的个数质因数的个数_牛客题霸_牛客网 (nowcoder.com)描述求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。输入描述：可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。输出描述：对于每组数据，输出N的质因数的个数。思路：完全没必要用书上的先求一定范围素数，在一个个遍历可以从2开始，一个个去除N，每遇到一个余0的num++，直到N完全没有该因子#include <iostream> using namespace std; int main() { int N; while (cin >> N) { int num = 0; int factor = 2; while (N != 1) { while (N % factor == 0) { N /= factor; num++; } factor++; } cout << num << endl; } }约数的个数描述输入n个整数,依次输出每个数的约数的个数输入描述：输入的第一行为N，即数组的个数(N<=1000) 接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)输出描述：可能有多组输入数据，对于每组输入数据， 输出N行，其中每一行对应上面的一个数的约数的个数。法1：偏暴力搜索思路：由欧拉函数知，一个合数的因数数目为所有素因数数目+1的乘积，例如$6=2\times3$，即6有$(1+1)\times(1+1)=4$个因数，$12=2^2\times3$，即12有$(2+1)\times(1+1)=6$个因数，以此方式计算约束个数但是由于需要找出素因数，会耗费不少时间（假如N很大，factor++这里循环较长时间），导致程序超时【当然有解决办法，即提前算好素因数】#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int N; while (cin >> N) { int num[N]; for (int i = 0; i < N; i++) { cin >> num[i]; int factor = 2; vector<int> M; while (num[i] != 1) { int factor_num = 0; while (num[i] % factor == 0) { num[i] /= factor; factor_num++; } if (factor_num) M.push_back(factor_num + 1); factor++; } int result = 1; for (int i = 0; i < M.size(); i++) { result *= M[i]; } cout << result << endl; } } }法2：因数成对出现除了完全平方数外，都是成对出现，因此只需计算到$\sqrt{n}$即可，每次+2，如果完全平方数中间+1#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int N; while (cin >> N) { int num[N]; for (int i = 0; i < N; i++) { cin >> num[i]; int result = 0, j; for (j = 1; j < sqrt(num[i]); j++) { if (num[i] % j == 0) { result += 2; } } if (num[i] == j * j) result++; cout << result << endl; } } }整除问题整除问题_牛客题霸_牛客网 (nowcoder.com)描述给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。输入描述：两个整数n(2<=n<=1000)，a(2<=a<=1000)输出描述：一个整数.思路：首先本题目肯定无法使用一般数字类型，因为n的阶乘太大；因此需要结合因数拆解来做这里有一些学网安数当时的味，发现很多当时学的完全可以用到现在这里这道题根本上还是得去做因式分解，文字不好描述，直接上案例：设a=12，则$12=2^2\times3$，我们要做的是找到n的阶乘结果中包含了多少个2和3因数，假设含有i个2和j个3，那么k应该是i/2和j中最大的结果首先还是获取1000以内的素数，使用模板！！！记住它const int MAXN = 1001; vector<int> prime; bool isPrime[MAXN]; void getPrime() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] = false; isPrime[1] = false; for (int i = 2; i < MAXN; i++) { if (!isPrime[i]) { continue; } else { prime.push_back(i); for (int j = i * i; j < MAXN; j += i) { isPrime[j] = false; } } } }getBiggestPrimeFactor用来获取a的最大素因数及其指数，getFactorNum获取n的阶乘中含有最大素因数个数pair<int, int> getBiggestPrimeFactor(int a) { int upper_bound = sqrt(a) + 1; pair<int, int> biggestPrimeFactor = make_pair(1, 0); for (int i = 0; i < a && i < upper_bound; i++) { int factor = prime[i]; int index = 0; while (a % factor == 0) { a /= factor; index++; } if (a == 1) { biggestPrimeFactor.first = factor; biggestPrimeFactor.second = index; break; } } if (a > 1) { biggestPrimeFactor.first = a; biggestPrimeFactor.second = 1; } return biggestPrimeFactor; } int getFactorNum(int n, int factor) { return n == 0? 0: n / factor + getFactorNum(n / factor, factor); } int main() { getPrime(); int a, n; while (cin >> n >> a) { pair<int ,int> biggestPrimeFactor = getBiggestPrimeFactor(a); int factor = biggestPrimeFactor.first; int res = getFactorNum(n, factor); res /= biggestPrimeFactor.second; cout << res << endl; } return 0; }求root(N, k)求root(N, k)_牛客题霸_牛客网 (nowcoder.com)描述N<k时，root(N,k) = N，否则，root(N,k) = root(N',k)。N'为N的k进制表示的各位数字之和。输入x,y,k，输出root(x^y,k)的值 (这里^为乘方，不是异或)，2=<k<=16，0<x,y<2000000000，有一半的测试点里 x^y 会溢出int的范围(>=2000000000)输入描述：每组测试数据包括一行，x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)输出描述：输入可能有多组数据，对于每一组数据，root(x^y, k)的值思路：本题很难，需要做一定的数论推导，得到$N'=N\%(k-1)$的结论同时要注意的是int类型可能无法装得下x、y，所以得用long long；同时需要用快速幂加速计算#include <iostream> using namespace std; long long FastExponentiation(long long x, long long y, int k) { long long result = 1; while (y) { if (y % 2 == 1) { result *= x; result %= k; } y /= 2; x *= x; x %= k; } return result? result: k; } int main() { long long x, y; int k; while (cin >> x >> y >> k) { cout << FastExponentiation(x, y, k-1) << endl; } }计算两个矩阵的乘积计算两个矩阵的乘积_牛客题霸_牛客网 (nowcoder.com)描述计算两个矩阵的乘积，第一个是23,第二个是32输入描述：输入为两个矩阵，其中一个为23的矩阵，另一个为32的矩阵输出描述：一个2*2的矩阵（每一个数字后都跟一个空格）思路：就直接写#include <iostream> using namespace std; int main() { int m1[2][3], m2[3][3]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { cin >> m1[i][j]; } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) { cin >> m2[i][j]; } } for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { int n = 0; for (int k = 0; k < 3; k++) { n += m1[i][k] * m2[k][j]; } cout << n << " "; } cout << endl; } }矩阵幂矩阵幂_牛客题霸_牛客网 (nowcoder.com)描述给定一个n*n的矩阵，求该矩阵的k次幂，即P^k。输入描述：第一行：两个整数n（2<=n<=10）、k（1<=k<=5），两个数字之间用一个空格隔开，含义如上所示。 接下来有n行，每行n个正整数，其中，第i行第j个整数表示矩阵中第i行第j列的矩阵元素Pij且（0<=Pij<=10）。另外，数据保证最后结果不会超过10^8。输出描述：对于每组测试数据，输出其结果。格式为： n行n列个整数，每行数之间用空格隔开，注意，每行最后一个数后面不应该有多余的空格。思路：与上一题不同，这次矩阵大小会变化，因此定义个struct Matrix和矩阵乘法函数同时，为了减少计算时间，使用了矩阵快速幂，与普通快速幂区别在于，初始值不是1，而是单位矩阵（对角线为1，其他为0）#include <iostream> using namespace std; struct Matrix { int m[10][10]; }; Matrix Multiply(Matrix a, Matrix b, int n) { Matrix r; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { r.m[i][j] = 0; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { r.m[i][j] += a.m[i][k] * b.m[k][j]; } } } return r; } Matrix FastExponentiation(Matrix x, int n, int k) { Matrix r; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { r.m[i][j] = 0; } r.m[i][i] = 1; } while (k) { if (k % 2 == 1) { r = Multiply(r, x, n); } k /= 2; x = Multiply(x, x, n); } return r; } int main() { int n, k; while (cin >> n >> k) { Matrix p; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> p.m[i][j]; } } p = FastExponentiation(p, n, k); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << p.m[i][j]; if (j != n -1) cout << " "; } cout << endl; } } }A+B for MatricesA+B for Matrices_牛客题霸_牛客网 (nowcoder.com)描述This time, you are supposed to find A+B where A and B are two matrices, and then count the number of zero rows and columns.输入描述：The input consists of several test cases, each starts with a pair of positive integers M and N (≤10) which are the number of rows and columns of the matrices, respectively. Then 2*M lines follow, each contains N integers in [-100, 100], separated by a space. The first M lines correspond to the elements of A and the second M lines to that of B. The input is terminated by a zero M and that case must NOT be processed.输出描述：For each test case you should output in one line the total number of zero rows and columns of A+B.思路：哎，就是一点点算；可以改进的点是读B的时候可先把行的0找出来#include <iostream> using namespace std; int main() { int M, N; while (cin >> M >> N) { int A[M][N], B[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { cin >> A[i][j]; } } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { cin >> B[i][j]; } } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { A[i][j] += B[i][j]; } } int cnt = 0, flag = 0; for (int i = 0; i < M; i++) { flag = 1; for (int j = 0; j < N; j++) { if (A[i][j] != 0) { flag = 0; } } cnt += flag; } for (int i = 0; i < N; i++) { flag = 1; for (int j = 0; j < M; j++) { if (A[j][i] != 0) { flag = 0; break; } } cnt += flag; } cout << cnt << endl; } }递推数列描述给定a0,a1,以及an=pa(n-1) + qa(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。输入描述：输入包括5个整数：a0、a1、p、q、k。输出描述：第k个数a(k)对10000的模。思路：乍一看，不就是递归么，刷刷写好了，测试案例也没问题，一提交，报错！超时！！！想想也是，清华上机题能简单么#include <iostream> using namespace std; int get_a(int a0, int a1, int p, int q, int k) { if (k > 3) return (p * get_a(a0, a1, p, q, k-1) + q * get_a(a0, a1, p, q, k-2)) % 10000; else if (k == 3) return (p * get_a(a0, a1, p, q, k-1) + q * a1) % 10000; else if (k == 2) return (p * a1 + q * a0) % 10000; else if (k == 1) return a1 % 10000; else return a0 % 10000; } int main() { int a0, a1, p, q, k; while (cin >> a0 >> a1 >> p >> q >> k) { cout << get_a(a0, a1, p, q, k) << endl; } }法1：while型递归思路：这样子写递归貌似会快#include <iostream> using namespace std; int get_a(int a0, int a1, int p, int q, int k) { int cnt = 2, a2; p %= 10000; q %= 10000; if (k == 0) return a0 % 10000; else if (k == 1) return a1 % 10000; else { while (cnt <= k) { a2 = (p * a1 + q * a0) % 10000; a0 = a1; a1 = a2; cnt++; } return a1; } } int main() { int a0, a1, p, q, k; while (cin >> a0 >> a1 >> p >> q >> k) { cout << get_a(a0, a1, p, q, k) << endl; } }法2：转换为矩阵快速幂略，不想学他了，直接复制了代码#include<iostream> #include <cstring> using namespace std; // 递推公式构造的矩阵大小为 2*2 const int MAXN = 2; const int mod = 10000; // 矩阵类，通用 struct Matrix{ int matrix[MAXN][MAXN]; int row, col; Matrix(int r, int c):row(r),col(c){ // 构造函数内将矩阵元素全部初始化为0 memset(matrix, 0, sizeof(matrix)); }; }; // 计算矩阵乘法 Matrix Multiply(Matrix x, Matrix y){ Matrix answer(x.row, y.col); for(int i = 0; i<answer.row; i++){ for(int j = 0; j<answer.col; j++){ for(int k = 0; k<x.col; k++){ // 注意中间结果也要进行取模运算 answer.matrix[i][j] = (answer.matrix[i][j] + x.matrix[i][k] * y.matrix[k][j]) % mod; } } } return answer; } // 构造单位矩阵初始化快速幂结果矩阵 Matrix InitAnswer(Matrix x){ Matrix answer(x.row, x.col); // 元素已全部初始化为0 for(int i=0;i<answer.row;i++) answer.matrix[i][i] = 1; // 对角线元素初始化为1，构造单位矩阵 return answer; } // 核心函数：计算矩阵快速幂 Matrix FastExponentiation(Matrix x, int k){ Matrix answer = InitAnswer(x); while(k>0){ if(k%2==1) // k为奇数则answer累乘当前x answer = Multiply(answer, x); // 矩阵平方，指数减半 x = Multiply(x, x); k /= 2; // 等价于右移一位 k>>=1; } return answer; } int main() { int a0, a1, p, q, k; while (cin >> a0 >> a1 >> p >> q >> k) { // 构造参数矩阵A Matrix answer(MAXN, MAXN); answer.matrix[0][0] = p, answer.matrix[0][1] = q; answer.matrix[1][0] = 1, answer.matrix[1][1] = 0; // 利用矩阵快速幂对参数矩阵A求解k-1次幂 answer = FastExponentiation(answer, k - 1); // A的第一行乘以起始元素列向量 [a1, a0]' 即为an的值，注意大数需要随时取模 int res = ((answer.matrix[0][0] * a1) % mod + (answer.matrix[0][1] * a0) % mod) % mod; cout << res << endl; } return 0; }
C++数据结构1向量相关知识数组存在一个限制：创建数组时必须规定大小，因此可能出现开的太大导致内存浪费的现象，或太小导致数组访问越界因此引入向量：可以改变大小的线性序列容器，与数组相同的是可以通过下标来访问。头文件如下#include <vector>vector的状态：empty()：返回向量是否为空size()：返回向量元素个数vector尾部元素的添加或删除：push_back：尾部添加一个元素，string也有pop_back：尾部删除一个元素，string也有vector元素操作：见词如面inserteraseclearvector迭代器操作begin()：返回向量中的首元素的迭代器beginend()：返回向量中尾元素后一个位置的迭代器下面为使用迭代器获取向量的循环方法vector<int>::iterator it; // 定义迭代器 for (it = myVector.begin(); it != myVector.end(); it++) { printf("%d ", *it); }题目完数VS盈数完数VS盈数_牛客题霸_牛客网 (nowcoder.com)描述一个数如果恰好等于它的各因子(该数本身除外)子和，如：6=3+2+1。则称其为“完数”；若因子之和大于该数，则称其为“盈数”。 求出2到60之间所有“完数”和“盈数”。输入描述：题目没有任何输入。输出描述：输出2到60之间所有“完数”和“盈数”，并以如下形式输出： E: e1 e2 e3 ......(ei为完数) G: g1 g2 g3 ......(gi为盈数) 其中两个数之间要有空格，行尾不加空格。#include <iostream> #include <vector> using namespace std; int main() { vector<int> yingshu; int num; printf("E:"); for (int i = 2; i < 61; i++) { num = 0; for (int j = 1; j <= i / 2; j++) { if (i % j == 0) { num += j; } if (num > i) { yingshu.push_back(i); break; } } if (num == i) { printf(" %d", i); } } printf("\nG:"); for (int i = 0; i < yingshu.size(); i++) { printf(" %d", yingshu[i]); } }vector在图论中邻接表还有应用队列知识队列（Queue）是一种线性的序列结构，其存放的元素按照现行的逻辑次序排列，但操作仅限于序列的两端【先进先出】STL-queue 引用头文件如下#include <queque>定义方法：queue<typename> namequeue状态：同vectorqueue元素添加或删除：push()、pop()queue元素的访问：front()、back()题目约瑟夫问题，猫狗收留领养队列经常用于宽度优先的搜索栈知识和队列一样，栈也是一种线性序列结构，但操作仅限于特定的一端，和queue的区别在于只能用top()来访问栈顶元素题目Zero-complexity TranspositionZero-complexity Transposition_牛客题霸_牛客网 (nowcoder.com)描述You are given a sequence of integer numbers. Zero-complexity transposition of the sequence is the reverse of this sequence. Your task is to write a program that prints zero-complexity transposition of the given sequence.输入描述：For each case, the first line of the input file contains one integer n-length of the sequence (0 ＜ n ≤ 10 000). The second line contains n integers numbers-a1, a2, …, an (-1 000 000 000 000 000 ≤ ai ≤ 1 000 000 000 000 000).输出描述：For each case, on the first line of the output file print the sequence in the reverse order.题目大意就是逆向一组数，需要注意使用long long接收数据，防止溢出#include <iostream> #include <stack> using namespace std; int main() { int n; while (scanf("%d", &n)!=EOF) { stack<long long> a; long long b; for (int i = 0; i < n; i++) { scanf("%lld", &b); a.push(b); } while (!a.empty()) { printf("%lld ", a.top()); a.pop(); } printf("\n"); } return 0; }括号匹配题目大意是不匹配的左括号输出问号，不匹配的右括号输出美元号思路：定义一个栈装左括号下标，每匹配一对弹出一个左括号下标，栈空时右括号无法匹配输出美元号，遍历字符串完后栈里还有没匹配的左括号输出问号，剩下的输出空格【预先定义一个和字符串长度的空格字符串】#include <iostream> #include <stack> using namespace std; int main() { string str; while (cin >> str) { cout << str << endl; stack<int> bracket; string r(str.size(), ' '); for (int i = 0; i < str.size(); i++) { if (str[i] == ')' && bracket.empty()) r[i] = '?'; else if (str[i] == '(') bracket.push(i); else if (str[i] == ')' && !bracket.empty()) bracket.pop(); } while(!bracket.empty()) { r[bracket.top()] = '$'; bracket.pop(); } cout << r << endl; } return 0; }堆栈使用堆栈的使用_牛客题霸_牛客网 (nowcoder.com)描述堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。其中 push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。（注：本题有多组输入，可以参考该网址：https://www.nowcoder.com/discuss/276）输入描述：对于每组测试数据，第一行是一个正整数 n（0 < n <= 10000）。而后的 n 行，每行的第一个字符可能是'P'或者'O'或者'A'；如果是'P'，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O'，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是'A'，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空。输出描述：对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A'操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E'。需要注意：可以边输入边输出的#include <iostream> #include <stack> using namespace std; int main() { int n, num; string c; while (scanf("%d", &n)!=EOF) { stack<int> s; for (int i = 0; i < n; i++) { cin >> c; if (c == "P") { scanf("%d", &num); s.push(num); } else if (c == "O" && !s.empty()) { s.pop(); } else if (c == "A") { if (s.empty()) printf("E\n"); else printf("%d\n", s.top()); } } } }简单计算器描述读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。输入描述：测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。输出描述：对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。输入： 1 + 2 4 + 2 * 5 - 7 / 11 0 输出： 3.00 13.36思路：设计两个栈，分别装数字和计算符号；同时is_prior用来判断符号优先级#include <iostream> #include <stack> #include <math.h> #include <string> using namespace std; float calc(float num1, float num2, char op) { if (op == '+') return num1 + num2; else if (op == '-') return num1- num2; else if (op == '*') return num1 * num2; else return num1 / num2 * 1.0; } int op2num(char op) { if (op == '+') return 0; else if (op == '-') return 1; else if (op == '*') return 2; else return 3; } bool is_prior(char op1, char op2) { //思路是同级或小的，可以计算；优先级大的等下一个在计算 bool cp[4][4] = {{false, false, true, true}, {false, false, true, true}, {false, false, false, false}, {false, false, false, false}}; return cp[op2num(op1)][op2num(op2)]; } int main() { string exp; while (getline(cin, exp)) { stack<float> num; stack<char> ops; exp = exp + " "; int n = 0; if (exp == "0 ") break; else { for (int i = 0; i < exp.size(); i++) { if (exp[i] == ' ' && (exp[i-1] <= '9' && exp[i-1] >= '0')) { num.push(n); // 只有当前字符为空格且上一个为数字才push数字 n = 0; } else if (exp[i] <= '9' && exp[i] >= '0') { n = n * 10 + (exp[i] - '0'); // 字符转数字 } else if (exp[i] == '+' || exp[i] == '-' || exp[i]== '*' || exp[i] == '/') { while (!ops.empty() && !is_prior(ops.top(), exp[i])) { //直到同优先级的计算完再填入当前计算符 float num1 = num.top(); num.pop(); float num2 = num.top(); num.pop(); num.push(calc(num2, num1, ops.top())); ops.pop(); } ops.push(exp[i]); } } while (!ops.empty()) { // 计算字符全部装完，遍历即可 float num1 = num.top(); num.pop(); float num2 = num.top(); num.pop(); num.push(calc(num2, num1, ops.top())); ops.pop(); } } printf("%.2f\n", num.top()); // 保留两位小数 } return 0; }计算表达式计算表达式_牛客题霸_牛客网 (nowcoder.com)描述对于一个不存在括号的表达式进行计算输入描述：存在多组数据，每组数据一行，表达式不存在空格输出描述：输出结果输入： 6/2+3+3*4 输出： 18思路：本题和上一题几乎一样，唯一需要注意的本题不严谨，输出格式有的是int有的是float，所以最好使用c++标准输出cout来输出，这样不用printf里规定%d还是%f了；同时本题没有空格，因此最后结束遍历表达式需要再push一次数字#include <iostream> #include <stack> #include <math.h> #include <string> using namespace std; float calc(float num1, float num2, char op) { if (op == '+') return num1 + num2; else if (op == '-') return num1- num2; else if (op == '*') return num1 * num2; else return num1 / num2; } int op2num(char op) { if (op == '+') return 0; else if (op == '-') return 1; else if (op == '*') return 2; else return 3; } bool is_prior(char op1, char op2) { //思路是同级或小的，可以计算；优先级大的等下一个在计算 bool cp[4][4] = {{false, false, true, true}, {false, false, true, true}, {false, false, false, false}, {false, false, false, false}}; return cp[op2num(op1)][op2num(op2)]; } int main() { string exp; while (getline(cin, exp)) { stack<float> num; stack<char> ops; int n = 0; for (int i = 0; i < exp.size(); i++) { if (exp[i] <= '9' && exp[i] >= '0') { n = n * 10 + (exp[i] - '0'); // 字符转数字 } else { num.push(n); // 只有当前字符为空格且上一个为数字才push数字 n = 0; while (!ops.empty() && !is_prior(ops.top(), exp[i])) { float num1 = num.top(); num.pop(); float num2 = num.top(); num.pop(); num.push(calc(num2, num1, ops.top())); ops.pop(); } ops.push(exp[i]); } } num.push(n); while (!ops.empty()) { // 计算字符全部装完，遍历即可 float num1 = num.top(); num.pop(); float num2 = num.top(); num.pop(); num.push(calc(num2, num1, ops.top())); ops.pop(); } cout << num.top() << endl; // 保留两位小数 } return 0; }
机试day7String MatchingString Matching_牛客题霸_牛客网 (nowcoder.com)描述Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically,the text is a document being edited,and the pattern searched for is a particular word supplied by the user. We assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m<=n.We further assume that the elements of P and T are all alphabets(∑={a,b...,z}).The character arrays P and T are often called strings of characters. We say that pattern P occurs with shift s in the text T if 0<=s<=n and T[s+1..s+m] = P1..m. If P occurs with shift s in T,then we call s a valid shift;otherwise,we calls a invalid shift. Your task is to calculate the number of vald shifts for the given text T and p attern P.输入描述：For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.输出描述：You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.输入： abababab abab 输出： 3思路：就是在练习KMP算法编写#include <iostream> using namespace std; int nextTable[1000]; void get_next(string pattern) { int i = -1, j = 0; nextTable[0] = -1; while (j < pattern.size()) { if (i == -1 || pattern[i] == pattern[j]) { i++; j++; nextTable[j] = i; } else { i = nextTable[i]; } } } int KMP(string text, string pattern) { get_next(pattern); int number = 0; int i = 0, j = 0; while (i < text.size()) { if (j == -1 || text[i] == pattern[j]) { i++; j++; } else { j = nextTable[j]; } if (j == pattern.size()) { number++; j = nextTable[j]; } } return number; } int main() { string text, pattern; while (cin >> text >> pattern) { printf("%d\n", KMP(text, pattern)); } }验证IP地址描述编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255， 用(".")分割。比如，172.16.254.1；同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。数据范围：字符串长度满足 $5\le n\le 50$进阶：空间复杂度$O(n)$，时间复杂度 $O(n)$法1：超极笨的不停if列举法【没脸看】略法2：正则-C++库透露出一种清澈的愚蠢，谁考试能记得呢:cry:，而且还没有对开头为0的不标准ipv4进行判断#include <iostream> #include <regex> bool is_ipv4(string IP) { regex pattern("((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)"); smatch res; if (regex_match(IP, res, pattern)) return true; else return false; } bool is_ipv6(string IP) { regex pattern("/^\s*((([0-9A-Fa-f]{1,4}:){7}([0-9A-Fa-f]{1,4}|:))|(([0-9A-Fa-f]{1,4}:){6}(:[0-9A-Fa-f]{1,4}|((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3})|:))|(([0-9A-Fa-f]{1,4}:){5}(((:[0-9A-Fa-f]{1,4}){1,2})|:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3})|:))|(([0-9A-Fa-f]{1,4}:){4}(((:[0-9A-Fa-f]{1,4}){1,3})|((:[0-9A-Fa-f]{1,4})?:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-Fa-f]{1,4}:){3}(((:[0-9A-Fa-f]{1,4}){1,4})|((:[0-9A-Fa-f]{1,4}){0,2}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-Fa-f]{1,4}:){2}(((:[0-9A-Fa-f]{1,4}){1,5})|((:[0-9A-Fa-f]{1,4}){0,3}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-Fa-f]{1,4}:){1}(((:[0-9A-Fa-f]{1,4}){1,6})|((:[0-9A-Fa-f]{1,4}){0,4}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(:(((:[0-9A-Fa-f]{1,4}){1,7})|((:[0-9A-Fa-f]{1,4}){0,5}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:)))(%.+)?\s*$/"); smatch res; if (regex_match(IP, res, pattern)) return true; else return false; } class Solution { public: /** * 验证IP地址 * @param IP string字符串 一个IP地址字符串 * @return string字符串 */ string solve(string IP) { if (is_ipv4(IP)) return "IPv4"; else if (is_ipv6(IP)) return "IPv6"; else return "Neither"; } };二进制数二进制数_牛客题霸_牛客网 (nowcoder.com)描述大家都知道，数据在计算机里中存储是以二进制的形式存储的。 有一天，小明学了C语言之后，他想知道一个类型为unsigned int 类型的数字，存储在计算机中的二进制串是什么样子的。 你能帮帮小明吗？并且，小明不想要二进制串中前面的没有意义的0串，即要去掉前导0。输入描述：多行，每一行表示要求的数字输出描述：输出共T行。每行输出求得的二进制串。思路：vector之类的数据结构接收每次模2的结果，最后倒着输出#include <iostream> #include <vector> using namespace std; int main() { int n; while (cin >> n) { vector<int> binary; while (n != 0) { binary.push_back(n % 2); n /= 2; } for (int i = binary.size() - 1; i >= 0; i--) { cout << binary[i]; } cout << endl; } }进制转换进制转换_牛客题霸_牛客网 (nowcoder.com)描述将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。输入描述：多组数据，每行为一个长度不超过30位的十进制非负整数。 （注意是10进制数字的个数可能有30个，而非30bits的整数）输出描述：每行输出对应的二进制数。思路：由于长度太长，肯定得用字符串来处理；模2余数好算，看最后一位即可；难点在于除以2后的结果单独写了个chu2函数，从第一位开始遍历算起，如果除以2有余数，则下一位除以2前+10。特殊情况是第一位为1（1除外）的情况，需要最后去除第一位#include <iostream> #include <vector> using namespace std; string chu2(string n) { int num, yu = 0, flag = 0; for (int i = 0; i < n.size(); i++) { num = n[i] - '0'; if (n[i] == '1' && i == 0 && n.size() != 1) flag = 1; else n[i] = (yu * 10 + num) / 2 + '0'; yu = num % 2; } if (flag == 1) n.erase(0, 1); return n; } int main() { string n; while (cin >> n) { vector<int> binary; if (n == "0") binary.push_back(0); else { while (n != "0") { binary.push_back((n[n.size() - 1] - '0') % 2); n = chu2(n); } } for (int i = binary.size() - 1; i >= 0; i--) { cout << binary[i]; } cout << endl; } }10进制 VS 2进制10进制 VS 2进制_牛客题霸_牛客网 (nowcoder.com)描述对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。 例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。输入描述：一个1000位(即10^999)以内的十进制数。输出描述：输入的十进制数的二进制逆序数。输入： 173 输出： 181思路：这题很难，对于十进制转二进制就上一题的方法，但是二进制也要转换为十进制，需要再写个字符串乘法和加法函数直接照抄书上的了，模板题【做的脑CPU都快烧了】#include <iostream> #include <vector> #include <algorithm> using namespace std; string Divide(string str, int x) { int remainder = 0; for (int i = 0; i < str.size(); i++) { int current = remainder * 10 + str[i] - '0'; str[i] = current / x + '0'; remainder = current % x; } int pos = 0; while (str[pos] == '0') pos++; return str.substr(pos); } string Multiple(string str, int x) { int carry = 0; for (int i = str.size() - 1; i >= 0; i--) { int current = x * (str[i] - '0') + carry; str[i] = current % 10 + '0'; carry = current / 10; } if (carry != 0) str = "1" + str; return str; } string Add(string str, int x) { int carry = x; for (int i = str.size() - 1; i >= 0; i--) { int current = (str[i] - '0') + carry; str[i] = current % 10 + '0'; carry = current / 10; } if (carry != 0) str = "1" + str; return str; } int main() { string str; while (cin >> str) { vector<int> binary; while (str.size() != 0) { int last = str[str.size() - 1] - '0'; binary.push_back(last % 2); str = Divide(str, 2); } string answer = "0"; for (int i = 0; i < binary.size(); i++) { answer = Multiple(answer, 2); answer = Add(answer, binary[i]); } cout << answer << endl; } return 0; }进制转换2进制转换2_牛客题霸_牛客网 (nowcoder.com)描述将M进制的数X转换为N进制的数输出。输入描述：输入的第一行包括两个整数：M和N(2<=M,N<=36)。下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。输出描述：输出X的N进制表示的数。输入： 10 2 11 输出： 1011【注意输入时如有字母，则字母为大写，输出时如有字母，则字母为小写。】思路：先转为10进制再转为N进制，要考虑大于10进制的字母形式【难点】需要注意的是int溢出！！！所以用long long#include <iostream> #include <vector> using namespace std; int ch2int(char c) { if (c <= '9' && c >= '0') return c - '0'; else return c - 'A' + 10; } char int2ch(int x) { if (x < 10) return char(x + '0'); else { return char(x - 10 + 'a'); } } int main() { int M, N; cin >> M >> N; string x; cin >> x; long long dec = 0; for (int i = 0; i < x.size(); i++) { dec = M * dec + ch2int(x[i]); } vector<char> n_num; while (dec != 0) { n_num.push_back(int2ch(dec % N)); dec /= N; } for (int i = n_num.size() - 1; i >= 0; i--) { cout << n_num[i]; } cout << endl; }八进制八进制_牛客题霸_牛客网 (nowcoder.com)输入一个整数转为八进制，做了前面的题目此题1min就敲完了#include <iostream> #include <vector> using namespace std; int main() { int N; while (cin >> N) { vector<int> oct; while (N != 0) { oct.push_back(N % 8); N /= 8; } for (int i = oct.size() - 1; i >= 0; i--) { cout << oct[i]; } cout << endl; } }又一版 A+B又一版 A+B_牛客题霸_牛客网 (nowcoder.com)描述输入两个不超过整型定义的非负10进制整数A和B($\le 2^{31}-1$)，输出A+B的m ($1\lt m\lt 10$)进制数。输入描述：输入格式：测试输入包含若干测试用例。每个测试用例占一行，给出m和A，B的值。 当m为0时输入结束。输出描述：输出格式：每个测试用例的输出占一行，输出A+B的m进制数。法1：字符串处理思路：如果A+B不溢出，那就很好做，直接按照正常数字进制转换即可；但是测试案例里有A+B很大溢出的情况，因此需要多加考虑我的想法是既然十进制加起来可能会溢出，那就先不相加，先转为对应的m进制后再相加，此时就好做多了；我是使用的字符串形式来计算，看起来有些麻烦；此种方法的好处是不用再去写转换字符串进制转换了（除法）#include <iostream> #include <algorithm> using namespace std; string Add(string a, string b, int m) { int carry = 0; if (a.size() > b.size()) { // 判断哪个长就用哪个接收最终相加结果 int current = 0; for (int i = 0; i < a.size(); i++) { if (i < b.size()) { current = (a[i] - '0') + (b[i] - '0') + carry; a[i] = current % m + '0'; carry = current / m; } else { // 超过短的长度后，不用取值，否则数组溢出 current = (a[i] - '0') + carry; a[i] = current % m + '0'; carry = current / m; } } if (carry != 0) // 最后还要在判断下，防止进位超出最大长度 a.push_back(carry + '0'); return a; } else { int current = 0; for (int i = 0; i < b.size(); i++) { if (i < a.size()) { current = (b[i] - '0') + (a[i] - '0') + carry; b[i] = current % m + '0'; carry = current / m; } else { current = (b[i] - '0') + carry; b[i] = current % m + '0'; carry = current / m; } } if (carry != 0) b.push_back(carry + '0'); return b; } } int main() { int m, a, b; while (cin >> m >> a >> b) { if (m == 0) break; string oct_a; while (a != 0) { oct_a.push_back(a % m + '0'); // 每次添加一个字符 a /= m; } string oct_b; while (b != 0) { oct_b.push_back(b % m + '0'); b /= m; } if (oct_a.size() == 0 && oct_b.size() == 0) //如果a、b都是0，直接输出0 cout << 0 << endl; else { string result = Add(oct_a, oct_b, m); // 字符串结果还要逆向一下才是正确的顺序 reverse(result.begin(), result.end()); cout << result << endl; } } }改进：数字进制转换写成了函数，这样增加代码可读性字符串相加函数中，使用while给较短字符串补0（参考其他人题解），使得长度相等，这样不用重复两遍代码了#include <iostream> #include <algorithm> using namespace std; string Add(string a, string b, int m) { while (a.size() > b.size()) b.push_back('0'); while (a.size() < b.size()) a.push_back('0'); int carry = 0; int current = 0; for (int i = 0; i < a.size(); i++) { current = (a[i] - '0') + (b[i] - '0') + carry; a[i] = current % m + '0'; carry = current / m; } if (carry != 0) a.push_back(carry + '0'); return a; } string dec2m(int x, int m) { string s; while (x != 0) { s.push_back(x % m + '0'); x /= m; } return s; } int main() { int m, a, b; while (cin >> m >> a >> b) { if (m == 0) break; string oct_a = dec2m(a, m); string oct_b = dec2m(b, m); if (oct_a.size() == 0 && oct_b.size() == 0) cout << 0 << endl; else { string result = Add(oct_a, oct_b, m); reverse(result.begin(), result.end()); cout << result << endl; } } }法2：直接long long接收A、B（感觉有些作弊？）#include <iostream> #include <vector> using namespace std; int main() { int m; long long A, B; while (cin >> m) { if (m == 0) break; cin >> A; cin >> B; long long val = A + B; vector<int> res; if (val == 0) res.push_back(0); while (val != 0) { res.push_back(val % m); val = val / m; } for (int i = res.size()-1; i >= 0; i--) { cout << res[i]; } cout << endl; } return 0; }进制转换进制转换_牛客题霸_牛客网 (nowcoder.com)描述写出一个程序，接受一个十六进制的数值字符串，输出该数值的十进制字符串(注意可能存在的一个测试用例里的多组数据)。输入描述：输入一个十六进制的数值字符串。输出描述：输出该数值的十进制字符串。法1：16进制字符转10进制#include <iostream> using namespace std; int hex2dec(char ch) { if (ch <= '9' && ch >= '0') return ch - '0'; else return ch - 'A' + 10; } int main() { string hex; while (cin >> hex) { int dec = 0; for (int i = 2; i < hex.size(); i++) { dec = dec * 16 + hex2dec(hex[i]); } cout << dec << endl; } }法2：超级简单，直接格式化输入和输出C的写法：#include <stdio.h> int main() { int num = 0; while (~scanf ("%x", &num)) printf("%d\n", num); return 0; }C++的写法：#include <iostream> using namespace std; int main() { int num = 0; while (cin >> hex >> num) cout << dec << num << endl; return 0; }数制转换数制转换_牛客题霸_牛客网 (nowcoder.com)描述求任意两个不同进制非负整数的转换（2进制～16进制），所给整数在long所能表达的范围之内。 不同进制的表示符号为（0，1，...，9，a，b，...，f）或者（0，1，...，9，A，B，...，F）。输入描述：输入只有一行，包含三个整数a，n，b。a表示其后的n 是a进制整数，b表示欲将a进制整数n转换成b进制整数。a，b是十进制整数，2 =< a，b <= 16。 数据可能存在包含前导零的情况。输出描述：可能有多组测试数据，对于每组数据，输出包含一行，该行有一个整数为转换后的b进制数。输出时字母符号全部用大写表示，即（0，1，...，9，A，B，...，F）。思路：首先a进制字符串转为十进制数字（a2dec），其中设置flag位为0，直到遇到开头不为'0'的字符，即去除开头的0十进制数字转为b进制字符串（dec2b），需要注意dec % b如果大于等于10，要改为字母，因此做一个条件判断如果b=10，第一步完可以直接输出，不用再去dec2b里转为字符串了#include <iostream> #include <algorithm> using namespace std; int a2dec(string num, int a) { int dec = 0, n, flag = 0; for (int i = 0; i < num.size(); i++) { if (num[i] != '0') flag = 1; if (flag) { if (num[i] <= '9' && num[i] >= '0') n = num[i] - '0'; else if (num[i] <= 'z' && num[i] >= 'a') n = num[i] - 'a' + 10; else n = num[i] - 'A' + 10; dec = dec * a + n; } } return dec; } string dec2b(int dec, int b) { string num; while (dec != 0) { if (dec % b >= 10) num.push_back(dec % b + 'A' - 10); else num.push_back(dec % b + '0'); dec /= b; } reverse(num.begin(), num.end()); //得逆转下顺序 return num; } int main() { int a, b; string num; while (cin >> a >> num >> b) { int dec = a2dec(num, a); if (b != 10) cout << dec2b(dec, b) << endl; else cout << dec << endl; } }
机试day6首字母大写首字母大写_牛客题霸_牛客网 (nowcoder.com)描述对一个字符串中的所有单词，如果单词的首字母不是大写字母，则把单词的首字母变成大写字母。 在字符串中，单词之间通过空白符分隔，空白符包括：空格(' ')、制表符('t')、回车符('r')、换行符('n')。输入描述：输入一行：待处理的字符串（长度小于100）。输出描述：可能有多组测试数据，对于每组数据， 输出一行：转换后的字符串。输入： if so, you already have a google account. you can sign in on the right. 输出： If So, You Already Have A Google Account. You Can Sign In On The Right.思路：设置flag位，初始为1，表示句子首字母得大写；如果碰到空白符（使用isspace判断），则flag置1，否则置0；这样碰到flag=1表明上一个字符位空白符，此字符该大写了#include <cstdio> #include <iostream> #include <string> #include <cctype> using namespace std; int main() { string s; while (getline(cin ,s)) { int flag = 1; for (int i = 0; i < s.size(); i++) { if (isspace(s[i])) { flag = 1; printf("%c", s[i]); } else { if (flag && 'a' <= s[i] && s[i] <= 'z') { printf("%c", s[i] + 'A' - 'a'); } else { printf("%c", s[i]); } flag = 0; } } } }也可以直接toupper转换浮点数加法浮点数加法_牛客题霸_牛客网 (nowcoder.com)描述求2个浮点数相加的和 题目中输入输出中出现浮点数都有如下的形式： P1P2...Pi.Q1Q2...Qj 对于整数部分，P1P2...Pi是一个非负整数 对于小数部分，Qj不等于0输入描述：对于每组案例，每组测试数据占2行，分别是两个加数。输出描述：每组案例是n行，每组测试数据有一行输出是相应的和。 输出保证一定是一个小数部分不为0的浮点数输入： 0.111111111111111111111111111111 0.111111111111111111111111111111 输出： 0.222222222222222222222222222222思路：难点在于小数点前后位数不同的情况下得补0，因此采用了获取小数点位置，然后分别计算前后带0的数目。选取带0最多的作为标准，少的补0。然后视为字符串一位位相加，如果大于10，则flag置1并加到下一位#include <iostream> #include <string> #include <math.h> using namespace std; int main() { string a, b; while (cin >> a >> b) { int pos1 = a.find('.'); int pos2 = b.find('.'); int num1 = max(pos1, pos2); int num2 = max(a.size()-pos1-1, b.size()-pos2-1); a.insert(0, num1-pos1, '0'); b.insert(0, num1-pos2, '0'); a.insert(a.size(), num1+num2+1-a.size(), '0'); b.insert(b.size(), num1+num2+1-b.size(), '0'); int sum = 0, flag = 0; for (int i = a.size() - 1; i >= 0; i--) { if (a[i] != '.') { sum = (a[i] - '0') + (b[i] - '0') + flag; a[i] = sum % 10 + '0'; flag = sum / 10; } } cout << a << endl; } }后缀子串排序描述对于一个字符串，将其后缀子串进行排序，例如grain 其子串有： grain rain ain in n 然后对各子串按字典顺序排序，即： ain,grain,in,n,rain输入描述：每个案例为一行字符串。输出描述：将子串排序输出输入： grain 输出： ain grain in n rain思路：使用algorithm库的sort来排序，传入两个字符串比较第一位、第二位直到两个字符不同，返回较小的排前面#include <iostream> #include <string> #include <algorithm> using namespace std; bool compare(string x, string y) { int i = 0; while (1) { if (x[i] == y[i]) { i++; continue; } else { return x[i] < y[i]; } } } int main() { string s; while (cin >> s) { string ss[s.size()]; for (int i = 0; i < s.size(); i++) { ss[i] = s.substr(i, s.size()); } sort(ss, ss+s.size(), compare); for (int i = 0; i < s.size(); i++) { cout << ss[i] << endl; } } }汗！！！发现不用写compare，sort会自动排序，修改后如下#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; while (cin >> s) { string ss[s.size()]; for (int i = 0; i < s.size(); i++) { ss[i] = s.substr(i, s.size()); } sort(ss, ss+s.size()); for (int i = 0; i < s.size(); i++) { cout << ss[i] << endl; } } }字符串变形字符串变形_牛客题霸_牛客网 (nowcoder.com)描述对于一个长度为 n 字符串，我们需要对它做一些变形。首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。比如"Hello World"变形后就变成了"wORLD hELLO"。数据范围: $1\le n\le 10^6$ , 字符串中包括大写英文字母、小写英文字母、空格。进阶：空间复杂度 $O(n)$ ， 时间复杂度 $O(n)$输入描述：给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)返回值描述：请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。输入： "This is a sample",16 返回值： "SAMPLE A IS tHIS" 输入： "nowcoder",8 返回值： "NOWCODER"法1：先大小写转换，再逆向整个，最后逆向单词思路：可以设置一个reverse函数用来反转一个单词/句子，对于如何根据空格划分单词，使用start接收一个单词开始位置，碰到空格记录i，即可截取句子中的单词（注意，最后一个单词需要判断是否到结尾，再起一个分支来处理）#include <cctype> #include <string> string reverse(string s) { char c; for (int i = 0, j = s.size() - 1; i < j; i++, j--) { c = s[i]; s[i] = s[j]; s[j] = c; } return s; } class Solution { public: string trans(string s, int n) { for (int i = 0; i < n; i++) { if (isupper(s[i])) { s[i] = tolower(s[i]); } else if (islower(s[i])) { s[i] = toupper(s[i]); } } s = reverse(s); int start = 0; string new_s; for (int i = 0; i < n; i++) { if (isspace(s[i])) { new_s = reverse(s.substr(start, i - start)); s.erase(start, i - start); s.insert(start, new_s); start = i + 1; } else if (i == n - 1) { new_s = reverse(s.substr(start, i + 1 - start)); s.erase(start, i + 1 - start); s.insert(start, new_s); } } return s; } };其中reverse函数可以由algorithm的reverse替换ps：经法2启发，在结尾加个空格会更简单class Solution { public: string trans(string s, int n) { for (int i = 0; i < n; i++) { if (isupper(s[i])) { s[i] = tolower(s[i]); } else if (islower(s[i])) { s[i] = toupper(s[i]); } } s = reverse(s); s += ' '; int start = 0; string new_s; for (int i = 0; i < n + 1; i++) { if (isspace(s[i])) { new_s = reverse(s.substr(start, i - start)); s.erase(start, i - start); s.insert(start, new_s); start = i + 1; } } s.erase(n, 1); return s; } };法2：栈！思路：使用栈stack，定义数据类型为string使用str接收每个单词，同时s后加一个空格好判断栈先入后出，因此可以实现句子单词逆序，而不需要反转单词本身，快了很多#include <cctype> class Solution { public: string trans(string s, int n) { stack<string> sk; string str; s.push_back(' '); // s后加空格 for (int i = 0; i <= n; i++) { if (s[i] == ' ') { sk.push(str); str = ""; } else { if (s[i] >= 'a' && s[i] <= 'z') { str += (s[i] - 'a' + 'A'); } else { str += (s[i] - 'A' + 'a'); } } } string ans; while (!sk.empty()) { ans += sk.top(); // 取栈顶值 sk.pop(); // 弹出栈顶 ans.push_back(' '); // 加空格 } ans.pop_back(); // 去除最后的空格 return ans; } };法3：超级无敌改进法1思路：就是reverse，使用官方库好了，甚至不需要加空格，以及不需要开辟新空间接收反转的字符串#include <cctype> class Solution { public: string trans(string s, int n) { reverse(s.begin(), s.end()); int i = 0, j = 0; while (i < n) { j = i; while (j < n && s[j] != ' ') { if (isupper(s[j])) { s[j] = tolower(s[j]); } else if (islower(s[j])) { s[j] = toupper(s[j]); } j++; } reverse(s.begin() + i, s.begin() + j); i = j + 1; } return s; } };最长公共前缀描述给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。数据范围： $0\le n\le 5000$， $0\le len(strs_i)\le 5000$进阶：空间复杂度 $O(1)$，时间复杂度 $O(n∗len)$输入： ["abca","abc","abca","abc","abcc"] 返回值： "abc" 输入： ["abc"] 返回值： "abc"思路：以第一个作为参照一个个比class Solution { public: /** * * @param strs string字符串vector * @return string字符串 */ string longestCommonPrefix(vector<string>& strs) { string s; if (!strs.size()) return ""; for (int i = strs[0].size(); i >= 0; i--) { int flag = 0; for (int j = 0; j < strs.size(); j++) { if (i > strs[j].size() || strs[0].substr(0, i) != strs[j].substr(0, i)) { flag = 0; break; } else { flag = 1; } } if (flag) return strs[0].substr(0, i); } return ""; } };nice！看了下和官方思路差不多，大多数思路差不多
机试day5特殊乘法特殊乘法_牛客题霸_牛客网 (nowcoder.com)描述写个算法，对2个小于1000000000的输入，求结果。 特殊乘法举例：123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5输入描述：两个小于1000000000的数输出描述：输入可能有多组数据，对于每一组数据，输出Input中的两个数按照题目要求的方法进行运算后得到的结果。思路：数字转为字符串，单个单个字符串计算#include <iostream> #include <string> using namespace std; int main() { string num1, num2; int result; while (cin >> num1 >> num2) { result = 0; for (int i = 0; i < num1.size(); i++) { for (int j = 0; j < num2.size(); j++) { result += (num1[i] - '0') * (num2[j] - '0'); } } printf("%d\n", result); } }密码翻译密码翻译_牛客题霸_牛客网 (nowcoder.com)描述在情报传递过程中，为了防止情报被截获，往往需要对情报用一定的方式加密，简单的加密算法虽然不足以完全避免情报被破译，但仍然能防止情报被轻易的识别。我们给出一种最简的的加密方法，对给定的一个字符串，把其中从a-y,A-Y的字母用其后继字母替代，把z和Z用a和A替代，则可得到一个简单的加密字符串。输入描述：读取这一行字符串，每个字符串长度小于80个字符输出描述：对于每组数据，输出每行字符串的加密字符串。思路：同上题，因为类似转筒，所以用到了模数，注意点直接cin或者scanf无法接收带有空格的字符串，因此要用getline(cin, s)，它以回车作为间隔#include <iostream> #include <string> using namespace std; int main() { string s; while (getline(cin, s)) { for (int i = 0; i < s.size(); i++) { if (s[i] >= 'a' && s[i] <= 'z') { s[i] = (s[i] - 'a' + 1) % 26 + 'a'; } else if (s[i] >= 'A' && s[i] <= 'Z') { s[i] = (s[i] - 'A' + 1) % 26 + 'A'; } } cout << s << endl; } }简单密码简单密码_牛客题霸_牛客网 (nowcoder.com)描述Julius Caesar曾经使用过一种很简单的密码。 对于明文中的每个字符，将它用它字母表中后5位对应的字符来代替，这样就得到了密文。 比如字符A用F来代替。如下是密文和明文中字符的对应关系。 密文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 明文 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 你的任务是对给定的密文进行解密得到明文。 你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。输入描述：输入中的测试数据不超过100组。每组数据都有如下的形式，而且各组测试数据之间没有空白的行。 一组测试数据包括三部分： 1. 起始行 - 一行，包括字符串 "START" 2. 密文 - 一行，给出密文，密文不为空，而且其中的字符数不超过200 3. 结束行 - 一行，包括字符串 "END" 在最后一组测试数据之后有一行，包括字符串 "ENDOFINPUT"。输出描述：对每组数据，都有一行输出，给出密文对应的明文。输入： START NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ END START IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT 输出： IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE思路：注意减回去时小于A的返回Z继续#include <iostream> using namespace std; int main() { string s; while (getline(cin, s)) { if (s == "START" || s == "END") { continue; } else if (s == "ENDOFINPUT") { break; } else { for (int i = 0; i < s.size(); i++) { if (s[i] >= 'A' && s[i] <= 'Z') s[i] = (s[i] - 'A' - 5 + 26) % 26 + 'A'; } cout << s << endl; } } }统计字符统计字符_牛客题霸_牛客网 (nowcoder.com)描述统计一个给定字符串中指定的字符出现的次数。输入描述：测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到'#'时输入结束，相应的结果不要输出。输出描述：对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出： c0 n0 c1 n1 c2 n2 ... 其中ci是第1行中第i个字符，ni是ci出现的次数。输入： I THIS IS A TEST i ng this is a long test string # 输出： I 2 i 3 5 n 2 g 2思路：一个个比较就好了，注意对结束符的判断#include <iostream> #include <string> using namespace std; int main() { string s1, s2; while (getline(cin, s1)) { if (s1 == "#") break; getline(cin, s2); int num; for (int i = 0; i < s1.size(); i++) { num = 0; for (int j = 0; j < s2.size(); j++) { if (s2[j] == s1[i]) num++; } printf("%c %d\n", s1[i], num); } } }字母统计字母统计_牛客题霸_牛客网 (nowcoder.com)描述输入一行字符串，计算其中A-Z大写字母出现的次数输入描述：案例可能有多组，每个案例输入为一行字符串。输出描述：对每个案例按A-Z的顺序输出其中大写字母出现的次数。输入： DFJEIWFNQLEF0395823048+_+JDLSFJDLSJFKK 输出： A:0 B:0 C:0 D:3 E:2 F:5 G:0 H:0 I:1 J:4 K:2 L:3 M:0 N:1 O:0 P:0 Q:1 R:0 S:2 T:0 U:0 V:0 W:1 X:0 Y:0 Z:0思路：设置一个数组，遍历每个字符，如果在A-Z的范围内，则在该字母上加一次，最后使用printf输出，'A'+i可以格式化为字符#include <iostream> #include <string> using namespace std; int main() { string s; while (cin >> s) { int c[26] = {0}; for (int i = 0; i < s.size(); i++) { if (s[i] >= 'A' && s[i] <= 'Z') { c[s[i] - 'A']++; } } for (int i = 0; i < 26; i++) { printf("%c:%d\n", 'A' + i, c[i]); } } }skew数skew数_牛客题霸_牛客网 (nowcoder.com)描述在 skew binary 表示中，第 k 位的值 x[k] 表示 x[k]×(2^(k+1)-1)。每个位上的可能数字是 0 或 1，最后面一个非零位可以是 2，例如，10120(skew) = 1×(2^5-1) + 0×(2^4-1) + 1×(2^3-1) + 2×(2^2-1) + 0×(2^1-1) = 31 + 0 + 7 + 6 + 0 = 44。前十个 skew 数是 0、1、2、10、11、12、20、100、101、以及 102。输入描述：输入包括多组数据，每组数据包含一个 skew 数。输出描述：对应每一组数据，输出相应的十进制形式。结果不超过 2^31-1。思路：输入明显视为字符串的话更好计算#include <cmath> #include <iostream> #include <string> #include <math.h> using namespace std; int main() { string s; int skew; while (cin >> s) { skew = 0; for (int i = s.size(); i > 0; i--) { skew += (s[s.size() - i] - '0') * (pow(2, i) - 1); } printf("%d\n", skew); } }单词替换单词替换_牛客题霸_牛客网 (nowcoder.com)描述输入一个字符串，以回车结束（字符串长度<=100）。该字符串由若干个单词组成，单词之间用一个空格隔开，所有单词区分大小写。现需要将其中的某个单词替换成另一个单词，并输出替换之后的字符串。输入描述：每组数据输入包括3行，第1行是包含多个单词的字符串s，第2行是待替换的单词a(长度<=100)，第3行是a将被替换的单词b(长度<=100)。s, a, b 最前面和最后面都没有空格。输出描述：每个测试数据输出只有 1 行， 将s中所有单词a替换成b之后的字符串。输入： You want someone to help you You I 输出： I want someone to help you首先贴出错误的代码：下面这个代码没有好好读题，是把单词替换掉，而非所有匹配字符串替换掉，比方说一个单词是CCCCC，要被替换的是CCC，这个CCCCC是不应该不替换的，尽管这个单词里包含了CCC#include <iostream> using namespace std; int main() { string s, a, b; while (getline(cin, s)) { cin >> a >> b; int index[100] = {0}; int i = 0, find_i = 0; while ((find_i = s.find(a, find_i)) != string::npos) { index[i] = find_i; find_i += a.size(); i++; } for (int j = 0; j < i; j++) { s.erase(index[j], a.size()); s.insert(index[j], b); } cout << s << endl; } }正确且十分恰当的思路：利用题目中说s、a、b前后都没空格的提示，把三个字符串前后都加上空格，从而把每个单词包含了前后的空格视为一个整体来查找！代码也更加简洁#include <iostream> using namespace std; int main() { string s, a, b; while (getline(cin, s)) { cin >> a >> b; s = ' ' + s + ' '; a = ' ' + a + ' '; b = ' ' + b + ' '; int find_i = 0; while ((find_i = s.find(a, find_i)) != string::npos) { s.erase(find_i, a.size()); s.insert(find_i, b); } cout << s.substr(1, s.size() - 2) << endl; } }其他思路：按照空格划分句子，这点在python中很好用，C++实现较难