• [N诺] 浙江大学历年机试题解

    1、统计字符

     统计一个给定字符串中指定的字符出现的次数。

    测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到'#'时输入结束，相应的结果不要输出。
    1. #include
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6. 	string c;
    7.     string n;
    8.     while(c[0] != '#'){
    9.         getline(cin,c);
    10.         getline(cin,n);
    11.         int cnt = 0;
    12.         int j = 0;
    13.         for(int i=0;ilength();i++){
    14.             for(j=0;jlength();j++){
    15.                 if(c[i]==n[j])
    16.                     cnt++;
    17.             }
    18.             if(cnt!=0){
    19.                 cout << c[i] << " " << cnt << endl;
    20.                 cnt = 0;
    21.             }
    22.         }
    23.     }
    24. }

    2、畅通工程

    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

    测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

    最小生成树问题

    1. #include
    2. using namespace std;
    3.  
    4. int n,m;
    5. const int max_n = 100;
    6.  
    7. struct node{
    8.     int b,e,w;
    9. }edges[max_n];
    10.  
    11. bool cmp(node n1,node n2){
    12.     return n1.w
    13. }
    14.  
    15. int S[max_n]; // 并查集
    16. int find_root(int x){
    17.     while(S[x]>0){
    18.         x = S[x];
    19.     }
    20.     return x;
    21. }
    22.  
    23. int kruskal()
    24. {
    25.     sort(edges,edges+n,cmp);
    26.     
    27.     int sum = 0; // 最小生成树的权值
    28.     
    29.     for(int i = 0;i
    30.         // 最小边
    31.         node now = edges[i];
    32.         // 若不成环可以加入
    33.         int fb = find_root(now.b);
    34.         int fe = find_root(now.e);
    35.         if(fb!=fe){
    36.             S[fb]=fe;
    37.             sum = sum+now.w;
    38.             m--;
    39.         }
    40.     }
    41.     if(m==1)
    42.         return sum;
    43.     else
    44.         return -1;
    45. }
    46.  
    47. int main(){
    48.     while(cin>>n>>m){
    49.         if(n==0) break; // 结束条件
    50.         memset(S,0,sizeof(S)); // 全初始化为-1或0
    51.         for(int i=0;i
    52.             cin>>edges[i].b>>edges[i].e>>edges[i].w;
    53.         }
    54.         int ans = kruskal();
    55.         if(ans==-1){
    56.             cout<<"?"<
    57.         }else cout << ans <
    58.     }
    59. }

    3、畅通工程2

    某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 
    注意:两个城市之间可以有多条道路相通,也就是说
    3 3
    1 2
    1 2
    2 1
    这种输入也是合法的
    当N为0时，输入结束，该用例不被处理。

    并查集的应用

    1. #include
    2. using namespace std;
    3.  
    4. int n,m;
    5. const int max_n = 1000;
    6.  
    7. int S[max_n];
    8.  
    9. int find_root(int x){
    10.     while(S[x]>0){
    11.         x = S[x];
    12.     }
    13.     return x;
    14. }
    15.  
    16. int main(){
    17.     while(cin>>n>>m) {
    18.         if (n == 0) break;
    19.         memset(S, 0, sizeof S);
    20.         int sum = 0;
    21.         for(int i =0;i
    22.             int x,y;
    23.             cin >> x >> y;
    24.             int fx = find_root(x);
    25.             int fy = find_root(y);
    26.             if(fx!=fy){
    27.                 S[fx] = fy;
    28.                 sum++;
    29.             }
    30.         }
    31.         cout << n-sum-1 << endl;
    32.     }
    33. }

    4.继续畅通工程

    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

    1. #include
    2. using namespace std;
    3.  
    4. const int max_n=100;
    5. int n;
    6. struct node{
    7.     int u,v,w;
    8.     int flag;
    9. }edges[max_n];
    10.  
    11. int cmp(node n1, node n2){
    12.     return n1.w < n2.w;
    13. }
    14.  
    15. int S[max_n];
    16. int find_root(int x){
    17.     while(S[x]>0){
    18.         x = S[x];
    19.     }
    20.     return x;
    21. }
    22.  
    23. int kruskal(int m){
    24.     sort(edges,edges+m,cmp);
    25.     int sum = 0;
    26.     int total = 0;
    27.     for(int i=0;i
    28.         node now = edges[i];
    29.         int fa = find_root(now.u);
    30.         int fb = find_root(now.v);
    31.         if(total == n-1){
    32.             break;
    33.         }
    34.         if(fa!=fb){
    35.             sum = sum + now.w;
    36.             S[fa] = fb;
    37.             total++;
    38.         }
    39.     }
    40.     return sum;
    41. }
    42.  
    43. int main(){
    44.     while(cin>>n){
    45.         if(n==0) break;
    46.         memset(S,-1,sizeof(S));
    47.         int m = n*(n-1)/2;
    48.         for(int i=0;i
    49.             cin>>edges[i].u>>edges[i].v>>edges[i].w>>edges[i].flag;
    50.             if(edges[i].flag==1) edges[i].w=0;
    51.         }
    52.         int ret = kruskal(m);
    53.         cout << ret << endl;
    54.     }
    55. }

    5.二叉搜索树

    判断两序列是否为同一二叉搜索树序列

    开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
    1. #include
    2. using namespace std;
    3.  
    4. typedef struct node{
    5.     char data; // 注意是以字符形式建树
    6.     struct node *lchild,*rchild;
    7. }*BitTree;
    8.  
    9. vector<char> right_ans,each_ans;
    10. void InsertBitTree(BitTree &T,char x){
    11.     if(T==NULL){
    12.         T = new node;
    13.         T->data = x;
    14.         T->lchild = NULL;
    15.         T->rchild = NULL;
    16.         return; // 递归终止
    17.     }else if(T->data > x){
    18.         InsertBitTree(T->lchild,x);
    19.     }else if(T->data < x){
    20.         InsertBitTree(T->rchild,x);
    21.     }
    22. }
    23.  
    24. void PreOrderTraverse(BitTree T) {
    25.     if (T == NULL) return;
    26.     each_ans.push_back(T->data);
    27.     PreOrderTraverse(T->lchild);
    28.     PreOrderTraverse(T->rchild);
    29. }
    30.  
    31. int main(){
    32.     int n;
    33.     string right,each;
    34.     while(cin>>n){
    35.         if(n==0) return 0;
    36.         cin >> right;
    37.         BitTree T = NULL;
    38.         for(int i = 0;isize();i++){
    39.             InsertBitTree(T,right[i]);
    40.         }
    41.         PreOrderTraverse(T);
    42.         for (int i = 0; i < each_ans.size(); ++i) right_ans.push_back(each_ans[i]); // 函数里默认写的是each_ans
    43.         while(n--){
    44.             each_ans = {};
    45.             cin>>each;
    46.             BitTree T = NULL;
    47.             for(int i = 0;isize();i++){
    48.                 InsertBitTree(T,each[i]);
    49.             }
    50.  
    51.             PreOrderTraverse(T);
    52.             int flag = 1;
    53.             for(int i=0;isize();i++){
    54.                 if(right_ans[i]!=each_ans[i]){
    55.                     flag = 0;
    56.                     break;
    57.                 }
    58.             }
    59.             if(flag==1){
    60.                 cout << "YES" << endl;
    61.             }else{
    62.                 cout << "NO" << endl;
    63.             }
    64.         }
    65.     }
    66. }

    6.统计同成绩学生人数

    读入N名学生的成绩，将获得某一给定分数的学生人数输出。

    测试输入包含若干测试用例，每个测试用例的格式为


第1行：N
第2行：N名学生的成绩，相邻两数字用一个空格间隔。
第3行：给定分数

当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。
    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5. 	int n;
    6. 	while(cin>>n){
    7. 		if(n==0) return 0;
    8. 		map<int,int> a;
    9. 		int grade,aim;
    10. 		while(n--){
    11. 			cin>>grade;
    12. 			a[grade]++;
    13. 		}
    14. 		cin>>aim;
    15. 		cout << a[aim] << endl;
    16. 	}
    17. }

    7.EXCEL排序

    Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。     对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

    测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (N<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有N行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间[0, 100]内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。
    1. #include
    2. using namespace std;
    3.  
    4. const int max_N = 100000;
    5. struct student{
    6.     string No;
    7.     string name;
    8.     int grade;
    9. }students[max_N];
    10.  
    11. bool cmp1(struct student stu1,struct student stu2){
    12.     return stu1.No < stu2.No;
    13. }
    14.  
    15. bool cmp2(struct student stu1,struct student stu2){
    16.     if(stu1.name == stu2.name){
    17.         return stu1.No < stu2.No;
    18.     }else{
    19.         return stu1.name < stu2.name;
    20.     }
    21. }
    22.  
    23. bool cmp3(struct student stu1,struct student stu2){
    24.     if(stu1.grade == stu2.grade){
    25.         return stu1.No < stu2.No;
    26.     }else{
    27.         return stu1.grade < stu2.grade;
    28.     }
    29. }
    30.  
    31. int main(){
    32.     int N,C;
    33.     cin >> N >> C;
    34.     for(int i=0;i
    35.         struct student stu;
    36.         cin >> stu.No >> stu.name >> stu.grade;
    37.         students[i] = stu;
    38.     }
    39.     if(C==1){
    40.         sort(students,students+N,cmp1);
    41.     }else if(C==2){
    42.         sort(students,students+N,cmp2);
    43.     }else if(C==3){
    44.         sort(students,students+N,cmp3);
    45.     }
    46.     cout << "Case:"<
    47.     for(int i=0;i
    48.         cout << students[i].No << " "<" " << students[i].grade<
    49.     }
    50. }

    8.最大连续子序列

    给定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. #include
    2. using namespace std;
    3.  
    4. const int max_k = 10000;
    5.  
    6. int dp[max_k],dp_copy[max_k];
    7. int main(){
    8.     int k;
    9.     while(cin>>k){
    10.         int flag = 0; // 是否全为负数
    11.         if(k==0) return 0;
    12.         memset(dp,0,max_k);
    13.         for(int i = 0;i
    14.             cin>>dp[i];
    15.             if(dp[i]>=0){
    16.                 flag = 1;
    17.             }
    18.             dp_copy[i] = dp[i];
    19.         }
    20.         if(flag){
    21.             for(int i = 1;i
    22.                 dp[i] = max(dp[i-1]+dp[i],dp[i]);
    23.             }
    24.             int max_value =*max_element(dp,dp+k);
    25.             int max_pos = distance(dp,max_element(dp,dp+k));
    26.  
    27.             int temp = max_value;
    28.             int min_pos = max_pos;
    29.             while(dp_copy[min_pos]!=temp){
    30.                 temp = temp - dp_copy[min_pos];
    31.                 min_pos--;
    32.             }
    33.  
    34.             cout << max_value <<" "<" "<
    35.         }else{
    36.             cout << 0 <<" "<0]<<" "<-1]<
    37.         }
    38.     }
    39. }

    9.最短路径问题

    给你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个集合（初始有n个点，一个点独自成一个集合），先选出一条最短的边，假设它属于集合u，然后从跟它邻接的边中选出一条最短的且不与集合u中已经存在的边形成回路的边，合并到集合u中，再从非u集合中选出一条与集合u中的边邻接且距离最短的边，加入到集合u中，以此类推。
     

    Dijkstra是用来解决给定起点和重点求路径的问题。
     

    1. #include
    2. using namespace std;
    3.  
    4. const int MAX_N = 1000;
    5.  
    6. int visited[MAX_N]; // 是否已经访问过该点
    7.  
    8. int dist[MAX_N]; // dist[i]起点到i的距离
    9. int cost[MAX_N]; // cost[i]起点到i的花费
    10.  
    11.  
    12. struct Edge{
    13.     int to;
    14.     int length;
    15.     int price;
    16.     Edge(int i, int j, int k): to(i), length(j), price(k){}
    17. };
    18.  
    19. vector graph[MAX_N];
    20.  
    21.  
    22. struct Point{
    23.     int number;
    24.     int distance;
    25.     Point(int i, int j): number(i), distance(j){}
    26.     bool operator< (const Point& p) const{ // 重定义操作符< 使得Point之间可比
    27.         return distance > p.distance;
    28.     }
    29. };
    30.  
    31.  
    32. void Dijkstra(int s, int n){ // s到n的最短路
    33.     dist[s] = 0;
    34.     cost[s] = 0;
    35.  
    36.     priority_queue q; // 优先队列
    37.     q.push(Point(s, 0)); // 加入起点 起点到起点距离显然为0
    38.  
    39.     while(!q.empty()){ // 只要q不空
    40.         int u = q.top().number;  // 队列头
    41.         q.pop();
    42.  
    43.         if(visited[u] == 1){  // 已经被访问过
    44.             continue;
    45.         }
    46.         visited[u] = 1; // 未被访问过 则标记位访问过
    47.  
    48.         for(int i=0; isize(); i++){ // 遍历与u邻接的边
    49.             int v = graph[u][i].to;
    50.             int uv_price = graph[u][i].price;
    51.             int uv_len = graph[u][i].length;
    52.             if(dist[u] + uv_len < dist[v] || (dist[u] + uv_len == dist[v] && cost[u] + uv_price < cost[v])){ // 直达距离更短或距离相同但花费更少
    53.                 // 更新从起点到v的距离
    54.                 dist[v] = dist[u] + uv_len;
    55.                 cost[v] = cost[u] + uv_price;
    56.             }
    57.             q.push(Point(v, dist[v])); // 加入v 下次循环找v的邻接...
    58.  
    59.         }
    60.     }
    61. }
    62.  
    63.  
    64.  
    65. int main(){
    66.     int m, n;
    67.     while(cin>>n>>m){
    68.         if(n == 0 && m==0) break;
    69.  
    70.         memset(graph, 0, sizeof(graph));
    71.         memset(cost, 0x3f, sizeof(cost)); // 0x3f表示无限大
    72.         memset(dist, 0x3f, sizeof(dist)); // 0x3f表示无限大
    73.         memset(visited, 0, sizeof(visited)); // 都是未访问
    74.  
    75.         for(int i=0; i
    76.             int from, to, d, c;
    77.             cin>>from>>to>>d>>c;
    78.             graph[from].push_back(Edge(to, d, c));
    79.             graph[to].push_back(Edge(from, d, c));
    80.         }
    81.  
    82.         int s, t;
    83.         cin>>s>>t;
    84.  
    85.         Dijkstra(s, n);
    86.  
    87.         cout<" "<
    88.     }
    89.  
    90.     return 0;
    91. }
     

    10.xxx定律
     

    对于一个数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。     请计算需要经过几步才能将n变到1，具体可见样例。
     

    测试包含多个用例，每个用例包含一个整数n,当n为0 时表示输入结束。（1<=n<=10000）
     

    1. #include
    2. using namespace std;
    3.  
    4. int main(){
    5.     int n;
    6.     while(cin>>n){
    7.         if(n==0) return 0;
    8.         int cnt = 0;
    9.         while(n!=1){
    10.             if(n%2==0){
    11.                 n = n/2;
    12.             }else{
    13.                 n = (3*n+1)/2;
    14.             }
    15.             cnt++;
    16.         }
    17.         cout << cnt << endl;
    18.     }
    19. }
  • 相关阅读:
    K8S架构原理
    【超简单-Java设计模式2】简单工厂模式
    图的拓扑序列
    Dynamsoft Barcode Reader新框架将医疗视觉提升到新水平
    亚信科技与中国信通院达成全方位、跨领域战略合作
    【39】MESI协议：如何让多核CPU的高速缓存保持一致？
    解决报错：Module Not Found Error: No module named ‘allennlp.commands.elmo‘
    STM32_project:led_beep
    java-php-python-ssm基于网络游戏后台管理系统计算机毕业设计
    Maven依赖解决
  • 原文地址：https://blog.csdn.net/tangchujiang/article/details/126898916