牛客练习23

发表于 | 更新于 | 阅读次数：
本文字数： 5.9k | 阅读时长 ≈ 5 分钟

牛客练习赛23

这次牛客练习赛，都考了一点小技巧。

A 随便模拟一下

链接：https://www.nowcoder.com/acm/contest/156/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

紧张刺激的世界杯正在进行中(在托米的世界线里)，欧洲人托米沉迷于赌球无法自拔。
托米的口袋里有 100 元，50元，20元，10元，5元，2元，1元的纸币，50分，20分，10分，5分，2分，1分的硬币各无限个。
托米计划买下几注 a 元 b 分的彩票，他希望能支出的纸票数量和硬币数量之和最小，他希望你帮助他完成这个任务。同时由于彩票亭不支持找零，托米希望他的支出恰好等于 a 元 b 分

输入描述:

1
第一行输入一个正整数 T下面 T 行每行两个整数 a,b

输出描述:

1
每行输出 13 个正整数 n1 ...n13, 对应题面顺序给出最小化支出纸票数量和硬币数量之和的情况下，每种货币的使用次数，如果有多种方案，输出字典序最大的一种，注意这里字典序是依次比较n1到n13，而不是简单的把 13 个正整数拼接在一起

示例1

输入

复制

1
2
3
 2
1 5
2 4

输出

复制

1
2
 0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 2 0

备注:

1
T=100,0≤ a≤ 109, 0≤ b<100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 #include<bits/stdc++.h>
using namespace std;
int a[7]= {100,50,20,10,5,2,1};
int b[6]= {50,20,10,5,2,1};
int a1[7],b1[6];
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int x,y;
        cin>>x>>y;
        for(int i=0; i<7; i++) {
            a1[i]=x/a[i];
            x=x%a[i];
        }
        for(int i=0; i<6; i++) {
            b1[i]=y/b[i];
            y%=b[i];
        }
        for(int i=0; i<7; i++) {
            printf("%d%c",a1[i],' ');
        }
        for(int i=0; i<6; i++) {
            printf("%d%c",b1[i],i==5?'\n':' ');
        }
    }
    return 0;
}

B

链接：https://www.nowcoder.com/acm/contest/156/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

欧洲人托米非常喜欢数字，他经常在空闲时玩下面的游戏
对于一个数字 n, 托米会随性选中一个数 p, (1 ＜ p <= n), 将 n 拆分成 ,v=n-u,并对 u,v 重复这个过程，直到他有了 n 个 1
1317 为了挑战托米，在每次托米进行划分时，会给托米奖励 u * v 的分数，托米希望你能帮他最大化他的得分。

输入描述:

1
第一行一个正整数 T下面 T 行每行一个正整数 n

输出描述:

1
对于每组数据，输出托米的最大得分

示例1

输入

复制

1
1 5

输出

复制

1
10

备注:

1
T≤ 104, n≤ 109

推公式
2 = 1*1

3 =12 +11;

4=13 +12+1*1;

规律就是 Sn = (n*(n-1))/2;

1
2
3
4
5
6
7
8
9
10
11
12
13
 #include<bits/stdc++.h>
using namespace std;
long long n;

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld",&n);
        printf("%lld\n",(n*(n-1))/2);
    }
    return 0;
}

C

链接：https://www.nowcoder.com/acm/contest/156/C
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

托米完成了1317的上一个任务，十分高兴，可是考验还没有结束
说话间1317给了托米 n 个自然数 a1… an, 托米可以选出一些带回家，但是他选出的数需要满足一些条件
设托米选出来了k 个数 b1,b2… bk, 设这个数列 b 的给值为 b 中所有数按位与的结果，如果你能找到一个整除 b 的最大的 2v,(v≥ 0)， 则设定 v 为这个数列的给价，如果不存在这样的 v，则给价值为 -1, 1317 希望托米在最大化给价的情况下，最大化 k

输入描述:

1
第一行输入一个整数 n, 第二行输入 a1...an

输出描述:

1
第一行输出最大的整数 k, 第二行输出 k 个整数 b1... bk, 按原数列的相对顺序输出 (如果行末有额外空格可能会格式错误)

示例1

输入

复制

1
2
 5
1 2 3 4 5

输出

复制

1
2
 2
4 5

备注:

1
n≤ 105, a1... an < 231

题目毒瘤读了半天

给你一个 n 个数 a1 …an,选几个数 b1…bk 然后全部&后 b=b1&b2…&bk, b&2^v==0, v最大就是当前选的这个b序列的值；

求 V最大的情况下K最大。

题解 ：从最高位为1 &到最低位是1 一路下来就行。v 的值是按位于之后最后一位为 1的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 #include<bits/stdc++.h>
using namespace std;
long long n;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn],x[maxn];
int main() {
    scanf("%d",&n);
    for(int i=0; i<n; i++) {
        scanf("%lld",&a[i]);
    }
    for(int i=0; i<=31; i++) { //预处理下最高位位置的值
        x[i]=1<<i;
    }
    int k=0,flag=0,bi=0;
    ll v=0,m=-1;
    for(int i=31; i>=0; i--) {//从最高为处理到最低位
        int t=0;
        flag=0;
        for(int j=0; j<n; j++) {
            if((a[j]&x[i])==x[i]) {  //把高于最高位的值全部选上
                if(t==0) {
                    flag=a[j];
                } else {
                    flag&=a[j];
                }
                t++;
            }
        }
        int pos=0;
        while(flag>0&&(flag&1)==0) {   //判断v 的位置
            pos++;
            flag>>=1;
        }
        if(pos>m||(pos==m&&t>k)) {   //更新值
            m=pos;
            v=flag<<pos;
            k=t;
        }
    }
    printf("%d\n",k);
    for(int i=0; i<n; i++) {
        if((a[i]&v)==v) {          //把所有能按位于成 v 的全部输出。
            k--;
            printf("%lld%c",a[i],k==0?'\n':' ');
        }
    }
    return 0;
}

有点难懂，看不懂留言。

D

链接：https://www.nowcoder.com/acm/contest/156/D
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

托米没有完成上一个任务，准备施展黑魔法推倒 1317

黑魔法咒语被描述为一个 长为 n 的，仅包含小写英文字母 ‘a’…’i’ 的字符串，在托米所在的星球，魔法造成的每次有效伤害都是来自他的一个子序列，对于每一个 ‘a’… ‘i’ 的排列(共 9! 种)，若作为咒语的子序列出现, 就会造成 1 的伤害

而咒语的总伤害为所有 ‘a’… ‘i’ 的排列造成的伤害值之和，托米能打出多少点的伤害，是否能击败 1317 呢？

输入描述:

1
一行输入一个字符串 s

输出描述:

1
一行输出一个数，表示伤害值

示例1

输入

复制

1
aabcdefghi

输出

复制

1
1

备注:

1
|s| ≤  3000

优雅的暴力。

全排列所有情况，二分查找这种情况在字符串里面可不可行，然后一个个加上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+5;
char ch[maxn];
int n[maxn];
vector<int> v[10];
int dp[maxn][9];
int main() {
    int ans[9]= {0,1,2,3,4,5,6,7,8};
    int k=0;
    do {
        for(int i=0; i<9; i++) {
            dp[k][i]=ans[i];
        }
        k++;
    } while(next_permutation(ans,ans+9));
    cin>>ch;
    int l=strlen(ch);
    for(int i=0; i<l; i++) {
        n[i]=ch[i]-'a';
        v[n[i]].push_back(i);
    }
    int res=0;
    for(int i=0; i<k; i++) {
        int p=-1;
        for(int j=0; j<9; j++) {
            int num=dp[i][j];
            if(upper_bound(v[num].begin(),v[num].end(),p)==v[num].end()) {
                break;
            }
            int t=upper_bound(v[num].begin(),v[num].end(),p)-v[num].begin();
            p=v[num][t];
            if(j==8) {
                res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}