2019-08-05 10:44 已编辑中国戏曲学院算法工程师

关注

网易2020校招笔试编程参考思路和代码

倒数排列

思路

令给出的排列是 $P_{i}$ ，则答案 $Q_{i} = n + 1 - P_{i}$ ，可以通过样例和直觉猜出来。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n ; scanf("%d",&n) ;
    for(int i = 1;i <= n;i++) {
        int x ; scanf("%d",&x) ;
        printf("%d ",n - x + 1) ;
    }
    return 0;
}

小易的英语软件

思路

有多种不同的做法。这里介绍一种比较好理解的：桶排+前缀和。
分数只有 $151$ 种，考虑对于每一种分数开一个桶 $buc_i$ ，表示分数等于 $i$ 的人数，输入的时候就可以搞定。
现在分数不超过 $s$ 的人数，就是求： $buc_0 + buc_1 + \cdots + buc_s$
这个用前缀和可以快速求出。
最后要求输出百分数，这个在纸上推一下就好了。

参考代码

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 10000;

int n, m;
int a[MAXN+1];
int buc[151], pre[151];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ++buc[ a[i] ];
    }
    pre[0] = buc[0];
    for (int i = 1; i <= 150; ++i)
        pre[i] = pre[i - 1] + buc[i];
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int x;
        scanf("%d", &x);
        double ans = 100.0 * (pre[ a[x] ] - 1) / n;
        printf("%.6lf\n", ans);
    }

    return 0;
}

最大公约数

思路

$gcd(a,b) = gcd(b , a \%b)$ ，这是欧几里得算法。那我们只要实现 $a % b$ 的计算。 $a % b$ 可以直接在输入的时候维护（详见代码）。

参考代码

#include<bits/stdc++.h>
using namespace std;
char s[100005];
long long gcd(long long a,long long b)
{
    return a % b == 0 ?b : gcd(b , a % b) ;
}
int main()
{
    scanf("%s",s+1) ;
    long long a ; cin >> a;
    long long b = 0;
    for(int i = 1;s[i] != '\0';i++) {
        b = (b * 10 + s[i] - '0') % a;
    }
    cout << gcd(b , a) ;
    return 0;
}

按位或

思路

对于每一次询问，我们肯定会选择所有 $y$ ，满足 $y\&x==y$ ，即在二进制表达下， $y$ 是 $x$ 的子集。
那么我们可以维护一个数组 $p[i$ ]，表示所有为 $i$ 的子集的数字的Or值是多少。每次插入一个数字，如果它没有重复出现过，就枚举它的超集更新答案。询问的时候只需要看 $p[x]$ 是否等于 $x$ 就好了。

参考代码

#include<bits/stdc++.h>
using namespace std;
int p[131072] ;
int mx = 131071 ;
int q ;
int main()
{
    scanf("%d",&q) ;
    while(q--) {
        int op , x;scanf("%d%d",&op,&x) ;
        if(op == 1) {
            if(p[x] == x) continue ;
            int s = mx ^ x;
            for(int i = s ; i ; i = (i - 1) & s) {
                p[i ^ x] |= x ;
            }
            p[x] = x;
        }
        else {
            if(p[x] == x) puts("YES") ;
            else puts("NO");
        }
    }
    return 0;
}

放置货物

思路

枚举货物放置的左上角，剩下的只需要检查某个矩形里面有没有障碍物。把障碍物看成1，空格看成0，维护二维前缀和，就可以快速查询矩形和。如果矩形和是0则可以放置。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n , m , k;
int a[1005][1005];
int c , d;
void solve()
{
    scanf("%d%d%d",&n,&m,&k);memset(a , 0 , sizeof(a)) ;
    for(int i = 1;i <= k;i++) {
        int x , y;scanf("%d%d",&x,&y);
        a[x][y] = 1;
    }
    scanf("%d%d",&c,&d);
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1] ;
        }
    }
    for(int i = 1;i <= n - c + 1 ; i ++) {
        for(int j = 1;j <= m - d + 1 ; j++) {
            int s = a[i+c-1][j+d-1] - a[i-1][j+d-1] - a[i+c-1][j-1] + a[i-1][j-1] ;
            if(!s) {
                puts("YES") ;return ;
            }
        }
    }
    puts("NO") ; return ;
}
int main()
{
    int t ;scanf("%d",&t) ;
    while(t--) solve();
}

最大最小值

思路

首先注意到答案按顺序不减。
考虑把数字从大到小插入，当前插入数字u，那么假设某个k满足ans[k] <= u，则u和u之前的数字把序列分成了一段段，k要满足k <= 这些段中最长的。这样处理完毕之后再填入处理过程中没有填的位置。

参考代码

#include<bits/stdc++.h>
using namespace std;
multiset<int> st ;
int n , k;
struct num
{
    int v ;
    int id;
}h[100005];
bool cmp(num a,num b)
{
    return a.v < b.v;
}
int L[100005] , R[100005];
int ans[100005];
int main()
{
    scanf("%d",&n) ;
    for(int i = 1;i <= n;i++) {
        scanf("%d",&h[i].v) ;
        h[i].id = i;
    }
    sort(h + 1 , h + n + 1, cmp) ;
    for(int i = 1;i <= n;i++) {
        L[i] = i - 1,R[i] = i + 1; ans[i] = 2e9;
    }
    for(int i = 1;i <= n;i++) {
        int a = h[i].id - L[h[i].id] - 1 , b = R[h[i].id] - h[i].id - 1 ;
        if(a) st.erase(st.find(a));
        if(b) st.erase(st.find(b)) ;
        st.insert(a + b + 1) ;
        L[R[h[i].id]] = L[h[i].id] ; R[L[h[i].id]] = R[h[i].id] ;
        multiset<int>::iterator it = st.end() ; it--;
        ans[*it] = min(ans[*it] , h[i].v) ;
    }
    for(int i = n ; i >= 1;i--){
        if(ans[i] == (2e9)) ans[i] = ans[i + 1];
    }
    for(int i = 1;i <= n;i++) printf("%d ",ans[i]) ;
    return 0;
}

序列交换

思路

只要数组中同时出现了奇数和偶数，那么直接对数组进行排序即可。

参考代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>

const int N = 1e5 + 10;

int a[N];

using namespace std;
int main()
{
    int n;
    cin >> n;
    int odd = 0,even = 0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]%2==0)
            even++;
        else
            odd++;
    }
    if(even>0 && odd>0)
        sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

数字圆环

思路

首先对数组进行排序，除了最后一个数字，都满足相邻两个数字大于自己
对于最后一个数字，交换最后两个数字，判断是否满足条件即可。

参考代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        for (int i = 0;i < n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        swap(a[n-2],a[n-1]);
        bool f = 0;
        for (int i = 0;i < n;i++)
        {
            int pre = (i-1+n)%n;
            int sub = (i+1) % n;
            if (a[pre] + a[sub] <= a[i]) f = 1;
        }
        if (f) puts("NO");
        else
        {
            puts("YES");
        }
    }
    return 0;
}

优秀的01序列

思路

我们对序列 $S$ 不断执行rev操作，得到的一系列序列 $S_{1},S_{2} \dot S_{n}$ 。再依次翻转每个序列的每一位，得到一系列序列 $T_{1},T_{2},\dot T_{n}$

例如"110011"可以生成{"110011","1100","11"}与{"001100","0011","00"}

如果 $T$ 是优秀的，当且仅当 $T$ 是由这两组序列拼接而成，并且第一组序列中最原始的序列 $S$ 不能接第二组序列中的序列。

可以使用dp来维护上述过程。令f[i][0/1]表示前i位是否优秀，且拼接的最后一个01串是不是初始序列 $S$ 。按定义转移即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
char s[1005] , t[1005];
int h[1005];
const int base = 773117 , mod = 1e9 + 7;
int pr[1005];
int s1[1005] , s2[1005] , len;
int pos[1005];
int n , m;
int ghash(int l,int r)
{
    return ((h[r] - 1LL*h[l-1]*pr[r-l+1]) % mod + mod ) % mod;
}
int dp[1005][2];
void solve()
{
    scanf("%s",s+1);
    scanf("%s",t+1);
    n = strlen(s + 1) , m = strlen(t + 1) ;
    for(int i = 1;i <= m;i++) h[i] = (1LL * h[i - 1] * base + t[i] - '0') % mod;
    int pc = 0;len = 0;
    for(int i = 1;i <= n;i++) {
        if(s[i] != s[i - 1]) {
            int h1 = 0 , h2 = 0;
            for(int j = i;j <= n;j++) {
                h1 = (1LL * h1 * base + s[j] - '0') %mod;
                h2 = (1LL * h2 * base + 1 + '0' - s[j]) % mod;
            }
            if(!pc) {
                ++len ; s1[len] = h1 ; s2[len] = h2;
            }
            else {
                ++len ; s1[len] = h2 ; s2[len] = h1 ;
            }
            pos[len] = (n - i + 1) ;
            pc ^= 1;
        }
    }
    memset(dp , 0 , sizeof(dp)) ; dp[0][1] = 1;
    for(int i = 1;i <= m;i++) {
        if(i >= pos[1] && ghash(i - pos[1] + 1 , i) == s1[1] && (dp[i - pos[1]][0] || dp[i - pos[1]][1])) dp[i][1] = 1;
        for(int j = 2;j <= len;j++) {
            if(i >= pos[j] && ghash(i - pos[j] + 1 , i) == s1[j] && (dp[i - pos[j]][0] || dp[i - pos[j]][1])) {dp[i][0] = 1;break;}
        }
        for(int j = 1;j <= len;j++) {
            if(i >= pos[j] && ghash(i - pos[j] + 1 , i) == s2[j] && dp[i - pos[j]][0]) {dp[i][0] = 1;break;}
        }
    }
    if(dp[m][0] || dp[m][1]) puts("YES");
    else puts("NO");
    return ;
}
int main()
{
    int t;scanf("%d",&t) ;
    pr[0] = 1;
    for(int i = 1;i <= 1000;i++) pr[i] = 1LL * pr[i - 1] * base % mod;
    while(t--) solve() ;
    return 0;
}

序列维护

思路

注意到如果 $a_{i} \leq a_{j}$ ，那么不管怎么操作都有 $a_{i} \leq a_{j}$ 。
于是把数字从小到大排序后，每次询问就二分出对应的位置，并把后面的数字全部减一。具体实现可以用树状数组或者更高级的数据结构。

参考代码

#include<bits/stdc++.h>
using namespace std;
int c[200005];
int n , q;
inline int lowbit(int x)
{
    return x & (-x) ;
}
void add(int x)
{
    while(x <= n) {
        c[x]++ ; x += lowbit(x) ;
    }
}
int query(int x)
{
    int ans = 0;
    while(x) {
        ans += c[x] ; x -= lowbit(x) ;
    }
    return ans;
}
int a[200005];
int main()
{
    scanf("%d%d",&n,&q) ;
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]) ;
    sort(a + 1 , a + n + 1) ;
    while(q--) {
        int x ; scanf("%d",&x) ;
        if(x > a[n] - query(n)) {puts("0");continue ;}
        int l = 1 , r = n;
        while(l < r) {
            int mid = (l + r >> 1) ;
            if(a[mid] - query(mid) >= x) r = mid ;
            else l = mid + 1;
        }
        printf("%d\n",n - l + 1) ;
        add(l) ;
    }
    return 0;
}

#网易##校招##笔试题目##题解##笔经#

全部评论

推荐最新楼层

wykxwyc

网易互娱_互动娱乐事业群_游戏研发工程师

优秀的01序列这道题的思路有大佬能再仔细讲讲吗？

点赞回复分享

发布于 2019-08-03 18:43

岚匀

河北工业大学 Java

非常遗憾，没有弄懂题主“按位或”一题的思路。我将代码调成如下形式以便于查看内部的运算步骤 #include<cstdio> #include<iostream> #include<bitset> using namespace std; int p[10] = {0}; int mx = 10 ; int q ; int main() { scanf("%d",&q) ; while(q--) { int op , x;scanf("%d%d",&op,&x) ; if(op == 1) { bitset<4> b_x(x); cout << "x = " << b_x << endl; if(p[x] == x){ printf("p[%d] == %d", x, x); continue; } int s = mx ^ x; bitset<4> b_s(s); bitset<4> b_mx(mx); cout << "mx ^ x = "<< b_mx << " ^ " << b_x << " = " << b_s << endl; for(int i = s ; i ; i = (i - 1) & s) { bitset<4> b_i(i); bitset<4> b_pbefore(p[i ^ x]); bitset<4> b_ix(i ^ x); p[i ^ x] |= x ; bitset<4> b_pafter(p[i ^ x]); cout << "p[i ^ x] = p[i ^ x] | x ="<< "p[ "<< b_ix<<" ] | "<< b_x <<" = " << "p[ "<< (i ^ x) <<" ] | "<< x <<" = "<< b_pbefore << " | " << b_x << " = " << b_pafter<< endl; } p[x] = x; } else { if(p[x] == x) puts("YES") ; else puts("NO"); } } return 0; } 然后得到了如下输出： 10 1 4 x = 0100 mx ^ x = 1010 ^ 0100 = 1110 p[i ^ x] = p[i ^ x] | x =p[ 1010 ] | 0100 = p[ 10 ] | 4 = 1001 | 0100 = 1101 p[i ^ x] = p[i ^ x] | x =p[ 1000 ] | 0100 = p[ 8 ] | 4 = 0000 | 0100 = 0100 p[i ^ x] = p[i ^ x] | x =p[ 1110 ] | 0100 = p[ 14 ] | 4 = 0000 | 0100 = 0100 p[i ^ x] = p[i ^ x] | x =p[ 1100 ] | 0100 = p[ 12 ] | 4 = 0000 | 0100 = 0100 p[i ^ x] = p[i ^ x] | x =p[ 0010 ] | 0100 = p[ 2 ] | 4 = 0000 | 0100 = 0100 p[i ^ x] = p[i ^ x] | x =p[ 0000 ] | 0100 = p[ 0 ] | 4 = 0000 | 0100 = 0100 p[i ^ x] = p[i ^ x] | x =p[ 0110 ] | 0100 = p[ 6 ] | 4 = 0000 | 0100 = 0100 2 5 NO 1 9 x = 1001 mx ^ x = 1010 ^ 1001 = 0011 p[i ^ x] = p[i ^ x] | x =p[ 1010 ] | 1001 = p[ 10 ] | 9 = 1011 | 1001 = 1011 p[i ^ x] = p[i ^ x] | x =p[ 1011 ] | 1001 = p[ 11 ] | 9 = 0000 | 1001 = 1001 p[i ^ x] = p[i ^ x] | x =p[ 1000 ] | 1001 = p[ 8 ] | 9 = 0100 | 1001 = 1101 1 15 x = 1111 mx ^ x = 1010 ^ 1111 = 0101 p[i ^ x] = p[i ^ x] | x =p[ 1010 ] | 1111 = p[ 10 ] | 15 = 1010 | 1111 = 1111 p[i ^ x] = p[i ^ x] | x =p[ 1011 ] | 1111 = p[ 11 ] | 15 = 1001 | 1111 = 1111 p[i ^ x] = p[i ^ x] | x =p[ 1110 ] | 1111 = p[ 14 ] | 15 = 0100 | 1111 = 1111 2 4 YES 1 11 x = 1011 mx ^ x = 1010 ^ 1011 = 0001 p[i ^ x] = p[i ^ x] | x =p[ 1010 ] | 1011 = p[ 10 ] | 11 = 1101 | 1011 = 1111 2 10 NO 2 7 NO 2 9 YES 2 4 YES 我不清楚int s = mx ^ x;一句的含义。不清楚如下循环的含义 for(int i = s ; i ; i = (i - 1) & s) { p[i ^ x] |= x ; } 以及上述循环为什么在4输入时，将p[10, 8, 14, 12, 2, 0, 6]依次赋值，后者的值是前者对x的异或。

点赞回复分享

发布于 2019-08-04 16:30

浮梦逍遥

University of Melbourne C++

个人感觉序列交换标程有问题，比如121， 24，直接排序的话是24121，但是字典序最小的应该是12124。个人认为正确的排序方式应该是 a + b < b + a，其中“+”表示将两个数字拼接起来，比如 121 + 24为12124。

点赞回复分享

发布于 2019-08-04 00:25

努力写论文呀

中国原子能科学研究院算法工程师

求py版本

点赞回复分享

发布于 2019-08-03 18:16