网易游戏研发第一场
第一题：
第一题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 统计二进制中1的个数
int NumOf_1_inBinary(long long value)
{
int counts = 0;
while (value)
{
++counts; // 如果value不为0，则这个数里至少有一个1
value = (value - 1) & value;
}
return counts;
}
int main()
{
size_t N; // 多少组样例;
cin >> N;
for (size_t i = 0; i < N; ++i)
{
size_t n;
cin >> n;
long long val;
vector<long long> aNum;
for (size_t i = 0; i < n; ++i)
{
cin >> val;
aNum.push_back(val);
}
vector<int> counts;
for (size_t i = 0; i < aNum.size(); ++i)
{
long long temp = NumOf_1_inBinary(aNum[i]);
counts.push_back(temp);
}
sort(counts.begin(), counts.end());
counts.erase(unique(counts.begin(), counts.end()), counts.end());
cout << counts.size() << endl;
}
return 0;
} 第四题
思路：存下未被淹的东西的下标，再比较下标的差
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
long long TheNumOfQun(vector<long long>& nHigh, long nFoold)
{
vector<long long> nIndex;
for (long long i = 0; i < nHigh.size(); ++i)
{
// 记下未被淹的东西的下标
if (nHigh[i] > nFoold)
nIndex.push_back(i);
}
int nCounts = 0;
if (nIndex.size() == 0)
{
return nCounts;
}
else
{
int nCounts = 1;
for (long long i = 1; i < nIndex.size(); ++i)
{
// 比较下标的关系
if (nIndex[i] - nIndex[i - 1] > 1)
++nCounts;
}
return nCounts;
}
}
int main()
{
long long N;
cin >> N;
vector<long long> nHigh = { 6, 12, 20, 14, 15, 15, 7, 19, 18, 13 };
vector<long long> nHigh;
long long val;
for (long long i = 0; i < N; ++i)
{
cin >> val;
scanf("lld", &val);
nHigh.push_back(val);
}
long long M;
cin >> M;
vector<long long> nFoold;
long long nF;
for (long long i = 0; i < M; ++i)
{
cin >> nF;
scanf("lld", &nF);
nFoold.push_back(nF);
}
for (long long i = 0; i < M; ++i)
{
long a = TheNumOfQun(nHigh, nFoold[i]);
cout << a << endl;
}
return 0;
} 第二题(仅作参考，欢迎指正)：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N;
cin >> N;
// vector<char> ch = { 'N', 'M', 'N', 'N', 'M', 'N', 'B', 'N' };
// vector<char> ch = { 'N', 'N', 'M', 'N', 'B', 'N' };
for (size_t i = 0; i < N; ++i)
{
vector<char> ch;
char a;
while (cin >> a)
{
ch.push_back(a);
}
int left = 0;
int right = 0;
vector<int> aNum;
if (ch.size() == 1)
{
if (ch[0] == 'N')
{
cout << 1 << endl;
return 0;
}
else
{
cout << 0 << endl;
return 0;
}
}
if (ch.size() == 2)
{
if (ch[0] == 'N' || ch[1] == 'N')
{
cout << 2;
return 0;
}
}
for (size_t i = 0; i < ch.size(); ++i)
{
if (ch[i] == 'N')
{
left = i;
for (size_t j = i + 1; j < ch.size(); ++j)
{
if (ch[j] != 'N')
{
right = j - 1;
aNum.push_back(left);
aNum.push_back(right);
i = j;
break;
}
else if ((ch[j] == 'N' && j == ch.size() - 1))
{
aNum.push_back(left);
aNum.push_back(j);
}
}
}
}
if (ch.size() > 1)
{
if (ch[ch.size() - 2] != 'N' && ch[ch.size() - 1] == 'N')
{
aNum.push_back(ch.size() - 1);
aNum.push_back(ch.size() - 1);
}
}
int res = aNum[1] - aNum[0] + 1;
for (size_t i = 2; i < aNum.size(); i += 2)
{
int gap = aNum[i] - aNum[i - 1];
if (gap <= 3)
{
// res = max(aNum[i + 1] - aNum[i] + 1 + aNum[i] - aNum[i - 1] - 1 + res, res);
res = max(aNum[i + 1] - aNum[i - 1] + aNum[i - 1] - aNum[i - 2] + 1, res);
}
else
{
res = max(res, aNum[i + 1] - aNum[i] + 1);
}
}
//for (size_t i = 0; i < aNum.size(); ++i)
// cout << aNum[i] << " ";
//cout << endl;
cout << res << endl;
}
return 0;
} 