2020/4/25 网易雷火服务端代码

~~17点结束发代码~~

大家都过了多少鸭留言回复下呗我想不到3.5/4题能不能给我个面试机会鸭，目前还是 0offer 投哪哪不理

最后一题我醉了题目描述（不就一个模拟题吗题面太含糊了吧）的啥啊读不懂最后只过了8.33 前三题倒是满简单的

第一题给了你一堆坐标(小立方体边长为1，小正方体体心在坐标点上) 问最后的集合体表面积

#include <bits/stdc++.h>
using namespace std;
const int cx[] = {0, 0, 1, -1, 0, 0};
const int cy[] = {1, -1, 0, 0, 0, 0};
const int cz[] = {0, 0, 0, 0, 1, -1};

bool vis[30][30][30];
int ans;

bool chk(int x, int y, int z) {
    return x < 0 || y < 0 || z < 0 || x > 20 || y > 20 || z > 20;
}

void sol(int x, int y, int z) {
    for(int i = 0; i < 6; ++ i) {
        int nx = x + cx[i];
        int ny = y + cy[i];
        int nz = z + cz[i];
        if(chk(nx, ny, nz)) continue;
        if(vis[nx][ny][nz]) ans -= 2;
    }
}

int main() {
    int n;
    cin >> n;
    ans = 0;
    for(int i = 1, x, y, z; i <= n; ++ i) {
        cin >> x >> y >> z;
        vis[x][y][z] = 1;
        ans += 6;
        sol(x, y, z);
    }
    cout << ans << endl;
    return 0;
}

第二题单调栈维护最远2端距离都背下来了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int a[maxn];
int L[maxn], R[maxn];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    stack<int> s;
    for(int i = 0; i < n; i ++) {
        while(!s.empty() && a[s.top()] >= a[i]) s.pop();
        s.empty() ? L[i] = -1 : L[i] = s.top();
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i = n - 1; i >= 0; i --) {
        while(!s.empty() && a[s.top()] >= a[i]) s.pop();
        s.empty() ? R[i] = n : R[i] = s.top();
        s.push(i);
    }
    
    long long ans = 0;
    for(int i = 1; i <= n; i ++) {
        //cout << L[i] <<  " " << R[i] << endl;
        ans = max(ans, (long long)(R[i] - L[i] - 1) * a[i]);
    }
    cout << ans << endl;
    return 0;
}

第三题算了下 50 位 * 10 * 10 * 10 的数位状态 * 10 的枚举状态 * 450 的总和状态顶天4e7 就直接写了

ans = DP[N][X]:[ALL]

转移方程就是 $DP[N][SUM+z][NOW]+=DP[N-1][SUM][PRE]$

优化的话无非是吧 (I+J+Z) % X == 0 的状态集合提前处理出来每次遍历这个状态集合就行这样 N 有 200 位大概也能过

#include <bits/stdc++.h>
using namespace std;

int dp[55][500][10][10][10];
const int mod = 1e6 + 9;
// ans = DP[N][X]:[ALL]
int N, S, X;

void init() {
    for(int i = 0; i <= 9; i ++) {
        for(int j = 0; j <= 9; j ++) {
            for(int z = 0; z <= 9; z ++) {
                if((i * 100 + j * 10 + z) % X == 0)
                    dp[3][i + j + z][i][j][z] ++;
            }
        }
    }
}

int main() {
    cin >> N >> S >> X;
    init();
    for(int p = 4; p <= N; p ++) {
        for(int sum = 0; sum <= S; sum ++) {
            for(int pre = 0; pre <= 9; pre ++) {
                for(int i = 0; i <= 9; i ++) {
                    for(int j = 0; j <= 9; j ++) {
                        if((pre*100 + i*10 + j) % X == 0) {
                            for(int z = 0; z <= 9; z ++) {
                                if((i * 100 + j * 10 + z) % X == 0) {
                                    dp[p][sum + z][i][j][z] += dp[p - 1][sum][pre][i][j];
                                    dp[p][sum + z][i][j][z] %= mod;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    // ans = DP[N][X]:[ALL]
    int ans = 0;
    for(int i = 0; i <= 9; i ++) {
        for(int j = 0; j <= 9; j ++) {
            for(int z = 0; z <= 9; z ++) {
                if((i * 100 + j * 10 + z) % X == 0) {
                    ans = (ans + dp[N][S][i][j][z]) % mod;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

第4题我醉了

我觉得不难啊求大佬指点我可能读错题了？

200行了都快

#include <bits/stdc++.h>
using namespace std;
/*
我是真的读不懂了 什么叫 Pop类型窗口永远在**最最上层？ 其他的更上一层？**
在PopX有显示的时候 除了 将**其**关闭， 这里关闭  我们访问下面的隐藏界面 关闭上层的 算这里的合理关闭吗？
还是只能 Close PopX的窗口？ 

唉 服了 1小时3道题 3小时这道题 醉了 实在不知道这操作什么意思？
敲了一小时 改了2小时， 一直都是 不到10%  RE orz
*/
int N, M, S;
unordered_map<string, int> level_id;

struct node {
    string win_name;
    node* pre, *next;
    node(string name){win_name = name, pre = next = NULL;}
};
unordered_map<string, int> level;

int maxcap, tot;
node* head, * tail;
unordered_map<string, pair<string, node*>> dic;
// init
void init(int maxc) {
    level_id["NormalWindow"] = 1;
    level_id["FullWindow"] = 2;
    level_id["PopWindow"] = 3;
    maxcap = maxc;
    tot = 0;
    node* dummy1 = new node("-1");
    node* dummy2 = new node("-1");
    head = dummy1, tail = dummy2;
    head->next = tail;
    tail->pre = head;
}
// del and tail_add
void del(node *now) {
    now->pre->next = now->next;
    now->next->pre = now->pre;
}
void tail_add(node *now) {
    now->next = tail;
    now->pre = tail->pre;
    tail->pre->next = now;
    tail->pre = now;
}
// cheak now loadCRU
string get(string& name) {
    if(!dic.count(name)) return "nofind";
    node* now = dic[name].second;
    del(now);
    tail_add(now);
    return dic[name].first;
}
// LRU ADD and chk MAX and tail add;
void put(string& name) {
    if(dic.count(name)) {
        dic[name].first = name;
        node* now = dic[name].second;
        del(now);
        tail_add(now);
    } else {
        if(tot == maxcap) {
            node* now = head->next;
            dic.erase(now->win_name);
            del(now); // pinjie !
            delete(now);
            tot --;
        }
        node* now = new node(name);
        dic[name] = make_pair(name, now);
        tail_add(now);
        tot ++;
    }
}
// stack ??
struct win_node{
    string win_name;
    int win_level;
};
stack<win_node> s_win;
unordered_map<string, int> vis;
stack<int> s_win_23;


int main() {
    cin >> N >> M;
    init(M);
    string name_win, win_level;
    for(int i = 1; i <= N; ++ i ) {
        cin >> name_win >> win_level;
        level[name_win] = level_id[win_level];
    }
    cin >> S;
    string op_name, cin_win_name;
    while(S --) {
        cin >> op_name;
        if(op_name == "Show") {
			cin >> cin_win_name;
            if(vis[cin_win_name]) {
                if(vis[cin_win_name] < s_win_23.top() || s_win.top().win_level == 3) {
                    cout << "Invalid operation" << endl;
                    continue;
                } else {
                    while(s_win.top().win_name != cin_win_name) {
						put(s_win.top().win_name);
                        vis[s_win.top().win_name] = 0;
                        s_win.pop();
						s_win_23.pop();
                    }
                    cout << cin_win_name << endl;
                    continue;
                }
            } else {
                if(s_win.empty()) {
                    s_win.push(win_node{cin_win_name, level[cin_win_name]});
					vis[cin_win_name] = s_win.size();
					s_win_23.push(s_win.size());
					s_win_23.push(1);
					if(get(cin_win_name) != "nofind") cout << "LoadFromPoll" << endl;
                    cout << cin_win_name << endl;
                    continue;
                } else {
                    if(cin_win_name != s_win.top().win_name && s_win.top().win_level == 3) {
                        cout << "Invalid operation" << endl;
                        continue;
                    } else if (cin_win_name == s_win.top().win_name && s_win.top().win_level == 3){
                        cout << cin_win_name << endl;
                        continue;
                    } else {
						s_win.push(win_node{cin_win_name, level[cin_win_name]});
						vis[cin_win_name] = s_win.size();
						//cout << level[cin_win_name] << endl;
						if(level[cin_win_name] == 2) s_win_23.push(s_win.size());
						else s_win_23.push(s_win_23.top());
						//cout << "   || " << vis[cin_win_name] << " " << s_win_23.top() << endl;
						if(get(cin_win_name) != "nofind") cout << "LoadFromPool" << endl;
						cout << cin_win_name << endl;
						continue;
					}
                }
            }
        } else if(op_name == "Close") {
			cin >> cin_win_name;
			if(s_win.empty()) {
				cout << "Invalid operation" << endl;
                continue;
			} else {
				if(vis[cin_win_name] == 0) cout << "Invalid operation" << endl;
                else if(cin_win_name == s_win.top().win_name && s_win.top().win_level == 3) {
                    vis[s_win.top().win_name] = 0;
					put(s_win.top().win_name);
					s_win.pop();
					s_win_23.pop();
					if(s_win.empty()) cout << "NULL" << endl;
					else cout << s_win.top().win_name << endl;
					continue;
                }
                else if(cin_win_name != s_win.top().win_name && s_win.top().win_level == 3) {
                    cout << "Invalid operation" << endl;
                }
				else if(vis[cin_win_name] < s_win_23.top()) cout << "Invalid operation" << endl;
				else {
					vis[s_win.top().win_name] = 0;
					put(s_win.top().win_name);
					s_win.pop();
					s_win_23.pop();
					if(s_win.empty()) cout << "NULL" << endl;
					else cout << s_win.top().win_name << endl;
					continue;
				}
			}
		} else if(op_name == "CloseAllWindow") {
			while(!s_win.empty()) {
				put(s_win.top().win_name);
				vis[s_win.top().win_name] = 0;
				s_win.pop();
				s_win_23.pop();
			}
			cout << "NULL" << endl;
			continue;
		} else if(op_name == "Check") {
			cin >> cin_win_name;
			if(s_win.empty()) {
				cout << "Invalid operation" << endl;
                continue;
			}
			//cout << vis[cin_win_name] << " " << s_win_23.top() << endl;
			if(vis[cin_win_name] == 0) cout << "False" << endl;
			else if(vis[cin_win_name] < s_win_23.top()) cout << "False" << endl;
			else cout << "True" << endl;
		}
    }
    return 0;
}

#网易雷火#