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

倒数排列

思路

令给出的排列是,则答案,可以通过样例和直觉猜出来。

参考代码

#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;
}

小易的英语软件

思路

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

参考代码

#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;
}

最大公约数

思路

,这是欧几里得算法。那我们只要实现的计算。 可以直接在输入的时候维护(详见代码)。

参考代码

#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;
}

按位或

思路

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

参考代码

#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序列

思路

我们对序列不断执行rev操作,得到的一系列序列。再依次翻转每个序列的每一位,得到一系列序列

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

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

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

参考代码

#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;
}

序列维护

思路

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

参考代码

#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;
}
#网易##校招##笔试题目##题解##笔经#
全部评论
优秀的01序列这道题的思路有大佬能再仔细讲讲吗?
点赞 回复
分享
发布于 2019-08-03 18:43
非常遗憾,没有弄懂题主“按位或”一题的思路。我将代码调成如下形式以便于查看内部的运算步骤 #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
秋招专场
校招火热招聘中
官网直投
个人感觉序列交换标程有问题, 比如121, 24, 直接排序的话是24121,但是字典序最小的应该是12124。个人认为正确的排序方式应该是 a + b < b + a,其中“+”表示将两个数字拼接起来,比如 121 + 24为12124。
点赞 回复
分享
发布于 2019-08-04 00:25
求py版本
点赞 回复
分享
发布于 2019-08-03 18:16
数字圆环的原理是啥呢?有大佬给讲讲么?
点赞 回复
分享
发布于 2019-08-03 19:53
1到11这个 11个整数 最小字典序列 和sort排序后的结果一样嘛? 有人能解释下嘛? 没搞懂自然数的字典排序
点赞 回复
分享
发布于 2019-08-03 23:32
大佬,能给Java版的上一份吗?跪求
点赞 回复
分享
发布于 2019-08-05 10:53
是dalao wsl
点赞 回复
分享
发布于 2019-08-03 17:47
是dalao wsl
点赞 回复
分享
发布于 2019-08-03 17:48
是真正的大佬,tql
点赞 回复
分享
发布于 2019-08-03 17:48
大佬,wsl
点赞 回复
分享
发布于 2019-08-03 17:50
太强了吧
点赞 回复
分享
发布于 2019-08-03 17:51
真大佬,给跪了
点赞 回复
分享
发布于 2019-08-03 17:51
你是何方的神仙!!!!
点赞 回复
分享
发布于 2019-08-03 17:51
tql
点赞 回复
分享
发布于 2019-08-03 17:57
给大佬递茶
点赞 回复
分享
发布于 2019-08-03 17:57
wsl
点赞 回复
分享
发布于 2019-08-03 17:59
点赞 回复
分享
发布于 2019-08-03 17:59
神啊
点赞 回复
分享
发布于 2019-08-03 18:02
tql
点赞 回复
分享
发布于 2019-08-03 18:02

相关推荐

89 615 评论
分享
牛客网
牛客企业服务