网易游戏（互娱）校招笔试-游戏研发

第一题

小A刚学了二进制，他十分激动。为了确定他的确掌握了二进制，你给他出了这样一道题目：给定N个非负整数，将这N个数字按照二进制下1的个数分类，二进制下1的个数相同的数字属于同一类。求最后一共有几类数字？

直接用bitset

#include<bits/stdc++.h>using namespace std;int main(){// bitset<100> b; int t;cin>>t;while(t--){map<int,int>mp;int n;cin>>n;int ans=0;for(int i=0;i<n;i++){int a;cin>>a;if(!mp[bitset<40>(a).count()]){mp[bitset<40>(a).count()]++;ans++;}}cout<<ans<<endl;}return 0;}

b.any(); //查找b是否存在1?

b.none();//b中不存在1吗?

b.count();//b中1的个数

b.size(); //b的位数

b[pos]; //访问b中pos处的数值

b.test(pos); //检测b中pos处是否为1

b.set(); //把b中所有位 置为1

b.set(pos); //把b中pos位置为1

b.reset();//把b中所有位置为0

b.reset(pos);//把b中pos位置为0

b.flip(); //b中所有二进制位取反

b.flip(pos);//b中在pos处的二进制位取反

b.to_ulong;//返回一个同值得unsigned long值

os << b; //把b中位集输出

第二题

伞屉国是一个以太阳能为主要发电手段的国家，因此他们国家中有着非常多的太阳能基站，链接着的基站会组合成一个发电集群。但是不幸的是伞屉国不时会遭遇滔天的洪水，当洪水淹没基站时，基站只能停止发电，同时被迫断开与相邻基站的链接。你作为伞屉国的洪水观察员，有着这样的任务：在洪水到来时，计算出发电集群被洪水淹没后被拆分成了多少个集群。

由于远古的宇宙战争的原因，伞屉文明是一个二维世界里的文明，所以你可以这样理解发电基站的位置与他们的链接关系：给你一个一维数组a，长度为n，表示了n个基站的位置高度信息。数组的第i个元素a[i]表示第i个基站的海拔高度是a[i],而下标相邻的基站才相邻并且建立链接，即x号基站与x-1号基站、x+1号基站相邻。特别的，1号基站仅与2号相邻，而n号基站仅与n-1号基站相邻。当一场海拔高度为y的洪水到来时，海拔高度小于等于y的基站都会被认为需要停止发电，同时断开与相邻基站的链接。

将基站高度和洪水高度排序，离线做法，低的基站被淹没了后面就一直被淹没。一开始把全部看成是一个集群，当有一个基站被淹没时，如果左右两边还在，集群+1，两边都已经被淹了，集群-1，否则集群不变。用sink数组表示所有基站当前的状态。

#include<bits/stdc++.h>using namespace std;struct nums {int h,index;bool operator <(nums a) {return h<a.h;}};nums a[200005],b[200005];int ans[200005],sk[200005];int main() {int n;cin>>n;for(int i=1; i<=n; i++) {cin>>a[i].h;a[i].index=i;}sort(a+1,a+n+1);int m;cin>>m;for(int i=1; i<=m; i++) {cin>>b[i].h;b[i].index=i;}sort(b+1,b+m+1);int cnt=1,ret=1;sk[0]=sk[n+1]=1;for(int i=1; i<=m; i++) {while(a[cnt].h<=b[i].h&&cnt<=n) {int ind=a[cnt].index;sk[ind]=1;if(sk[ind-1]==0&&sk[ind+1]==0)ret++;else if(sk[ind-1]==1&&sk[ind+1]==1)ret--;cnt++;}ans[b[i].index]=ret;}for(int i=1; i<=m; i++) {cout<<ans[i]<<endl;}return 0;}

第三题

小明作为一个游泳池管理员，以玩弄给水管和排水管为乐，也因此产生了很多数学题考验小朋友。

现在小明想把这个行动升级，考验一下程序员，做了一个自动装置来控制给水管和排水管。在开始时，给水管和排水管都是打开状态的，并且游泳池里没有水。在自动装置的作用下，每经过t1分钟，给水管的状态都会改变，即从打开状态变为关闭状态或从关闭状态变为打开状态，而同时每经过t2分钟，排水管的状态也会改变。当给水管打开时，给水管每分钟会向游泳池里注入m1升水；当排水管打开时，排水管每分钟会把游泳池里水排走m2升；当给水管和排水管同时打开时，游泳池的水量变化为每分钟(m1-m2)升。当然泳池的水量不能变为负数，同时泳池也有个最大容量m，水量不能超过m升。那么经过t分钟后，游泳池里有多少升水？

暴力

#include<bits/stdc++.h>using namespace std;int main() {int T;cin>>T;while(T--) {int m,t,m1,t1,m2,t2;int in=0,ou=0;int ans=0;cin>>m>>t>>m1>>t1>>m2>>t2;for(int i=0;i<t;i++){if(i%t1==0)in = in^1;if(i%t2==0)ou = ou^1;ans+=in*m1-ou*m2;if(ans<=0)ans=0;if(ans>=m)ans=m;}cout<<ans<<endl;//5 5 9 2 2 2 2 1 9///* int times=t/t1;//4int rt;//3if((((t1*times)/t1)%2)==0)rt=times/2;else rt=times/2+1;// cout<<t-t1*times<<endl;int in=rt*m1;//4// cout<<in<<endl;if((((t1*times)/t1)%2)==0)in+= (t-t1*times)*m1;int times2=t/t2;//4int rt2;//3if((((t2*times2)/t2)%2)==0)rt2=times2/2;else rt2=times2/2+1;int ou=rt2*m2;//4if((((t2*times2)/t2)%2)==0)ou+= (t-t2*times2)*m2;cout<<in-ou<<endl;*/}return 0;}

第四题

小A很喜欢字母N，他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串，他被允许改变最多2个大写字母（也允许不改变或者只改变1个大写字母），使得字符串中所包含的最长的连续的N串的长度最长。你能帮助他吗？

滑动窗口（？）窗口里超过两个字母不是N就去掉最前面的一个字符

#include<bits/stdc++.h>using namespace std;int main() {int t;cin>>t;while(t--){string s;string a="";cin>>s;int c=0;int st=0,ed=0;for(int i=0;i<s.length();i++){a+=s[i];if(a.length()-count(a.begin(),a.end(),'N')>=3)a.erase(0,1);int len=a.length();c=max(c,len);}cout<<c<<endl;}}