「一隻青蛙一張嘴，兩隻眼睛四條腿。兩隻青蛙兩張嘴，四隻眼睛八條腿。三隻青蛙三張嘴，六隻眼睛十二條腿。……二十隻青蛙二十張嘴，四十隻眼睛八十條腿。」
請問上面這段文字，如果完全不省略，全部寫出來，從 1 到 20 只青蛙，總共有多少個漢字。
約定：數位 2 單獨出現讀成 「兩」，在其他數裡面讀成 「二」，例如 「十二」。10 讀作 「十」，11 讀作 「十一」，22 讀作 「二十二」。請只計算漢字的個數，標點符號不計算。
上限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;
}
今年是 2020 年，今天是 10 月 18 日。
請問在 1 到 2020 中，有多少個數與 1018 互質。
因為是填空題,所以不需要考慮什麼演演算法,直接暴力試就可
#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;
}
A 市的車牌由六位組成，其中前三位可能為數位 0 至 9，或者字母 A 至 F，每位有 16 種可能。後三位只能是數位 0 至 9。為了減少攀比，車牌中不能有連續三位是相同的字元。
例如，202020 是合法的車牌，AAA202 不是合法的車牌，因為前三個字母相同。
請問，A 市有多少個合法的車牌？
總共情況為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;
}
小藍定義了一個 Fibonacci 集合 F，集合的元素如下定義：
1. 最小的 5 個 Fibonacci 數 1, 2, 3, 5, 8 屬於集合 F。
2. 如果一個元素 x 屬於 F，則 3x + 2、5x + 3 和 8x + 5 都屬於集合 F。
3. 其他元素都不屬於 F。
請問，這個集合中的第 2020 小元素的值是多少？
標準深搜題,數位要求也不大,暴力即可
從最小的五個數開始搜尋,把搜尋到的數位置一,然後再找地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;
}
小藍有一個字母矩陣，他喜歡和小夥伴們在這個矩陣上玩一些遊戲。今天，他打算玩找上升子串的遊戲。遊戲是合作性質的。小藍和小夥伴們首先要在矩陣中指定一個位置，然後從這個位置開始，向上下左右相鄰位置移動，移動必須滿足所到達位置上的字母比當前位置大。小藍和小夥伴們可以移動任意多次，也可以隨時停下來，這樣就找到了一個上升子串。只要子串在矩陣中的位置不同，就認為是不同的子串。
小藍想知道，一共可以找到多少個上升子串。小藍的矩陣很大，已經放在了試題目錄下面，叫 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;
}
小藍要處理非常多的資料，其中有一些資料是日期。在小藍處理的日期中有兩種常用的形式：英文形式和數位形式。英文形式採用每個月的英文的前三個字母作為月份標識，後面跟兩位數位表示日期，月份標識第一個字母大寫，後兩個字母小寫，日期小於 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;
}
九九乘法表是學習乘法時必須要掌握的。在不同進位制數下，需要不同的乘
法表。
例如，四進位制下的乘法表如下所示：
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;
}
【問題描述】
某市有 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;
}
【問題描述】
在夢境中，你踏上了一隻木筏，在江上漂流。根據對當地的瞭解，你知道在你下游 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;
}
【問題描述】
從前，在海上有 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;
}