网易笔试编程题代码共享
第一题矩形覆盖问题，n比较小，所以直接离散化之后暴力即可，需要注意边界重合不算。复杂度O(n^3)
n如果很大的话，可以离散化之后，用扫描线+线段树来做，复杂度O(nlogn)。
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> using namespace std; #define all(x) x.begin(), x.end() const int maxn = 555; int n; vector<int> G; int x_1[maxn], y_1[maxn], x_2[maxn], y_2[maxn]; int getid(int x) { return lower_bound(all(G), x) - G.begin() + 1; } int cnt[1111][1111]; int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &x_1[i]); for(int i = 0; i < n; i++) scanf("%d", &y_1[i]); for(int i = 0; i < n; i++) scanf("%d", &x_2[i]), x_2[i]--; for(int i = 0; i < n; i++) scanf("%d", &y_2[i]), y_2[i]--; for(int i = 0; i < n; i++) { G.push_back(x_1[i]); G.push_back(y_1[i]); G.push_back(x_2[i]); G.push_back(y_2[i]); } sort(all(G)); G.erase(unique(all(G)), G.end()); for(int i = 0; i < n; i++) { x_1[i] = getid(x_1[i]); y_1[i] = getid(y_1[i]); x_2[i] = getid(x_2[i]); y_2[i] = getid(y_2[i]); } int ans = 0; for(int i = 0; i < n; i++) { for(int j = x_1[i]; j <= x_2[i]; j++) for(int k = y_1[i]; k <= y_2[i]; k++) cnt[j][k]++, ans = max(ans, cnt[j][k]); } cout<<ans; return 0; }
第二题枚举y，之后枚举y的倍数，统计答案即可。复杂度O(nlogn)。
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
#define all(x) x.begin(), x.end()
int n, k;
int main() {
scanf("%d%d", &n, &k);
long long ans = 0;
if(k == 0) {
cout<<1LL*n*n<<endl;
return 0;
}
for(int i = k + 1; i <= n; i++) {
for(int j = k - 1, t = i - 1; j <= n; j += i, t = min(t+i, n)) {
ans += t - j;
}
}
cout<<ans;
return 0;
}
第3题，按题意模拟，先把任务要求和能力值离散化，然后插到树状数组里，这样每次询问报酬的时候就是一个区间最大值的查询。复杂度O(nlogn)。
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> using namespace std; #define all(x) x.begin(), x.end() const int maxn = 220000; int n, m; int D[maxn], P[maxn], A[maxn]; vector<int> G; int C[maxn]; int lowbit(int x) { return x & -x; } void ins(int x, int v) { for(int i = x; i < maxn; i += lowbit(i)) C[i] = max(C[i], v); } int ask(int x) { int ans = 0; for(int i = x; i; i -= lowbit(i)) ans = max(ans, C[i]); return ans; } int get(int x) { return lower_bound(all(G), x) - G.begin() + 1; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d%d", &D[i], &P[i]); G.push_back(D[i]); } for(int i = 1; i <= m; i++) { scanf("%d", &A[i]); G.push_back(A[i]); } sort(all(G)); G.erase(unique(all(G)), G.end()); for(int i = 1; i <= n; i++) { D[i] = get(D[i]); ins(D[i], P[i]); } for(int i = 1; i <= m; i++) A[i] = get(A[i]); for(int i = 1; i <= m; i++) printf("%d\n", ask(A[i])); return 0; }