牛客寒假算法基础集训营6 题解

发表于 | 分类于 | 阅读次数:

最后一场福利局，签到题好多。

A.出题

如果只考虑7 8 9的话，n道题能凑的分数是$[7*n,9*n]$，加上6的话就是$[6*n,9*n]$。
所以，如果$m \in [7*n,9*n]$，就不需要6，如果$m >9*n$，则无截，否则就是$m*7-n$.

题目连接

描述

小B准备出模拟赛。
她把题目按难度分为四等，分值分别为6,7,8,9。
已知小B共出了m道题，共n分。
求小B最少出了多少道6分题。

输入

两个正整数$n,m$ $n,m \leq 10^{12}$

输出

一个数，表示答案。
若无解，输出”jgzjgzjgz”。

样例输入

1
2
3
34 5
32 5
5 1

样例输出

1
2
3
1
3
jgzjgzjgz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
typedef long long ll;

int main(){
    ll n,m;
    cin>>n>>m;
    if(n>=7*m&&n<=9*m) cout<<0<<endl;
    else if(n>9*m||n<6*m) cout<<"jgzjgzjgz"<<endl;
    else cout<<m*7-n<<endl;
    return 0;
}

B.煤气灶

这道题用C写求根公式的话中途会爆long long，所以因该用二分来写。
能py当然是py.
暴力好像也过了。

题目连接

描述

小j开始打工，准备赚钱买煤气灶。
第一天，小j的工资为n元，之后每天他的工资都比前一天多d元。
已知煤气灶需要m元，求小j最少工作几天才能买到煤气灶。

输入

四个整数 n,m,d,x
分别表示小j第一天的工资，煤气灶的价格，工资每天的增长量，答案不超过x
$0≤n,d≤10^9,n+d>0$
$1≤m≤10^{18}$
$1≤x≤10^9$

输出

一个数表示答案

样例输入

1
10 100 20 100

样例输出

1
2
4
TRDD Got lost...TAT
1
2
3
4
5
6
7
8
import math
n, m, d, x = map(int, input().split())
if d==0:
    ans=math.ceil(m/n)
else:
    ans=math.ceil(((d-2*n)+math.sqrt((2*n-d)*(2*n-d)+8*d*m))/2/d)
print(ans)

C.项链

排序贪心，每次先涂喜爱度大的。

题目连接

描述

小B想给她的新项链染色。
现在有m种颜色，对于第i种颜色，小B有a_i单位的颜料，每单位颜料可以染项链的一个珠子；
同时，小B对于第i种颜色的喜爱度为b_i。
已知项链有n个珠子，求染色后每个珠子的颜色的喜爱度之和的最大值。
(每个珠子只能至多被染一次，不被染色则喜爱度为0)

输入

第一行两个数$n,m$
第二行m个数$a_i$
第三行m个数$b_i$
$1 \leq n,m \leq10^5,0 \leq a_i,b_i \leq 10^6$

输出

一个数表示答案

样例输入

1
2
3
4
5
6
5 3
1 2 3
3 2 1
5 3
1 2 1
3 2 1

样例输出

1
2
9
8
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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e5+5;
typedef long long ll;

struct node{
    int ai,bi;
    bool operator<(node e) const{
        return bi>e.bi;
    }
}a[N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,1,m) scanf("%d",&a[i].ai);
    rep(i,1,m) scanf("%d",&a[i].bi);

    sort(a+1,a+1+n);
    ll ans=0;
    rep(i,1,m){
        if(n>a[i].ai){
            ans+=a[i].ai*a[i].bi;
            n-=a[i].ai;
        }
        else{
            ans+=a[i].bi*n;
            break;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

D.美食

从1开始，每次先两口两口把自己的吃完，如果是奇数（吃完剩一口），就看下一个有没有食物，有的话就跟着下一块一起吃一次。
因为如果下一个也是奇数，那么相当于多了吃了一次，如果写一个是偶数，那么就这两块而言，次数是一样的，但是下一块和下下快还可能凑一个出来，所以这样永远不会亏。

题目连接

描述

小B喜欢美食。
现在有n个美食排成一排摆在小B的面前，依次编号为1..n，编号为i的食物大小为 a[i]，即足够小B吃a[i]口。
小B每次会吃两口，这两口要么是编号相同的美食，要么是编号之差的绝对值为1的美食。
小B想知道，她最多能吃几次？

输入

第1行一个正整数n，表示美食个数
接下来n行，第i行一个整数a[i]，表示编号为i的美食的大小。
$1 \leq n \leq 10^5,0 \leq a[i] \leq 10^9$

输出

一个数表示小B最多吃几次。

样例输入

1
2
3
4
5
4
1
5
7
8

样例输出

1
10
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;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e5+5;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    int a[N],n;ll ans=0;
    cin>>n;
    rep(i,1,n) cin>>a[i];

    rep(i,1,n){
        if(a[i]&1&&i<n&&a[i+1]) { //看是否是奇数且下一个是不是0
            ans+=a[i]/2+1;
            a[i+1]--;
        }
        else
            ans+=a[i]/2;
    }

    cout<<ans<<endl;
    return 0;
}

E.海啸

比赛的时候看成每次询问d都不一样，然后就跳过了…
我们用$O(n*m)$预处理出前缀和，即：a[i][j]为$1 \leq x \leq i\&\&1 \leq y \leq j$，中不会被淹没的。详解看这里
这样就可以每次询问都O(1)算出来。
但是这道题开二维数组是开不下的，所以我们压缩一下，因为$1≤n×m≤10^6$,所以我们用a[i*m+j]表示a[i][j].
当然也可以用vector动态开。

题目连接

描述

有一个沿海地区，可以看作有n行m列的城市，第i行第j列的城市海拔为h[i][j]。
由于沿海，所以这个地区经常会发生海啸。
海啸发生时，部分城市会被淹没，具体来说，海水高度会达到d，因此海拔低于d的城市都会被淹没。
现在有q次询问，每次问你一个矩形区域中，有多少城市不会被淹没。

输入

第一行三个整数n,m,d，具体含义见题目描述。
接下来n行，每行m个整数，其中第i行第j列的整数为h[i][j]，具体含义见题目描述。
第n+2行一个整数q，表示询问数。
接下来q行，每行四个整数a,b,x,y，
表示询问从第a行第b列到第x行第y列的矩形地区中，有多少地区不会被淹没。
即有多少个i,j，满足
$a≤i≤x,b≤j≤y$ ，且 $h[i][j]≥d$。
$1≤n×m≤10^6$
$1≤q≤10^5$
$0≤d,h[i][j]≤10^9 $
$1≤a≤x≤n,1≤b≤y≤m$

输出

共q行，第i行一个整数，表示第i个询问的答案。

样例输入

1
2
3
4
5
6
7
3 3 3
1 2 3
2 1 5
4 3 2
2
1 2 2 3
2 1 3 3

样例输出

1
2
2
3
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
#include<iostream>
#include<string>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
 
const int N=3e6+5;
typedef long long ll;
 
int Map[N]={0};
 
int main()
{
    ios::sync_with_stdio(false);
    int n,m,d;
    cin>>n>>m>>d;
 
    rep(i,1,n){
        rep(j,1,m){
            cin>>Map[i*(m+1)+j];
            Map[i*(m+1)+j]=Map[i*(m+1)+j]>=d;
        }
    }
 
    rep(i,1,n)
        rep(j,1,m)
            Map[i*(m+1)+j]+=Map[(i-1)*(m+1)+j]+Map[i*(m+1)+j-1]-Map[(i-1)*(m+1)+j-1];
 
    int Q,a,b,x,y;
    cin>>Q;
    while(Q--){
        cin>>a>>b>>x>>y;
        cout<<Map[x*(m+1)+y]-Map[(a-1)*(m+1)+y]-Map[x*(m+1)+b-1]+Map[(a-1)*(m+1)+b-1]<<endl;
    }
 
    return 0;
}

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
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))

const int N=1e6+5;
typedef long long ll;

vector<vector<int> > Map;

int main()
{
    ios::sync_with_stdio(false);
    int n,m,d,x;
    cin>>n>>m>>d;

    Map.push_back(vector<int>());
    rep(i,0,m) Map[0].push_back(0);
    rep(i,1,n){
        Map.push_back(vector<int>());
        Map[i].push_back(0);
        rep(j,1,m){
            cin>>x;
            Map[i].push_back(x>=d);
        }
    }

    rep(i,1,n)
        rep(j,1,m)
            Map[i][j]+=Map[i-1][j]+Map[i][j-1]-Map[i-1][j-1];

    int Q,a,b,y;
    cin>>Q;
    while(Q--){
        cin>>a>>b>>x>>y;
        cout<<Map[x][y]-Map[a-1][y]-Map[x][b-1]+Map[a-1][b-1]<<endl;
    }

    return 0;
}

F.石头剪刀布

玩去了，待补…

题目连接

描述

wzms 今年举办了一场剪刀石头布大赛，bleaves 被选为负责人。
比赛共有$2^n$ 个人参加， 分为 $n$ 轮，
在每轮中，第 1 位选手和第 2 位选手对战，胜者作为新的第 1 位选手，
第 3 位和第 4 位对战，胜者作为新的第 2 位选手，以此类推。
bleaves 调查得知，每个人都有其偏爱决策，每个人在每一次对战中都会使用他的偏爱决策。
如果一次对战的双方的偏爱决策相同，那么这次对战就永远不会结束，所以 bleaves 不希望这种情况发生。
现在 bleaves 知道了每个人的偏爱决策，但她不知道如何安排初始的次序，使得上面的情况不会发生，你能帮帮她吗？

输入

一行三个整数 R,P,S ，表示偏爱石头，布，剪刀的人数分别为 R,P,S 。
全部的输入数据满足：
$R+P+S=2^n，1≤n≤20$

输出

如果无解，输出 IMPOSSIBLE ；
否则输出一个长度为 R+P+S 的字符串，第 i 个字符表示初始时第 i 位选手的偏爱决策，
如果有多种方案，输出字典序最小的。

样例输入

1
2
3
1 1 0
2 0 0
1 1 2

样例输出

1
2
3
PR
IMPOSSIBLE
PSRS
1
//待补...

G.区间或和

比赛不知道为什么看成了异或和，浪费了一个小时de不存在的bug，A了心态也崩了，就玩去了。
把l和r的二进制处理出来，对于第i位，如果l 或 r是1，则ans这一位也是1。如果不是，就看l的这个0需要多少个数之后才会变成1，再和r-l比较。
怎么看0需要多少个数之后才会变成1： 例如一个二进制数是 100110，那么第1个0就需要$2^4-(0100)_B$,也就是$(10000)_B-(0100)_B$.

题目连接

描述

求a|(a+1)|(a+2)|…|(b-1)|b。

其中|表示按位或。

输入

多组输入，每行两个数表示a和b
输入不超过10000行，
$0≤a,b≤10^{18}，a≤b$

输出

对于每组输入，输出一个数a|(a+1)|(a+2)|…|(b-1)|b。

样例输入

1
2
3
4
5
99 109
68 77
55 66
34 43
1111234 1114321

样例输出

1
2
3
4
5
111
79
127
47
1179647
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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
typedef long long ll;
 
int main() {
    ll l,r;
    int a[100],b[100],c[100],p1,p2;
    while(cin>>l>>r) {
        CRL(a,0);  CRL(b,0);  CRL(c,0);
        p1=p2=1;
        
        //处理出二进制
        ll tl=l;
        while(tl) {
            a[p1++]=tl%2;
            tl>>=1;
        }
        tl=r;
        while(tl) {
            b[p2++]=tl%2;
            tl>>=1;
        }
 
        int Len=max(p1,p2);
        ll sum=0;
        //逐位比较
        rep(i,1,Len) {
            if(a[i]||b[i]) c[i]=1;
            else
                c[i]=((1LL<<i)-sum<=r-l);
 
            sum+=a[i]*(1LL<<(i-1LL));
        }
 
        //把c数组转化成10进制，注意1要用long long ，即1LL
        ll ans=0;
        rep(i,1,Len)
            ans+=c[i]*(1LL<<(i-1LL));
        cout<<ans<<endl;
    }
    return 0;
}

H.肥猪

待补…

题目连接

描述

小B来到了一个异世界，成为了肥猪之王。
在这个异世界，共有n种肥猪，编号分别为1，…，n。
小B希望集齐这n种肥猪。
召集肥猪有两种方式：

  1. 花费a[i]的金币召唤一只编号为i的肥猪。
  2. 花费x的金币使所有已召集的肥猪进化。
    即编号为i的肥猪编号变成i+1，特殊的，编号为n的肥猪编号变成1。

请问小B最少要花多少金币才能集齐n种肥猪。

输入

第一行两个正整数n,x
接下来n行，第i行一个正整数a[i].
$1≤n≤2000,1≤x,a[i]≤10^9$

输出

一个数表示答案

样例输入

1
2
3
4
5
6
7
8
2 10
1
20
4 10
1
2
3
4

样例输出

1
2
12
10
1
//待补

I.wzoj

待补…

题目连接

描述

bleaves 最近在 wzoi 上面做题。
wzoi 的题目有两种，一种是 noip 题，一种是省选题。
bleaves 的做题方式很特别。每一天，她可能会看一道题目，这时她会选择题目种类，然后 wzoi 会在选定种类中随机扔给她一道她还没看过的题，她会把这道题看一遍，然后存在脑子里慢慢思考；她也有可能写题，这时她一定会写没写过的题中看的时间最迟的一题(如果不存在没写过的且没看过的题，她就不能写题)。
wzoi 每天会有一个推荐的题目种类，
如果 bleaves 看一道题目：如果种类和推荐的相同，那么这道题目最大得分为10，否则为5
如果 bleaves 写一道题目：如果种类和推荐的相同，那么这道题目得分为最大得分，否则为最大得分-5
假如 bleaves 现在还没看过任何一题，并且她知道了 wzoi 接下来一些天每天推荐的种类，问她在这些天的最大得分。

输入

一行一个01串 s ，|s| 表示天数，$s_i=0$表示 wzoi 第 i 天推荐 noip 题， $si=1$ 表示 wzoi 第 i 天推荐省选题。

输出

一行一个整数最大得分。

样例输入

1
2
3
0011
0101
0110

样例输出

1
2
3
20
10
20
1
//待补...

J.迷宫

BFS，倒是没什么说的。

题目连接

描述

你在一个 n 行 m 列的网格迷宫中，迷宫的每一格要么为空，要么有一个障碍。
你当前在第 r 行第 c 列(保证该格子为空)。每次移动你可以向上下左右任意一个方向移动一格，前提是不能走到障碍上，也不能超出迷宫的边界。
你向左移动的次数不能超过 x 次，向右不能超过 y 次。
问在这种情况下，对于每个格子，是否存在一种移动方案让你走到它。
输出有多少个格子存在移动方案让你走到它。

输入

第一行两个正整数 n,m 。
第二行两个正整数 r,c ，保证$1≤r≤n ，1≤c≤m$ 。
第三行两个整数 x,y ，保证$0≤x,y≤10^9$ 。
接下来 n 行，每行一个长度为 m 的字符串，
第 i 行第 j 个字符表示迷宫第 i 行第 j 列的格子，
字符为. 表示格子为空，字符为* 表示格子上有一个障碍。
对于全部数据， $1≤n,m≤1000$

输出

输出一个数，表示有多少个格子存在移动方案让你走到它。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4 5
3 2
1 2
.....
.***.
...**
*....
4 4
2 2
0 1
....
..*.
....
....

样例输出

1
2
10
7
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
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e3+5;
typedef long long ll;

int M_x[4]={1,0,-1,0},
    M_y[4]={0,1,0,-1},L,R;
char Map[N][N],Map2[N][N];

struct node{int x,y,l,r;};

ll bfs(int sx,int sy){
    queue<node> Way;ll ans=0;
    Way.push(node{sx,sy,0,0});
    while(!Way.empty()){
        node tem=Way.front();
        if(tem.l<=L&&tem.r<=R){
            ans++;
            Map2[tem.x][tem.y]='+';
            rep(i,0,4){
                int X=tem.x+M_x[i];
                int Y=tem.y+M_y[i];
                if(Map[X][Y]=='*'||Map[X][Y]=='+') continue;
                Map[X][Y]='+';
                if(i==1)Way.push(node{X,Y,tem.l,tem.r+1});
                else if(i==3) Way.push(node{X,Y,tem.l+1,tem.r});
                else  Way.push(node{X,Y,tem.l,tem.r});
            }

        }
        Way.pop();
    }
    return ans;
}

int main()
{
    CRL(Map,'*');
    CRL(Map2,'*');
    int sx,sy,n,m;
    scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&L,&R);
    rep(i,1,n+1){
        getchar();
        rep(j,1,m+1){
            Map2[i][j]=Map[i][j]=getchar();
        }
    }
    ll ans=0;
    ans= bfs(sx,sy);
    printf("%lld\n",ans-1);

    return 0;
}
-------------本文结束 感谢您的阅读-------------

本文标题:牛客寒假算法基础集训营6 题解

文章作者:Armin

发布时间:2019年02月02日 - 19:02

最后更新:2019年02月02日 - 22:02

原始链接:http://x-armin.com/牛客寒假算法基础集训营6-题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波