网易2018春招笔试编程题参考代码

练习地址：https://www.nowcoder.com/test/9763997/summary

牛牛的闹钟

分析

对于每一个闹钟，计算x分钟后的时间，和上课时间进行比较，如果不超过上课时间，把闹钟时间和保存的答案进行比较，取最晚。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

int h[105], m[105];
int main() {
    int n, x;
    int ans1 = 0, ans2 = 0, temp1, temp2;
    int a, b;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d%d", &h[i], &m[i]);
    scanf("%d", &x);
    scanf("%d%d", &a, &b);
    for(int i = 0; i < n; i++) {
        temp2 = m[i] + x;
        temp1 = h[i] + temp2 / 60;
        temp2 = temp2 % 60;
        if(temp1 < a || (temp1 == a && temp2 <= b)) {
            if(h[i] > ans1 || (h[i] == ans1 && m[i] > ans2)) {
                ans1 = h[i];
                ans2 = m[i];
            }
        }
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

迷路的牛牛

分析

统计一共向左和向右转了多少次，计算最后的方向相对于初始方向的差异，模拟即可。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

char s[1005];
int main() {
    int now = 0, n;
    scanf("%d", &n);
    scanf("%s", s);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'L')
            now--;
        else
            now++;
    }
    now = (now % 4 + 4) % 4;
    if(now == 0)
        printf("N\n");
    else if(now == 1)
        printf("E\n");
    else if(now == 2)
        printf("S\n");
    else
        printf("W\n");
    return 0;
}

安置路灯

分析

贪心。
对于一个需要照亮的位置的右边一格放置一个路灯就好了。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;
int n;
char s[1005];
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%s", s);
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] == 'X') continue;
            if(s[i] == '.') ans++;
            i += 2;
        }
        printf("%d\n",ans);
    }
    return 0;
}

被3整除

分析

手算一下会发现规律。
三个数为一组,第一个数不能被3整除,另外两个可以被3整除。
于是把区间端点都移到某组的开端,记录移动过程中满足的数, 之后就可以通过(b - a) / 3 * 2快速计算。

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>

using namespace std;
int main() {
    int l, r;
    scanf("%d%d", &l, &r);
    int cnt1 = 0, cnt2 = 0, cnt = 0;
    if(l % 3 == 2 || l % 3 == 0) cnt++;
    if(r % 3 == 2 || r % 3 == 0) cnt++;
    while(l % 3 != 1) {
        if(l % 3 == 2 || l % 3 == 0) cnt1++;
        l--;
    }
    while(r % 3 != 1) {
        if(r % 3 == 2 || r % 3 == 0) cnt2++;
        r++;
    }
    cnt += (r - l) / 3 * 2;
    printf("%d\n", cnt - cnt1 - cnt2);
    return 0;
}

数对

分析

对于一个b, n范围内的数模b的序列应该是:
0,1,2,...,b-1, 0, 1, 2,..., b-1,...0,1,2,..n%b
前面部分是个循环节,所以可以通过(n / b) * max(0, b - k)计算。
后面部分是max(0, n % b - k + 1),
于是我们枚举合法的b计算就可以了。
k = 0的情况特判处理。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    if(k == 0) cout << 1LL * n * n << endl;
    else {
        long long ans = 0;
        for(int i = k + 1; i <= n; i++){
            ans += (n / i) * (i - k);
            if(n % i >= k)    ans += n % i - k + 1;
        }
        cout << ans << endl;
    }
    return 0;
}

矩形重叠

分析

分别枚举所有的横纵坐标,挨着判断每个矩形是否符合条件，计数维护最大即可。

时间复杂度

O(n^3)

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 50 + 5;
int X1[maxn], Y1[maxn];
int X2[maxn], Y2[maxn];
set<int> xx, yy;
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> X1[i];
        xx.insert(X1[i]);
    }
    for(int i = 0; i < n; i++) {
        cin >> Y1[i];
        yy.insert(Y1[i]);
    }
    for(int i = 0; i < n; i++) {
        cin >> X2[i];
        xx.insert(X2[i]);
    }
    for(int i = 0; i < n; i++) {
        cin >> Y2[i];
        yy.insert(Y2[i]);
    }
    int ans = 0;
    for(int x : xx) {
        for(int y : yy) {
            int cnt = 0;
            for(int i = 0; i < n; i++) {
                if(X1[i] <= x && Y1[i] <= y && X2[i] > x && Y2[i] > y) cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
    return 0;
}

牛牛的背包问题

分析

容量太大,没办法dp。
看到物品数量是30,直接爆搜也不行。。
于是对半分成两部分枚举之后,二分计算贡献。
当然用个map来做个map版本的背包也是兹磁的吧？

时间复杂度

O(2^(n/2) * log(2^(n/2)))

参考代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL v[35];
vector<LL> val1, val2;
int n, w;
void calc(LL *item, int mx, vector<LL> &val){
    for(int i = 0; i < mx; i++){
        LL sum = 0;
        for(int j = 0; j < 20; j++){
            if(i & (1 << j)){
                sum += item[j];
                if(sum > w) break;
            }
        }
        if(sum <= w) val.push_back(sum);
    }
}
int main() {
    val1.clear();
    val2.clear();
    scanf("%d%d", &n, &w);
    for(int i = 0; i < n; i++) scanf("%lld", &v[i]);
    calc(v, 1 << (n / 2), val1);
    calc(&v[n - (n + 1) / 2], 1 << (n - n / 2), val2);
    sort(val2.begin(), val2.end());
    LL ans = 0;
    for(int i = 0; i < val1.size(); i++){
        ans += upper_bound(val2.begin(), val2.end(), w - val1[i]) - val2.begin();
    }
    printf("%lld\n", ans);
    return 0;
}

牛牛找工作

分析

实际上对于每个难度的工作，只有报酬最高的那一种是可能成为答案的，剩下的都可以无视。
由于只有N项工作和M个小伙伴，最多只会出现N+M种难度(能力值)，所以可以把难度和能力值映射到不超过N+M个数上(std通过排序+map来完成)。
对这些难度(能力值)分别求出最高的报酬，再按i从小到大的顺序维护难度(能力值)不超过i的最大报酬。最后输出每个小伙伴对应的能力值以下的最高报酬即可。

时间复杂度

O((N+M)*log(N+M))

参考代码

#include <bits/stdc++.h>
using namespace std;

map<int,int> mp;
int cnt = 0;
int ans[200005];
int d[100005], p[100005];
int val[200005];
int a[100005];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &d[i], &p[i]);
        val[i] = d[i];
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
        val[i + n] = a[i];
    }
    sort(val + 1, val + 1 + n + m);
    for(int i = 1; i <= n + m; i++) {
        if(val[i] != val[i - 1]) {
            cnt++;
            mp[val[i]] = cnt;
        }
    }
    for(int i = 1; i <= n; i++) ans[mp[d[i]]] = max(ans[mp[d[i]]], p[i]);
    for(int i = 2; i <= n + m; i++) ans[i] = max(ans[i], ans[i - 1]);
    for(int i = 1; i <= m; i++)
        printf("%d\n", ans[mp[a[i]]]);
    return 0;
}