~~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;
} 
全部评论
(3) 回帖