首页 > 资源分享 > 网易笔试编程题代码共享

网易笔试编程题代码共享

头像
meopass
发布于 2018-03-27 21:29:11
回复15 | 赞 8 | 浏览2983
第一题矩形覆盖问题,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; }

15条回帖

回帖
加载中...

热门推荐

资源分享近期热帖

牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋