牛客寒假算法基础集训营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 国际 转载请保留原文链接及作者。

小礼物走一波