牛客华为题库前40题_while(cin>>s); cout<

/*作者：jennie
* 开始时间：2022年08月30日 00:49:29 星期二 
* 结束时间：2022年08月30日 00:52:56 星期二 （3）
* 课程名：华为题库
* 知识单元：HJ1 字符串最后一个单词的长度
* 属性：HJ1 字符串最后一个单词的长度
* 具体题目要求：
* 描述
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
输入描述：
输入一行，代表要计算的字符串，非空，长度小于5000。
输出描述：
输出一个整数，表示输入字符串最后一个单词的长度。
示例1
输入：
hello nowcoder
复制
输出：
8
复制
说明：
最后一个单词为nowcoder，长度为8   
*/
#include<bits/stdc++.h>
using namespace std;
 
int main1() {
	string s;
	while (cin >> s);
	cout << s.size();
	return 0;
}
 
/*2022年08月30日 00:52:50 星期二
* 2022年08月30日 00:57:23 星期二 （5）
HJ2 计算某字符出现次数
题目
题解(824)
讨论(2k)
排行
面经new
简单  通过率：33.63%  时间限制：1秒  空间限制：32M
知识点
字符串
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
数据范围： 1 \le n \le 1000 \1≤n≤1000
输入描述：
第一行输入一个由字母和数字以及空格组成的字符串，第二行输入一个字符。
输出描述：
输出输入字符串中含有该字符的个数。（不区分大小写字母）
示例1
输入：
ABCabc
A
复制
输出：
2
复制*/
int main2() {
	string s;
	getline(cin, s);
	char ch;
	int res = 0;
	cin >> ch;
	for (auto c : s) {
		if (tolower(c) == ch || toupper(c) == ch) {
			res++;
		}
	}
	cout << res;
	return 0;
}
 
 
 
/*HJ3 明明的随机数
题目
题解(824)
讨论(2k)
排行
面经new
较难  通过率：24.98%  时间限制：1秒  空间限制：32M
知识点
数组
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
明明生成了NN个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。
数据范围： 1 \le n \le 1000 \1≤n≤1000  ，输入的数字大小满足 1 \le val \le 500 \1≤val≤500 
输入描述：
第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。 具体格式可以参考下面的"示例"。
输出描述：
输出多行，表示输入数据处理后的结果
示例1
输入：
3
2
2
1
复制
输出：
1
2
复制
说明：
输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到500之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
2
2
1
所以样例的输出为：
1
2       
2022年08月30日 00:57:58 星期二
2022年08月30日 01:02:31 星期二 （5）*/
int main3() {
	int n,num;
	set<int> s0;
	vector<int> v0;
	cin >> n;
	while (n--)
	{
		cin >> num;
		s0.insert(num);
	}
	for (auto it : s0) {
		cout << it << endl;
	}
	return 0;
}
 
 
 
 
/*HJ4 字符串分隔
题目
题解(904)
讨论(1k)
排行
面经new
简单  通过率：31.27%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
•输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
输入描述：
连续输入字符串(每个字符串长度小于等于100)
输出描述：
依次输出所有分割后的长度为8的新字符串
示例1
输入：
abc
复制
输出：
abc00000
复制
2022年08月30日 01:02:58 星期二
2022年08月30日 01:14:06 星期二 （12）*/
int main4() {
	string s;
	getline(cin, s);
	int i=0,n=8-s.size() % 8;
	s.append(n%8, '0');
	while (i < s.size()) {
		cout << s.substr(i, 8)<<endl;
		i += 8;
	}
	return 0;
}
 
 
 
 
 
/*HJ5 进制转换
题目
题解(597)
讨论(1k)
排行
面经new
简单  通过率：37.25%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。
数据范围：保证结果在 1 \le n \le 2^{31}-1 \1≤n≤2 
31
 −1 
输入描述：
输入一个十六进制的数值字符串。
输出描述：
输出该数值的十进制字符串。不同组的测试用例用\n隔开。
示例1
输入：
0xAA
复制
输出：
170
复制
2022年08月30日 01:14:42 星期二 */
 
int main5() {
	string s;
	cin >> s;
	//int n = 0;
	//for (int i = 2; i < s.size(); i++) {
	//	n *= 16;
	//	if (isdigit(s[i])) {
	//		n += (s[i] - '0');	//数字
	//	}
	//	else {
	//		n+=(s[i] - 'A'+10);
	//	}
	//}
	//cout << n;
	cout << stoi(s, 0, 16);
	return 0;
}
 
 
 
 
 
 
 
/*
HJ6 质数因子
题目
题解(564)
讨论(1k)
排行
面经new
简单  通过率：28.18%  时间限制：1秒  空间限制：32M
知识点
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
数据范围： 1 \le n \le 2 \times 10^{9} + 14 \1≤n≤2×10 
9
 +14 
输入描述：
输入一个整数
输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。
示例1
输入：
180
复制
输出：
2 2 3 3 5
复制
相似企业真题
TOP
2022年08月30日 13:50:38 星期二
2022年08月30日 14:00:40 星期二 （10）*/
//bool judge(int n) {	//不用判断质数
//	for (int i = 2; i <= sqrt(n); i++) {
//		if (!(n % i)) {
//			return false;
//		}
//	}
//	return true;
//}
int main6() {
	int n;
	cin >> n;
	for (int i = 2; i <= sqrt(n); i++) {	//不用判断质数，为了有限时间注意i<=sqrt(n)，绝妙想法
		while (!(n % i)) {
			cout << i << ' ';
			n /= i;
		}
	}
	return 0;
}
 
 
 
 
 
 
 
/*
HJ7 取近似值
题目
题解(467)
讨论(1k)
排行
面经new
入门  通过率：53.27%  时间限制：1秒  空间限制：32M
知识点
基础数学
语法题
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于 0.5 ,向上取整；小于 0.5 ，则向下取整。
数据范围：保证输入的数字在 32 位浮点数范围内
输入描述：
输入一个正浮点数值
输出描述：
输出该数值的近似整数值
示例1
输入：
5.5
复制
输出：
6
复制
说明：
0.5>=0.5，所以5.5需要向上取整为6   
示例2
输入：
2.499
复制
输出：
2
复制
说明：
0.499<0.5，2.499向下取整为2   
相似企业真题
TOP
2022年08月30日 14:03:12 星期二 */
int main7() {
	double n;
	cin >> n;
	cout << int(n + 0.5);
	return 0;
}
 
 
 
 
 
 
/*
HJ8 合并表记录
题目
题解(554)
讨论(1k)
排行
面经new
简单  通过率：37.57%  时间限制：1秒  空间限制：32M
知识点
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。
提示:
0 <= index <= 11111111
1 <= value <= 100000
输入描述：
先输入键值对的个数n（1 <= n <= 500）
接下来n行每行输入成对的index和value值，以空格隔开
输出描述：
输出合并后的键值对（多行）
示例1
输入：
4
0 1
0 2
1 2
3 4
复制
输出：
0 3
1 2
3 4
复制
示例2
输入：
3
0 1
0 2
8 9
复制
输出：
0 3
8 9
复制
相似企业真题
TOP
2022年08月30日 14:32:26 星期二 
2022年08月30日 14:38:48 星期二 （6）
*/
int main8() {
	int i, n, v;
	map<int, int> m;
	cin >> n;
	while (n--) {
		cin >> i >> v;
		m[i] += v;
	}
	for (auto it : m) {
		cout << it.first << ' ' << it.second << endl;
	}
	return 0;
}
 
 
 
 
 
 
 
/*
HJ9 提取不重复的整数
题目
题解(656)
讨论(1k)
排行
面经new
入门  通过率：48.70%  时间限制：1秒  空间限制：32M
知识点
数组
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。
保证输入的整数最后一位不是 0 。
数据范围： 1 \le n \le 10^{8} \1≤n≤10 
8
  
输入描述：
输入一个int型整数
输出描述：
按照从右向左的阅读顺序，返回一个不含重复数字的新的整数
示例1
输入：
9876673
复制
输出：
37689
复制
相似企业真题
TOP
2022年08月30日 14:39:06 星期二 
2022年08月30日 14:43:08 星期二（4） */
 
int main9() {
	string s;
	cin >> s;
	set<int> s0;
	int len = 0;
	for (int i = s.size()-1; i >= 0; i--) {
		s0.insert(s[i]);
		if (s0.size() > len) {
			cout << s[i];
			len++;
		}
	}
	return 0;
}
 
 
 
 
 
 
/*
HJ10 字符个数统计
题目
题解(544)
讨论(1k)
排行
面经new
简单  通过率：52.23%  时间限制：1秒  空间限制：32M
知识点
字符串
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
数据范围： 1 \le n \le 500 \1≤n≤500 
输入描述：
输入一行没有空格的字符串。
输出描述：
输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。
示例1
输入：
abc
复制
输出：
3
复制
示例2
输入：
aaa
复制
输出：
1
复制
相似企业真题
TOP
2022年08月30日 14:45:39 星期二 
2022年08月30日 14:47:46 星期二 （2）*/
 
int main10() {
	set<int> s0;
	string s;
	cin >> s;
	for (auto c : s) {
		s0.insert(c);
	}
	cout << s0.size();
	return 0;
}
 
 
 
/*
HJ11 数字颠倒
题目
题解(387)
讨论(1k)
排行
面经new
简单  通过率：61.80%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
数据范围： 0 \le n \le 2^{30}-1 \0≤n≤2 
30
 −1 
输入描述：
输入一个int整数
输出描述：
将这个整数以字符串的形式逆序输出
示例1
输入：
1516000
复制
输出：
0006151
复制
示例2
输入：
0
复制
输出：
0
复制
相似企业真题
TOP
2022年08月30日 14:48:04 星期二
2022年08月30日 14:49:50 星期二 （1）*/
 
 
int main1112() {
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	cout << s;
	return 0;
}
 
 
 
 
 
/*
HJ13 句子逆序
题目
题解(426)
讨论(1k)
排行
面经new
简单  通过率：44.31%  时间限制：1秒  空间限制：32M
知识点
数组
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”
所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
数据范围：输入的字符串长度满足 1 \le n \le 1000 \1≤n≤1000 
注意本题有多组输入
输入描述：
输入一个英文语句，每个单词用空格隔开。保证输入只包含空格和字母。
输出描述：
得到逆序的句子
示例1
输入：
I am a boy
复制
输出：
boy a am I
复制
示例2
输入：
nowcoder
复制
输出：
nowcoder
复制
相似企业真题
TOP
2022年08月30日 14:50:13 星期二
2022年08月30日 14:52:44 星期二（2） */
 
 
int main13() {
	vector<string> v;
	string s;
	while (cin>>s)
	{
		v.push_back(s);
	}
	for (int i = v.size() - 1; i >= 0; i--) {
		cout << v[i] << ' ';
	}
	return 0;
}
 
 
 
 
/*
HJ14 字符串排序
题目
题解(411)
讨论(1k)
排行
面经new
简单  通过率：45.57%  时间限制：1秒  空间限制：32M
知识点
字符串
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
给定 n 个字符串，请对 n 个字符串按照字典序排列。
数据范围： 1 \le n \le 1000 \1≤n≤1000  ，字符串长度满足 1 \le len \le 100 \1≤len≤100 
输入描述：
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述：
数据输出n行，输出结果为按照字典序排列的字符串。
示例1
输入：
9
cap
to
cat
card
two
too
up
boat
boot
复制
输出：
boat
boot
cap
card
cat
to
too
two
up
复制
相似企业真题
TOP
2022年08月30日 14:54:02 星期二
2022年08月30日 14:56:00 星期二（2） */
 
 
int main14() {
	int n;
	cin >> n;
	string* arr = new string[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		cout<< arr[i]<<endl;
	}
	return 0;
}
 
 
 
 
 
 
/*
HJ15 求int型正整数在内存中存储时1的个数
题目
题解(465)
讨论(1k)
排行
面经new
简单  通过率：60.65%  时间限制：1秒  空间限制：32M
知识点
位运算
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。
数据范围：保证在 32 位整型数字范围内
输入描述：
 输入一个整数（int类型）
输出描述：
 这个数转换成2进制后，输出1的个数
示例1
输入：
5
复制
输出：
2
复制
示例2
输入：
0
复制
输出：
0
复制
TOP
2022年08月30日 14:57:03 星期二 
2022年08月30日 14:58:36 星期二 （1）*/
 
int main15() {
	int n;
	cin >> n;
	bitset<32> b(n);	//记住32
	cout << b.count();
	return 0;
}
 
 
 
 
 
/*0-1背包问题
问题描述：有一个背包可以装物品的总重量为W，现有N个物品，
每个物品中w[i]，价值v[i]，用背包装物品，能装的最大价值是多少？*/
//dp[i][j],前i个个在限重j最大价值,0(WN),从左到右，从上到下
//对每个物品只有两种状态，放入和不放入，对应得出状态方程如下
//dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])	正上方和斜左上
//目标是获得dp[N][W]
//dp[0][0]=0
int main01() {
	int W = 10,n=5,w[6]={0,5,1,7,6,3},v[6]={0,5,2,6,8,4};
	int dp[6][11] = { 0 };
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			if (j - w[i] >= 0) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]]+v[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
	cout << dp[n][W];
	return 0;
}
 
 
 
 
 
 
 
 
 
/*
HJ16 购物单
题目
题解(196)
讨论(532)
排行
面经new
中等  通过率：23.51%  时间限制：1秒  空间限制：32M
知识点
动态规划
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第ii件物品的价格为v[i]v[i]，重要度为w[i]w[i]，共选中了kk件物品，编号依次为j_1,j_2,...,j_kj 
1
​
 ,j 
2
​
 ,...,j 
k
​
 ，则满意度为：v[j_1]*w[j_1]+v[j_2]*w[j_2]+ … +v[j_k]*w[j_k]v[j 
1
​
 ]∗w[j 
1
​
 ]+v[j 
2
​
 ]∗w[j 
2
​
 ]+…+v[j 
k
​
 ]∗w[j 
k
​
 ]。（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。
输入描述：
输入的第 1 行，为两个正整数N，m，用一个空格隔开：
（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
 
输出描述：
 输出一个正整数，为张强可以获得的最大的满意度。
示例1
输入：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
复制
输出：
2200
复制
示例2
输入：
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0
复制
输出：
130
复制
说明：
由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130       
相似企业真题
TOP
*/
 
#include<iostream>
#include<math.h>
using namespace std;
 
int main16() {
	int n, m, a, b, id, res, last = 0;
	int flag[65] = { 0 };    //标记主附件情况
	cin >> n >> m;
	int w[65][4] = { 0 }, v[65][4] = { 0 };
	int** dp = new int* [m + 1];
	dp[0] = new int[n + 1]{ 0 };
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> id;
		if (!id) {    //主件
			flag[i]++;
			for (int j = 0; j < 4; j++) {
				w[i][j] += a;
				v[i][j] += b * a;
			}
		}
		else {    //附件
			w[id][3] += a;
			v[id][3] += b * a;
			if (v[id][1] == v[id][0]) {
				w[id][1] += a;
				v[id][1] += b * a;
				flag[id]++;
			}
			else {
				w[id][2] += a;
				v[id][2] += b * a;
				flag[id] += 2;
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		dp[i] = new int[n + 1]{ 0 };
		if (flag[i]) {
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k < flag[i]; k++) {
					if (j - w[i][k] >= 0) {
						dp[i][j] = max(dp[i][j], max(dp[last][j], dp[last][j - w[i][k]] + v[i][k]));
					}
					else {
						dp[i][j] = max(dp[i][j], dp[last][j]);
					}
				}
				res = dp[i][j];
			}
			last = i;
		}
	}
	cout << res;
	return 0;
}
 
 
 
 
 
 
/*
HJ17 坐标移动
题目
题解(584)
讨论(1k)
排行
面经new
中等  通过率：29.54%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。
输入：
合法坐标为A(或者D或者W或者S) + 数字（两位以内）
坐标之间以;分隔。
非法坐标点需要进行丢弃。如AA10;  A1A;  $%$;  YAD; 等。
下面是一个简单的例子 如：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
处理过程：
起点（0,0）
+   A10   =  （-10,0）
+   S20   =  (-10,-20)
+   W10  =  (-10,-10)
+   D30  =  (20,-10)
+   x    =  无效
+   A1A   =  无效
+   B10A11   =  无效
+  一个空 不影响
+   A10  =  (10,-10)
结果 （10， -10）
数据范围：每组输入的字符串长度满足 1\le n \le 10000 \1≤n≤10000  ，坐标保证满足 -2^{31} \le x,y \le 2^{31}-1 \−2 
31
 ≤x,y≤2 
31
 −1  ，且数字部分仅含正数
输入描述：
一行字符串
输出描述：
最终坐标，以逗号分隔
示例1
输入：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
复制
输出：
10,-10
复制
示例2
输入：
ABC;AKL;DA1;
复制
输出：
0,0
复制
相似企业真题
TOP
2022年08月30日 17:01:19 星期二
2022年08月30日 17:34:00 星期二 */
void move(string s, int& x, int& y) {
	int step = stoi(s.substr(1));
	switch (s[0]) {
	case 'A':
		x -= step;
		return;
	case 'D':
		x += step;
		return;
	case 'S':
		y -= step;
		return;
	case 'W':
		y += step;
	}
}
int main17() {
	string s;
	int x=0, y=0;
	while (getline(cin, s, ';')) {
		if (s.size()==2 && isdigit(s[1])||s.size() == 3 && isdigit(s[1]) && isdigit(s[2])) {
			move(s, x, y);
		}
	}
	cout << x << ',' << y;
	return 0;
}
 
 
 
 
 
 
 
/*
HJ18 识别有效的IP地址和掩码并进行分类统计
题目
题解(196)
讨论(528)
排行
面经new
较难  通过率：21.24%  时间限制：1秒  空间限制：32M
知识点
字符串
查找
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
请解析IP地址和对应的掩码，进行分类识别。要求按照A/B/C/D/E类地址归类，不合法的地址和掩码单独归类。
所有的IP地址划分为 A,B,C,D,E五类
A类地址从1.0.0.0到126.255.255.255;
B类地址从128.0.0.0到191.255.255.255;
C类地址从192.0.0.0到223.255.255.255;
D类地址从224.0.0.0到239.255.255.255；
E类地址从240.0.0.0到255.255.255.255
私网IP范围是：
从10.0.0.0到10.255.255.255
从172.16.0.0到172.31.255.255
从192.168.0.0到192.168.255.255
子网掩码为二进制下前面是连续的1，然后全是0。（例如：255.255.255.32就是一个非法的掩码）
（注意二进制下全是1或者全是0均为非法子网掩码）
注意：
1. 类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时请忽略
2. 私有IP地址和A,B,C,D,E类地址是不冲突的
输入描述：
多行字符串。每行一个IP地址和掩码，用~隔开。
请参考帖子https://www.nowcoder.com/discuss/276处理循环输入的问题。
输出描述：
统计A、B、C、D、E、错误IP地址或错误掩码、私有IP的个数，之间以空格隔开。
示例1
输入：
10.70.44.68~255.254.255.0
1.0.0.1~255.0.0.0
192.168.0.2~255.255.255.0
19..0.~255.255.255.0
复制
输出：
1 0 1 0 0 2 1
复制
说明：
10.70.44.68~255.254.255.0的子网掩码非法，19..0.~255.255.255.0的IP地址非法，所以错误IP地址或错误掩码的计数为2；
1.0.0.1~255.0.0.0是无误的A类地址；
192.168.0.2~255.255.255.0是无误的C类地址且是私有IP；
所以最终的结果为1 0 1 0 0 2 1        
示例2
输入：
0.201.56.50~255.255.111.255
127.201.56.50~255.255.111.255
复制
输出：
0 0 0 0 0 0 0
复制
说明：
类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时请忽略         
相似企业真题
TOP
2022年08月30日 17:35:20 星期二
2022年08月30日 18:00:48 星期二 
2022年08月30日 19:23:48 星期二 
2022年08月30日 20:30:12 星期二 （78浪费时间）*/
void judgeip(int ip[4], int& a, int& b, int& c, int& d, int& e, int& p) {
	if (ip[0] > 0 && ip[0] < 127) {
		a++;
		if (ip[0] == 10) {
			p++;
		}
	}else if (ip[0] > 127 && ip[0] < 192) {
		b++;
		if (ip[0] == 172&&ip[1]>=16&&ip[1]<32) {
			p++;
		}
	}
	else if (ip[0] >= 192 && ip[0] < 224) {
		c++;
		if (ip[0] == 192 && ip[1]==168) {
			p++;
		}
	}
	else if (ip[0] >= 224 && ip[0] < 240) {
		d++;
	}
	else if (ip[0] >= 240 && ip[0] < 256) {
		e++;
	}
}
int main18() {
	string s;	//一个个数字读入，每次循环里会读8次s
	bool flag1, flag2,flag3;	//标记当下行ip和mask是否正确,以及mask的变号
	int a=0, b=0, c=0, d=0, e=0, r=0, p=0,ip[4],mask[4];
	while (getline(cin, s, '.')) {	//为了区别循环结束，第一个数单独读
		if (s =="0" || s == "127") {
			//类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时请忽略
			getline(cin, s);
			continue;
		}
		flag1 = true,flag2 = true,flag3=true;
		for (int i = 0; i < 4; i++) {	//读ip并判断是否合法
			if (i==3) {	//ip第4个数~结尾
				getline(cin, s, '~');
			}
			else if (i) {
				getline(cin, s, '.');	//读第2 3个数
			}
			if (flag1 && (s.empty() || s[0] == '0' && s.size() > 1)) {
				r++;	//有误以0开头
				flag1 = false;
			}
			else if (flag1) {	//进一步判断数字范围是否合法
				ip[i] = stoi(s);
				if (ip[i] < 0 || ip[i]>255) {
					r++;	//有误
					flag1 = false;
				}
			}
		}
		for (int i = 0; i < 4; i++) {	//读mask并判断是否合法
			if (i == 3) {	//第4个数
				getline(cin, s);
			}
			else{
				getline(cin, s, '.');	//读第2 3个数
			}
			if (flag2 && (s.empty() || s[0] == '0' && s.size() > 1)) {
				r++;	//有误以0开头
				flag2 = false;
			}
			else if (flag2) {	//进一步判断数字范围是否合法
				mask[i] = stoi(s);
				if (!mask[0]||!flag3 && mask[i]) {	//开头为0或末尾0段出现非0有误
					r++;	//有误
					flag2 = false;
				}
				else if (flag3 &&mask[i] != 255) {	//变号中间段(包括0)
					if (mask[i]>=0&&mask[i]<=255&&(!mask[i]||log2(~mask[i] + 1) == int(log2(~mask[i] + 1)))) {
						flag3 = false;	//中间段无误，变号
					}
					else {
						r++;	//中间段非法
						flag2 = false;
					}
				}
				else {	//开头1段
					if (flag3&&mask[i] != 255) {
						r++;	//开头1段非1非法非法
						flag2 = false;
					}
				}
			}
		}
		if (flag3) {
			//r++;
			flag2 = false;	//掩码全1
		}else if (flag1&&flag2) {	//合法判断ip类型
			judgeip(ip, a, b, c, d, e, p);
		}
	}
	cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << ' ' << r << ' ' << p;
	return 0;
}
 
 
 
 
 
 
 
 
 
 
 
/*
HJ19 简单错误记录
题目
题解(229)
讨论(676)
排行
面经new
较难  通过率：23.49%  时间限制：1秒  空间限制：32M
知识点
字符串
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
开发一个简单错误记录功能小模块，能够记录出错的代码所在的文件名称和行号。
处理：
1、 记录最多8条错误记录，循环记录，最后只用输出最后出现的八条错误记录。对相同的错误记录只记录一条，但是错误计数增加。最后一个斜杠后面的带后缀名的部分（保留最后16位）和行号完全匹配的记录才做算是“相同”的错误记录。
2、 超过16个字符的文件名称，只记录文件的最后有效16个字符；
3、 输入的文件可能带路径，记录文件名称不能带路径。也就是说，哪怕不同路径下的文件，如果它们的名字的后16个字符相同，也被视为相同的错误记录
4、循环记录时，只以第一次出现的顺序为准，后面重复的不会更新它的出现时间，仍以第一次为准
数据范围：错误记录数量满足 1 \le n \le 100 \1≤n≤100  ，每条记录长度满足 1 \le len \le 100 \1≤len≤100 
输入描述：
每组只包含一个测试用例。一个测试用例包含一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。
输出描述：
将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开，如：
示例1
输入：
D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645
E:\je\rzuwnjvnuz 633
C:\km\tgjwpb\gy\atl 637
F:\weioj\hadd\connsh\rwyfvzsopsuiqjnr 647
E:\ns\mfwj\wqkoki\eez 648
D:\cfmwafhhgeyawnool 649
E:\czt\opwip\osnll\c 637
G:\nt\f 633
F:\fop\ywzqaop 631
F:\yay\jc\ywzqaop 631
D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645
复制
输出：
rzuwnjvnuz 633 1
atl 637 1
rwyfvzsopsuiqjnr 647 1
eez 648 1
fmwafhhgeyawnool 649 1
c 637 1
f 633 1
ywzqaop 631 2
复制
说明：
由于D:\cfmwafhhgeyawnool 649的文件名长度超过了16个字符，达到了17，所以第一个字符'c'应该被忽略。
记录F:\fop\ywzqaop 631和F:\yay\jc\ywzqaop 631由于文件名和行号相同，因此被视为同一个错误记录，哪怕它们的路径是不同的。
由于循环记录时，只以第一次出现的顺序为准，后面重复的不会更新它的出现时间，仍以第一次为准，所以D:\zwtymj\xccb\ljj\cqzlyaszjvlsjmkwoqijggmybr 645不会被记录。  
相似企业真题
TOP
2022年08月30日 20:30:53 星期二 
2022年08月30日 21:20:25 星期二 (50)*/
struct file {
	string name;
	int line;
	int n;
	file(string s,int l,int n0):name(s),line(l),n(n0){}
};
int main19() {
	vector<file> v;
	string s;
	int l;
	bool flag;
	while (cin>>s>>l)
	{
		flag = true;
		s = s.substr(max(int(s.find_last_of('\\')) + 1,int(s.size()) - 16));	//取文件名,注意原本是unsigned long long,有负数需要2个都类型转换
		for (auto &it : v) {
			if (it.name == s&&it.line==l) {
				it.n++;
				flag = false;
				break;
			}
		}
		if(flag)
			v.push_back(file(s, l, 1));
	}
	for (int i = max(int(v.size()) - 8,0); i < v.size(); i++) {
		cout << v[i].name << ' ' << v[i].line << ' ' << v[i].n << endl;
	}
	return 0;
}
 
 
 
/*
HJ20 密码验证合格程序
题目
题解(364)
讨论(811)
排行
面经new
中等  通过率：33.56%  时间限制：1秒  空间限制：32M
知识点
字符串
数组
模拟
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
密码要求:
1.长度超过8位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有长度大于2的包含公共元素的子串重复 （注：其他符号不含空格或换行）
数据范围：输入的字符串长度满足 1 \le n \le 100 \1≤n≤100 
输入描述：
一组字符串。
输出描述：
如果符合要求输出：OK，否则输出NG
示例1
输入：
021Abc9000
021Abc9Abc1
021ABC9000
021$bc9000
复制
输出：
OK
NG
NG
OK
复制
相似企业真题
TOP
2022年08月30日 21:22:03 星期二
2022年08月30日 21:41:02 星期二 （19）*/
bool judgepass(string s) {
	if (s.size() < 8) {
		return false;
	}
	bool u=0, l=0, d=0, o=0;
	int n = 0;
	for (auto c : s) {
		if (isupper(c)) {
			if (!u) {
				u = 1;
				n++;
				if (n >= 3) {
					break;
				}
			}
		}else if (islower(c)) {
			if (!l) {
				l = 1;
				n++;
				if (n >= 3) {
					break;
				}
			}
		}
		else if ( isdigit(c)) {
			if (!d) {
				d = 1;
				n++;
				if (n >= 3) {
					break;
				}
			}
		}
		else if (!o) {
			o = 1;
			n++;
			if (n >= 3) {
				break;
			}
		}
	}
	if (n < 3) {
		return false;
	}
	for (int i = 0; i < s.size() - 3; i++) {	//子串1起始下标
		if (s.find(s.substr(i,3),i+1) != string::npos) {	//注意i+1
			return false;	//找到重复子串。
		}
	}
	return true;
}
int main20() {
	string s;
	while (cin >> s) {
		if (judgepass(s)) {
			cout << "OK" << endl;
		}
		else {
			cout << "NG" << endl;
		}
	}
	return 0;
}
 
 
 
/*
HJ21 简单密码
题目
题解(419)
讨论(870)
排行
面经new
简单  通过率：44.99%  时间限制：1秒  空间限制：32M
知识点
字符串
模拟
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
现在有一种密码变换算法。
九键手机键盘上的数字与字母的对应： 1--1， abc--2, def--3, ghi--4, jkl--5, mno--6, pqrs--7, tuv--8 wxyz--9, 0--0，把密码中出现的小写字母都变成九键键盘对应的数字，如：a 变成 2，x 变成 9.
而密码中出现的大写字母则变成小写之后往后移一位，如：X ，先变成小写，再往后移一位，变成了 y ，例外：Z 往后移是 a 。
数字和其它的符号都不做变换。
数据范围： 输入的字符串长度满足 1 \le n \le 100 \1≤n≤100 
输入描述：
输入一组密码，长度不超过100个字符。
输出描述：
输出密码变换后的字符串
示例1
输入：
YUANzhi1987
复制
输出：
zvbo9441987
复制
相似企业真题
TOP
2022年08月30日 21:41:22 星期二 
2022年08月30日 21:52:08 星期二 （11）*/
 
 
 
int main21() {
	string s;
	cin >> s;
	for (auto& c : s) {
		if (islower(c)) {
			if (c == 'z') {
				c = '9';
			}else if (c < 's') {
				c = (c - 'a') / 3 + '2';
			}
			else {
				c= (c - 'a'+1) / 3 + '2';
			}
		}
		else if (isupper(c)) {
			if (c == 'Z') {
				c == 'a';
			}else
				c = tolower(c)+1;
		}
	}
	cout << s;
	return 0;
}
 
 
 
 
 
 
 
 
/*
HJ22 汽水瓶
题目
题解(431)
讨论(1k)
排行
面经new
简单  通过率：30.18%  时间限制：1秒  空间限制：32M
知识点
数学
模拟
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。
小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。
数据范围：输入的正整数满足 1 \le n \le 100 \1≤n≤100 
注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。
输入描述：
输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（ 1<=n<=100 ），表示小张手上的空汽水瓶数。n=0 表示输入结束，你的程序不应当处理这一行。
输出描述：
对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。
示例1
输入：
3
10
81
0
复制
输出：
1
5
40
复制
说明：
样例 1 解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换
样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板    
相似企业真题
TOP
2022年08月30日 21:55:51 星期二 
2022年08月30日 21:58:47 星期二 （3）
*/
 
int main22() {
	int n=1;
	while (n) {
		cin >> n;
		if(n)
			cout << n / 2 << endl;
	}
	return 0;
}
 
 
 
 
/*
HJ23 删除字符串中出现次数最少的字符
题目
题解(429)
讨论(950)
排行
面经new
简单  通过率：38.25%  时间限制：1秒  空间限制：32M
知识点
字符串
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
数据范围：输入的字符串长度满足 1 \le n \le 20 \1≤n≤20  ，保证输入的字符串中仅出现小写字母
输入描述：
字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。
输出描述：
删除字符串中出现次数最少的字符后的字符串。
示例1
输入：
aabcddd
复制
输出：
aaddd
复制
相似企业真题
TOP
2022年08月30日 23:28:32 星期二
2022年08月30日 23:35:37 星期二（7） */
 
 
 
int main23() {
	string s;
	cin >> s;
	int num[26] = { 0 },min0=0x3f3f3f3f;
	for (auto c : s) {
		num[c - 'a']++;
	}
	for (int i = 0; i < 26; i++) {
		if(num[i])
			min0 = min(min0, num[i]);
	}
	string s0 = "";
	for (int i = 0; i < 26; i++) {
		if (min0 == num[i]) {
			s0 += (i+'a');
		}
	}
	for (auto c : s) {
		if (s0.find(c) == string::npos) {
			cout << c;
		}
	}
	return 0;
}
 
 
 
 
/*
HJ24 合唱队
题目
题解(158)
讨论(343)
排行
面经new
中等  通过率：28.89%  时间限制：1秒  空间限制：32M
知识点
动态规划
队列
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
设KK位同学从左到右依次编号为 1，2…，K ，他们的身高分别为T_1,T_2,…,T_KT 
1
​
 ,T 
2
​
 ,…,T 
K
​
  ，若存在i(1\leq i\leq K)i(1≤i≤K) 使得T_1<T_2<......<T_{i-1}<T_iT 
1
​
 <T 
2
​
 <......<T 
i−1
​
 <T 
i
​
  且 T_i>T_{i+1}>......>T_KT 
i
​
 >T 
i+1
​
 >......>T 
K
​
 ，则称这KK名同学排成了合唱队形。
通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等
数据范围： 1 \le n \le 3000 \1≤n≤3000 
输入描述：
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开
输出描述：
最少需要几位同学出列
示例1
输入：
8
186 186 150 200 160 130 197 200
复制
输出：
4
复制
说明：
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130           
相似企业真题
TOP
2022年08月30日 23:37:07 星期二
2022年08月31日 00:27:47 星期三（50） */
//梅花桩
int main24() {
	int n,max0=0;	
	cin >> n;
	int* h = new int[n];
	//dp[i]:一从左边向右递增为例，表示前i个包括它自己的递增序列最长可有多少人，从头双层循环获得
	int* dpl = new int[n];
	int* dpr = new int[n];
 
	//l[i]:表示前i个递增序列（可不包括自己）最长可有多少人，从头双层循环获得
	int* l = new int[n];	
	int* r = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	//左边,dpl过程从头开始填，
	for (int i = 0; i <n; i++) {
		dpl[i] = 1;	//初始为1(起码它本身)
		for (int j = 0; j < i; j++) {
			if (h[j] < h[i]) {
				dpl[i] = max(dpl[i], dpl[j] + 1);
			}
		}
	}
	//右边
	for (int i = n-1; i >=0; i--) {
		dpr[i] = 1;	//初始为1(起码它本身)
		for (int j = i+1; j < n; j++) {
			if (h[i] > h[j]) {
				dpr[i] = max(dpr[i], dpr[j] + 1);
			}
		}
	}
	max0 = 0;
	for (int i = 0; i < n; i++) {	//i为中间人
		max0 = max(max0, l[i] + r[i]);	//因为第i人左右两边都重复计算了，所以最终得--
	}
	cout << n - (max0 - 1);	//减去重复计算的人
	return 0;
}
 
 
 
 
/*
HJ25 数据分类处理
题目
题解(172)
讨论(406)
排行
面经new
较难  通过率：26.15%  时间限制：1秒  空间限制：32M
知识点
排序
模拟
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。
采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。
数据范围：1 \le I,R \le 100 \1≤I,R≤100  ，输入的整数大小满足 0 \le val \le 2^{31}-1\0≤val≤2 
31
 −1 
输入描述：
一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~(2^31)-1，序列个数不限
输出描述：
从R依次中取出R<i>，对I进行处理，找到满足条件的I： 
I整数对应的数字需要连续包含R<i>对应的数字。比如R<i>为23，I为231，那么I包含了R<i>，条件满足 。 
按R<i>从小到大的顺序:
(1)先输出R<i>； 
(2)再输出满足条件的I的个数； 
(3)然后输出满足条件的I在I序列中的位置索引(从0开始)； 
(4)最后再输出I。 
附加条件： 
(1)R<i>需要从小到大排序。相同的R<i>只需要输出索引小的以及满足条件的I，索引大的需要过滤掉 
(2)如果没有满足条件的I，对应的R<i>不用输出 
(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)
 
序列I：15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123（第一个15表明后续有15个整数） 
序列R：5,6,3,6,3,0（第一个5表明后续有5个整数） 
输出：30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786
说明：
30----后续有30个整数
3----从小到大排序，第一个R<i>为0，但没有满足条件的I，不输出0，而下一个R<i>是3
6--- 存在6个包含3的I 
0--- 123所在的原序号为0 
123--- 123包含3，满足条件 
示例1
输入：
15 123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123
5 6 3 6 3 0
复制
输出：
30 3 6 0 123 3 453 7 3 9 453456 13 453 14 123 6 7 1 456 2 786 4 46 8 665 9 453456 11 456 12 786
复制
说明：
将序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）排序去重后，可得0,3,6。
序列I没有包含0的元素。
序列I中包含3的元素有：I[0]的值为123、I[3]的值为453、I[7]的值为3、I[9]的值为453456、I[13]的值为453、I[14]的值为123。
序列I中包含6的元素有：I[1]的值为456、I[2]的值为786、I[4]的值为46、I[8]的值为665、I[9]的值为453456、I[11]的值为456、I[12]的值为786。
最后按题目要求的格式进行输出即可。     
相似企业真题
TOP
2022年08月31日 12:45:05 星期三 
2022年08月31日 13:29:38 星期三 （45）*/
 
int main25() {
	int n1, n2,num;
	cin >> n1;
	string* arr = new string[n1];
	for (int i = 0; i < n1; i++) {
		cin >> arr[i];
	}
	cin >> n2;
	set<int> s0;
	while (n2--)
	{
		cin >> num;
		s0.insert(num);	//int才有排序去重
	}
	int size = s0.size(),j=0,sum=0;	//j标识set下标,sum为数字个数
	vector<string> res;
	vector<string>* value = new vector<string>[size];	//二维数组，size行，每行为动态数组vector
	vector<int>* i = new vector<int>[size];	//二维数组，size行，每行为动态数组vector
	for (auto it : s0) {
		res.push_back(to_string(it));
		for (int k = 0; k < n1; k++) {
			if (arr[k].find(res[j]) != string::npos) {
				value[j].push_back(arr[k]);
				i[j].push_back(k);
			}
		}
		j++;
	}
	string s3 = "";	//结果字符串
	for (int j = 0; j < size; j++) {
		if (!value[j].empty()) {
			sum = sum + 2 + 2 * value[j].size();
			s3 = s3 +" "+ res[j] + " "+to_string(value[j].size());
			for (int k = 0; k < value[j].size(); k++) {
				s3 = s3+ " " + to_string(i[j][k]) + " " + value[j][k] ;
			}
		}
	}
	cout << sum << s3;
	return 0;
}
 
 
 
 
 
 
 
/*
HJ26 字符串排序
题目
题解(317)
讨论(703)
排行
面经new
中等  通过率：41.60%  时间限制：1秒  空间限制：32M
知识点
字符串
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
编写一个程序，将输入字符串中的字符按如下规则排序。
规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type 输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA 输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e 输出： Be?y
数据范围：输入的字符串长度满足 1 \le n \le 1000 \1≤n≤1000 
输入描述：
输入字符串
输出描述：
输出字符串
示例1
输入：
A Famous Saying: Much Ado About Nothing (2012/8).
复制
输出：
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).
复制
相似企业真题
TOP
2022年08月31日 13:30:09 星期三
2022年08月31日 13:43:43 星期三 (13)*/
bool cmp26(char a, char b) {
	return tolower(a) < tolower(b);
}
 
int main26() {
	string s,s1="";
	getline(cin, s);
	for (auto it : s) {
		if (isalpha(it)) {
			s1 += it;
		}
	}
	stable_sort(s1.begin(), s1.end(), cmp26);	//记住
	int j = 0;	//s1下标
	for (auto &it : s) {
		if (isalpha(it)) {
			it = s1[j++];
		}
	}
	cout << s;
	return 0;
}
 
 
 
 
/*
HJ27 查找兄弟单词
题目
题解(334)
讨论(642)
排行
面经new
中等  通过率：24.03%  时间限制：1秒  空间限制：32M
知识点
查找
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
定义一个单词的“兄弟单词”为：交换该单词字母顺序（注：可以交换任意次），而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如： ab 和 ba 是兄弟单词。 ab 和 ab 则不是兄弟单词。
现在给定你 n 个单词，另外再给你一个单词 x ，让你寻找 x 的兄弟单词里，按字典序排列后的第 k 个单词是什么？
注意：字典中可能有重复单词。
数据范围：1 \le n \le 1000 \1≤n≤1000 ，输入的字符串长度满足 1 \le len(str) \le 10 \1≤len(str)≤10  ， 1 \le k < n \1≤k<n 
输入描述：
输入只有一行。 先输入字典中单词的个数n，再输入n个单词作为字典单词。 然后输入一个单词x 最后后输入一个整数k
输出描述：
第一行输出查找到x的兄弟单词的个数m 第二行输出查找到的按照字典顺序排序后的第k个兄弟单词，没有符合第k个的话则不用输出。
示例1
输入：
3 abc bca cab abc 1
复制
输出：
2
bca
复制
示例2
输入：
6 cab ad abcd cba abc bca abc 1
复制
输出：
3
bca
复制
说明：
abc的兄弟单词有cab cba bca，所以输出3
经字典序排列后，变为bca cab cba，所以第1个字典序兄弟单词为bca         
相似企业真题
TOP
2022年08月31日 13:44:03 星期三
2022年08月31日 14:02:37 星期三 (17）*/
 
 
 
int main27() {
	int n,n2=0,k,m=0;
	cin >> n;
	string* arr = new string[n];
	string* arr2 = new string[n];
	string s, s2;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		arr2[i] = arr[i];
		sort(arr2[i].begin(), arr2[i].end());
	}
	cin >> s>>k;
	s2 = s;
	sort(s2.begin(), s2.end());
	for (int i = 0; i < n; i++) {
		if (s2 == arr2[i] && s != arr[i]) {
			m++;
		}
		else {
			arr[i] = "z";
		}
	}
	sort(arr, arr + n);
	cout << m << endl;
	if(k<=m)
		cout<< arr[k - 1];
	return 0;
}
 
 
 
 
 
/*
HJ28 素数伴侣
题目
题解(15)
讨论(153)
排行
面经new
困难  通过率：26.02%  时间限制：1秒  空间限制：32M
知识点
查找
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
数据范围： 1 \le n \le 100 \1≤n≤100  ，输入的数据大小满足 2 \le val \le 30000 \2≤val≤30000 
输入描述：
输入说明
1 输入一个正偶数 n
2 输入 n 个整数
输出描述：
求得的“最佳方案”组成“素数伴侣”的对数。
示例1
输入：
4
2 5 6 13
复制
输出：
2
复制
示例2
输入：
2
3 6
复制
输出：
0
复制
相似企业真题
TOP
试下用存暴力（全排列搞？）
2022年08月31日 14:37:02 星期三 */
//超时
bool judge28(int num) {
	for (int i = 2; i <= sqrt(num); i++) {
		if (!(num % i)) {
			return false;
		}
	}
	return true;
}
int main28() {
	int n, num, n2, max0 = 0;;
	cin >> n;
	if (n == 1) {
		cout << 0;
		return 0;
	}
	vector<int> arr1, arr2;	//存奇数偶数
	while (n--) {
		cin >> num;
		if (num % 2) {
			arr1.push_back(num);	//奇数
		}
		else
			arr2.push_back(num);
	}
	if (arr1.empty()||arr2.empty()) {
		cout << 0;
		return 0;
	}
	if (arr1.size() > arr2.size()) {
		swap(arr1, arr2);		//arr2大，全排列
	}
	do {
		n2 = 0;	//当前排列对数初始为0
		for (int i = 0; i < arr1.size(); i++) {
			if (judge28(arr1[i] + arr2[i])) {
				n2++;
			}
		}
		max0 = max(n2, max0);
		if (max0 == arr1.size()) {
			break;
		}
	} while (next_permutation(arr2.begin(), arr2.end()));
	cout << max0;
	return 0;
}
 
 
 
 
 
 
/*
HJ29 字符串加解密
题目
题解(273)
讨论(564)
排行
面经new
中等  通过率：30.06%  时间限制：1秒  空间限制：32M
知识点
字符串
模拟
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
对输入的字符串进行加解密，并输出。
加密方法为：
当内容是英文字母时则用该英文字母的后一个字母替换，同时字母变换大小写,如字母a时则替换为B；字母Z时则替换为a；
当内容是数字时则把该数字加1，如0替换1，1替换2，9替换0；
其他字符不做变化。
解密方法为加密的逆过程。
数据范围：输入的两个字符串长度满足 1 \le n \le 1000 \1≤n≤1000  ，保证输入的字符串都是只由大小写字母或者数字组成
输入描述：
第一行输入一串要加密的密码
第二行输入一串加过密的密码
输出描述：
第一行输出加密后的字符
第二行输出解密后的字符
示例1
输入：
abcdefg
BCDEFGH
复制
输出：
BCDEFGH
abcdefg
复制
相似企业真题
TOP
2022年08月31日 14:59:25 星期三 
2022年08月31日 15:04:22 星期三 */
 
int main29() {
	string s1, s2;
	cin >> s1 >> s2;
	for (auto& c : s1) {
		if (islower(c)) {
			c = ((c - 'a') + 1) % 26 + 'A';
		}else if (isupper(c)) {
			c = ((c - 'A') + 1) % 26 + 'a';
		}else if (isdigit(c)) {
			c = ((c - '0') + 1) % 10 + '0';
		}
	}
	for (auto& c : s2) {
		if (islower(c)) {
			c = ((c - 'a') - 1) % 26 + 'A';
		}
		else if (isupper(c)) {
			c = ((c - 'A') - 1) % 26 + 'a';
		}
		else if (isdigit(c)) {
			c = ((c - '0') - 1) % 10 + '0';
		}
	}
	cout << s1 << endl << s2;
	return 0;
}
 
 
 
 
 
/*
HJ30 字符串合并处理
题目
题解(192)
讨论(426)
排行
面经new
较难  通过率：28.22%  时间限制：1秒  空间限制：32M
知识点
字符串
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
按照指定规则对输入的字符串进行处理。
详细描述：
第一步：将输入的两个字符串str1和str2进行前后合并。如给定字符串 "dec" 和字符串 "fab" ， 合并后生成的字符串为 "decfab"
第二步：对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标的意思是字符在字符串中的位置。注意排序后在新串中仍需要保持原来的奇偶性。例如刚刚得到的字符串“decfab”，分别对下标为偶数的字符'd'、'c'、'a'和下标为奇数的字符'e'、'f'、'b'进行排序（生成 'a'、'c'、'd' 和 'b' 、'e' 、'f'），再依次分别放回原串中的偶数位和奇数位，新字符串变为“abcedf”
第三步：对排序后的字符串中的'0'~'9'、'A'~'F'和'a'~'f'字符，需要进行转换操作。
转换规则如下：
对以上需要进行转换的字符所代表的十六进制用二进制表示并倒序，然后再转换成对应的十六进制大写字符（注：字符 a~f 的十六进制对应十进制的10~15，大写同理）。
如字符 '4'，其二进制为 0100 ，则翻转后为 0010 ，也就是 2 。转换后的字符为 '2'。
如字符 ‘7’，其二进制为 0111 ，则翻转后为 1110 ，对应的十进制是14，转换为十六进制的大写字母为 'E'。
如字符 'C'，代表的十进制是 12 ，其二进制为 1100 ，则翻转后为 0011，也就是3。转换后的字符是 '3'。
根据这个转换规则，由第二步生成的字符串 “abcedf” 转换后会生成字符串 "5D37BF"。
数据范围：输入的字符串长度满足 1 \le n \le 100 \1≤n≤100 
输入描述：
样例输入两个字符串，用空格隔开。
输出描述：
输出转化后的结果。
示例1
输入：
dec fab
复制
输出：
5D37BF
复制
示例2
输入：
ab CD
复制
输出：
3B5D
复制
说明：
合并后为abCD，按奇数位和偶数位排序后是CDab（请注意要按ascii码进行排序，所以C在a前面，D在b前面），转换后为3B5D          
示例3
输入：
123 15
复制
输出：
88C4A
复制
相似企业真题
TOP
用投机手算
2022年08月31日 15:04:42 星期三 
2022年08月31日 15:27:43 星期三 （23）
*/
 
int main30() {
	string s1, s2,s3="";
	cin >> s1 >> s2;
	s1 += s2;
	int i = 0;
	string res = "084C2A6E195D3B7F";
	s2 = "";
	for(auto c:s1){
		if (i % 2) {
			s3 += c;	//奇数串
		}
		else {
			s2 += c;
		}
		i++;
	}
	sort(s2.begin(), s2.end());
	sort(s3.begin(), s3.end());
	s1 = "";
	for (i = 0; i < s2.size() && i < s3.size(); i++) {
		s1 =s1+ s2[i] + s3[i];
	}
	if (s2.size()!=s3.size()) {
		s1 += s2[i];
	}
	for (auto& c : s1) {
		if (isdigit(c)) {
			c = res[c - '0'];
		}
		else if (c >= 'a' && c <= 'f') {
			c = res[c - 'a' + 10];
		}
		else if (c >= 'A' && c <= 'F') {
			c = res[c - 'A' + 10];
		}
	}
	cout << s1;
	return 0;
}
 
 
 
 
 
 
/*
HJ31 单词倒排
题目
题解(429)
讨论(812)
排行
面经new
简单  通过率：28.43%  时间限制：1秒  空间限制：32M
知识点
排序
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
对字符串中的所有单词进行倒排。
说明：
1、构成单词的字符只有26个大写或小写英文字母；
2、非构成单词的字符均视为单词间隔符；
3、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
4、每个单词最长20个字母；
数据范围：字符串长度满足 1 \le n \le 10000 \1≤n≤10000 
输入描述：
输入一行，表示用来倒排的句子
输出描述：
输出句子的倒排结果
示例1
输入：
I am a student
复制
输出：
student a am I
复制
示例2
输入：
$bo*y gi!r#l
复制
输出：
l r gi y bo
复制
相似企业真题
TOP
2022年08月31日 15:28:12 星期三
2022年08月31日 15:34:18 星期三（6） */
 
int main31() {
	string s,s1;
	getline(cin, s);
	for (auto& c : s) {
		if (!isalpha(c)) {
			c = ' ';
		}
	}
	istringstream input(s);
	vector<string> v;
	while (input >> s1) {
		v.push_back(s1);
	}
	reverse(v.begin(), v.end());
	for (auto it : v) {
		cout << it<<' ';
	}
	return 0;
}
 
 
 
 
/*
HJ32 密码截取
题目
题解(233)
讨论(406)
排行
面经new
中等  通过率：33.39%  时间限制：1秒  空间限制：32M
知识点
字符串
动态规划
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？
数据范围：字符串长度满足 1 \le n \le 2500 \1≤n≤2500 
输入描述：
输入一个字符串（字符串的长度不超过2500）
输出描述：
返回有效密码串的最大长度
示例1
输入：
ABBA
复制
输出：
4
复制
示例2
输入：
ABBBA
复制
输出：
5
复制
示例3
输入：
12HHHHA
复制
输出：
4
复制
相似企业真题
TOP
2022年08月31日 15:34:42 星期三 
2022年08月31日 15:49:34 星期三 */
 
//用bool dp[i][j]上三角从i到j是否回文，对角先填，在从下到上，从左到右
//本身和双同为 1,对角2行可判断，不断更新maxres
int main32(){
	string s;
	cin >> s;
	int res = 1;	//最短长度1单字符
	int n = s.size();
	bool** dp = new bool* [n];
	for (int i = 0; i < n; i++) {
		dp[i] = new bool[n]{ 1 };	//上三角，单字符为1
		if (i != n - 1 && s[i] == s[i + 1]) {
			dp[i][i+1] = 1;	//双同顺带写上
			if (res <2) {
				res = 2;	//更新res
			}
		}
	}
	for (int i = n - 2; i >= 0; i--) {
		for (int j = i+2; j < n; j++) {
			if (dp[i + 1][j - 1] && s[i] == s[j]) {
				dp[i][j] = 1;	//中间回文，2头相同回文
				if (res < j - i + 1) {
					res = j - i + 1;	//更新res
				}
			}
		}
	}
	cout << res;
	return 0;
}
 
 
 
 
 
 
 
/*
HJ33 整数与IP地址间的转换
题目
题解(251)
讨论(448)
排行
面经new
中等  通过率：36.78%  时间限制：1秒  空间限制：32M
知识点
字符串
模拟
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
原理：ip地址的每段可以看成是一个0-255的整数，把每段拆分成一个二进制形式组合起来，然后把这个二进制数转变成
一个长整数。
举例：一个ip地址为10.0.3.193
每段数字             相对应的二进制数
10                   00001010
0                    00000000
3                    00000011
193                  11000001
组合起来即为：00001010 00000000 00000011 11000001,转换为10进制数就是：167773121，即该IP地址转换后的数字就是它了。
数据范围：保证输入的是合法的 IP 序列
输入描述：
输入 
1 输入IP地址
2 输入10进制型的IP地址
输出描述：
输出
1 输出转换成10进制的IP地址
2 输出转换后的IP地址
示例1
输入：
10.0.3.193
167969729
复制
输出：
167773121
10.3.3.193
复制
相似企业真题
TOP
2022年08月31日 15:49:51 星期三 
2022年08月31日 16:02:37 星期三 */
 
 
int main33() {
	int a, b, c, d,e;
	scanf_s("%d.%d.%d.%d", &a, &b, &c, &d);
	long long res = d + 256 * (c + 256 * (b + 256 * a));
	cout<<res<<endl;
	cin >> e;
	long f = 256 * 256 * 256;
	while (1) {
		cout << e / f;
		e %= f;
		f /= 256;
		if (f) {
			cout << '.';
		}
		else {
			break;
		}
	}
	return 0;
}
 
 
 
/*
HJ34 图片整理
题目
题解(274)
讨论(465)
排行
面经new
简单  通过率：53.83%  时间限制：1秒  空间限制：32M
知识点
字符串
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
Lily上课时使用字母数字图片教小朋友们学习英语单词，每次都需要把这些图片按照大小（ASCII码值从小到大）排列收好。请大家给Lily帮忙，通过代码解决。
Lily使用的图片使用字符"A"到"Z"、"a"到"z"、"0"到"9"表示。
数据范围：每组输入的字符串长度满足 1 \le n \le 1000 \1≤n≤1000 
输入描述：
一行，一个字符串，字符串中的每个字符表示一张Lily使用的图片。
输出描述：
Lily的所有图片按照从小到大的顺序输出
示例1
输入：
Ihave1nose2hands10fingers
复制
输出：
0112Iaadeeefghhinnnorsssv
复制
相似企业真题
TOP
2022年08月31日 16:04:25 星期三 
2022年08月31日 16:05:13 星期三 （1）*/
 
 
int main34() {
	string s;
	cin >> s;
	sort(s.begin(), s.end());
	cout << s;
	return 0;
}
 
 
 
 
 
/*
HJ35 蛇形矩阵
题目
题解(374)
讨论(684)
排行
面经new
简单  通过率：49.91%  时间限制：1秒  空间限制：32M
知识点
数组
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。
例如，当输入5时，应该输出的三角形为：
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11
输入描述：
输入正整数N（N不大于100）
输出描述：
输出一个N行的蛇形矩阵。
示例1
输入：
4
复制
输出：
1 3 6 10
2 5 9
4 8
7
复制
相似企业真题
TOP
*/
 
 
 
int main35() {
	int n,d;
	cin >> n;
	for (int i = 0; i < n; i++) {
		d= (1 + i) * i / 2 + 1;
		cout << d;
		for (int j = i+1; j < n; j++) {
			d += (j + 1);
			cout << " " << d;
		}
		cout << endl;
	}
	return 0;
}
 
 
/*
HJ36 字符串加密
题目
题解(275)
讨论(572)
排行
面经new
中等  通过率：45.59%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
有一种技巧可以对数据进行加密，它使用一个单词作为它的密匙。下面是它的工作原理：首先，选择一个单词作为密匙，如TRAILBLAZERS。如果单词中包含有重复的字母，只保留第1个，将所得结果作为新字母表开头，并将新建立的字母表中未出现的字母按照正常字母表顺序加入新字母表。如下所示：
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
T R A I L B Z E S C D F G H J K M N O P Q U V W X Y (实际需建立小写字母的字母表，此字母表仅为方便演示）
上面其他用字母表中剩余的字母填充完整。在对信息进行加密时，信息中的每个字母被固定于顶上那行，并用下面那行的对应字母一一取代原文的字母(字母字符的大小写状态应该保留)。因此，使用这个密匙， Attack AT DAWN (黎明时攻击)就会被加密为Tpptad TP ITVH。
请实现下述接口，通过指定的密匙和明文得到密文。
数据范围：1 \le n \le 100 \1≤n≤100  ，保证输入的字符串中仅包含小写字母
输入描述：
先输入key和要加密的字符串
输出描述：
返回加密后的字符串
示例1
输入：
nihao
ni
复制
输出：
le
复制
相似企业真题
TOP
2022年08月31日 16:25:28 星期三 
2022年08月31日 16:39:49 星期三 （14）*/
 
int main36() {
	string s, s1,s2="";
	int num[26];
	cin >> s >> s1;
	set<char> set0;
	for (auto c : s) {
		if (set0.insert(c).second) {
			s2 += c;
		}
	}
	for (char c = 'a'; c <= 'z'; c++) {
		if (set0.insert(c).second) {
			s2 += c;
		}
	}
	for (int i = 0; i < 26; i++) {
		num[i] = s2[i] - 'a'-i;
	}
	for (auto& c : s1) {
		c += num[tolower(c) - 'a'];
	}
	cout << s1;
	return 0;
}
 
 
 
 
 
 
 
/*
HJ37 统计每个月兔子的总数
题目
题解(313)
讨论(666)
排行
面经new
简单  通过率：46.83%  时间限制：1秒  空间限制：32M
知识点
查找
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
数据范围：输入满足 1 \le n \le 31 \1≤n≤31 
输入描述：
输入一个int型整数表示第n个月
输出描述：
输出对应的兔子总数
示例1
输入：
3
复制
输出：
2
复制
相似企业真题
TOP
递归，2数组记录
2022年08月31日 16:40:12 星期三
2022年08月31日 16:47:25 星期三 （7）*/
 
 
 
int main37() {
	int n;
	cin >> n;
	if (n < 3) {
		cout << 1;
		return 0;
	}
	int* mother = new int[n] {0};	//第i+1月时母兔个数
	int* child = new int[n] {1};	//当月出生小兔
	for (int i = 2; i < n; i++) {
		mother[i] = mother[i - 1] + child[i - 2];	//2个月前的小兔成熟了，增加到当月母兔
		child[i] = mother[i];	//当月出生小兔
	}
	cout << mother[n - 1] + child[n - 2] + child[n - 1];	//当前兔子数包括当下母兔+小兔（本月和上个月）
	return 0;
}
 
 
 
 
 
 
/*
HJ38 求小球落地5次后所经历的路程和第5次反弹的高度
题目
题解(194)
讨论(395)
排行
面经new
中等  通过率：43.53%  时间限制：1秒  空间限制：32M
知识点
模拟
思维
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
假设一个球从任意高度自由落下，每次落地后反跳回原高度的一半; 再落下, 求它在第5次落地时，共经历多少米?第5次反弹多高？
数据范围：输入的小球初始高度满足 1 \le n \le 1000 \1≤n≤1000  ，且保证是一个整数
输入描述：
输入起始高度，int型
输出描述：
分别输出第5次落地时，共经过多少米以及第5次反弹多高。
注意：你可以认为你输出保留六位或以上小数的结果可以通过此题。
示例1
输入：
1
复制
输出：
2.875
0.03125
复制
相似企业真题
TOP
*/
 
 
 
int main38() {
	int h;
	cin >> h;
	cout << 23.0 / 8 * h << endl << 1.0 / 32 * h;
	return 0;
}
 
 
 
 
/*
HJ39 判断两个IP是否属于同一子网
题目
题解(169)
讨论(341)
排行
面经new
较难  通过率：21.08%  时间限制：1秒  空间限制：32M
知识点
字符串
模拟
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
IP地址是由4个0-255之间的整数构成的，用"."符号相连。
二进制的IP地址格式有32位，例如：10000011，01101011，00000011，00011000;每八位用十进制表示就是131.107.3.24
子网掩码是用来判断任意两台计算机的IP地址是否属于同一子网络的根据。
子网掩码与IP地址结构相同，是32位二进制数，由1和0组成，且1和0分别连续，其中网络号部分全为“1”和主机号部分全为“0”。
你可以简单的认为子网掩码是一串连续的1和一串连续的0拼接而成的32位二进制数，左边部分都是1，右边部分都是0。
利用子网掩码可以判断两台主机是否在同一子网中。
若两台主机的IP地址分别与它们的子网掩码进行逻辑“与”运算（按位与/AND）后的结果相同，则说明这两台主机在同一子网中。
示例：
I P 地址　 192.168.0.1
子网掩码　 255.255.255.0
转化为二进制进行运算：
I P 地址　  11000000.10101000.00000000.00000001
子网掩码　11111111.11111111.11111111.00000000
AND运算   11000000.10101000.00000000.00000000
转化为十进制后为：
192.168.0.0
I P 地址　 192.168.0.254
子网掩码　 255.255.255.0
转化为二进制进行运算：
I P 地址　11000000.10101000.00000000.11111110
子网掩码  11111111.11111111.11111111.00000000
AND运算  11000000.10101000.00000000.00000000
转化为十进制后为：
192.168.0.0
通过以上对两台计算机IP地址与子网掩码的AND运算后，我们可以看到它运算结果是一样的。均为192.168.0.0，所以这二台计算机可视为是同一子网络。
输入一个子网掩码以及两个ip地址，判断这两个ip地址是否是一个子网络。
若IP地址或子网掩码格式非法则输出1，若IP1与IP2属于同一子网络输出0，若IP1与IP2不属于同一子网络输出2。
注:
有效掩码与IP的性质为：
1. 掩码与IP每一段在 0 - 255 之间
2. 掩码的二进制字符串前缀为网络号，都由‘1’组成；后缀为主机号，都由'0'组成
输入描述：
3行输入，第1行是输入子网掩码、第2，3行是输入两个ip地址
题目的示例中给出了三组数据，但是在实际提交时，你的程序可以只处理一组数据（3行）。
输出描述：
若IP地址或子网掩码格式非法则输出1，若IP1与IP2属于同一子网络输出0，若IP1与IP2不属于同一子网络输出2
示例1
输入：
255.255.255.0
192.168.224.256
192.168.10.4
255.0.0.0
193.194.202.15
232.43.7.59
255.255.255.0
192.168.0.254
192.168.0.1
复制
输出：
1
2
0
复制
说明：
对于第一个例子:
255.255.255.0
192.168.224.256
192.168.10.4
其中IP:192.168.224.256不合法，输出1
对于第二个例子:
255.0.0.0
193.194.202.15
232.43.7.59
2个与运算之后，不在同一个子网，输出2
对于第三个例子，2个与运算之后，如题目描述所示，在同一个子网，输出0
          
相似企业真题
TOP
2022年08月31日 16:52:13 星期三 */
 
 
int main39() {
	int mask[4] = { 0 }, ip1[4] = { 0 }, ip2[4] = { 0 };
	while (scanf_s("%d.%d.%d.%d", &mask[0], &mask[1], &mask[2], &mask[3]) != EOF) {
		scanf_s("%d.%d.%d.%d", &ip1[0], &ip1[1], &ip1[2], &ip1[3]);
		scanf_s("%d.%d.%d.%d", &ip2[0], &ip2[1], &ip2[2], &ip2[3]);
		long long res = mask[0];
		for (int i = 1; i < 4; i++) {
			res = res*256+mask[i];
		}
		bitset<32> b(~res + 1);
		if (b.count() != 1 || b == 1) {
			cout << 1;	//掩码非法
			return 0;
		}
		for (int i = 0; i < 3; i++) {
			if (ip1[i] < 0 || ip1[i]>255 || ip2[i] < 0 || ip2[i]>255) {
				cout << 1;	//ip非法
				return 0;
			}
		}
		for (int i = 0; i < 3 && mask[i]; i++) {
			if (ip1[i] & mask[i] != ip2[i] & mask[i]) {
				cout << 2;	//非同一子网
				return 0;
			}
		}
		cout << 0;
		return 0;
	}
	return 0;
}
 
 
 
 
 
 
 
 
/*
HJ40 统计字符
题目
题解(238)
讨论(435)
排行
面经new
简单  通过率：51.09%  时间限制：1秒  空间限制：32M
知识点
字符串
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
输入一行字符，分别统计出包含英文字母、空格、数字和其它字符的个数。
数据范围：输入的字符串长度满足 1 \le n \le 1000 \1≤n≤1000 
输入描述：
输入一行字符串，可以有空格
输出描述：
统计其中英文字符，空格字符，数字字符，其他字符的个数
示例1
输入：
1qazxsw23 edcvfr45tgbn hy67uj m,ki89ol.\\/;p0-=\\][
复制
输出：
26
3
10
12
复制
相似企业真题
TOP
2022年08月31日 17:36:27 星期三 
2022年08月31日 17:39:44 星期三 （3）*/
 
int main() {
	string s0;
	int a = 0, s = 0, d = 0, o = 0;
	getline(cin, s0);
	for (char c : s0) {
		if (isalpha(c)) {
			a++;
		}
		else if (isspace(c)) {
			s++;
		}
		else if (isdigit(c)) {
			d++;
		}
		else {
			o++;
		}
	}
	cout << a << endl << s << endl << d << endl << o << endl;
	return 0;
}