Xherlock - C/C++&机试
type: channel
link: http://xherlock.top/index.php/category/C-C-机试/
items: 机试day12
items: 机试day11
items: 机试day10
items: C++数据结构2
items: 机试day9
items: 机试day8
items: C++数据结构1
items: 机试day7
items: 机试day6
items: 机试day5

机试day12
type: item
date: 2023-06-29T21:20:06+08:00
description: 机试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]…

机试day11
type: item
date: 2023-06-29T21:18:00+08:00
description: 机试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 …

机试day10
type: item
date: 2023-06-25T18:46:50+08:00
description: 机试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 表示图的顶点数目，…

C++数据结构2
type: item
date: 2023-06-23T19:30:00+08:00
description: 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),…

机试day9
type: item
date: 2023-06-18T16:48:48+08:00
description: 机试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…

机试day8
type: item
date: 2023-06-12T21:36:47+08:00
description: 机试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 <…

C++数据结构1
type: item
date: 2023-06-10T10:17:00+08:00
description: 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 t…

机试day7
type: item
date: 2023-06-10T10:12:00+08:00
description: 机试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 比特。这些组数字通过 (":")分割。比如,…

机试day6
type: item
date: 2023-06-04T21:41:13+08:00
description: 机试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 …

机试day5
type: item
date: 2023-05-31T22:12:01+08:00
description: 机试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 …