头条,京东2019笔试题

头条,京东2019笔试题

1.头条1-AcWing 677. 找零

Z国的货币系统包含面值1元、4元、16元、64元共计四种硬币,以及面值1024元的纸币。

现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币。

输入格式

共一行,包含整数N。

输出格式

共一行,包含一个数,表示最少收到的硬币数。

数据范围

0<N≤1024

输入样例:

200

输出样例:

17

样例解释

花200,需要找零824块,找12个64元硬币,3个16元硬币,2个4元硬币即可。

分析:贪心水题,先考虑用大面值的换即可

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e3 + 6;

int coin[4] = {64, 16, 4, 1};

int main(){
    int n; sd(n);
    n = 1024 - n;
    int ans = 0;
    for(int i = 0;i < 4;++i){
        ans += n / coin[i];
        n %= coin[i];
    }
    cout << ans << endl;

    return 0;
}

2.头条2-AcWing 678. 万万没想到之聪明的编辑

我叫王大锤,是一家出版社的编辑。

我负责校对投稿来的英文稿件,这份工作非常烦人,因为每天都要去修正无数的拼写错误。

但是,优秀的人总能在平凡的工作中发现真理。

我发现了一个发现拼写错误的捷径:

1.三个同样的字母连在一起,一定是拼写错误,去掉一个的就好啦:比如 helllo -> hello

2.两对一样的字母(AABB型)连在一起,一定是拼写错误,去掉第二对的一个字母就好啦:比如 helloo -> hello

3.上面的规则优先“从左到右”匹配,即如果是AABBCC,虽然AABB和BBCC都是错误拼写,应该优先考虑修复AABB,结果为AABCC

我特喵是个天才!

我在蓝翔学过挖掘机和程序设计,按照这个原理写了一个自动校对器,工作效率从此起飞。

用不了多久,我就会出任CEO,当上董事长,迎娶白富美,走上人生巅峰,想想都有点小激动呢!

……

万万没想到,我被开除了,临走时老板对我说:“做人做事要兢兢业业、勤勤恳恳、本本分分,人要是行,干一行行一行。一行行行行行;要是不行,干一行不行一行,一行不行行行不行。”

我现在整个人红红火火恍恍惚惚的……

请听题:请实现大锤的自动校对程序

输入格式

第一行包括一个数字N,表示本次用例包括多少个待校验的字符串。

后面跟随N行,每行为一个待校验的字符串,由大写英文字母和小写英文字母构成。

输出格式

N行,每行包括一个被修复后的字符串。

数据范围

N≤1000
字符串长度≤1000000

输入样例:

2
helloo
wooooooow

输出样例:

hello
woow

分析:水模拟

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e6 + 66;

char str[maxn];

int main(){
    int n; sd(n);
    while(--n >= 0){
        scanf("%s", str);
        int ki = 0;
        for(int i = 0;str[i];++i){
            str[ki++] = str[i];
            if(ki >= 3 && str[ki - 1] == str[ki - 2] && str[ki - 2] == str[ki - 3]) ki--;
            if(ki >= 4 && str[ki - 1] == str[ki - 2] && str[ki - 3] == str[ki - 4]) ki--;
        }
        for(int i = 0;i < ki;++i){
            printf("%c", str[i]);
        }
        puts("");
    }

    return 0;
}

3.头条3-AcWing 679. 奖品分配

有n个人参加编程比赛,比赛结束后每个人都得到一个分数;现在所有人排成一圈(第一个和第n个相邻)领取奖品,要求:

1、如果某个人的分数比左右的人高,那么奖品数量也要比左右的人多;

2、每个人至少得到一个奖品;

问最少应该准备多少个奖品。

输入格式

第一行是整数T,表示测试样例个数。

每个测试样例的第一行是一个整数n,表示参加比赛的人数。

第二行是n个正整数a[i],表示从第1个人到第n个人的分数。

输出格式

对每个测试样例,输出应该准备的最少奖品,每个结果占一行。

数据范围

1≤T≤10
0<n<100000
0<a[i]<100000

输入样例

2
2
1 2
4
1 2 3 3

输出样例:

3
8

分析:排序:考虑成绩最低的那个小朋友,它肯定分的糖果是1,然后再考虑倒数第2的小朋友,判断它是否把旁边的小朋友分数高,如果高的话,取 + 1个糖果即可,以此处理到结束。

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

int arr[maxn];
int ret[maxn];
int pos[maxn];
int ans;

int main(){
    int t; sd(t);
    while(--t >= 0){
        int n; sd(n);
        ans = 0;
        for(int i = 0;i < n;++i){
            sd(arr[i]);
            ret[i] = 0;
            pos[i] = i;
        }
        sort(pos, pos + n, [](int a, int b) -> bool {
            return arr[a] < arr[b];
        });
        for(int i = 0;i < n;++i){
            int id = pos[i];
            int res = 1;
            if(arr[id] > arr[(id - 1) % n]){
                res = max(res, ret[(id - 1 + n) % n] + 1);
            }
            if(arr[id] > arr[(id + 1) % n]){
                res = max(res, ret[(id + 1 + n) % n] + 1);
            }
            ret[id] = res;
            // cout << "---id::  " << id << " ---res::  " << res << endl;
            ans += ret[id];
        }
        cout << ans << endl;
    }

    return 0;
}

4.头条4-AcWing 680. 剪绳子

有N根绳子,第i根绳子长度为Li,现在需要M根等长的绳子,你可以对N根绳子进行任意裁剪(不能拼接),请你帮忙计算出这M根绳子最长的长度是多少。

输入格式

第一行包含2个正整数N、M,表示原始绳子的数量和需求绳子的数量。

第二行包含N个整数,其中第 i 个整数Li表示第 i 根绳子的长度。

输出格式

输出一个数字,表示裁剪后最长的长度,保留两位小数。

数据范围

1≤N,M≤100000
0<Li<1e9

输入样例:

3 4
3 5 4

输出样例:

2.50

样例解释

第一根和第三根分别裁剪出一根2.50长度的绳子,第二根剪成2根2.50长度的绳子,刚好4根。

分析:二分。答案长度有明显的单调性,长度越短的能切出的绳子数量越多,因此二分答案,判断是否可以切成即可,判断方法枚举每一个绳子即可。

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;
const double eps = 1e-4;

int arr[maxn];
int n, m;

bool check(double x){
    int res = 0;
    for(int i = 0;i < n;++i){
        res += static_cast<int >(arr[i] / x);
    }
    return res >= m;
}

int main(){
    sd(n), sd(m);
    int maxx = -inf;
    for(int i = 0;i < n;++i){
        sd(arr[i]);
        maxx = max(maxx, arr[i]);
    }
    double l = 0.0, r = maxx;
    while(r - l > eps){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2f\n", r);

    return 0;
}

5.京东1-AcWing 681. 疏散人群

体育场突然着火了,现场需要紧急疏散,但是过道真的是太窄了,同时只能容许一个人通过。

现在知道了体育场的所有座位分布,座位分布图是一棵树,已知每个座位上都做了一个人,安全出口在树的根部,也就是1号结点的位置上。

其他结点上的人每秒都能向树根部前进一个结点,但是除了安全出口以外,没有任何一个结点能够同时容纳两个及以上的人。

这就需要一种策略来使得人群尽快疏散。

请问在采取最优策略的情况下,体育场最快可以在多长时间内完成疏散。

输入格式

第一行包含整数n,表示树的结点数量。

接下来n-1行,每行包含两个整数x和y,表示x和y结点之间存在一条边。

输出格式

输出一个正整数表示最短疏散时间。

数据范围

1≤n≤105
1≤y≤x≤n

输入样例:

6
2 1
3 2
4 3
5 2
6 1

输出样例:

4

分析:考虑根节点子节点位置人流量。因为除了根节点其他节点都只能容纳一个人,那么后面的人必须要到根节点的某一个子节点然后再到根节点,因为根节点的子节点也是只能容纳一个人,因为每一步会使得根节点的子节点上的人离开,因此就是根节点的每个子树节点数的最大值

1)DFS – 可能会超时

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 6;

vector<int > v[maxn];
int vis[maxn];

int dfs(int s){
    vis[s] = 1;
    int res = 1;
    for(int i = 0;i < v[s].size();++i){
        int nxt = v[s][i];
        if(!vis[nxt])
            res += dfs(nxt);
    }
    return res;
}

int main(){
    int n; sd(n);
    for(int i = 0;i < n - 1;++i){
        int a, b; sd(a), sd(b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int ans = -inf;
    vis[1] = 1;
    for(int i = 0;i < v[1].size();++i){
        ans = max(ans, dfs(v[1][i]));
    }
    cout << ans << endl;

    return 0;
}

2)BFS

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 6;

vector<int > v[maxn];
int vis[maxn];

int bfs(int s){
    queue<int > q;
    while(!q.empty()) q.pop();
    q.push(s);
    int ret = 0;
    while(!q.empty()){
        int now = q.front();
        ret++;
        vis[now] = 1;
        q.pop();
        for(int i = 0;i < v[now].size();++i){
            int nxt = v[now][i];
            if(!vis[nxt])
                q.push(nxt);  
        }
    }
    return ret;
}

int main(){
    int n; sd(n);
    for(int i = 0;i < n - 1;++i){
        int a, b; sd(a), sd(b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vis[1] = 1;
    int ans = 0;
    for(int i = 0;i < v[1].size();++i){
        ans = max(ans, bfs(v[1][i]));
    }
    cout << ans << endl;

    return 0;
}

6.京东2-AcWing 682. 丢失的序列

有一个含有 n 个数字的序列,每个数字的大小是不超过200的正整数,同时这个序列满足以下条件:

  1. a1≤a2
  2. an≤an−1,此时n大于2。
  3. ai≤max(ai−1,ai+1)

但是很不幸的是,在序列保存的过程中,有些数字丢失了,请你根据上述条件,计算可能有多少种不同的序列可以满足以上条件。

输入格式

第一行包含整数n,表示序列长度。

第二行包含 n 个非负整数,如果数字为 0 说明这个数字丢失了,其他数字均在1-200之间。

输出格式

输出一个整数,表示满足条件的序列数对998244353取模后的值。

数据范围

3≤n≤10000

输入样例:

3
2 0 1

输出样例:

1

分析:dp。先画一下图会发现,对于前面两个点直接的关系,可以推出后面的情况(走向)。用f(i, j, 0)表示前面点\( a_{i – 1} > a_{i} \)的情况集合,其属性就是集合中的元素(方案个数),同样的用f(i, j, 1)表示\( a_{i – 1} = a_{i} \)的方案个数,f(i, j, 2)表示小于的方案个数,其中j都是表示\( a_{i} = j \)则

转移方程很容易得到:

\( f(i, j, 2) = f(i – 1, j’, 2) + f(i – 1, j’, 0) + f(i – 1, j’, 1) – 0 1 2, j + 1 \leq j’ \leq 200 \)

\( f(i, j, 1) = f(i – 1, j’, 2) + f(i – 1, j’, 0) + f(i – 1, j’, 1) – 0 1 2,j’ = j \)

\( f(i, j, 0) = f(i – 1, j’, 0) + f(i – 1, j’, 1) – 01,1 \leq j’ \leq j \)

然后如何快速的求解中间的和,可以采用前缀和的方式,维护两个前缀和

\( sum1[i] : 1 – 200中的dp[now][i][0] + dp[now][i][1] \)
\( sum2[i]: 1 – 200中的dp[now][i][0] + dp[now][i][1] + dp[now][i][2] \)

now表示的是当前便利到第几个了,前缀和要实时的更新

答案根据题意容易知道是:\( f[n][][0] + f[n][][1] \)

具体数值要看最后一个数是不是0,如果是0的话,就是1 – 200,否则就是这个数arr[n]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 6, M = 206;
const int mod = 998244353;

ll dp[N][M][6];
ll arr[N];
ll sum1[N];
ll sum2[N];

int main(){
    int n; sd(n);
    for(int i = 1;i <= n;++i){
        sld(arr[i]);
    }
    for(int i = (arr[1] ? arr[1] : 1);i <= (arr[1] ? arr[1] : 200);++i){
        for(int j = (arr[2] ? arr[2] : 1);j <= (arr[2] ? arr[2] : 200);++j){
            if(i == j) dp[2][j][1]++;
            else if(j > i) dp[2][j][2]++;
        }
    }
    for(int i = 1;i <= 200;++i){
        sum1[i] = sum1[i - 1] + dp[2][i][0] + dp[2][i][1];
        sum2[i] = sum2[i - 1] + dp[2][i][0] + dp[2][i][1] + dp[2][i][2];
    }
    for(int i = 3;i <= n;++i){
        for(int j = (arr[i] ? arr[i] : 1);j <= (arr[i] ? arr[i] : 200);++j){
            dp[i][j][0] = (sum1[200] - sum1[j]) % mod;
            dp[i][j][1] = (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) % mod;
            dp[i][j][2] = sum2[j - 1] % mod;
        }
        for(int j = 1;j <= 200;++j){
            sum1[j] = sum1[j - 1] + dp[i][j][0] + dp[i][j][1];
            sum2[j] = sum2[j - 1] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2];
        }
    }
    // cout << dp[3][1][0] << " " << dp[3][1][1] << endl;
    ll res = 0;
    for(int i = (arr[n] ? arr[n] : 1);i <= (arr[n] ? arr[n] : 200);++i){
        res = (res + dp[n][i][0] + dp[n][i][1]) % mod;
    }
    cout << (res + mod) % mod << endl;

    return 0;
}
0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

6 − 1 =