网易有道C++后端9.8秋招笔试题
网易有道C++后端9.8秋招笔试题
时间 2018.9.8 C++后端
| name | 描述 | 解析 |
|---|---|---|
| 小易走路 | 小易有1,2,3,4,5种方法走路，问到x最少要走几次 | 送分题 |
| 翻牌 | N*M矩阵，每翻一张牌周围8张都会翻过来，求问所有翻完后背面的张数 | 注意到N，M都是1e9的数量级，所以不可能靠搜索方法解决，肯定是有公式的。于是找规律，可以发现，M=1是一种情况，M=2是结果全为0，M>2时除了最外圈全是背面。 |
| 香槟塔 | 往香槟塔的一层倒酒，满了会溢出到下一层。妞妞有2个操作，往x层倒v升的酒，以及查询第x层的酒数量。 | 注意到行为是修改与查询，应该选择合适的数据结构。但因为满了的杯子是不会变的，所以用很简单的线性结构就行了。在处理溢出时，搜索未满杯子可以用另一个跳转表记录当前层数下一个未满杯子层数。不过这道题直接搜索也可以过。 |
第一题
int main() {
cin >> x;
INT_64 cnt = x / 5;
if (x % 5) cnt += 1;
cout << cnt << endl;
}
第二题
int main() {
cin >> T;
FOR(t, T) {
cin >> N >> M;
if (N < M) {
INT_64 tmp = N;
N = M;
M = tmp;
}
INT_64 out;
if (N == 1) out = 1;
else if (N == 2) out = 0;
else if (M == 2) out = 0;
else if (M == 1) out = N-2;
else out = (M - 2)*(N - 2);
cout << out << endl;
}
}
第三题
typedef long long INT_64;
INT_64 T,N,M;
#define FOR(i,n) for(INT_64 i=0;i<n;++i)
#define MAXN (200001)
INT_64 a[MAXN];
INT_64 b[MAXN];
INT_64 query(INT_64 k) {
return b[k-1]-a[k-1];
}
int nextNoFull[MAXN];
bool isFull[MAXN];
int findNextNoFull(INT_64 x) {
int next;
next = nextNoFull[x];
while (isFull[next] == true) {
next = nextNoFull[next];
}
nextNoFull[x] = next;
return next;
}
void addToX(INT_64 x, INT_64 v) {
x = x - 1;
INT_64 now = x;
INT_64 rest = v;
while (rest != 0) {
if (isFull[now]) now = nextNoFull[now];
if (now == N) break;//到地板了
INT_64 tmp = a[now] - rest;
if (tmp < 0) {
tmp = a[now];
}
else tmp = rest;
//更新a
a[now] -= tmp;
rest -= tmp;
//更新full
if (a[now] == 0) isFull[now] = true;
}
}
int main() {
cin >> N >> M;
FOR(i, N) cin >> a[i];
FOR(i, N) b[i]= a[i];
FOR(i, N+1) isFull[i]=false;
FOR(i, N) nextNoFull[i] = i+1;
char c;
INT_64 x, v,k;
FOR(m, M) {
cin >> c;
if (c == '1') {
cin >> k;
cout << query(k) << endl;
}
else {
cin >> x >> v;
addToX(x, v);
}
}
return 0;
}
