9.22 拼多多服务端开发笔试4题（CPP版本）
1.图书馆找书（100%）前缀+二分
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < n; i++) {
a[i] += a[i - 1];
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int b;
cin >> b;
//二分法来了
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] < b) {
l = mid + 1;
} else {
r = mid;
}
}
cout << l + 1 << endl;
}
return 0;
} 2.走不同颜色的路有多少条（100%）简单DFS
#include <bits/stdc++.h>
using namespace std;
set<int> st;
int nums = 0;
void dfs(int i, int j, int& n, int& m, vector<vector<int>>& tb) {
if (st.find(tb[i][j]) != st.end()) return;
else st.insert(tb[i][j]);
if (i == n - 1 && j == m - 1) nums++;
if (i < n - 1) dfs(i + 1, j, n, m, tb);
if (j < m - 1) dfs(i, j + 1, n, m, tb);
st.erase(tb[i][j]);
}
int main () {
int T;
cin >> T;
for (int p = 0; p < T; p++) {
int n, m, k;
cin >> n >> m >> k;
st.clear();
nums = 0;
vector<vector<int>> tab(n, vector<int> (m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> tab[i][j];
}
}
dfs(0, 0, n, m, tab);
cout << nums << endl;
}
return 0;
} 3.前面有多少矮的（100%）笨办法做的，听说可以用栈
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
vector<int> sortIdx(n, -1);
for (int i = n - 1; i >= 0; i--) {
int lowNum = h[i];
for (int t = 0; t < n; t++) {
if (lowNum == 0 && sortIdx[t] == -1) {
sortIdx[t] = i;
break;
}
if (sortIdx[t] == -1) lowNum--;
}
}
for (int i = 0; i < n; i++) {
h[sortIdx[i]] = i + 1;
}
for (int i = 0; i < n; i++) cout << h[i] << " ";
cout << endl;
return 0;
} 4.N步M个棋子，求移动后坐标（超时20%）听说可以移动棋盘法
#include <bits/stdc++.h>
using namespace std;
int main () {
int T;
cin >> T;
for (int p = 0; p < T; p++) {
int N, M, X, Y;
cin >> N >> M >> X >> Y;
vector<int> steps(N);
int totalX = 0;
int totalY = 0;
int minX = 0;
int minY = 0;
int maxX = 0;
int maxY = 0;
for (int k = 0; k < N; k++) cin >> steps[k];
for (int k = 0; k < N; k++) {
if (steps[k] == 1) {
totalX--;
if (totalX < minX) minX = totalX;
} else if (steps[k] == 2) {
totalY--;
if (totalY < minY) minY = totalY;
} else if (steps[k] == 3) {
totalX++;
if (totalX > maxX) maxX = totalX;
} else if (steps[k] == 4) {
totalY++;
if (totalY > maxY) maxY = totalY;
}
}
for (int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
int fixL = 0, fixR = 0, fixT = 0, fixB = 0;
if ((x + minX >= 1) && (x + maxX <= X) && (y + minY >= 1) && (y + maxY <= Y)) {
x += totalX;
y += totalY;
} else {
for (int k = 0; k < N; k++) {
if (steps[k] == 1) {
if (x > 1) x--;
} else if (steps[k] == 2) {
if (y > 1) y--;
} else if (steps[k] == 3) {
if (x < X) x++;
} else if (steps[k] == 4) {
if (y < Y) y++;
}
}
}
cout << x << " " << y<< endl;
}
}
return 0;
} 挣扎半天没救的解法
#include <bits/stdc++.h>
using namespace std;
int main () {
int T;
cin >> T;
for (int p = 0; p < T; p++) {
int N, M, X, Y;
cin >> N >> M >> X >> Y;
vector<int> steps(N);
int totalX = 0;
int totalY = 0;
int minX = 0;
int minY = 0;
int maxX = 0;
int maxY = 0;
for (int k = 0; k < N; k++) cin >> steps[k];
for (int k = 0; k < N; k++) {
if (steps[k] == 1) {
totalX--;
if (totalX < minX) minX = totalX;
} else if (steps[k] == 2) {
totalY--;
if (totalY < minY) minY = totalY;
} else if (steps[k] == 3) {
totalX++;
if (totalX > maxX) maxX = totalX;
} else if (steps[k] == 4) {
totalY++;
if (totalY > maxY) maxY = totalY;
}
}
for (int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
int fixL = 0, fixR = 0, fixT = 0, fixB = 0;
if (x + minX < 1) fixL = 1 - x - minX;
if (x + maxX > X) fixR = X - x - maxX;
if (y + minY < 1) fixT = 1 - y - minY;
if (y + maxY > Y) fixB = Y - y - minY;
x += totalX + fixL + fixR;
x = max(0, min(X, x));
y += totalY + fixT + fixB;
y = max(0, min(Y, y));
cout << x << " " << y<< endl;
}
}
return 0;
} 
