9.27网易互娱游研笔试4道编程题满分题解
前三题对我来说比较容易把，可能对有些同学有点难度，一直顺风顺水，大概前两题做完还剩2小时，然后03花了50分钟， 最后一题因为细节，卡了最后剩10分钟才满分，这里分享下做法。
01题
让你列A * B的竖式，然后算出现的0-9每个数字的频率，最后还要求出现最多的那个。
比如11 * 12
11
12
—
22
11
132
2出现了4次。
老实说，这题我一开始扫了一眼，大概就是个暴力列竖式就好了，没看到0是不算的，因此我是按算0的来求的（代码会复杂）
最后跑样例发现是不用的，因为如果有0的话，这题难度会高一点，那我就按有0的情况说了。
首先可以发现，由于他要求A * B的竖式，必须是A在上面，B在下面，找规律容易发现，其实就是取B的每一位跟A去乘，得一个C，然后算一下C的每一位数字是多少，cnt[i]++即可
最后要注意，A和B本身要被记录一次，A*B也要被记录一次。然后输出cnt数组就好。
由于要算全部n个竖式的频率，那就再开个sum数组记一下（cnt每次一个竖式情况，sum永远不清空），输出即可，代码如下：
难度提升：假如题目要求考虑0，你必须注意，while会碰到0直接不进入，因为会发现无法把0计数进来，解决的办法很容易，加个bool变量，强制进一次，或者do while循环即可。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <forward_list>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l + r) >> 1)
#define midmid ((r + mid) >> 1)
#define LONG_LONG_MIN -9223372036854775808ll
#define LONG_LONG_MAX 9223372036854775807ll
using namespace std;
typedef long long int ll;
const int MAXN = 1e5 + 310;
const int MOD = 1e9 + 7;
int n,a,b;
int cnt[10],sum[10];
int main(){
scanf("%d",&n); memset(sum,0,sizeof(sum));
for(int i = 1; i <= n; ++i){
memset(cnt,0,sizeof(cnt));
scanf("%d%d",&a,&b); int nb = b; bool flag = true;
while(nb != 0 || flag){
flag = false;
int now = nb % 10; nb /= 10;
bool flag2 = true;
int c = a * now;
while(c != 0 || flag2){
flag2 = false;
cnt[c % 10]++; c /= 10;
}
}
flag = true; int c = a * b;
while(c != 0 || flag){
flag = false;
cnt[c % 10]++; c /= 10;
}
flag = true;
while(a != 0 || flag){
flag = false;
cnt[a % 10]++; a /= 10;
}
flag = true;
while(b != 0 || flag){
flag = false;
cnt[b % 10]++; b /= 10;
}
for(int i = 1; i <= 9; ++i){
sum[i] += cnt[i];
i == 9 ? printf("%d\n",cnt[i]) : printf("%d ",cnt[i]);
}
}
int ans,maxn; maxn = -1;
for(int i = 1; i <= 9; ++i){
if(sum[i] > maxn){
maxn = sum[i]; ans = i;
}
}
printf("%d\n",ans);
return 0;
}
02题 一看这才6个键，枚举全排列才6！=720，这还有啥好说的，直播暴力枚举全排列，每种情况答案取min即可。
当时迟疑了一会，虽然这题很容易，但是我觉得应该有动态规划解法，来解决键更多的情况，但是他既然没要求那么难，就暴力好了。
C++有自己可以枚举排列的函数，可以用用减少代码量。
update:02有人回复说看不大懂代码，我这边详细解释下我做法吧。
首先为了处理方便，ASDFGH 6个键，你压根没必要真的就ASDFGH这样存，可以当作是1 2 3 4 5 6，丢进数组a里，对a枚举全排列就好了。
那么对于某个排列，比如2 4 3 1 6 5，我建一个数组bi，表示第i个数在a中的位置（其实有点置换的概念），比如此时b4 = 2,b6 = 5
然后我去枚举这个打字序列s，记录一下上一次手指的位置，比如一开始是1，那么下一个要打的字是6，b6 = 5,那么abs(b6 - 1)就是此次手指移动的代价，last改成b6，因此手指此时放在b6上面了
next_permutation
algorithm库中自带的函数，用于生成全排列，其底层算法我记得没错的话，比你自己手写效率是要高一点的。在《组合数学》这本书中有详细展开全排列生成算法，包括格雷码等等，有兴趣的可以了解一下。
如果不用这个函数，这部分你得写一个dfs（深度优先搜索）去枚举一下。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <forward_list>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l + r) >> 1)
#define midmid ((r + mid) >> 1)
#define LONG_LONG_MIN -9223372036854775808ll
#define LONG_LONG_MAX 9223372036854775807ll
using namespace std;
typedef long long int ll;
const int MAXN = 1e3 + 10;
const int MOD = 1e9 + 7;
int t,a[10],b[10],len;
char s[MAXN];
int pd(){
int last = 1;
int re = 0;
for(int j = 0; j < len; ++j){
re = re + abs(b[s[j] - '0'] - last);
last = b[s[j] - '0'];
}
return re;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%s",s); len = strlen(s);
for(int i = 0; i < len; ++i){
switch(s[i]){
case 'A': s[i] = '1'; break;
case 'S': s[i] = '2'; break;
case 'D': s[i] = '3'; break;
case 'F': s[i] = '4'; break;
case 'G': s[i] = '5'; break;
case 'H': s[i] = '6'; break;
}
}
for(int i = 1; i <= 6; ++i){
a[i] = i; b[i] = i;
}
int ans = INT_MAX;
while(1){
ans = min(ans,pd());
if(!next_permutation(a + 1,a + 7)){
break;
}
for(int i = 1; i <= 6; ++i){
b[a[i]] = i;
}
}
printf("%d\n",ans);
}
return 0;
}
03 又是一道没营养的没算法题，一眼就看出来是个大模拟题，这种题就不考察你算法，考代码的基本功。
想好流程就好了，先对地图bfs每个连通块，找到那个题目要求的那个，然后暴力再bfs一次，把那块全置-1，然后先掉落，再左移即可。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <forward_list>
//#define left (now<<1)
//#define right ((now<<1)+1)
//#define mid ((l + r) >> 1)
//#define midmid ((r + mid) >> 1)
#define LONG_LONG_MIN -9223372036854775808ll
#define LONG_LONG_MAX 9223372036854775807ll
using namespace std;
typedef long long int ll;
const int MAXN = 1e3 + 10;
const int MOD = 1e9 + 7;
struct s1{
int x,y;
int num;
int id;
};
int a[60][30];
int n,m,t;
char s[30];
s1 maxn,dnow;
bool vis[60][30];
queue<int> qx,qy;
int mv[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
void bfs(int x,int y){
dnow.num = 1;
dnow.x = x;
dnow.y = y;
dnow.id = a[x][y];
qx.push(x); qy.push(y);
vis[x][y] = true;
while(!qx.empty()){
int nowx = qx.front(); qx.pop();
int nowy = qy.front(); qy.pop();
if(nowx < dnow.x){
dnow.x = nowx; dnow.y = nowy;
}else if(nowx == dnow.x && nowy < dnow.y){
dnow.x = nowx; dnow.y = nowy;
}
for(int i = 0; i < 4; ++i){
int nextx = nowx + mv[i][0];
int nexty = nowy + mv[i][1];
if(vis[nextx][nexty] == false && a[nextx][nexty] == a[nowx][nowy]){
vis[nextx][nexty] = true;
dnow.num++;
qx.push(nextx); qy.push(nexty);
}
}
}
}
bool pd(){
maxn.num = -1; maxn.id = INT_MAX;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
vis[i][j] = true;
if(a[i][j] != -1){
vis[i][j] = false;
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(vis[i][j] == false){
bfs(i,j);
if(maxn.num < dnow.num){
maxn = dnow;
}else if(maxn.num == dnow.num){
if(maxn.id > dnow.id){
maxn = dnow;
}else if(maxn.id == dnow.id){
if(maxn.x > dnow.x){
maxn = dnow;
}else if(maxn.x == dnow.x && maxn.y > dnow.y){
maxn = dnow;
}
}
}
}
}
}
return maxn.num >= 2;
}
void poke(){
qx.push(maxn.x); qy.push(maxn.y);
a[maxn.x][maxn.y] = -1;
while(!qx.empty()){
int nowx = qx.front(); qx.pop();
int nowy = qy.front(); qy.pop();
for(int i = 0; i < 4; ++i){
int nextx = nowx + mv[i][0];
int nexty = nowy + mv[i][1];
if(a[nextx][nexty] == maxn.id){
a[nextx][nexty] = -1;
qx.push(nextx); qy.push(nexty);
}
}
}
}
void down(){
for(int i = n - 1; i >= 1; --i){
for(int j = 1; j <= m; ++j){
if(a[i][j] == -1){ continue;}
int nowx = i; int nowy = j;
while(nowx < n && a[nowx + 1][nowy] == -1){
swap(a[nowx + 1][nowy],a[nowx][nowy]);
++nowx;
}
}
}
}
void left(){
bool none = true;
for(int i = 1; i <= n; ++i){
if(a[i][1] != -1){
none = false; break;
}
}
for(int j = 2; j <= m; ++j){
if(none){
for(int i = 1; i <= n; ++i){
swap(a[i][j],a[i][j - 1]);
}
}else{
none = true;
for(int i = 1; i <= n; ++i){
if(a[i][j] != -1){
none = false; break;
}
}
}
}
}
void ceshi(){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
j == m ? printf("%d\n",a[i][j]) : printf("%d ",a[i][j]);
}
}
printf("\n");
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m); memset(vis,true,sizeof(vis)); memset(a,-1,sizeof(a));
for(int i = 1; i <= n; ++i){
scanf("%s",s);
for(int j = 0; j < m; ++j){
a[i][j + 1] = s[j] - '0';
}
}
while(pd()){
poke();
//printf("after poke:\n"); ceshi();
down();
//printf("after down:\n"); ceshi();
left();
//printf("after left:\n"); ceshi();
}
int ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i][j] != -1){ ++ans;}
//printf("%d ",a[i][j]);
}
}
//ceshi();
printf("%d\n",ans);
}
return 0;
}
/**
1
4 4
0322
0310
1210
3220
**/
04题暴力O（n ^ 2）,正解是O（nlogn）
先说说暴力，一开始10分钟我看错题目了，我以为是随机给的矩形，根本没想法（30%的当然好做，直接枚举每对矩形其实可以的），后来发现，原来都是有个顶点在原点的。
一看对题目，思路就来了，既然都在原点，我们会发现，假如一个矩形在第一象限，左下角肯定是原点对吧，那么只有另一个矩形也在第一象限，他们才可能重叠，会产生新的矩形。
因此把4个象限的矩形分开放4个数组里，然后取一下绝对值，转到第一象限，那么分开算4次就行了，这样问题就变成了，矩形一定会出现在第一象限，然后balabala算
那么怎么算呢？我当时是思考，不去考虑重复的矩形不计数进来
我们发现，当且仅当一个矩形a比矩形b的x要大，y却要小的时候，会出现非包含然后重叠出来一个新矩形的情况。
那么我们可以这样，对矩形按x轴排序，然后从小到大，比如枚举到第i个矩形，那么前1 - i-1个矩形必定x比他小，看看几个y比它大就能新生成几个。
但是要是你暴力这么做还是O（n ^ 2）的复杂度，怎么办？
我们可以离散化所有矩形的坐标，离散化可能有些同学不清楚，因为x和y很多，是10的9次，而n却很小，说明中间肯定很多坐标是空白没用的，比如线段【1,7】【2,4】你可以压缩成【1,4】【2,3】
这样的好处是，数据范围变成了n以内，然后线段之间的包含啊，相交关系是不变的（自己想想）显然，这个结论可以推到***。
那么离散了做什么呢？我们建一个前缀和数组ai，表示y为1 - i的矩形有多少。边枚举边更新。
那么有小伙伴问了，你这样更新，比如a1+1，a2,a3,a4不也得+1，还是n的平方啊
这里考虑用数据结构优化，我这里是利用树状数组（线段树也可以）可以做到logn的时间内维护前缀和。
那么这样问题就解决了。
等等，还没有解决，还有重叠的情况怎么办！？
这里必须要考虑去重了，我们发现，第一，当一个矩形的存在x和它相同，y比它大，的矩形以及另一个y和它相同，x比它大的矩形，它就一定可以被这俩矩形构造出来，因此这样的矩形，我们可以考虑不计算，直接continue
另外，如果对于矩形a存在x相同，y更大的矩形b，a和b的重叠矩形肯定是a，因此维护树状数组的时候必须对合适的矩形去添加。（这里细节有点不好说清楚，大家多画画图，我这里纠结卡了20分钟）
然后就AC了
下面是代码：
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <forward_list>
//#define left (now<<1)
//#define right ((now<<1)+1)
//#define mid ((l + r) >> 1)
//#define midmid ((r + mid) >> 1)
#define LONG_LONG_MIN -9223372036854775808ll
#define LONG_LONG_MAX 9223372036854775807ll
using namespace std;
typedef long long int ll;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
struct point{
ll x,y;
};
vector<point> a[4],b[4];
ll bit[MAXN],maxx[MAXN],maxy[MAXN];
int t,n;
ll ans;
ll lowbit(ll x){
return x & (-x);
}
void add(ll x,ll y){
while(x <= 100000){
bit[x] += y; x += lowbit(x);
}
}
ll getsum(ll x){
ll re = 0;
while(x > 0){
re += bit[x]; x -= lowbit(x);
}
return re;
}
bool cmpy(point x,point y){
return x.y < y.y;
}
bool cmpx(point x,point y){
if(x.x != y.x){
return x.x < y.x;
}
return x.y < y.y;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n); ans = 0;
for(int i = 0; i < 4; ++i){ a[i].clear(); b[i].clear();}
for(int i = 1; i <= n; ++i){
ll x,y;
scanf("%lld%lld",&x,&y);
ll p = 0;
if(x < 0 && y > 0){ p = 1;}
if(x < 0 && y < 0){ p = 2;}
if(x > 0 && y < 0){ p = 3;}
point pp; pp.x = abs(x); pp.y = abs(y);
a[p].push_back(pp);
}
for(int i = 0; i < 4; ++i){
sort(a[i].begin(),a[i].end(),cmpy); //离散y
ll cnt = 0;
for(int j = 0; j < a[i].size(); ++j){
b[i].push_back(a[i][j]);
if(j != 0 && a[i][j].y == a[i][j - 1].y){
b[i][j].y = b[i][j - 1].y;
}else{
b[i][j].y = ++cnt;
}
}
swap(a[i],b[i]); b[i].clear();
sort(a[i].begin(),a[i].end(),cmpx); //离散x
cnt = 0;
for(int j = 0; j < a[i].size(); ++j){
b[i].push_back(a[i][j]);
if(j != 0 && a[i][j].x == a[i][j - 1].x){
b[i][j].x = b[i][j - 1].x;
}else{
b[i][j].x = ++cnt;
}
}
memset(bit,0,sizeof(bit));
memset(maxx,0,sizeof(maxx));
memset(maxy,0,sizeof(maxy));
for(int j = 0; j < b[i].size(); ++j){
point now = b[i][j];
maxx[now.y] = max(maxx[now.y],now.x);
maxy[now.x] = max(maxy[now.x],now.y);
}
for(int j = 0; j < b[i].size(); ++j){
if(j != 0 && b[i][j].x == b[i][j - 1].x && b[i][j].y == b[i][j - 1].y){ continue;}
if(maxx[b[i][j].y] > b[i][j].x && maxy[b[i][j].x] > b[i][j].y){ continue;}
++ans;
//printf("%lld\n",getsum(100000));
if(maxx[b[i][j].y] == b[i][j].x){
ans = ans + getsum(100000) - getsum(b[i][j].y);
}
if(j < b[i].size() - 1 && maxy[b[i][j].x] == b[i][j].y){
add(b[i][j].y,1ll);
}
}
}
printf("%lld\n",ans);
}
}
