试题 A: 数青蛙
“一只青蛙一张嘴，两只眼睛四条腿。两只青蛙两张嘴，四只眼睛八条腿。三只青蛙三张嘴，六只眼睛十二条腿。……二十只青蛙二十张嘴，四十只眼睛八十条腿。”
请问上面这段文字，如果完全不省略，全部写出来，从 1 到 20 只青蛙，总共有多少个汉字。
约定：数字 2 单独出现读成 “两”，在其他数里面读成 “二”，例如 “十二”。10 读作 “十”，11 读作 “十一”，22 读作 “二十二”。请只计算汉字的个数，标点符号不计算。
答案353
上限20只青蛙,腿最多80只,所以只需要考虑1~80的汉字个数即可.
个位数一位;11~19以及10的倍数两位;其余情况三位
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
using
namespace
std;
-
int n(int x){
-
if(x<=
10)
return
1;
-
if(x%
10==
0)
return
2;
-
if(x<
20)
return
2;
-
return
3;
-
}
-
int main(){
-
int sum =
0;
-
for(
int i =
1 ; i <=
20 ; i ++){
-
int a = i;
-
int b = i + i;
-
int c = i *
4;
-
sum +=
10;
-
sum += n(a)*
2;
-
sum+=n(b) + n(c);
-
}
-
cout<<sum<<
endl;
-
return
0;
-
}
试题 B: 互质
今年是 2020 年，今天是 10 月 18 日。
请问在 1 到 2020 中，有多少个数与 1018 互质。
答案:1008
因为是填空题,所以不需要考虑什么算法,直接暴力试就可
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
using
namespace
std;
-
-
int gcd2(int a,int b){
-
return b==
0?a:gcd(b,a%b);
-
}
-
int main(){
-
int sum =
0;
-
for(
int i =
1 ; i <=
2020; i ++){
-
if(gcd2(
1018,i) ==
1){
-
sum ++;
-
}
-
}
-
cout<< sum <<
endl;
-
return
0;
-
}
试题 C: 车牌
A 市的车牌由六位组成，其中前三位可能为数字 0 至 9，或者字母 A 至 F，每位有 16 种可能。后三位只能是数字 0 至 9。为了减少攀比，车牌中不能有连续三位是相同的字符。
例如，202020 是合法的车牌，AAA202 不是合法的车牌，因为前三个字母相同。
请问，A 市有多少个合法的车牌？
答案:3997440
总共情况为16*16*16*10*10*10
第一位第二位第三位字符一致,可以看做一位,有16种情况,第四位第五位第六位分别有10种情况
第一位16种情况,第二位第三位第四位一致,看做一位,有10种情况,第五位第六位分别有10种情况
第一位16种情况,第二位16种情况,第三第四第五位一致看做一位,有10种情况,第六位10种情况
第一位第二位第三位分别16种情况,第四位第五位第六位一致,看做一位,有10种情况
采用正难则反的思想,总数减去排除情况数,就是答案
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
using
namespace
std;
-
-
int main(){
-
int sum =
16*
16*
16*
10*
10*
10;
-
sum -=
16*
10*
10*
10;
-
sum -=
16*
10*
10*
10;
-
sum -=
16*
16*
10*
10;
-
sum -=
16*
16*
16*
10;
-
cout<<sum<<
endl;
-
return
0;
-
}
试题 D: Fibonacci 集合
小蓝定义了一个 Fibonacci 集合 F，集合的元素如下定义：
1. 最小的 5 个 Fibonacci 数 1, 2, 3, 5, 8 属于集合 F。
2. 如果一个元素 x 属于 F，则 3x + 2、5x + 3 和 8x + 5 都属于集合 F。
3. 其他元素都不属于 F。
请问，这个集合中的第 2020 小元素的值是多少？
答案 41269
标准深搜题,数字要求也不大,暴力即可
从最小的五个数开始搜索,把搜索到的数字置一,然后再找地2020个置一的数字即可
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
using
namespace
std;
-
int fx[
100010];
-
bool is[
100010];
-
void dfs(int n){
-
if(n >
100000)
return ;
-
is[n] =
true;
-
dfs(n*
3+
2);
-
dfs(n*
5+
3);
-
dfs(n*
8+
5);
-
}
-
int main(){
-
dfs(
1);
-
dfs(
2);
-
dfs(
3);
-
dfs(
5);
-
dfs(
8);
-
int sum =
0;
-
for(
int i =
1;i<=
100010;i++){
-
if(is[i]){
-
sum ++;
-
cout<< sum <<
" ge = " << i<<
endl;
-
if(sum ==
2020){
-
break;
-
}
-
}
-
}
-
return
0;
-
}
试题 E: 上升子串
小蓝有一个字母矩阵，他喜欢和小伙伴们在这个矩阵上玩一些游戏。今天，他打算玩找上升子串的游戏。游戏是合作性质的。小蓝和小伙伴们首先要在矩阵中指定一个位置，然后从这个位置开始，向上下左右相邻位置移动，移动必须满足所到达位置上的字母比当前位置大。小蓝和小伙伴们可以移动任意多次，也可以随时停下来，这样就找到了一个上升子串。只要子串在矩阵中的位置不同，就认为是不同的子串。
小蓝想知道，一共可以找到多少个上升子串。小蓝的矩阵很大，已经放在了试题目录下面，叫 inc.txt。为了更清楚的
描述问题，他还找了一个很小的矩阵用来解释。
例如，对于矩阵：
-
AB
-
BC
可以找到 4 个长度为 1 的上升子串、4 个长度为 2 的上升子串、2 个长度
为 3 的上升子串，共 10 个。
现在，请你对于小蓝的大矩阵，找到上升子串的数量。
答案未知
这题暴力过不去,比赛的时候跑了两个多小时,还在跑......
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
#include<queue>
-
using
namespace
std;
-
char a[
102][
102];
-
int sum;
-
struct mu{
-
int x;
-
int y;
-
char maxChar;
-
mu(
int xx,
int yy,
char z){
-
x = xx;
-
y = yy;
-
maxChar = z;
-
}
-
};
-
bool check(int x){
-
if(x<
0 || x >=
100)
return
false;
-
return
true;
-
}
-
void bfs(int x,int y){
-
queue<mu> q;
-
q.push(mu(x,y,a[x][y]));
-
while(!q.empty()){
-
mu mm = q.front();
-
sum ++;
-
cout<<sum<<
endl;
-
q.pop();
-
if(check(mm.x -
1) && mm.maxChar < a[mm.x -
1][mm.y]){
-
mu m2 = mu(mm.x -
1,mm.y,a[mm.x -
1][mm.y]);
-
q.push(m2);
-
}
-
if(check(mm.x +
1) && mm.maxChar < a[mm.x +
1][mm.y]){
-
mu m3 = mu(mm.x +
1,mm.y,a[mm.x +
1][mm.y]);
-
q.push(m3);
-
}
-
if(check(mm.y +
1) && mm.maxChar < a[mm.x][mm.y +
1]){
-
mu m4 = mu(mm.x,mm.y +
1,a[mm.x][mm.y +
1]);
-
q.push(m4);
-
}
-
if(check(mm.y -
1) && mm.maxChar < a[mm.x][mm.y -
1]){
-
mu m5 = mu(mm.x,mm.y -
1,a[mm.x][mm.y -
1]);
-
q.push(m5);
-
}
-
}
-
}
-
int main(){
-
sum =
0;
-
for(
int i =
0 ; i <
100;i++){
-
cin>>a[i];
-
}
-
for(
int i =
0 ; i <
100;i++){
-
for(
int j =
0 ; j <
100 ; j ++){
-
bfs(i,j);
-
}
-
}
-
cout<<sum<<
endl;
-
return
0;
-
}
试题 F: 日期识别
小蓝要处理非常多的数据，其中有一些数据是日期。在小蓝处理的日期中有两种常用的形式：英文形式和数字形式。英文形式采用每个月的英文的前三个字母作为月份标识，后面跟两位数字表示日期，月份标识第一个字母大写，后两个字母小写，日期小于 10 时要补前导 0。1 月到 12 月英文的前三个字母分别是 Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec。数字形式直接用两个整数表达，中间用一个空格分隔，两个整数都不写前导 0。其中月份用 1 至 12 分别表示 1 月到 12 月。
输入一个日期的英文形式，请输出它的数字形式。
-
【样例输入】
-
Feb08
-
【样例输出】
-
2
8
-
【样例输入】
-
Oct18
-
【样例输出】
-
10
18
话不多说,暴力
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
using
namespace
std;
-
void run(string s){
-
if(s[
0] ==
'J' && s[
1] ==
'a' && s[
2] ==
'n'){
-
printf(
"1 ");
-
}
-
else
if(s[
0] ==
'F' && s[
1] ==
'e' && s[
2] ==
'b'){
-
printf(
"2 ");
-
}
-
else
if(s[
0] ==
'M' && s[
1] ==
'a' && s[
2] ==
'r'){
-
printf(
"3 ");
-
}
-
else
if(s[
0] ==
'A' && s[
1] ==
'p' && s[
2] ==
'r'){
-
printf(
"4 ");
-
}
-
else
if(s[
0] ==
'M' && s[
1] ==
'a' && s[
2] ==
'y'){
-
printf(
"5 ");
-
}
-
else
if(s[
0] ==
'J' && s[
1] ==
'u' && s[
2] ==
'n'){
-
printf(
"6 ");
-
}
-
else
if(s[
0] ==
'J' && s[
1] ==
'u' && s[
2] ==
'l'){
-
printf(
"7 ");
-
}
-
else
if(s[
0] ==
'A' && s[
1] ==
'u' && s[
2] ==
'g'){
-
printf(
"8 ");
-
}
-
else
if(s[
0] ==
'S' && s[
1] ==
'e' && s[
2] ==
'p'){
-
printf(
"9 ");
-
}
-
else
if(s[
0] ==
'O' && s[
1] ==
'c' && s[
2] ==
't'){
-
printf(
"10 ");
-
}
-
else
if(s[
0] ==
'N' && s[
1] ==
'o' && s[
2] ==
'v'){
-
printf(
"11 ");
-
}
-
else
if(s[
0] ==
'D' && s[
1] ==
'e' && s[
2] ==
'c'){
-
printf(
"12 ");
-
}
-
if(s[
3] !=
'0'){
-
cout<<s[
3];
-
}
-
cout<<s[
4]<<
endl;
-
}
-
int main(){
-
string str;
-
while(
cin>>str){
-
run(str);
-
}
-
return
0;
-
}
试题 G: 乘法表
九九乘法表是学习乘法时必须要掌握的。在不同进制数下，需要不同的乘
法表。
例如，四进制下的乘法表如下所示：
-
1*
1=
1
-
2*
1=
2
2*
2=
10
-
3*
1=
3
3*
2=
12
3*
3=
21
请注意，乘法表中两个数相乘的顺序必须为样例中所示的顺序，不能随意
交换两个乘数。
给定 P，请输出 P 进制下的乘法表。
-
【输入格式】
-
输入一个整数
P。
-
【输出格式】
-
输出
P
进制下的乘法表。P
进制中大于等于
10
的数字用大写字母
A、B、
C、·
·
·
表示。
-
【样例输入】
-
4
-
【样例输出】
-
1
*1=1
-
2
*1=2
2
*2=10
-
3
*1=3
3
*2=12
3
*3=21
-
-
【样例输入】
-
8
-
【样例输出】
-
1
*1=1
-
2
*1=2
2
*2=4
-
3
*1=3
3
*2=6
3
*3=11
-
4
*1=4
4
*2=10
4
*3=14
4
*4=20
-
5
*1=5
5
*2=12
5
*3=17
5
*4=24
5
*5=31
-
6
*1=6
6
*2=14
6
*3=22
6
*4=30
6
*5=36
6
*6=44
-
7
*1=7
7
*2=16
7
*3=25
7
*4=34
7
*5=43
7
*6=52
7
*7=61
【评测用例规模与约定】
对于所有评测数据，2 ≤ P ≤ 36。
使用栈进行进制转换即可,注意10以上进制的需要输出字符A-F
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
#include<stack>
-
using
namespace
std;
-
void printNum(int num,int p){
-
stack<
int> s;
-
while(num>
0){
-
s.push(num%p);
-
num/=p;
-
}
-
while(!s.empty()){
-
if(s.top() >
9){
-
printf(
"%c",
'A'+ s.top() -
10);
-
}
-
else{
-
cout<<s.top();
-
}
-
s.pop();
-
}
-
}
-
void run(int p){
-
for(
int i =
1 ; i < p ; i ++){
-
for(
int j =
1;j <= i;j ++){
-
int sum = i * j;
-
if(j!=
1){
-
printf(
" ");
-
}
-
if(i >
9){
-
printf(
"%c",
'A'+i
-10);
-
}
else{
-
printf(
"%d", i);
-
}
-
printf(
"*");
-
if(j >
9){
-
printf(
"%c",
'A'+j
-10);
-
}
else{
-
printf(
"%d", j);
-
}
-
printf(
"=");
-
printNum(sum,p);
-
}
-
printf(
"\n");
-
}
-
}
-
int main(){
-
int p;
-
while(
cin>>p){
-
run(p);
-
}
-
return
0;
-
}
试题 H: 限高杆
【问题描述】
某市有 n 个路口，有 m 段道路连接这些路口，组成了该市的公路系统。其中一段道路两端一定连接两个不同的路口。道路中间不会穿过路口。由于各种原因，在一部分道路的中间设置了一些限高杆，有限高杆的路段货车无法通过。在该市有两个重要的市场 A 和 B，分别在路口 1 和 n 附近，货车从市场 A出发，首先走到路口 1 ，然后经过公路系统走到路口 n，才能到达市场 B。
两个市场非常繁华，每天有很多货车往返于两个市场之间。市长发现，由于限高杆很多，导致货车可能需要绕行才能往返于市场之间，这使得货车在公路系统中的行驶路程变长，增加了对公路系统的损耗，增加了能源的消耗，同时还增加了环境污染。市长决定要将两段道路中的限高杆拆除，使得市场 A 和市场 B 之间的路程变短。请问最多能减少多长的距离？
【输入格式】
输入的第一行包含两个整数 n, m，分别表示路口的数量和道路的段数。
接下来 m 行，每行四个整数 a, b, c, d，表示路口 a 和路口 b 之间有一段长度为 c 的道路。如果 d 为 0，表示这段道路上没有限高杆；如果 d 为 1，表示这段道路上有限高杆。两个路口之间可能有多段道路。
输入数据保证在不拆除限高杆的情况下，货车能通过公路系统从路口 1 正常行驶到路口 n。
【输出格式】
输出一行，包含一个整数，表示拆除两段道路的限高杆后，市场 A 和市场B 之间的路程最大减少多长距离。
-
【样例输入】
-
5
7
-
1
2
1
0
-
2
3
2
1
-
1
3
9
0
-
5
3
8
0
-
4
3
5
1
-
4
3
9
0
-
4
5
4
0
-
【样例输出】
-
6
【样例说明】
只有两段道路有限高杆，全部拆除后，1 到 n 的路程由原来的 17 变为了
11，减少了 6。
【评测用例规模与约定】
对于 30% 的评测样例，2 ≤ n ≤ 10，1 ≤ m ≤ 20, 1 ≤ c ≤ 100。
对于 50% 的评测样例，2 ≤ n ≤ 100，1 ≤ m ≤ 1000, 1 ≤ c ≤ 1000。
对于 70% 的评测样例，2 ≤ n ≤ 1000，1 ≤ m ≤ 10000, 1 ≤ c ≤ 10000。
对于所有评测样例，2 ≤ n ≤ 10000，2 ≤ m ≤ 100000, 1 ≤ c ≤ 10000，至少
有两段道路有限高杆。
先计算不拆限高架的情况下,即d等于1的输入数据,我们先保存起来,其中ganx保存起点,gany保存终点,ganLi保存距离
因为蓝桥杯是闭卷考试,dijkstra算法一下子想不起来了,所以使用了floyd算法,暴力三层for循环,找到每个点之间的最短路径保存在li1数组中,把1到n的最短路径保存在 qianAns 中
然后再两层for循环遍历限高的道路,使用li2临时数组复制li1的最短路数据,然后尝试把两个拆掉限高的路加进去,再求一遍最短路
多次遍历完成,计算出最短值
相减就是答案,算法非常差,但基础样例可以过
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
#include<queue>
-
using
namespace
std;
-
int li1[
10002][
10002];
// qian
-
int li2[
10002][
10002];
// hou
-
int ganx[
10002];
-
int gany[
10002];
-
int ganLi[
10002];
-
int main(){
-
-
int n,m;
-
-
while(
cin>>n>>m){
-
memset(li1,
1,
sizeof(li1));
-
int ganGe =
0;
-
for(
int i =
0 ; i <= n ; i ++){
-
li1[i][i] =
0;
-
}
-
for(
int i =
0 ; i < m ; i ++){
-
int a,b,c,d;
-
scanf(
"%d%d%d%d",&a,&b,&c,&d);
-
if(d ==
0){
-
if(li1[a][b] > c){
-
li1[a][b] = c;
-
}
-
if(li1[b][a] > c){
-
li1[b][a] = c;
-
}
-
}
else{
-
ganx[ganGe] = a;
-
gany[ganGe] = b;
-
ganLi[ganGe++] = c;
-
}
-
}
-
for(
int i =
1 ; i <= n ; i ++ ){
-
for(
int j =
1 ; j <= n ; j++ ){
-
for(
int k =
1 ; k <= n ; k ++ ){
-
if(li1[i][j] > li1[i][k] + li1[k][j] ){
-
li1[i][j] = li1[i][k] + li1[k][j];
-
}
-
}
-
}
-
}
-
int qianAns = li1[
1][n];
-
int houAns =
99999;
-
for(
int g1 =
0 ; g1<ganGe ; g1 ++ ){
-
for(
int g2 = g1 +
1 ; g2 < ganGe ; g2++){
-
for(
int i =
1;i<=n;i++){
-
for(
int j =
1 ; j <= n ; j ++){
-
li2[i][j] = li1[i][j];
-
}
-
}
-
if(li2[ganx[g1]][gany[g1]] > ganLi[g1]){
-
li2[ganx[g1]][gany[g1]] = ganLi[g1];
-
}
-
if(li2[gany[g1]][ganx[g1]] > ganLi[g1]){
-
li2[gany[g1]][ganx[g1]] = ganLi[g1];
-
}
-
if(li2[ganx[g2]][gany[g2]] > ganLi[g2]){
-
li2[ganx[g2]][gany[g2]] = ganLi[g2];
-
}
-
if(li2[gany[g2]][ganx[g2]] > ganLi[g2]){
-
li2[gany[g2]][ganx[g2]] = ganLi[g2];
-
}
-
for(
int i =
1 ; i <= n ; i ++ ){
-
for(
int j =
1 ; j <= n ; j++ ){
-
for(
int k =
1 ; k <= n ; k ++ ){
-
if(li2[i][j] > li2[i][k] + li2[k][j] ){
-
li2[i][j] = li2[i][k] + li2[k][j];
-
}
-
}
-
}
-
}
-
if(li2[
1][n] < houAns){
-
houAns = li2[
1][n];
-
}
-
}
-
}
-
-
// cout<<qianAns << endl;
-
// cout<<houAns<<endl;
-
cout<<qianAns - houAns<<
endl;
-
}
-
return
0;
-
}
试题 I: 画中漂流
【问题描述】
在梦境中，你踏上了一只木筏，在江上漂流。根据对当地的了解，你知道在你下游 D 米处有一个峡谷，如果你向下游前
进大于等于 D 米则必死无疑。现在你打响了急救电话，T 秒后救援队会到达并将你救上岸。水流速度是1 m/s，你现在有 M 点体力。每消耗一点体力，你可以划一秒桨使船向上游前进 1m，否则会向下游前进 1m (水流)。M 点体力需在救援队赶来前花光。因为江面太宽了，凭借你自己的力量不可能上岸。请问，有多少种划桨的方案可以让你得救。
两个划桨方案不同是指：存在某一秒钟，一个方案划桨，另一个方案不划。
【输入格式】
输入一行包含三个整数 D, T, M。
【输出格式】
输出一个整数，表示可以让你得救的总方案数，答案可能很大，请输出方
案数除以 1, 000, 000, 007 的余数。
-
【样例输入】
-
1
6
3
-
【样例输出】
-
5
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ T ≤ 350。
对于所有评测用例，1 ≤ T ≤ 3000, 1 ≤ D ≤ T, 1 ≤ M ≤ 1500。
我运用了广搜,结构体的weizhi是相对于起点的位置,tili为当前还剩下的体力,time是当前剩余的时间
注意题目要求,必须在救援队来之前把体力用完,如果没用完,不计数
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
#include<queue>
-
using
namespace
std;
-
struct mu{
-
int weizhi;
-
int tili;
-
int time;
-
mu(
int x,
int y,
int z){
-
weizhi = x;
-
tili = y;
-
time = z;
-
}
-
};
-
void bfs(int d,int t,int m){
-
int ans =
0;
-
d = -d;
-
queue<mu> q;
-
q.push(mu(
0,m,t));
-
while(!q.empty()){
-
mu mm = q.front();
-
if(mm.weizhi <= d){
// si
-
q.pop();
-
continue;
-
}
-
if(mm.tili ==
0 && mm.time ==
0){
-
ans ++;
-
}
-
if(mm.time <=
0){
-
q.pop();
-
continue;
-
}
-
if(mm.tili >
0){
// up
-
mu m1 = mu(mm.weizhi +
1,mm.tili
-1 , mm.time -
1);
-
q.push(m1);
-
}
-
// down
-
mu m2 = mu(mm.weizhi -
1,mm.tili , mm.time -
1);
-
q.push(m2);
-
q.pop();
-
}
-
cout<<ans<<
endl;
-
}
-
int main(){
-
int d,t,m;
-
while(
cin>>d>>t>>m){
-
bfs(d,t,m);
-
}
-
return
0;
-
}
试题 J: 旅行家
【问题描述】
从前，在海上有 n 个岛屿，编号 1 至 n。居民们深受洋流困扰，无法到达比自己当前所在岛屿编号更小的岛屿。经过数年以后，岛屿上的人数随着岛屿的编号递增（可能相等）。作为一名出色的旅行家（RP 学家），你想从 1 号岛屿出发开启一次旅程，以获得更多的 RP，因为受到海洋的洋流影响，你只能去到比当前岛屿编号更大的岛屿。因为你比较善良，你会在离开一个岛屿的时候将你的 RP 分散给岛民，具体的：你的 RP 会除以 2（用去尾法取整，或者说向零取整）（当你的 RP 小于零时，岛民也依旧要帮你分担，毕竟你们已经建立起了深厚的友谊）。第 i 号岛屿有 Ti 人, 但是你很挑剔，每次你从 j 号岛屿到达 i 号岛屿时，你只会在到达的岛屿上做 Ti × T j 件好事（一件好事可以获得 1 点 RP)。
唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 i 号岛屿的住宿扣除 Fi 点 RP。注意：将离开一个岛屿时，先将 RP 扣除一半，再扣除住宿的 RP，最后在新到达的岛屿上做好事，增加 RP。离开 1 号岛屿时需要扣除在 1 号岛屿住宿的 RP，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 RP。你因为热爱旅行 (RP)，所以从 1 号岛屿开始旅行，初始时你有 0 点 RP。
你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 RP 值是多少？
【输入格式】
输入的第一行包含一个数 n , 表示岛屿的总数。
第二行包含 n 个整数 T1, T2, · · · , Tn , 表示每个岛屿的人口数。
第三行包含 n 个整数 F1, F2, · · · , Fn , 表示每个岛屿旅馆损失的 RP。
【输出格式】
输出一个数，表示最大获得的 RP 值。
-
【样例输入】
-
3
-
4
4
5
-
1
10
3
-
【样例输出】
-
19
【样例说明】
从一号岛屿直接走到三号岛屿最优，初始 0 点 RP，扣除一半取整变成 0点。扣除在一号节点住宿的 1 RP，在三号岛屿做好事产生 4 × 5 = 20 点 RP,最终得到 19 点 RP。
-
【样例输入】
-
5
-
969
980
1013
1016
1021
-
888423
945460
865822
896150
946615
-
【样例输出】
-
246172
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 15；
对于 70% 的评测用例，1 ≤ n ≤ 5000；
对于所有评测用例，1 ≤ n ≤ 500000, 1 ≤ Ti ≤ 20000, 1 ≤ Fi ≤ 200, 000, 000。
给定的 Ti 已经按照升序排序。建议使用 64 位有符号整数进行运算。
我是完全模拟题目的思路写得代码,注意n等于1的时候需要特判
-
#include<iostream>
-
#include<string>
-
#include<cstring>
-
#include<algorithm>
-
#include<cmath>
-
#include<cstdio>
-
#include<queue>
-
using
namespace
std;
-
long
long a[
500010];
-
long
long b[
500010];
-
int n;
-
long
long maxRp;
-
void dfs(long long rp,int index,long long qianRen){
-
// ting
-
if(index +
1 > n)
return ;
-
if(rp + qianRen * a[index +
1] > maxRp){
-
maxRp = rp + qianRen * a[index +
1];
-
}
-
dfs((rp + qianRen * a[index +
1])/
2 - b[index +
1],index +
1,a[index +
1]);
-
//buting
-
dfs(rp,index+
1,qianRen);
-
}
-
int main(){
-
while(
cin>>n){
-
-
for(
int i =
1 ; i <= n ; i ++){
-
scanf(
"%lld",&a[i]);
-
}
-
for(
int i =
1 ; i <= n ; i ++){
-
scanf(
"%lld",&b[i]);
-
}
-
if(n ==
1) {
-
cout<<
"0"<<
endl;
-
}
else{
-
maxRp = -b[
1];
-
dfs(-b[
1],
1,a[
1]);
-
cout << maxRp <<
endl;
-
}
-
}
-
return
0;
-
}
转载：https://blog.csdn.net/qq_41464123/article/details/109145005