网易互娱笔试C++代码分享 全AC

1. 按二进制中1的个数归类，没啥好说的，计算出数字的二进制个数之后，放到相应的集合里（至多有32个集合）

#include <iostream>

using namespace std;

int main() {
	int T;
	cin >> T;
	bool* res = new bool[33];
	for (; T; --T) {
		int N;
		cin >> N;
		int* arr = new int[N];
		for (int i = 0; i < 33; ++i)
			res[i] = 0;
		for (int i = 0; i < N; ++i) {
			cin >> arr[i];
			int sum = 0;
			while (arr[i] != 0) {
				sum += arr[i] & 1;
				arr[i] = arr[i] >> 1;
			}
			res[sum] = 1;
		}
		int sum = 0;
		for (int i = 0; i < 33; ++i)
			sum += res[i];
		cout << sum << endl;
	}
    delete[] res;
}

2. 按固定时间切换出水进水开关，求最后水池水量，注意边界问题；

#include <iostream>

using namespace std;

int main() {
	int T;
	cin >> T;
	for (; T; --T) {
		int m, t, m1, t1, m2, t2, sum = 0;
		cin >> m >> t >> m1 >> t1 >> m2 >> t2;
		bool giveP = 0, takeP = 0;
		for (int i = 0; i < t; ++i) {
			if (i % t1 == 0)
				giveP = !giveP;
			if (i % t2 == 0)
				takeP = !takeP;
			sum += int(giveP) * m1 - int(takeP) * m2;
			if (sum < 0)
				sum = 0;
			else if (sum > m)
				sum = m;
		}
		cout << sum << endl;
	}
}

开始也知道这题用t对t1和t2的最小公倍数求余最后部分单独求解肯定可以减小计算量，懒癌发作发现暴力法过了就没管了；

3.  两个改变字母的机会相当于N字符串开始位置的延时更改，根据这个思路这题就很简单了

#include <iostream>
#include <string>

using namespace std;

int main() {
	int T;
	cin >> T;
	for (; T; --T) {
		int max = 0, sum = 0, firstI = -1, secI = -1, startI = -1;
		string str;
		cin >> str;
		for (int i = 0; i < str.size(); ++i) {
			if (str[i] != 'N') {
				startI = firstI;
				firstI = secI;
				secI = i;
			}
			max = (max < (i - startI)) ? (i - startI) : max;
		}
		cout << max << endl;
	}
}

4. 开局依然是暴力破解流，每一次洪水洗刷了几个基站，然后根据剩下的基站计算集合数量，发现只能过40%；思考改进方法，将洪水高度建立索引堆，洪水高度从小到大判定是否能够冲刷基站并计算集合数量仍旧超时；最后按洪水高度对洪水建立索引堆，同时按基站高度对基站建立索引堆，并且给基站建立bool数组记录基站是否被淹没才成功AC本题。

#include <iostream>
#include <map>

using namespace std;

int main() {
	int n, q;
	cin >> n;
	bool* existB = new bool[n];
	int* baseI = new int[n];
	multimap<int, int> baseH;
	for (int i = 0; i < n; ++i) {
		cin >> baseI[i];
		existB[i] = 1;
		baseH.insert({ baseI[i],i });
	}
	cin >> q;
	int* flood = new int[q];
	int* res = new int[q];
	multimap<int, int> floodI;
	for (int i = 0; i < q; ++i) {
		cin >> flood[i];
		floodI.insert({ flood[i] , i });
	}
	auto bI = baseH.begin();
	int ans = 1;
	for (auto i : floodI) {
		if (bI != baseH.end())
		{
			while (bI->first <= i.first) {
				existB[bI->second] = 0;
				if (bI->second != 0 && bI->second != n - 1) {
					if (existB[bI->second + 1] && existB[bI->second - 1])
						++ans;
					if (!existB[bI->second + 1] && !existB[bI->second - 1])
						--ans;
				}
				else if (bI->second == 0 && !existB[bI->second + 1])
					--ans;
				else if (bI->second == n - 1 && !existB[bI->second - 1])
					--ans;
				++bI;
				if (bI == baseH.end()) {
					ans = 0;
					break;
				}
			}
		}
		res[i.second] = ans;
	}
	for (int i = 0; i < q; ++i)
		cout << res[i] << endl;
	delete[] baseI;
	delete[] res;
	delete[] flood;
	delete[] existB;
}

集合数的计算这里没有像别的同学那样着眼集合，而是判断被淹没的基站相邻的两个基站状态：

1.若相邻两个基站未被淹没，则该基站的淹没将导致集合数的增加；

2.若相邻两个基站均淹没（边界问题计做被淹没），则该基站的淹没将导致集合数的减少；

3.其他情况下集合数量均不会变化。