2021年计算机能力挑战赛真题总结C++版

前言

题型都是往届比赛（2019~2020）真题，知识点或大概思路重复的我没有放进来。
已经比完初赛，把我这份刷完加上在牛客刷概念选择题，想拿奖不难的，想进决赛多刷题吧反正（比如图）。个人觉得比赛赛重点就是字符串基本操作方面、关于图（邻接矩阵、邻接表）的相关题目。遗留的问题有空解决，或者有小伙伴评论留下你的题解链接~多多交流呀
别只收藏不点赞呀~
我自己刷题遇到的题都按知识点分为几个部分，都是必会的基础点（不全）。题解仅供参考，有其他想法可在评论区留言。

吐槽一下
1.官方平台打代码太难受了。代码格式可能有点乱，我没怎么调。
2.官方题目与测试点不匹配。我有些都要靠测试点去判断对应题目内容！
PS：
标题有类似 (4/5)字样表示测试点五个只过了四个，期待大神解答！其他都是ALL PASS

选择题

选项1 ：运算结果进行比较的话，已经溢出导致结果变化，去比较也为时已晚。所以不正确
选项2 ：检测符号为变化可以防止符号溢出，正确。
选项3 ： a+b = c c – a != b 则c溢出正确
选项4 ：参数长度 0000000000000000000000000 这个长度算溢出么不正确

【解析】 sizeof 是 C 语言中的一个操作符 (operator), 不是函数调用 , 简单的说其作用就是返回一个对象或者类型所占的内存字节数。所以选择 A 。

引用是一个对象的别名，主要用于函数参数和返回值类型，符号X&表示X类型的引用
1.首先，引用不可以为空，但指针可以为空。前面也说过了引用是对象的别名，引用为空——对象都不存在，怎么可能有别名！故定义一个引用的时候，必须初始化。因此如果你有一个变量是用于指向另一个对象，但是它可能为空，这时你应该使用指针；如果变量总是指向一个对象，i.e.，你的设计不允许变量为空
2.其次，引用不可以改变指向，对一个对象”至死不渝”；但是指针可以改变指向，而指向其它对象。说明：虽然引用不可以改变指向，但是可以改变初始化对象的内容。
3.再次，引用的大小是所指向的变量的大小，因为引用只是一个别名而已；指针是指针本身的大小，4个字节。

dynamic_cast :
继承体系安全向下转型或跨系转型；找出某对象占用内存的起始点
static_cast:
同旧式C转型，如int 到double
const_cast:
常用于去除某个对象的常量性
reinterpret_cast
不具备移植性，常见用途是转化函数指针类型

1.普通函数（不能被覆盖）
2.友元函数（C++不支持友元函数继承）
3.内联函数（编译期间展开，虚函数是在运行期间绑定）
4.构造函数（没有对象不能使用构造函数，先有构造函数后有虚函数，虚函数是对对象的动作）
5.静态成员函数（只有一份大家共享）

先析构子类再析构父类，如果父类析构函数有虚函数，会导致调用子类的已经析构的内容。

先构造父亲类再构造子类，如果父类构造函数有虚函数，会导致调用子类还没构造的内容。

编程题

asii码操作问题

3185

小明设计了一种基于质数(2、3、5、7、11…)的变进制数，第一位为2进制，第二位为3进制，第三位为5进制，以此类推。请将该变进制数转化为十进制数。

要点注意

注意变量类型选取最好都是long long ,否则测试点有部分不通过
num数组要深刻理解进制的含义（1=1，2 = 1×2 ，6 = 1x2x3 ,30 = 1x2x3x5 以此类推）

#include<iostream>
#include<string>
using namespace std;
int main() { 
   
	string str;
	cin >> str;
	long long temp = 0;
	long long result = 0;
	int i, num[] = { 
    1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870 }, toDec;
	for (i = str.length() - 1; i > -1; --i) { 
   
		toDec = num[str.length() - 1 - i];
		if (str[i] > 47 && str[i] < 58) { 
    //‘0’ == 48 ， ‘9’== 57
			temp = str[i] - 48;
			result += temp*toDec;
		}
		else { 
   
			temp = str[i] - 87;  //'a' =97 - 87 = 10;
			result += temp*toDec;
		}
	}
	cout << result;
	return 0;
}

3225.

要点注意

A ~Z ——65~90 ，a~z ——97~122
（187 = A与z的ascii码相加，该思路常用于字母对应转换）

有一组均由字符A~ Z和a~z组成的字符串，其中要求将字符串中各字符按如下要求进行转换
A<->z、B<->y、C<->x、… 、X<->c、Y<->b、Z<->a。

C语言版

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main()
{ 
   
    char s[10000];
    int i;
    //printf("锟斤拷锟斤拷\n");
    gets(s);
    for (i = 0;i < strlen(s);++i)
    { 
   
        s[i] = 187 - s[i];
    }
    printf("%s\n",s);
    return 0;
}

CPP版

#include<iostream>
#include<string>
using namespace std;
int main() { 
   
	char s[10000];
	cin >> s;
	int len = (sizeof(s) / sizeof(s[0])) - 1;//获取长度
	for (int i = 0; i< len; i++) { 
   
		if (s[i] > 'z' || s[i] < 'A' || s[i]>'Z'&& s[i]<'a') break;//跳过空元素
		s[i] = 187 - s[i];
		
	}
	for (int i = 0; i< len; i++) { 
   
		if (s[i] > 'z' || s[i] < 'A'||s[i]>'Z'&& s[i]<'a') break;//跳过空元素
		cout << s[i];
	}
	
	return 0;
}

3208. student成绩计算与排名

要点注意

C++11特性：
链接: push_back与emplace_back.
resize()与reserve都是vector容器中的方法：

resize():改变了capacity()和size()

reserve():增加了vector的capacity()，但是它的size()没有改变
setiosflags( ios::fixed ),头文件为:include.在遇到要计算浮点数且希望能控制其输出、精度、小数点后的位数等时，用setiosflags( ios::fixed )来控制。
使用setprecision(n)可控制输出流显示浮点数的数字个数。C++默认的流输出数值有效位是6。
如果setprecision(n)与setiosflags(ios::fixed)合用,可以控制小数点右边的数字个数。
如果如果setprecision(n)与setiosnags(ios::scientific)合用，可以控制指数表示法的小数位数。
setiosflags(ios::scientific)是用指数方式表示实数

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip> //小数点操作用的

//#include <bits/stdc++.h> //包含以上所有
using namespace std;
class Student { 
   
public:
	Student(long long ID, int wuL, int huaX, int shengW) :ID(ID), wuL(wuL), huaX(huaX), shengW(shengW) { 
   
		total = 0.4*wuL + 0.35*huaX + 0.25*shengW;
	}
long long ID;
int wuL, huaX, shengW;
double total;
};

bool mycmp(Student stu1, Student stu2) { 
   
	if (stu1.total == stu2.total) { 
   
		if (stu1.wuL == stu2.wuL) { 
   
			if (stu1.huaX == stu2.huaX) { 
   
				if (stu1.shengW == stu2.shengW) { 
   
					return false;
				}
				else return stu1.shengW > stu2.shengW;
			}
			else return stu1.huaX > stu2.huaX;
		}
		else return stu1.wuL >stu2.wuL;
	}
	else return stu1.total > stu2.total;//从大到小
}
int main() { 
   
	vector<Student> vstu;
	int N;
	cin >> N;

		for (int i = 0; i<N; i++) { 
   
			long long ID;
			int wuL, huaX, shengW;
			cin >> ID >> wuL >> huaX >> shengW;
			vstu.emplace_back(ID, wuL, huaX, shengW);
		}
	sort(vstu.begin(), vstu.end(), mycmp);
	for (int i = 0; i< 3; i++) { 
   
		cout << vstu[i].ID <<" "<< setiosflags(ios::fixed) << setprecision(1) <<  vstu[i].total << endl;
	}
	return 0;
}

3207 ,选择、填空、应用取第一，总分取前三

要点注意

别漏了 using namespace std
注意初值列赋值，类中成员是左值，传入参数是右值。Student(long long ID, int xuanZ, int tianK, int yingY) :_ID(ID), _xuanZ(xuanZ), _tianK(tianK), _yingY(yingY)

#include<bits/stdc++.h>
using namespace std;

class Student { 
   

public:
	Student() { 
   }
	Student(long long ID, int xuanZ, int tianK, int yingY) :_ID(ID), _xuanZ(xuanZ), _tianK(tianK), _yingY(yingY) { 
   
		total = xuanZ + tianK + yingY;
	}

	long long  _ID;
	int _xuanZ, _tianK, _yingY;
	int total;
};
bool mycmp(Student& s1, Student& s2) { 
   
	if (s1.total == s2.total) { 
   
		if (s1._yingY == s2._yingY) { 
   
			if (s1._tianK == s2._tianK) { 
   
				if (s1._xuanZ == s2._xuanZ) { 
   
					return s1._ID< s2._ID;
				}
				else return s1._xuanZ>s2._xuanZ;
			}
			else return s1._tianK > s2._tianK;
		}
		else return s1._yingY > s2._yingY;
	}
	else return s1.total>s2.total;

}
int main() { 
   
	vector<Student> st;
	Student X_king;
	Student T_king;
	Student Y_king; //3个题型的最高分数学生
	int X_max = 0, T_max = 0, Y_max = 0;
	int N;
	long long ID;
	int xuanZ, tianK, yingY;
	cin >> N;
	for (int i = 0; i< N; i++) { 
   
		cin >> ID >> xuanZ >> tianK >> yingY;
		Student stu1(ID, xuanZ, tianK, yingY);
		st.emplace_back(stu1);
		if (X_max < xuanZ) { 
   
			X_max = xuanZ;
			X_king = stu1;
		}
		if (T_max < tianK) { 
   
			T_max = tianK;
			T_king = stu1;
		}
		if (Y_max < yingY) { 
   
			Y_max = yingY;
			Y_king = stu1;
		}
	}
	sort(st.begin(), st.end(), mycmp);
	cout << X_king._ID << " " << X_king._xuanZ << endl;
	cout << T_king._ID << " " << T_king._tianK << endl;
	cout << Y_king._ID << " " << Y_king._yingY << endl;
	cout << endl;
	for (int i = 0; i < 3; i++) { 
   
		cout << st[i]._ID << " " << st[i].total << endl;
	}
	return 0;
}

时间秒数计算

3205

注意要点

测试用例
输入样例2:
23:59:59
00:00:01
理解代码 second = (second + 24 * 60 * 60) % (24 * 60 * 60);的用意

#include <bits/stdc++.h>

using namespace std;

int main()
{ 
   
    int hh1, mm1, ss1, hh2, mm2, ss2;
    long long second = 0;

    scanf("%d:%d:%d", &hh1, &mm1, &ss1);
    scanf("%d:%d:%d", &hh2, &mm2, &ss2);

    second = (hh2 - hh1) * 60 * 60 + (mm2 - mm1) * 60 + (ss2 - ss1);
    second = (second + 24 * 60 * 60) % (24 * 60 * 60);

    printf("%d", second);

    return 0;
}

3204

注意要点

多看多记

 #include <bits/stdc++.h>
int main()
{ 
   
    int hh, mm, ss, second;
    scanf("%d:%d:%d", &hh, &mm, &ss);
    scanf("%d", &second);

    ss -= second;
      
    mm += ss/60;//有多少份60s 就有多少分钟
    ss %= 60;//找出余数就是 秒
    if(ss < 0){ 
   //小于零 补60 类似进制
      mm--;
      ss += 60;
    }
  
    hh += mm/60;//同上
    mm %= 60;
    if(mm < 0) { 
   //小于零 补60 类似进制
		 hh--;
      mm += 60;
    }
   hh = ((hh%24)+24)%24;
  printf ("%02d:%02d:%02d",hh,mm,ss);
  return 0;
}

公共质因数、最小公倍数、最大公约数

3202

要点注意

对于 vector<int> vec(numBegin, istream_iterator<int>()) 的理解
链接: vector 构造函数问题.
质因数概念

#include<iostream>
#include<vector>
#include<iterator>
//1没有质因子。
//5只有1个质因子，5本身。（5是质数）
//6的质因子是2和3。(6 = 2 × 3)
//2、4、8、16等只有1个质因子：2。（2是质数，4 =2²，8 = 2³，如此类推）
//10有2个质因子：2和5。(10 = 2 × 5)
using namespace std;
using ll = long long;

inline ll publicNum(ll a, ll b) { 
   
	//始终保持a为最小

	if (a < b) { 
   
		swap(a, b);
	}
	for (int i = 2; i <= b; i++) { 
   
		if (a % i == 0 && b % i == 0) { 
   
			return i;
		}
	}
  return 1;
}

int main() { 
   
	int N;
	cin >> N;

	//第一种vector构造写法
	istream_iterator<int> numBegin(cin);//相当于开头
	vector<int> vec(numBegin, istream_iterator<int>());

	//第二种vector构造写法
	//istream_iterator<int> numBegin(cin);//相当于开头
	//istream_iterator<int> numEnd;
	//vector<int> vec(numBegin,numEnd);
	ll result = 0;
	for (int i = 0; i< N; i++) { 
   
		for (int j = i + 1; j < N; j++) { 
   
			ll temp1 = vec[i], temp2 = vec[j];
			while (true) { 
   
				ll temp = publicNum(temp1, temp2);
				if (temp != 1) { 
   
					result += temp;
					result %= 1000000007;
					temp1 /= temp;
					temp2 /= temp;
				}
				else { 
   
					break;
				}
			}
		}
	}
	cout << result;
	return 0;
}

3201

要点注意

最大公约数用辗转相除法求
两个数的乘积等于这两个数的最大公约数与最小公倍数的积

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

inline ll gys(ll a, ll b) { 
   
	int temp;
	if (a < b) { 
   
		swap(a, b);
	}
	while (b != 0) { 
   //最大公约数用辗转相除法
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}
inline ll gbs(ll a, ll b) { 
   //两个数的乘积等于这两个数的最大公约数与最小公倍数的积

	return a * b / gys(a, b);
}
int main() { 
   
	int N;
	cin >> N;
	istream_iterator<int> numBegin(cin);
	vector<int> vec(numBegin, istream_iterator<int>());
	ll result = 0;
	for (int i = 0; i<N; i++) { 
   

		for (int j = i + 1; j < N; j++) { 
   
			
			result += gbs (vec[i],vec[j]);
			result %= 1000000007;
		}
	}
	cout << result;
	return 0;
}

字符串处理

KMP算法复习

class Solution { 
   
public: 判断while）不相等还是if）相等 对j处理 然后用j对next表赋值
    void getNext(int* next, const string& s) { 
   //利用模式串构建next表
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { 
    // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { 
    // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { 
    // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) { 
   
        if (needle.size() == 0) { 
   
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { 
    // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { 
    // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { 
    // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { 
    // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

2019原题-C++组决赛

1、自动编码。给一个字符串，里面含有数字字符，将数字加3后模10的结果放在原位上。即’1’变成’4’，’2’变成’5’,’9’变成’2’，请输出变换后的字符串。
输入说明：一个字符串（长度小于255）。
输出说明：按照题目规则变换后得到的字符序列。
输入样例：2012-09-05A
输出样例：5345-32-38A

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;

char s[260]; 

int main(void)
{ 
   
	cin >> s;
	int len = strlen(s);
	int t;
	for (int i = 0; i < len; i++){ 
   
		if (s[i] >= '0' && s[i] <= '9'){ 
   
			t = s[i] - '0';
			t = (t + 3) % 10;
			s[i] = t + '0';
		}
	}
	cout << s << endl;
	return 0;
}

个人预测题：字符串转化为整型

将数字串“12321421” 转换为int

#include<iostream>
#include<string>
using namespace std;
int main() { 
   
	string str;
	cin >> str;
	int num = 0;
	for (int i = 0; i < str.length(); i++) { 
   
		num = num * 10 + (str[i] - '0');
		//cout << "第" << i << "次" << num << endl;
	}
	cout << num<<endl;
	//cout << str[0]<<str.back();
	return 0;
}

2946（在str1中找str2的出现位置以及次数）

要点注意

有两种方法一种单纯用for循环一种用compare 函数较为方便。
int compare (size_type pos, size_type n, const basic_string& s) const; 从pos 位置开始，以n的大小进行与字符串s 的进行比对，若相等返回0

string A ("aBcdef");
string B ("AbcdEf");

int m=A.compare (B); //完整的A和B的比较
int n=A.compare(1,5,B）；//"Bcdef"和"AbcdEf"比较
 int p=A.compare(1,5,B,4,2); //"Bcdef"和"Ef"比较
 int q=C.compare(0,3,D,0,3); //"123"和"123"比较

#include<iostream>
#include<vector>
#include<string>
using namespace std;

/******************方法一 用for循环***************/
int main01() { 
   
	string str1;
	cin >> str1;
	int count = 0;
	vector<int> v1;
	int startpos;
	//文本串
	string str2 = "_1234.exe";
	for (int i = 0; i<str1.length(); i++) { 
   
		startpos = i;//记录比较起始位置
		for (int j = 0; j < str2.length(); j++) { 
   

			if (str2[j] != str1[startpos++]) { 
   //比较完一次 同时+1.
				break;
			}
			else if (j == str2.length() - 1) { 
   
				count++;
				v1.push_back(i);
			}
		}
	}
	cout << count << " ";
	for (int k = 0; k<v1.size(); k++) { 
   
		cout << v1[k] << " ";
	}
	return 0;
}


/******************方法一 用compare函数***************/
int main02() { 
   
	string str1;
	cin >> str1;
	int count = 0;
	vector<int> v1;
	int startpos;
	//文本串
	string str2 = "_1234.exe";
	for (int i = 0; i<str1.length(); i++) { 
   
		if(str1.compare(i,9,str2) == 0){ 
   
          count++;
          v1.push_back(i);
        }
	}
	cout << count << " ";
	for (int k = 0; k<v1.size(); k++) { 
   
		cout << v1[k] << " ";
	}
	return 0;
}

3181

在一个小写英文字母(a-z)组成的字符串的最短子串，其包含这个字符串中出现过的所有字母。输出最左边的该类子串。

要点注意

运用map 容器进行去重（也可以用set<pair<char,int>>去搞）
求最短的题大多用一个参数如’len 去记录比较。在起始点和终点作为for循环条件的情况下最好用len 去记录，不要用起始点和终点相减，会比较麻烦。

#include<iostream>
#include<string>
#include<map>
using namespace std;
bool check( map<char, int>& m) { 
   
	bool isFind = false;
	for (map<char, int>::iterator itbegin = m.begin(); itbegin != m.end(); itbegin++) { 
   
		if (itbegin->second != 0) { 
   
			isFind = false;
			break;
		}
		else { 
   
			isFind = true;
		}
	}
	return isFind;
}
int main() { 
   
	string str;
	cin >> str;
	map<char, int> mset;
	//统计出现的字母种类
	for (int i = 0; i < str.length(); i++) { 
   
		if (mset.find(str[i]) != mset.end()) continue;
		else mset.insert(pair<char, int>(str[i], 1));
	}
	
	int startPos = 0;
	int strStart = 0;
	int endPos = str.length();//当 check 超出数组范围，不执行
	bool isFind = false;
	int len = str.length();
	while (startPos < endPos) { 
   
		map<char, int> mCheck(mset);
		for (int j = startPos; j < endPos; j++) { 
   
			mCheck[str[j]] = 0;
			isFind = check(mCheck);
			if (isFind) { 
   
				if (j - startPos + 1 < len) { 
   
					strStart = startPos;
					len = j - startPos + 1;
				}	
				break;
			}
		}
		startPos++;
		isFind = false;
	}
	/* test for (map<char, int>::iterator itbegin = mset.begin(); itbegin != mset.end(); itbegin++) { cout <<"map中的" <<itbegin->first<<":"<<itbegin->second << endl; } */

	for (int ii = strStart; ii < len + strStart; ii++) { 
   
		cout << str[ii];
	}
	return 0;
}

3199.str2 每个字符是否能在str1中找到，是输出Y 不是输出N

要点注意

关联式容器set的去重，有序排列 ,默认升序,插入删除快

#include <iostream>
#include<set>
using namespace std;

int main(int argc, char const* argv[])
{ 
   
	ios::sync_with_stdio(true);
	string str1, str2;
	set<char> set1, set2;

	cin >> str1 >> str2;
	for (size_t i = 0; i < str1.length(); i++) { 
   
		set1.insert(str1[i]);//或者set1.insert(str1.at(i);
	}

	for (size_t i = 0; i < str2.length(); i++) { 
   
		if (set1.find(str2[i]) == set1.end()) { 
    //同上set1.find(str2.at(i));
			cout << 'N';
		}
		else { 
   
			cout << 'Y';
		}
	}

	return 0;
}

3198. 九键字母转对应数字

注意要点

暴力法
switch用法

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char const* argv[])
{ 
   
    string str;

    cin >> str;

    for (size_t i = 0; i < str.length(); i++) { 
   
        switch (str.at(i)) { 
   
        case 'a':
        case 'b':
        case 'c':
            cout << 2;
            break;
        case 'd':
        case 'e':
        case 'f':
            cout << 3;
            break;
        case 'g':
        case 'h':
        case 'i':
            cout << 4;
            break;
        case 'j':
        case 'k':
        case 'l':
            cout << 5;
            break;
        case 'm':
        case 'n':
        case 'o':
            cout << 6;
            break;
        case 'p':
        case 'q':
        case 'r':
        case 's':
            cout << 7;
            break;
        case 't':
        case 'u':
        case 'v':
            cout << 8;
            break;
        case 'w':
        case 'x':
        case 'y':
        case 'z':
            cout << 9;

            break;
        default:
            break;
        }
    }

    return 0;
}

3197 给定列，算两个列间距多少列

要点注意

不直接计算两者之差，计算第一个字符串的列数减去另一个字符砖的列数，注意还要减去1，最终结果才表示
加一减一的理解

//思路：1.不直接计算两者之差 2. 计算 第一个字符串的列数 减去 另一个字符砖的列数

#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

 ull strCount(const string& str){ 
   
  //计算该字符串列数
  ull result = 0;
  for(int i = 0 ;i < str.length();i++) { 
   
		 result *= 26;//计算 几个A~Z
      result += str[i] - 'A' + 1;//加上剩余列
  }
  return result;
}


int main() { 
   
  string str1,str2;
  cin>>str1>>str2;
  ull count1 = strCount(str1);
  ull count2 = strCount(str2);
  ull result =(count1==count2)?0: max(count1,count2) - min(count1,count2);
  cout << result;
  return 0; 
}

*3196

要点注意

标志位isFind要及时复位
for循环要注意条件

#include<iostream>
#include<string>
using namespace std;
int main() { 
   
	string str1;
	cin >> str1;
	int N;
	char ch;
	int firstNum, secondNum;
	cin >> N >> ch;
	bool isFind = false;
	int size = str1.length();
	for (int i = 0; i < N; i++) { 
   
		cin >> firstNum >> secondNum;
		for (int i = firstNum - 1; i < secondNum ; i++) { 
   
			if (ch == str1[i]) { 
   
				for (int j = i ; j <size ; j++) { 
   //删除操作；
					str1[j] = str1[j+1];
				}
				str1.resize(--size);
				isFind = true;
				//cout <<"shanchu操作 " <<str1<<str1.size()<<endl;
				break;
			}
		}
		if (!isFind) { 
   
			++size;
			str1.resize(size);
			for (int k = size - 2; k > secondNum - 1; k--) { 
   //添加
				str1[k + 1] = str1[k];
			}
			str1[secondNum] = ch;
			//cout << "添加操作" <<str1 <<str1.size()<<endl;
			
		}
		isFind = false;
	}
	cout << str1;
	return 0;
}

3192

题目描述
现要对一个由字符a-z和A-Z组成的字符串进行解密，已知加密规则是：字符串中所有字符分别在大写或小写的字母表中被循环右移5位(fGh–>aBc)。请你写程序完成解密。

要点注意

注意末尾可移部分不足五位的处理方法

#include<bits\stdc++.h>
using namespace std;
int main() { 
   
  string sStr;
  cin >> sStr;
  for(int i = 0 ; i< sStr.length();i++) { 
   
    if(sStr[i] >= 'A' && sStr[i]<= 'Z') { 
   
      if(sStr[i] + 5 >'Z') { 
   
        sStr[i] = 'A' + 5 - ('Z'- sStr[i] ) - 1;
      }
      else sStr[i] += 5;
    } 
    if(sStr[i] >= 'a' && sStr[i] <= 'z') { 
   
      if(sStr[i] + 5 >'z') { 
   
        sStr[i] = 'a' + 5 - ('z'- sStr[i]) - 1;
      }else sStr[i] += 5;
    }
  }
  cout<< sStr<<endl;
  return 0;
}

3191

输入一行由字符a_z和AZ组成的字符串，字符串长度<=10000，求其中任意两个字符出现次数的差值的绝对值

要点注意

大小写的判断问题。本题不区分大小写
本题写出区分大小写的方法，若要不区分大小写只需加几行判断就行。

#include<iostream>
#include<string>
#include<map>
using namespace std;

int main() { 
   
	string str1;
	char A, B;
	int countA = 0;
	int countB = 0;
	cin >> str1;
	cin >> A >> B;
	//multimap 容器
	multimap<char, int> mmp;
	//统计字符出现数量
	for (int i = 0; i < str1.length(); i++) { 
   
		multimap<char, int>::iterator it = mmp.find(str1[i]);
		if (it != mmp.end()) { 
   
			(*it).second++;
		}
		else { 
   
			mmp.insert(pair<char, int>(str1[i], 1));
		}
	}
	multimap<char, int>::iterator it1 = mmp.find(A);
	multimap<char, int>::iterator it2 = mmp.find(B);
	if (it1 != mmp.end()) countA = (*it1).second;
	if (it2 != mmp.end()) countB = (*it2).second;
	if (countA<countB) { 
   
		swap(countA, countB);
	}
	cout << countA - countB << endl;
	return 0;
}

//方法2 ：原题答案
//int main() { 
   
// string str1;
// cin >> str1;
// char A, B;
// cin >> A >> B;
// int countA = 0, countB = 0;
// //遍历查找字符
// for (int i = 0; i< str1.length(); i++) { 
   
// if (str1[i] == A || str1[i] == A + 32 || str1[i] == A - 32) { 
   
// countA++;
// }
// if (str1[i] == B || str1[i] == B + 32 || str1[i] == B - 32) { 
   
// countB++;
// }
// }
// //绝对值运算
// if (countA<countB) swap(countA, countB);
// cout << countA - countB << endl;
// return 0;
//}

3170

输入一个正整数N(1<=N<10000),然后输入这N个正整数序列，再输入一个正整数K(1<=K<=100),其后有K行操作，每行操作输入一个字符c（取‘+’、‘-’、‘=’）、正整数i和j(1<=i<=j<=N)、正整数m。当c取‘+’时表示将区间[i,j]中的元素都加上m；c取‘-’时表示将区间[i,j]中的元素都减去m；c取‘=’时表示将区间[i,j]中的元素都赋为m；操作结束后输出最终的序列。

要点注意

注意题目中所给的数值取值范围！防止数组越界，如第 i （1<=i<= N ） 个位置若不执行减一操作，数组操作时会报错。

#include<iostream>
#include<vector>

using namespace std;

int main() { 
   
	int N;
	cin >> N;//正整数序列
	vector<int> v1;
	for (int i = 0; i < N; i++) { 
   
		int num;
		cin >> num;
		v1.push_back(num);
	}
	char c;//+ - =
	int A, B, C;//三个参数
	int K;//操作次数
	cin >> K;
	for (int j = 0; j < K; j++) { 
   
		cin >> c >> A >> B >> C;
		switch (c) { 
   //分类操作
		case '+':for (int k = A - 1; k < B; k++) { 
   
			v1[k] += C;
		}
				 break;
		case '-':for (int k = A - 1; k < B; k++) { 
   
			v1[k] -= C;
		}
				 break;
		case '=':for (int k = A - 1; k < B; k++) { 
   
			v1[k] = C;
		}
				 break;
		default:break;
		}
	}
	for (int v = 0; v < v1.size(); v++) { 
   
		cout << v1[v] << " ";
	}
	return 0;
}

3169

输入一个正整数N(1<=N<10000),接下来输入这N个正整数序列，再输入一个正整数K(1<=K<=100),其后跟K行操作，每行操作包括两个正整数i和j(1<=i<=j<=N)，表示将区间[i,j]中的元素删除，操作结束后输出最终的正整数序列。

要点注意

注意看题目输入输出自己验证一下便于理解题目
一开始用vector容器的 erase 函数，报错就是因为没有理解题目要求。

#include<iostream>
#include<vector>
using namespace std;
int main() { 
   
	int N;//序列长度
	vector<int> v1(10000, 0);
	cin >> N;
	for (int i = 0; i < N; i++) { 
   
		int num;
		cin >> num;
		v1[i] = num;
	}
	int K, A, B;
	cin >> K;
	for (int j = 0; j < K; j++) { 
   
		cin >> A >> B;
		for (int j1 = A - 1; j1<B; j1++) { 
   
			v1[j1] = 0;
		}
	}
	for (int k = 0; k< N; k++) { 
   
		if (v1[k] != 0) { 
   
			cout << v1[k] << " ";
		}

	}
	return 0;
}

3182

要点总结

注意 if (nLoc - i< len) {//找到最短的字符串。注： nLoc-i不能再加一了因为当遇到只有母字符串满足条件会有错误! len = nLoc - i; outFirst = i; outLast = nLoc; }这行代码
任何变量能初始化的就初始化！防止bug

#include<iostream>
#include<string>
using namespace std;
int main() { 
   
	string str;
	int outFirst =-1;//结果字符串首
	int outLast= -1;//结果字符串尾
	cin >> str;
	int len = str.length();
	//cout << len<<endl;
	for (int i = 0; i< str.length(); i++) { 
   
		int nLoc = str.find(str[i], i + 1);//从字符串第i+1的位置开始找，返回第一个出现的位置
		if (nLoc != string::npos) { 
   // 理解string 类 find 函数的用法
			if (nLoc - i< len) { 
   //找到最短的字符串。注： nLoc-i不能再加一了 因为当遇到只有母字符串满足条件会有错误!
				len = nLoc - i;
				outFirst = i;
				outLast = nLoc;
			}
		}
	}
	if (outFirst == -1) return 0;//没有相同的 
	for (int j = outFirst; j < outLast+1; j++) { 
     //outFirst 与 outLast 记得初始化！！！
		cout << str[j];
	}
	return 0;
}

多元素运算问题

2019原题1

对给定的整数数组（数组长度N满足1〈N〈10000），选择一个位置，把数组分割为前后两个部分。求使得前后两个部分所有元素和的差值绝对值最大的分割位置（即使得分割后前后两部分数据的和尽可能悬殊）。如有多种分割情况，选择分割位置最小的情况输出。
输入说明：第一行是整数N，说明数组中元素个数，接下来一行是这N个数。
输出说明：一个整数，即前面部分包含的元素个数。
输入样例：6
11 102 13 24 35 46
输出样例：1

先计算出前缀和，再枚举断点找到最小的情况即可
int abs(int X) 注意只返回整型绝对值，浮点型变量处理时要注意！

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
typedef long long ll;

ll arr[N], sum[N];

int main(void)
{ 
   
	int n, pos = 0;
	ll maxv = 0;
	scanf("%d", &n);
	///计算前缀值
	for (int i = 0; i < n; i++){ 
   
		scanf("%lld", &arr[i]);
		if (i == 0){ 
   
			sum[i] = arr[i];
		}
		else{ 
   
			sum[i] = sum[i - 1] + arr[i];
		}
	}
	for (int i = 0; i < n - 1; i++){ 
   
		if (abs(sum[i] - (sum[n - 1] - sum[i])) > maxv){ 
   //利用sum末尾值减去 某一前缀值即可得到 后半部分的和。
			maxv = abs(sum[i] - (sum[n - 1] - sum[i]));
			pos = i + 1;//+1 ！
		}
	}
	printf("%d\n", pos);
	return 0;
}

2019原题2

求1 – N整数中所有立方值的平方根为整数的数的个数
例子：输入10 输出3

要点注意

sqrt 求平方根
– （int）result == result 判断是否整数另一个 result* result == I3 也可判断。

#include<iostream>
#include<algorithm>
using namespace std;
//求1 - N整数中所有立方值的平方根为整数的数的个数
int main() {
	int N;
	cin >> N;
	int count = 0;
	for (int i = 1; i < N; i++) {
		long long I3 = i*i*i;
		double result = sqrt(I3);
		if ((int)result ==result) {
			count++;
		}
	}
	cout << count << endl;
	return 0;
}

2948

要点注意

C++ 创建和释放二维数组的方法（申请空间法、vector嵌套法）
注意题目结果是从0开始还是1开始数，注意+1 或-1。
vector详细介绍链接

#include<iostream>
using namespace std;

int main() { 
   
	int N ;
	cin >> N;
	/***********vector嵌套法**************/
	
	/*vector<vector<int>> Hums(N); for (int iv; iv <N; iv++ ) { Hums[iv].resize(N); }*/
	
	/***********在堆上 申请二维数组的空间***注意最后要释放***********/
	int **Hums = new int*[N];
	for (int kk = 0; kk < N; kk++) { 
   
		Hums[kk] = new int[N];
	}
	//接收二维数组
	for (int ii = 0; ii< N; ii++) { 
   
		for (int jj = 0; jj< N; jj++) { 
   
			cin >> Hums[ii][jj];
		}
	}
	int rpointX = -1;
	int rpointY = -1;
	int maxPoint = -1;
	for (int i = 1; i < N - 1; i++) { 
   
		for (int j = 1; j < N - 1; j++) { 
   
			//判断顶点
			if (Hums[i][j]>Hums[i - 1][j]
				&& Hums[i][j] > Hums[i + 1][j]
				&& Hums[i][j] > Hums[i + 1][j]
				&& Hums[i][j] > Hums[i][j + 1]
				&& Hums[i][j] > Hums[i][j - 1]
				) { 
   
				//是否为最大顶点
				if (Hums[i][j] >= maxPoint) { 
   
					maxPoint = Hums[i][j];
					rpointX = i + 1; //注意 题目所需要输出的 数是从1 开始算 所以＋1；
					rpointY = j + 1;
				}
			}

		}
	}
	cout << rpointX << " " << rpointY;
	//释放二维数组
	for (int iii = 0; iii < N; iii++) { 
   
		delete [] Hums[iii];
	}
	delete [] Hums;
	return 0;
}

3194

若有非零整数A、B、C,将其组成一个表达式(A@B)#C，其中@和#为运算符号’+‘、’-‘、’*‘、’/‘、’%’之一，同一符号可选择一次或多次，求这个表达式的运算结果的最大值。

要点注意

原题答案过于暴力，这里稍微简化了一下，测试全过。


#include<stdio.h>
using namespace std;
int main() { 
   
	int n, result = 0;
	int max = 0;
	int num[1000][3];
	scanf("%d", &n);
	for (int i = 0; i<n; i++) { 
   //输入数据 
		scanf("%d %d %d", &num[i][0], &num[i][1], &num[i][2]);
	}
	for (int i = 0; i<n; i++) { 
   
		for (int j = 0; j<5; j++) { 
   
    		for (int k = 0; k<5; k++) { 
   
				switch (j) { 
   
					case 0: result = num[i][0] + num[i][1]; break;
					case 1: result = num[i][0] - num[i][1]; break;
					case 2: result = num[i][0] * num[i][1]; break;
					case 3: result = num[i][0] / num[i][1]; break;
					case 4: result = num[i][0] % num[i][1]; break;
					default: break;
				}
				switch (k) { 
   
					case 0: result += num[i][2]; break;
					case 1: result -= num[i][2]; break;
					case 2: result *= num[i][2]; break;
					case 3: result /= num[i][2]; break;
					case 4: result %= num[i][2]; break;
					default: break;
				}
				max = (result>max) ? result : max;
			}
		}
		printf("%d/n",max);
		//复位进入下一个组合运算
		max = 0;
	}
	return 0;
}

3193

要点注意

官方平台代码运行不了郁闷！！，但放VS运行的了且测试集都通过了。有大佬解答吗？？？！

#include<iostream>
using namespace std;
int main() { 
   
	int N;
	cin >> N;
	float num[1000][3]; //不为int 是为了解决 除法的结果问题
	for (int i = 0; i<N; i++) { 
   //输入数据 
		scanf("%f %f %f", &num[i][0], &num[i][1], &num[i][2]);
	}
	float result = 0;//结果
	bool isFind = false;// 标志位
	for (int i = 0; i < N; i++) { 
   
		for (int j = 0; j < 5; j++) { 
   
			switch (j) { 
   
				case 0: result = num[i][0] + num[i][1]; break;
				case 1: result = num[i][0] - num[i][1]; break;
				case 2: result = num[i][0] * num[i][1]; break;
				case 3: result = num[i][0] / num[i][1]; break;
				case 4: result =(int)num[i][0] % (int)num[i][1]; break;
				default: break;
			}
			if (result == num[i][2]) { 
   
				isFind = true;
				cout << result << "用的符号" << j << endl;
				break;
			}
		}
		if (isFind) cout << "YES" << endl;
		else cout << "NO" << endl;
		//复位
		result = 0;
		isFind = false;
	}
	return 0;
}

3167（4/5）

若有一个区间[M,N]，求区间(包括两端点M、N)内所有数中不含数字K的数的和。

要点注意

有标志位的情况，每次判断完要记得复位。
循环中不要改变循环参数（如 i，j ，k）
有一个测试点超时，不知道为啥。。。有待大佬解答

#include<iostream>
using namespace std;
int main() { 
   
	int M, N, K;
	cin >> M >> N >> K;
	int result = 0;
	int isAdd = true;
	for (int i = M; i <= N; i++) { 
   
		int temp = i;
		while (temp) { 
   
			if (temp % 10 == K) { 
    isAdd = false; break; }
			temp /= 10;
		}
		if (isAdd) { 
   
			result += i;
			result %= 1000000007;
		}
		isAdd = true;
	}
	cout << result;
	return 0;
}

3166（2/5）

若有一个正整数A1A2…An==A1^1+A22+…+An^n,则称这个数是特殊数。

要点注意

只过了两个
注意变量复位

#include<iostream>
using namespace std;
int calMultiSquare(int num, int count) { 
   
	for (int i = 0; i < count - 1; i++) { 
   
		num *= num;
	}
	return num;
}
int main() { 
   
	int N;
	//int numSum;//接收多次方数
	int result = 0;//接收结果
	cin >> N;
	for (int i = 0; i < N + 1; i++) { 
   
		int tmp = i;
		int count = 0;//计算位数
		while (tmp) { 
   
			count++;
			tmp /= 10;
		}
		tmp = i;
		while (tmp) { 
   

			result += calMultiSquare(tmp % 10, count--);
			tmp /= 10;
		}
		if (result == i) { 
   
			result = 0;//复位
			cout << i << " ";
		}

	}
	return 0;
}

3195

要点注意

暴力：这个题解无语。。。创建一个二维数组，一个for用于接收输出，一个for用于查找所有运算符组合是否有等于24.
简单：还没想

#include"stdio.h"
int main(){ 
   
	int n;
	int num[1000][3];
	scanf("%d",&n);
	for(int i=0;i<n;i++){ 
   //输入数据 
		scanf("%d %d %d",&num[i][0],&num[i][1],&num[i][2]);
	}
	for(int i=0;i<n;i++){ 
   //穷举列出运算式子的组合 
		int flag=0;//设置逻辑标志 
		if((num[i][0]+num[i][1])+num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]+num[i][1])-num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]+num[i][1])*num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]+num[i][1])/num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]+num[i][1])%num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]-num[i][1])+num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]-num[i][1])-num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]-num[i][1])*num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]-num[i][1])/num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]-num[i][1])%num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]*num[i][1])+num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]*num[i][1])-num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]*num[i][1])*num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]*num[i][1])/num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]*num[i][1])%num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]/num[i][1])+num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]/num[i][1])-num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]/num[i][1])*num[i][2]==24){ 
   
			flag=1;
		}
				if((num[i][0]/num[i][1])/num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]/num[i][1])%num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]%num[i][1])+num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]%num[i][1])-num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]%num[i][1])*num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]%num[i][1])/num[i][2]==24){ 
   
			flag=1;
		}
		if((num[i][0]%num[i][1])%num[i][2]==24){ 
   
			flag=1;
		}
		if(flag==1){ 
    
			printf("YES\n");
		}else{ 
   //flag为0时表示上述的所以组合没有等于24的 
			printf("NO\n");
		}
	}
	return 0;
}

二叉树

链接：二叉树相关算法总结

题目1

已知结点元素值为正整数且值不相同的一棵二叉树。该二叉树通过给出其先序遍历序列和中序遍历序列构造而成。输入一个整数x，针对此二叉树编写程序求出x的右子树中所有结点值的和（若×不在树上，输出-1）。
输入说明：第一行输入某二叉树的先序遍历序列
第二行输入该二叉树的中序遍历序列
第三行输入正整数x输出说明：若×在树上，输出以x节点为根节点的树中所有结点值的和；如果×不在树上则输出-1。

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
// 创建二叉树结构体
struct TreeNode { 
   
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) { 
   }
};
//构造二叉树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 
   
	//递归终止条件 ：后序遍历数组为空
	if (postorder.size() == 0) return NULL;
	//找到找到前序/后续遍历数组 第一个/最后一个元素 初始化当前节点
	TreeNode * root = new TreeNode(postorder[postorder.size() - 1]);

	//找到前序/后续遍历数组 第一个/最后一个元素 在中序遍历数组中的位置
	int delimiterIndex;
	for (int i = 0; i < inorder.size(); i++) { 
   
		if (postorder[postorder.size() -1] == inorder[i]) { 
   
			delimiterIndex = i;
			break;
		}
	}
	//通过这个位置 去分离中序数组 左闭右开!!!!!
	vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
	vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
	// postorder 舍弃末尾元素
	postorder.resize(postorder.size() - 1);
	//通过这个位置 去分离后序数组
	vector<int> leftPostorder(postorder.begin(), postorder.begin() + delimiterIndex);
	vector<int> rightPostorder(postorder.begin() + delimiterIndex, postorder.end());
	//第六步：递归处理左区间和右区间
	root->left = buildTree(leftInorder, leftPostorder);
	root->right = buildTree(rightInorder, rightPostorder);
	return root;
}


//前序遍历找到对应点开始叠加
int AddTree(TreeNode* root,int Target,int result) { 
   
	stack<TreeNode*> st;
	bool isFind = false;
	if (root == NULL) return result;
	st.push(root);
	while (!st.empty()) { 
   
		TreeNode* node = st.top();                       // 中
		st.pop();
		if (node->val == Target) isFind = true;
		if (isFind) result += node->val;
		if (node->right) st.push(node->right);           // 右（空节点不入栈）
		if (node->left) st.push(node->left);             // 左（空节点不入栈）
	}
	return isFind ? result :-1 ;
}



int main() { 
   
	
	
	int inputa[5] = { 
    9, 3, 15, 20, 7 };
	int inputb[5] = { 
    9, 15, 7, 20, 3 };
	vector<int> A(inputa, inputa + 5);//左闭右开
	vector<int> B(inputb, inputb + 5);
	TreeNode * node = buildTree(A, B);
	/*for (int i = 0; i < A.size(); i++) { cout << A[i]<<" ----"<<A.size(); }*/
	int sum = AddTree(node, 20, 0);
	cout << sum;
	return 0;
}

最短距离求解（dijkstra算法）

（这个题解由于变量命名问题不太好理解，当时比较菜，瞎命名以为好理解结果第二遍看晕了。建议找其他同题目的解去理解。）
村村通：求解2个村庄之间的修路最低成本。输入包括两两村庄之间道路的建设成本。计算修筑给定两个村庄之间道路的最小建设成本，如果两村之间通过已知数据发现不能构成联通，输出-1。
输入说明：第一行是3个整数，分别表示村庄的数目N（村庄编号1~N，0〈N〈10000）和待求解的两个村庄的编号，之后是多行道路修筑成本信息，每行有3个整数，分别表示两个村庄的编号和修筑这两个村庄之间道路的建设成本，以-1 -1 -1结束。
输出说明：修筑指定村落间道路的最小建设成本。

输入：5 1 3
1 2 11
1 4 12
2 3 8
3 4 5
4 5 8
-1 -1 -1
输出：17

要点注意

思路
1.定义全局变量 N 、startC、 endC 以及初始化用到的INF
2.声明邻接表创建最少消费数组和最短标志数组并定义初始化函数 init
3.定义宏函数用于插入邻接表
4.定义djlts 算法（不需要传入参数，利用全局变量）注意dijlts 算法只是创建该起始点对于所有对象的最短距离表
4.1 初始化 distance 起始点位置为0，利用优先级队列小顶堆
5.main 函数接收，调用 init、djlts ，输出distanceS 【】对应元素值。
注意优先级队列的使用

#include<iostream>
#include<vector>
#include<functional>
#include<queue>
/*思路*/
/* 1.定义全局变量 N 、startC、 endC 以及初始化用到的INF 2.声明邻接表 创建最少消费数组 和 最短标志数组 并 定义初始化函数 init 3.定义宏函数 用于插入邻接表 4.定义djlts 算法 （不需要传入参数，利用全局变量） 注意dijlts 算法只是创建该起始点对于所有对象的最短距离表 4.1 初始化 distance 起始点位置 为0，利用优先级队列 小顶堆 5.main 函数接收 ，调用 init、djlts ，输出distanceS 【】对应元素值。 */
const int INF = 0x3f3f3f3f, N = 10005;//int 32位
using namespace std;
using P =pair<int, int> ;
int NUMS, startC, endC;

//创建邻接表
vector<P> G[N];
//创建 最少消费 记录数组 以及 是否已经找到最短标志数组
int distanceS[N];
bool isFindShortest[N];

#define PUSH(a,b,c) G[a].push_back(P(b,c)) //宏函数
//初始化
void init(){ 
   
	for (int i = 0; i < N; i++)
		G[i].clear();
	memset(distanceS, INF, sizeof distanceS);
	memset(isFindShortest, false, sizeof isFindShortest);
}

//重写仿函数
struct tmp2 //重写仿函数
{ 
   
	bool operator() (P a, P b)
	{ 
   
		return a.second > b.second; //大顶堆
	}
};
//迪杰拉特斯算法
void djlts() { 
   
	//初始化起始村庄点到起始村庄点的消费为零 
	distanceS[startC] = 0;
	//创建优先级队列适配vector容器
	priority_queue<P, vector<P>, tmp2> pque;
	pque.push(P(startC, 0));
	while (!pque.empty()) { 
   
		P p = pque.top();
		pque.pop();
		//初始化起始村庄点 
		int NowStPoint = p.first;
		if (isFindShortest[NowStPoint]) continue;//若已经找到最少消费 进入下一个循环

		
												 //当前节点虽然找到但未被使用，但要利用到这个节点的最小消费值， 所以在这里赋值为true
		isFindShortest[NowStPoint] = true;
		for (int i = 0; i < G[NowStPoint].size(); i++) { 
   
			int aimPoint = G[NowStPoint][i].first;
			int cost = G[NowStPoint][i].second;
			//判断最小消费，对distance 进行赋值 ,distanceS中的元素 默认最大。
			if (!isFindShortest[aimPoint] && distanceS[aimPoint] > distanceS[NowStPoint] + cost) { 
   
				distanceS[aimPoint] = distanceS[NowStPoint] + cost;
				pque.push(P(aimPoint, distanceS[aimPoint]));
			}
		}
		
	}
}

int main() { 
   
	//初始化邻接表 和两个数组
	init();
	cin >> NUMS >> startC >> endC;//村庄个数 ，村庄1 ，村庄2
	int A, B, cost;
	while (cin >> A >> B >> cost) { 
   
		if (A == -1)
			break;
		PUSH(A, B, cost);
		PUSH(B, A, cost);
	}
	djlts();
	cout << (distanceS[endC] == INF ? -1 : distanceS[endC]) << endl;
	return 0;
}

今天的文章2021年计算机能力挑战赛真题总结C++版分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/61302.html

2021年计算机能力挑战赛真题总结C++版

前言

选择题

编程题

asii码操作问题

3185

要点注意

3225.

要点注意

3208. student成绩计算与排名

要点注意

3207 ,选择、填空、应用 取第一，总分取前三

要点注意

时间秒数计算

3205

注意要点

3204

注意要点

公共质因数、最小公倍数、最大公约数

3202

要点注意

3201

要点注意

字符串处理

KMP算法复习

2019原题-C++组决赛

个人预测题：字符串转化为整型

2946（在str1中找str2的出现位置以及次数）

要点注意

3181

要点注意

3199.str2 每个字符是否能在str1中找到，是输出Y 不是输出N

要点注意

3198. 九键字母转对应数字

注意要点

3197 给定列，算两个列间距多少列

要点注意

*3196

要点注意

3192

要点注意

3191

要点注意

3170

要点注意

3169

要点注意

3182

要点总结

多元素运算问题

2019原题1

2019原题2

要点注意

2948

要点注意

3194

要点注意

3193

要点注意

3167（4/5）

要点注意

3166（2/5）

要点注意

3195

要点注意

二叉树

题目1

最短距离求解（dijkstra算法）

要点注意

相关推荐

发表回复

3207 ,选择、填空、应用取第一，总分取前三