牛客寒假算法基础集训营6 题解
牛客寒假算法基础集训营6 题解
A出题
链接：https://ac.nowcoder.com/acm/contest/332/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小B准备出模拟赛。
她把题目按难度分为四等，分值分别为6,7,8,9。
已知小B共出了m道题，共n分。
求小B最少出了多少道6分题。
输入描述:
两个正整数n,m输出描述:
一个数，表示答案。
若无解，输出"jgzjgzjgz"。示例1
输入
34 5输出
1示例2
输入
32 5输出
3示例3
输入
5 1输出
jgzjgzjgz备注:
n,m≤1012
分析：
无解：6m>n或n>9m 。
有解：
设6，7，8，9分的题数为a,b,c,d,
则：
n=6a+7b+8c+9d
m=a+b+c+d
得出，
a=7*m-n+c+2*d
7*m-n是固定的，c+2*d是随便的数，因为我们知道我们这种情况肯定有解。
所以a的最小值为7*m-n
官方题解：
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//Scanner in = new Scanner (new BufferedInputStream(System.in));
Scanner in = new Scanner(new BufferedInputStream(System.in));
Long n=in.nextLong();
Long m=in.nextLong();
if(n<6*m||n>9*m)
{System.out.println("jgzjgzjgz");return ;}
Long ans=(long) (1<<30);
if(7*m-n>=0)
System.out.println(7*m-n);
else
System.out.println(0);
}
}
B 煤气灶
链接：https://ac.nowcoder.com/acm/contest/332/B
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小j开始打工，准备赚钱买煤气灶。
第一天，小j的工资为n元，之后每天他的工资都比前一天多d元。
已知煤气灶需要m元，求小j最少工作几天才能买到煤气灶。
输入描述:
四个整数 n,m,d,x
分别表示小j第一天的工资，煤气灶的价格，工资每天的增长量，答案不超过x输出描述:
一个数表示答案示例1
输入
10 100 20 100输出
4说明
10+30+50+70>=100备注:
0≤n,d≤109,n+d>00≤n,d≤109,n+d>0
1≤m≤10181≤m≤1018
1≤x≤109我的解直接二分的答案
官方题解：
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//Scanner in = new Scanner (new BufferedInputStream(System.in));
Scanner in = new Scanner(new BufferedInputStream(System.in));
Long n=in.nextLong();
Long m=in.nextLong();
Long d=in.nextLong();
Long x=in.nextLong();
Long l=(long) 1;
Long r=x;
while(l<r)
{
Long mid=(l+r)>>1;
Long f=mid*n+mid*(mid-1)/2*d;
if(f>=m)
{
r=mid;
}
else
l=mid+1;
}
System.out.println(l);
}
}
C项链
很裸的贪心
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 20007
using namespace std;
struct node
{
int x,y;
}a[100005];
bool cmp(node q,node w)
{
return q.y>w.y;
}
int main ( )
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
scanf("%d",&a[i].x);
for(int i=1;i<=m;i++)
scanf("%d",&a[i].y);
sort(a+1,a+m+1,cmp);
long long ans=0;
for(int i=1;i<=m&&n>0;i++)
{
//cout<<a[i].x<<" "<<a[i].y<<" "<<n<<endl;
if(n>=a[i].x)
{
ans=ans+(long long)(a[i].x*a[i].y);
n-=a[i].x;
}
else
{
ans=ans+(long long)((n)*a[i].y);
break;
}
}
cout<<ans<<endl;
return 0;
}D美食
贪心
i从1到n枚举，依次贪心。
对于a[i]，
首先把答案加上a[i]/2，
如果a[i]是奇数且a[i+1]>0，则把a[i+1]减去1，答案加上1。
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//Scanner in = new Scanner (new BufferedInputStream(System.in));
Scanner in = new Scanner(new BufferedInputStream(System.in));
Long []a=new Long[100005];
Long n=in.nextLong();
for(int i=1;i<=n;i++)
{
a[i]=in.nextLong();
}
Long ans=(long) 0;
a[(int) (n+1)]=(long) 0;
for(int i=1;i<=n;i++)
{
ans+=a[i]/2;
if(a[i]%2==1&&a[i+1]!=0)
{a[i+1]--;ans++;}
}
System.out.println(ans);
}
}
海啸
待补
用 s[x][y] 表示 (1,1) 到 (x,y) 的答案，
则 (a,b) 到 (x,y) 的答案 =s[x][y]+s[a-1][b-1]-s[a-1][y]-s[x][b-1] 。
所以只用预处理 s[x][y] 即可。
而 s[x][y] 可以通过两次计算前缀和得到。
还有一个问题就是只保证了 n∗m≤106n∗m≤106 ，怎么开数组？
只需要先开一个 106106 的指针数组，然后new出来就好了。
石头剪刀布
待补
根据获胜者的偏爱决策可以推出对战的两人的偏爱决策，所以枚举最终获胜者的偏爱决策判断一下就好了。字典序问题只需递归处理+暴力 cmp 。
时间 O(2n×n)O(2n×n)
G 区间或和
链接：https://ac.nowcoder.com/acm/contest/332/G
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
求a|(a+1)|(a+2)|...|(b-1)|b。
其中|表示[按位或](https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E6%88%96)。
输入描述:
多组输入，每行两个数表示a和b
输出描述:
对于每组输入，输出一个数a|(a+1)|(a+2)|...|(b-1)|b。
示例1
输入
99 109 68 77 55 66 34 43 1111234 1114321
输出
111 79 127 47 1179647
备注:
输入不超过10000行，0≤a,b≤10180≤a,b≤1018，a≤b
规律题：
发现当一个数按位或一个比它大的数的时候它才会变，那么我们对于a和b，依次枚举ans按位或ans+1，直到大于等于b就好了。
官方题解：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll a,b;
while(scanf("%lld%lld",&a,&b) != EOF){
while(a < b){
a|= (a + 1);
}
printf("%lld\n", a);
}
return 0;
}
肥猪
待补
从0到n-1枚举第二种操作的使用次数step，
那么对于最终得到的编号为i的肥猪，
假如它是召唤编号为j的肥猪然后进化多次得到的，
则一定有 i−step≤j≤ii−step≤j≤i ，
并且这是充要的，即它可以由这个区间的任何一个j召唤后进化多次得到。
因此只用这个区间的a[j]的最小值就是得到i的代价。
把所有i的代价相加再加上step*x就是step对应的最小代价。
注意，这个题目是一个环而不是链，这只需要将a复制一份即可。
求区间最小值有很多方法，比如单调队列。
时间复杂度 O(n2)O(n2) 。
wzoi
令看题为左括号，做题为右括号，就可以用一个括号序列表示行动序列。
那么一个括号序列的价值就是，对于每个匹配的括号，如果他们推荐种类相同，+10分，否则+5分。
如果 s 中有两个连续的1或0，那么可以让他们匹配，然后删去他们，递归处理。
最终剩下来的一定是1,0交错，这时一定无法让两个相同种类匹配了，贡献可以直接算。
时间复杂度 O(n)
J迷宫
链接：https://ac.nowcoder.com/acm/contest/332/J
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
你在一个 n 行 m 列的网格迷宫中，迷宫的每一格要么为空，要么有一个障碍。
你当前在第 r 行第 c 列(保证该格子为空)。每次移动你可以向上下左右任意一个方向移动一格，前提是不能走到障碍上，也不能超出迷宫的边界。
你向左移动的次数不能超过 x 次，向右不能超过 y 次。
问在这种情况下，对于每个格子，是否存在一种移动方案让你走到它。
输出有多少个格子存在移动方案让你走到它。
输入描述:
第一行两个正整数 n,m 。 第二行两个正整数 r,c ，保证 1≤r≤n1≤r≤n ，1≤c≤m1≤c≤m 。 第三行两个整数 x,y ，保证 0≤x,y≤1090≤x,y≤109 。 接下来 n 行，每行一个长度为 m 的字符串， 第 i 行第 j 个字符表示迷宫第 i 行第 j 列的格子， 字符为`.` 表示格子为空，字符为`*` 表示格子上有一个障碍。
输出描述:
输出一个数，表示有多少个格子存在移动方案让你走到它。
示例1
输入
4 5 3 2 1 2 ..... .***. ...** *....
输出
10
说明
将能走到的格子用+标记： +++.. +***. +++** *+++.
示例2
输入
4 4 2 2 0 1 .... ..*. .... ....
输出
7
说明
.++. .+*. .++. .++.
备注:
对于全部数据， 1≤n,m≤10001≤n,m≤1000 。
这题简单的bfs就能过
不过题解给了啥：
import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class node
{
int x,y,ls,rs;
public node(int x, int y, int ls, int rs) {
super();
this.x = x;
this.y = y;
this.ls = ls;
this.rs = rs;
}
@Override
public String toString() {
return "node [x=" + x + ", y=" + y + ", ls=" + ls + ", rs=" + rs + "]";
}
}
public class Main {
static int [] dx={1,0,-1,0};
static int [] dy={0,1,0,-1};
static int n,m,x,y;
static String[] map =new String[1005];
static int[][] vis =new int[1005][1005];
public static int bfs(int x1,int y1)
{
Queue<node> q=new LinkedList<node>();
node a = new node(x1,y1,0,0);
q.offer(a);
int ans=1;
vis[x1][y1]=1;
while(q.size()!=0)
{
a=q.poll();
//System.out.println(a);
for(int i=0;i<4;i++)
{
node b=null;
if(i==1)
b=new node(a.x+dx[i],a.y+dy[i],a.ls,a.rs+1);
else if(i==3)
b=new node(a.x+dx[i],a.y+dy[i],a.ls+1,a.rs);
else
b=new node(a.x+dx[i],a.y+dy[i],a.ls,a.rs);
if(b.x>=0&&b.x<n&&b.y>=0&&b.y<m&&map[b.x].charAt(b.y)!='*'&&b.ls<=x&&b.rs<=y&&vis[b.x][b.y]==0)
{
ans++;
q.offer(b);
vis[b.x][b.y]=1;
}
}
}
return ans;
}
public static void main(String[] args) {
//Scanner in = new Scanner (new BufferedInputStream(System.in));
Scanner in = new Scanner(new BufferedInputStream(System.in));
n=in.nextInt();
m=in.nextInt();
int r=in.nextInt();
int c=in.nextInt();
r--;
c--;
x=in.nextInt();
y=in.nextInt();
in.nextLine();
for(int i=0;i<n;i++)
{
map[i]=new String();
map[i]=in.next();
}
System.out.println(bfs(r,c));
}
}
std
https://ac.nowcoder.com/acm/contest/332#submit/{%22searchUserName%22%3A%22kczno1%22}