2020.05.21 牛客网 校招全国统一模拟笔试（2020年5月场）- C++方向

几天前报名了牛客网的“校招全国统一模拟笔试（2020年5月场）- C++方向”，考试时间也就是今晚的 19:00 - 21:00 ~

整体题目难度中等吧，至少算不上难的。总共20个选择题，3个编程题，编程题我做出来两个，最后一个时间不够了。

下面大概写一下我的3个编程题的解题思路(●’◡’●)

题目一：偶串

（1）题目

时间限制： C/C++1秒，其他语言2秒

空间限制： C/C++ 32768K，其他语言65536K

64bit I0 Format: %lld

如果一个字符串由两个相同字符串连接而成，就称这个字符串是偶串。例如 "xyzxyz" 和 "aaaaa" 是偶串，但是 "ababab" 和 "xyzxy" 却不是。

牛牛现在给你一个只包含小写字母的偶串 s ，你可以从字符串 s 的未尾删除1个或者多个字符，保证删除之后的字符串还是一个偶串，牛牛想知道删除之后得到最长偶串长度是多少。

输入描述：

• 输入包括一个字符串 s ，字符串长度 length（2 <= length <= 2000），保证 s 是一个偶串且由小写字母构成

输出描述：

• 输出一个整数，表示删除之后能得到的最长偶串长度是多少。保证测试数据有非零解

示例（输入输出示例仅供调试，后台判题数据一般不包含示例）

输入：

abaababaab

输出：

6

（2）解题思路

首先容易观察到的是，这个偶串的长度其实始终是偶数，即使我们从字符串 s 末尾删掉字符也必然是两个一组删除的，因为不可能存在长度为奇数的偶串。

又由于给定的字符串本身就是一个偶串，同时至少需要删除一个字符，所以直接先删掉末尾两个字符，然后循环，直接使用 substr() 函数比较字符串 s 的前一半和后一半是否相同，相同则输出 s 的长度，跳出循环结束运行；不相同则继续删掉末尾两个字符，重复上述步骤。

小思路：其实可以把循环前面的删除字符操作统一写到循环内部，逻辑更加清晰！

（3）代码

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

int main() {
	string str;
	cin >> str;
	str.pop_back();//至少删除一个字符
	str.pop_back();//至少删除一个字符
	while (!str.empty())
	{
		int len = str.size() / 2;//字符串长度的一半
		if (str.substr(0, len) == str.substr(len, len)) {
			cout << str.size() << endl;
			break;
		}
		else {
			//删除两个字符
			str.pop_back();
			str.pop_back();
			continue;
		}
	}
	return 0;
}

题目二：制造回文

（1）题目

时间限制： CIC++1秒，其他语言2秒

空间限制： C/C++ 32768K，其他语言65536K

64bit 10 Format: %lld

牛牛有一些字母卡片，每张卡片上都有一个小写字母，所有卡片组成一个字符串 s 。牛牛一直认为回文这种性质十分优雅，于是牛牛希望用这些卡片拼凑出一些回文串，但是有以下要求：

1. 每张卡片只能使用一次
2. 要求构成的回文串的数量最少

牛牛想知道用这些字母卡片，最少能拼凑出多少个回文串。

例如：

• s = "abbaa"，输出1，因为最少可以拼凑出 "ababa" 这一个回文串
• s = "abc"，输出3，因为最少只能拼凑出 "a"，"b"，"c" 这三个回文串

输入描述：

• 输入包括一行，一个字符串 s，字符串 s 长度 length （1 <= length <= 1000）.

• s 中每个字符都是小写字母

输出描述：

• 输出一个整数，即最少的回文串个数。

示例（输入输出示例仅供调试，后台判题数据一般不包含示例）

输入：

abc

输出：

3

（2）解题思路

之前在 Leetcode 上做过这个题。这一次思路大体也和之前一样，但有一点使得逻辑更加简单~

题目的意思其实就是用尽可能多的字符来构造一个回文串。构成回文串的规律是，同一个字符的偶数个数一定可以是任意回文串的一部分，换言之偶数个数的同一字符对能生成的最少的回文串个数是没有影响的，所以我们应该关注的重心是个数为奇数的字符。

要使构成的回文串的个数最少，那么根据前面所说的，首先我们尽可能的去构造一个最长的回文串，也就是把所有偶数个数的字符都用来构造这个回文串，这其中也包括 "aaa" 中的两个 'a' 也可以用于构造这个回文串，此时，如果有剩下的字符，显然都是单个的字符了。

但事实上前面构造的最大回文串长度为偶数，其实还可以在其正中间插入任意一个单个的字符，插入后仍然是回文串，此时剩下的单个字符的个数，也就是其余可以构成的回文串的个数了。

普遍情况下，可以根据前面所述的得到：最少的回文串个数 = 奇数个数的字符数 - 1 + 1 = 奇数个数的字符数

但是特殊的，需要考虑没有奇数个数的字符的情况，这种情况也就更简单了，所有的字符都用来构造唯一的一个回文串，最少的回文串个数也就是 1 。

（3）代码

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

int main() {
	string str;
	cin >> str;
	//统计不同字符的个数
	vector<pair<char, int>> words;
	for (int i = 0; i < str.size(); i++) {
		bool exist = false;
		for (int j = 0; j < words.size(); j++) {
			if (words[j].first == str[i]) {
				exist = true;
				words[j].second++;
			}
		}
		if (exist == false) {
			words.push_back({ str[i], 1 });
		}
	}
	int odd = 0;//奇数个数的字符数
	for (int i = 0; i < words.size(); i++) {
		if (words[i].second % 2 != 0) {
			odd++;
		}
	}
	cout << (odd > 0 ? odd : 1) << endl;
	return 0;
}

题目三：猜数游戏

（1）题目

时间限制： CIC++1秒，其他语言2秒

间限制： C/C++ 32768K，其他语言65536K

64bit 1O Format: %lld

牛牛和羊羊在玩一个有趣的猜数游戏。在这个游戏中，牛牛玩家选择一个正整数，羊羊根据已给的提示猜这个数字。第个提示是 "Y" 或者 "N" ，表示牛牛选择的数是否是的倍数。

例如，如果提示是 "YYNYY"，它表示这个数是1，2，4，5的倍数，但不是3的倍数。

注意到一些提示会出现错误。例如：提示 "NYYY" 是错误的，因为所有的整数都是1的倍数，所以起始元素肯定不会是 "N" 。此外，例如 "YNNY" 的提示也是错误的，因为结果不可能是4的倍数但不是2的倍数。

现在给出一个整数 n ，表示已给的提示的长度。请计算出长度为 n 的合法的提示的个数。

例如 n = 5 ，合法的提示有：

YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY
YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY

所以输出 12

输入描述：

输入包括一个整数 n （1 <= n <= 10^6） ，表示已给提示的长度。

输出描述：

输出一个整数，表示合法的提示个数。因为答案可能会很大，所以输出对于 1000000007 的模

示例（输入输出示例仅供调试，后台判题数据一般不包含示例）

输入：

5

输出：

12

（2）解题思路

这个题看完题目就知道是动态规划了，知道难搞，不过还是尝试着做了一下，时间不够，大概写了个框架出来，明明还有十多分钟的，不知道为啥就自动给我交卷了……

下面的代码是考试结束后我继续完善的，自己本地简单测试了几组较小的数据，主要是我也不知道正确答案应该是什么，就不方便测试了，也不确定代码的正确性。另外我觉得我这代码就算逻辑是对的，但是性能也不太好，应该是有更好的办法的o_o ….

大概思路就是逐个的插入“提示”，也就是逐个的插入 'Y' 或 'N' ，判断当前插入是否合法，直到字符串长度达到输入的 n 并且该提示字符串合法，则合法的提示个数+1。

其中我判断当前插入的字符是否合法的想法是，我认为只有插入的是 'Y' 才可能是不合法的，比如当前第四个字符插入的是 'Y' ，也就是说是 4 的倍数，但字符串前面可能第二个提示是 'N' ，即不是 2 的倍数，那么当前的插入就矛盾了，不合法。另外，前述不合法的情况，只需要判断当前第 i 个字符是 'Y' ，只要找到一个 i 的约数对应的提示为 'N' 则当前提示不合法。

（3）代码

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

//动态规划，参数分别为合法提示的个数、可能的提示、剩余的提示个数
void dp(long long& count, string way, int n) {
	//判断当前选择是否合法
	bool legal = true;
	int l = way.size();//当前长度
	char ch = way.back();//末尾字符即当前的选择
	for (int i = 1; ch == 'Y' && i < l - 1; i++) {
		if (l % (i + 1) == 0 && way[i] == 'N') {
			legal = false;
			return;
		}
	}
	if (legal == true && n == 0) {
		count++;
		//cout << way << endl;//打印合法的提示
		return;
	}
	//做选择
	dp(count, way + "Y", n - 1);
	dp(count, way + "N", n - 1);
}

int main() {
	int n;
	cin >> n;
	long long count = 0;
	dp(count, "Y", n - 1);
	cout << count << endl;
	return 0;
}