試題 A: 數青蛙

“一隻青蛙一張嘴，兩隻眼睛四條腿」匣青蛙兩張嘴，四隻眼睛八條腿。三隻青蛙三張嘴，六隻眼睛十二條腿。……二十隻青蛙二十張嘴，四十隻眼睛八十條腿。”

請問膳绫擎這(zhè)段文字，如不(bù)雅完全不(bù)省略，全部寫出(chū)來(lái)，大(dà)年夜 1 到(dào) 20 隻青蛙，總共有若幹個(gè)漢字。

商定：數字 2 零丁出(chū)現讀成 “兩”，在(zài)其他(tā)數琅绫擎讀成 “二”，例如 “十二”。10 讀作 “十”，11 讀作 “十一”，22 讀作 “二十二”。請隻計算漢字的(de)個(gè)數，标點符号不(bù)計算。

謎底353

上(shàng)限20隻青蛙,腿最多80隻,所以(yǐ)隻須要(yào / yāo)推敲1~80的(de)漢字個(gè)數即可.

個(gè)位數一位;11~19以(yǐ)及10的(de)倍數兩位;其餘情況三位

#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: 互質

本年是(shì) 2020 年，今天是(shì) 10 月 18 日。
請問在(zài) 1 到(dào) 2020 中，有若幹個(gè)數與 1018 互質。

謎底:1008

因爲(wéi / wèi)是(shì)填空題,所以(yǐ)不(bù)須要(yào / yāo)推敲什麽算法,直接暴力試就(jiù)可

#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 市的(de)車牌由六位構成，個(gè)中前三位可能爲(wéi / wèi)數字 0 至 9，或者字母 A 至 F，每位有 16 種可能。後三位隻能是(shì)數字 0 至 9。爲(wéi / wèi)了(le／liǎo)削減攀比，車牌中不(bù)克不(bù)及有持續三位是(shì)雷同的(de)字符。

例如，202020 是(shì)合法的(de)車牌，AAA202 不(bù)是(shì)合法的(de)車牌，因爲(wéi / wèi)前三個(gè)字母雷同。

請問，A 市有若幹個(gè)合法的(de)車牌？

謎底:3997440

---

總共情況爲(wéi / wèi)16*16*16*10*10*10

第一位第二位第三位字符一緻,可以(yǐ)看做一位,有16種情況,第四位第五位第六位分别有10種情況

第一位16種情況,第二位第三位第四位一緻,看做一位,有10種情況,第五位第六位分别有10種情況

第一位16種情況,第二位16種情況,第三第四第五位一緻看做一位,有10種情況,第六位10種情況

第一位第二位第三位分别16種情況,第四位第五位第六位一緻,看做一位,有10種情況

采取正難則反的(de)思惟,總數減去清除情況數,就(jiù)是(shì)謎底

#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 集合

小藍定義了(le／liǎo)一個(gè) Fibonacci 集合 F，集合的(de)元素如下定義：

1. 最小的(de) 5 個(gè) Fibonacci 數 1, 2, 3, 5, 8 屬于(yú)集合 F。

2. 如不(bù)雅一個(gè)元素 x 屬于(yú) F，則 3x + 2、5x + 3 和(hé / huò) 8x + 5 都屬于(yú)集合 F。

3. 其他(tā)元素都不(bù)屬于(yú) F。

請問，這(zhè)個(gè)集合中的(de)第 2020 小元素的(de)值是(shì)若幹？

謎底 41269

标準深搜題,數字請求也(yě)不(bù)大(dà)年夜,暴力即可

大(dà)年夜最小的(de)五個(gè)數開端搜刮,把搜刮到(dào)的(de)數字置一,然後再找地(dì / de)2020個(gè)置一的(de)數字即可

#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: 上(shàng)升子(zǐ)串

小藍有一個(gè)字母矩陣，他(tā)愛好和(hé / huò)小夥伴們在(zài)這(zhè)個(gè)矩陣上(shàng)玩一些遊戲。今天，他(tā)計算玩找上(shàng)升子(zǐ)串的(de)遊戲。遊戲是(shì)合作性質的(de)。小藍和(hé / huò)小夥伴們起重要(yào / yāo)在(zài)矩陣中指定一個(gè)地(dì / de)位，然後大(dà)年夜這(zhè)個(gè)地(dì / de)位開端，向高低閣下相鄰地(dì / de)位移動，移動必須知足所達到(dào)地(dì / de)位上(shàng)的(de)字母比當前地(dì / de)位大(dà)年夜。小藍和(hé / huò)小夥伴們可以(yǐ)移動随便率性多次，也(yě)可以(yǐ)随時(shí)停下來(lái)，如許就(jiù)找到(dào)了(le／liǎo)一個(gè)上(shàng)升子(zǐ)串。隻要(yào / yāo)子(zǐ)串在(zài)矩陣中的(de)地(dì / de)位不(bù)合，就(jiù)認爲(wéi / wèi)是(shì)不(bù)合的(de)子(zǐ)串。

小藍想知道(dào)，一共可以(yǐ)找到(dào)若幹個(gè)上(shàng)升子(zǐ)串。小藍的(de)矩陣很大(dà)年夜，已經放在(zài)了(le／liǎo)試标題次下面，叫 inc.txt。爲(wéi / wèi)了(le／liǎo)更清跋扈的(de)

描述問題，他(tā)還找了(le／liǎo)一個(gè)很小的(de)矩陣用來(lái)解釋。

例如，對于(yú)矩陣：

AB
BC

可以(yǐ)找到(dào) 4 個(gè)長度爲(wéi / wèi) 1 的(de)上(shàng)升子(zǐ)串、4 個(gè)長度爲(wéi / wèi) 2 的(de)上(shàng)升子(zǐ)串、2 個(gè)長度

爲(wéi / wèi) 3 的(de)上(shàng)升子(zǐ)串，共 10 個(gè)。

如今，請你對于(yú)小藍的(de)大(dà)年夜矩陣，找到(dào)上(shàng)升子(zǐ)串的(de)數量。

謎底未知

這(zhè)題暴力過不(bù)去,比賽的(de)時(shí)刻跑了(le／liǎo)兩個(gè)多小時(shí),還在(zài)跑......

#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: 日期辨認

小藍要(yào / yāo)處理異常多的(de)數據，個(gè)中有一些數據是(shì)日期。在(zài)小藍處理的(de)日期中有兩種常用的(de)情勢：英文情勢和(hé / huò)數字情勢。英文情勢采取每個(gè)月的(de)英文的(de)前三個(gè)字母作爲(wéi / wèi)月份标識，後面跟兩位數字表示日期，月份标識第一個(gè)字母大(dà)年夜寫，後兩個(gè)字母小寫，日孚小于(yú) 10 時(shí)要(yào / yāo)補前導 0。1 月到(dào) 12 月英文的(de)前三個(gè)字母分别是(shì) Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec。數字情勢直接用兩個(gè)整數表達，中心用一個(gè)空格分隔，兩個(gè)整數都不(bù)寫前導 0。個(gè)中月份用 1 至 12 分别表示 1 月到(dào) 12 月。

輸入一個(gè)日期的(de)英文情勢，請輸出(chū)它的(de)數字情勢。

【樣例輸入】
Feb08
【樣例輸出(chū)】
2 8
【樣例輸入】
Oct18
【樣例輸出(chū)】
10 18

話不(bù)多說(shuō),暴力

#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: 乘法表

九九乘法表是(shì)進修乘法時(shí)必須要(yào / yāo)控制的(de)。在(zài)不(bù)合進制數下，須要(yào / yāo)不(bù)合的(de)乘
法表。
例如，四進制下的(de)乘法表如下所示：

1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21

請留意，乘法表中兩個(gè)數相乘的(de)次序必須爲(wéi / wèi)樣例中所示的(de)次序，不(bù)克不(bù)及随便
交換兩個(gè)乘數。
給定 P，請輸出(chū) P 進制下的(de)乘法表。

【輸入格局】
輸入一個(gè)整數 P。
【輸出(chū)格局】
輸出(chū) P 進制下的(de)乘法表。P 進制中大(dà)年夜于(yú)等于(yú) 10 的(de)數字用大(dà)年夜寫字母 A、B、 C、· · · 表示。
【樣例輸入】
4
【樣例輸出(chū)】
1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21

【樣例輸入】
8
【樣例輸出(chū)】
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

【評測用例範圍與商定】

對于(yú)所有評測數據，2 ≤ P ≤ 36。

應用棧進行進制轉換即可,留意10以(yǐ)長進制的(de)須要(yào / yāo)輸出(chū)字符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 個(gè)路口，有 m 段門路連接這(zhè)些路口，構成了(le／liǎo)該市的(de)公路體系。個(gè)一一段門路兩端必定連接兩個(gè)不(bù)合的(de)路口。門路中心不(bù)會穿過路口。因爲(wéi / wèi)各類原因，在(zài)一部分門路的(de)中心設置了(le／liǎo)一些限高杆，有限高杆的(de)路段貨車無法經由過程。在(zài)該市有兩個(gè)重要(yào / yāo)的(de)市場 A 和(hé / huò) B，分别在(zài)路口 1 和(hé / huò) n 鄰近，貨車大(dà)年夜市場 A出(chū)發，起首走到(dào)路口 1 ，然後經由公路體系走到(dào)路口 n，才能達到(dào)市場 B。

兩個(gè)市場異常繁華，天天有很多貨車往返于(yú)兩個(gè)市場之(zhī)間。市長發明，因爲(wéi / wèi)限高杆很多，導緻貨車可能須要(yào / yāo)繞行才能往返于(yú)市場之(zhī)間，這(zhè)使得貨車袈溱公路體系中的(de)行駛路程變長，增長了(le／liǎo)對公路體系的(de)損耗，增長了(le／liǎo)能源的(de)消費，同時(shí)還增長了(le／liǎo)情況污染。市長決定要(yào / yāo)将兩段門路中的(de)限高杆拆除，使得市場 A 和(hé / huò)市場 B 之(zhī)間的(de)路程變短。請問最多能削減多長的(de)距離？

【輸入格局】

輸入的(de)第一行包含兩個(gè)整數 n, m，分别表示路口的(de)數量和(hé / huò)門路的(de)段數。
接下來(lái) m 行，每行四個(gè)整數 a, b, c, d，表示路口 a 和(hé / huò)路口 b 之(zhī)間有一段長度爲(wéi / wèi) c 的(de)門路。如不(bù)雅 d 爲(wéi / wèi) 0，表示這(zhè)段門路膳绫腔有限高杆；如不(bù)雅 d 爲(wéi / wèi) 1，表示這(zhè)段門路上(shàng)有限高杆。兩個(gè)路口之(zhī)間可能有多段門路。
輸入數據包管在(zài)不(bù)拆除限高杆的(de)情況下，貨車能經由過程公路體系大(dà)年夜路口 1 正常行駛到(dào)路口 n。

【輸出(chū)格局】
輸出(chū)一行，包含一個(gè)整數，表示拆除兩段門路的(de)限高杆後，市場 A 和(hé / huò)市場B 之(zhī)間的(de)路程最大(dà)年夜削減多長距離。

【樣例輸入】
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
【樣例輸出(chū)】
6

【樣例解釋】

隻有兩段門路有限高杆，全部拆除後，1 到(dào) n 的(de)路程由本來(lái)的(de) 17 變爲(wéi / wèi)了(le／liǎo)
11，削減了(le／liǎo) 6。

【評測用例範圍與商定】

對于(yú) 30% 的(de)評測樣例，2 ≤ n ≤ 10，1 ≤ m ≤ 20, 1 ≤ c ≤ 100。
對于(yú) 50% 的(de)評測樣例，2 ≤ n ≤ 100，1 ≤ m ≤ 1000, 1 ≤ c ≤ 1000。
對于(yú) 70% 的(de)評測樣例，2 ≤ n ≤ 1000，1 ≤ m ≤ 10000, 1 ≤ c ≤ 10000。
對于(yú)所有評測樣例，2 ≤ n ≤ 10000，2 ≤ m ≤ 100000, 1 ≤ c ≤ 10000，至少
有兩段門路有限高杆。

先計算不(bù)拆限高架的(de)情況下,即d等于(yú)1的(de)輸入數據,我們先保存起來(lái),個(gè)中ganx保存起點,gany保存終點,ganLi保存距離

因爲(wéi / wèi)藍橋杯是(shì)閉卷測驗,dijkstra算法一會兒想不(bù)起來(lái)了(le／liǎo),所以(yǐ)應用了(le／liǎo)floyd算法,暴力三層for輪回,找到(dào)每個(gè)點之(zhī)間的(de)最短路徑保存在(zài)li1數組中,把1到(dào)n的(de)最短路徑保存在(zài) qianAns 中

然後再兩層for輪回遍曆限高的(de)門路,應用li2臨時(shí)數組複制li1的(de)最短路數據,然後測驗測驗把兩個(gè)拆掉落限高的(de)路加進去,再求一遍最短路

多次遍曆完成,計算出(chū)最短值

相減就(jiù)是(shì)謎底,算法異常差,但基本樣例可以(yǐ)過

#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: 畫中漂流

【問題描述】

在(zài)夢境中，你踏上(shàng)了(le／liǎo)一隻木筏，在(zài)江上(shàng)漂流。根據對本地(dì / de)的(de)懂得，你知道(dào)在(zài)你下流 D 米處有一個(gè)峽谷，如不(bù)雅你向下流前
進大(dà)年夜于(yú)等于(yú) D 米則必逝世無疑。如今你打響了(le／liǎo)急救德律風，T 秒後救濟隊會達到(dào)并将你救上(shàng)岸。水流速度是(shì)1 m/s，你如今有 M 點體力。每消費一點體力，你可以(yǐ)整潔秒槳使船向上(shàng)遊進步 1m，不(bù)然會向下流進步 1m (水流)。M 點體力需在(zài)救濟隊趕來(lái)前花光。因爲(wéi / wèi)江面太寬了(le／liǎo)，憑借你本身的(de)力量弗成能上(shàng)岸。請問，有若幹種劃槳的(de)籌劃可以(yǐ)讓你得救。

兩個(gè)劃槳籌劃不(bù)合是(shì)指：存在(zài)某一秒鍾，一個(gè)籌劃劃槳，另一個(gè)籌劃不(bù)劃。

【輸入格局】

輸入一行包含三個(gè)整數 D, T, M。

【輸出(chū)格局】
輸出(chū)一個(gè)整數，表示可以(yǐ)讓你得救的(de)總籌劃數，謎底可能很大(dà)年夜，請輸出(chū)方
案數除以(yǐ) 1, 000, 000, 007 的(de)餘數。

【樣例輸入】
1 6 3
【樣例輸出(chū)】
5

【評測用例範圍與商定】

對于(yú) 50% 的(de)評測用例，1 ≤ T ≤ 350。
對于(yú)所有評測用例，1 ≤ T ≤ 3000, 1 ≤ D ≤ T, 1 ≤ M ≤ 1500。

我應用了(le／liǎo)廣搜,構造體的(de)weizhi是(shì)相對于(yú)起點的(de)地(dì / de)位,tili爲(wéi / wèi)當前還剩下的(de)體力,time是(shì)當前殘剩的(de)時(shí)光

留意标題請求,必須在(zài)救濟隊來(lái)之(zhī)前把體力用完,如不(bù)雅沒用完,不(bù)計數

#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: 觀光家

【問題描述】

早年，在(zài)海上(shàng)有 n 個(gè)島嶼，編号 1 至 n。居平易近們深受洋流困擾，無法達到(dào)比本身當前地(dì / de)點島嶼編号更小的(de)島嶼。經由數年今後，島嶼上(shàng)的(de)人(rén)數跟着島嶼的(de)編号遞增（可能相等）。作爲(wéi / wèi)一名出(chū)色的(de)觀光家（RP 學家），你想大(dà)年夜 1 号島嶼出(chū)發開啓一次路程，以(yǐ)獲得更多的(de) RP，因爲(wéi / wèi)受到(dào)海洋的(de)洋流影響，你隻能去到(dào)比當前島嶼編号更大(dà)年夜的(de)島嶼。因爲(wéi / wèi)你比較仁慈，你會在(zài)分開一個(gè)島嶼的(de)時(shí)刻将你的(de) RP 分散給島平易近，具體的(de)：你的(de) RP 會除以(yǐ) 2（用去尾法取整，或者說(shuō)向零取整）（當你的(de) RP 小于(yú)零時(shí)，島平易近也(yě)依舊要(yào / yāo)幫你分擔，畢竟你們已經建立起了(le／liǎo)深摯的(de)友情）。第 i 号島嶼有 Ti 人(rén), 然則你很抉剔，每次你大(dà)年夜 j 号島嶼達到(dào) i 号島嶼時(shí)，你隻會在(zài)達到(dào)的(de)島嶼上(shàng)做 Ti × T j 件功德（一件功德可以(yǐ)獲得 1 點 RP)。

獨一不(bù)足的(de)是(shì)，因爲(wéi / wèi)你在(zài)島上(shàng)住宿，勞平易近傷财，你會扣除巨量 RP，第 i 号島嶼的(de)住宿扣除 Fi 點 RP。留意：将分開一個(gè)島嶼時(shí)，先将 RP 扣除一半，再扣除住宿的(de) RP，最後在(zài)新達到(dào)的(de)島嶼上(shàng)做功德，增長 RP。分開 1 号島嶼時(shí)須要(yào / yāo)扣除在(zài) 1 号島嶼住宿的(de) RP，當達到(dào)這(zhè)段路程的(de)最後一個(gè)島嶼上(shàng)時(shí)，要(yào / yāo)做完功德，行程才能争止，也(yě)就(jiù)是(shì)說(shuō)不(bù)消扣除在(zài)最後達到(dào)的(de)島嶼上(shàng)住宿的(de) RP。你因爲(wéi / wèi)酷愛觀光 (RP)，所以(yǐ)大(dà)年夜 1 号島嶼開端觀光，初始時(shí)你有 0 點 RP。

你欲望選擇一些島嶼經由，最終選擇一個(gè)島嶼停下來(lái)，求最大(dà)年夜的(de) RP 值是(shì)若幹？

【輸入格局】

輸入的(de)第一行包含一個(gè)數 n , 表示島嶼的(de)總數。

第二行包含 n 個(gè)整數 T1, T2, · · · , Tn , 表示每個(gè)島嶼的(de)人(rén)口數。

第三行包含 n 個(gè)整數 F1, F2, · · · , Fn , 表示每個(gè)島嶼旅店損掉的(de) RP。

【輸出(chū)格局】

輸出(chū)一個(gè)數，表示最大(dà)年夜獲得的(de) RP 值。

【樣例輸入】
3
4 4 5
1 10 3
【樣例輸出(chū)】
19

【樣例解釋】

大(dà)年夜一号島嶼直接走到(dào)三号島嶼最優，初始 0 點 RP，扣除一半取整變成 0點。扣除在(zài)一号節點住宿的(de) 1 RP，在(zài)三号島嶼做功德産生 4 × 5 = 20 點 RP,最終獲得 19 點 RP。

【樣例輸入】
5
969 980 1013 1016 1021
888423 945460 865822 896150 946615
【樣例輸出(chū)】
246172

【評測用例範圍與商定】

對于(yú) 20% 的(de)評測用例，1 ≤ n ≤ 15；
對于(yú) 70% 的(de)評測用例，1 ≤ n ≤ 5000；
對于(yú)所有評測用例，1 ≤ n ≤ 500000, 1 ≤ Ti ≤ 20000, 1 ≤ Fi ≤ 200, 000, 000。
給定的(de) Ti 已經按照升序排序。建議應用 64 位有符号整數進交運算。

我是(shì)完全模仿标題标思路寫得代碼,留意n等于(yú)1的(de)時(shí)刻須要(yào / yāo)特判

#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;
}