一、題目標(biāo)題: 高斯日記
大數(shù)學(xué)家高斯有個(gè)好習(xí)慣：無論如何都要記日記。
他的日記有個(gè)與眾不同的地方，他從不注明年月日，而是用一個(gè)整數(shù)代替，比如：4210
后來人們知道，那個(gè)整數(shù)就是日期，它表示那一天是高斯出生后的第幾天。這或許也是個(gè)好習(xí)慣，它時(shí)時(shí)刻刻提醒著主人：日子又過去一天，還有多少時(shí)光可以用于浪費(fèi)呢？
高斯出生于：1777年4月30日。
在高斯發(fā)現(xiàn)的一個(gè)重要定理的日記上標(biāo)注著：5343，因此可算出那天是：1791年12月15日。
高斯獲得博士學(xué)位的那天日記上標(biāo)著：8113
請你算出高斯獲得博士學(xué)位的年月日。
提交答案的格式是：yyyy-mm-dd, 例如：1980-03-21
一天天模擬即可。
法一：用excell 兩千年一個(gè)輪回
法二： 一天天模擬即可。代碼如下
答案：1799/7/16
#include <queue>
#include <iostream>
#include <stack>
using namespace std;
typedef long long in;
int month[2][13] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int y, m, d;
int f;
int yyy(int yy)
{
if (yy % 400 == 0 || (yy % 4 == 0 && (yy % 100 != 0)))
{
return 0;//run nian;
}
return 1;
}
int main() {
y = 1791, m = 12, d = 15;
int n;
cin >> n;
while (n--)
{
d++;
f = yyy(y);
if (d > month[f][m])
{
m++;
if (m > 12)
{
y++;
m = 1;
}
d = 1;
}
}
cout << y << " " << m << " " << d;
return 0;
}
二、標(biāo)題: 馬虎的算式
小明是個(gè)急性子，上小學(xué)的時(shí)候經(jīng)常把老師寫在黑板上的題目抄錯(cuò)了。
有一次，老師出的題目是：36 x 495 = ?
他卻給抄成了：396 x 45 = ?
但結(jié)果卻很戲劇性，他的答案竟然是對的??！
因?yàn)?36 * 495 = 396 * 45 = 17820
類似這樣的巧合情況可能還有很多，比如：27 * 594 = 297 *54
假設(shè) a b c d e 代表1~9不同的5個(gè)數(shù)字（注意是各不相同的數(shù)字，且不含0）
能滿足形如： ab * cde = adb * ce 這樣的算式一共有多少種呢？
直接暴力
答案：142
// ab * cde = adb * ce
#include<iostream>
using namespace std;
int ans = 0;
int main()
{
int a, b, c, d, e;
for (a = 1; a < 10; a++)
{
for (b = 1; b < 10; b++)
{
for (c = 1; c < 10; c++)
{
for (d = 1; d < 10; d++)
{
for (e = 1; e < 10; e++)
{
if (a!=b&&a!=c&&a!=d&&a!=e&&b!=c&&b!=d&&b!=e&&c!=d&&c!=e&&e!=d)
if ((a * 10 + b) * (c * 100 + 10 * d + e) == (a * 100 + 10 * d + b) *(10 * c + e))
{
ans++;
}
}
}
}
}
}
cout << ans;
return 0;
}
三、題目標(biāo)題: 第39級臺階
小明剛剛看完電影《第39級臺階》，離開電影院的時(shí)候，他數(shù)了數(shù)禮堂前的臺階數(shù)，恰好是39級! 站在臺階前，他突然又想著一個(gè)問題：
如果我每一步只能邁上1個(gè)或2個(gè)臺階。先邁左腳，然后左右交替，最后一步是邁右腳，也就是說一共要走偶數(shù)步。那么，上完39級臺階，有多少種不同的上法呢？
請你利用計(jì)算機(jī)的優(yōu)勢，幫助小明尋找答案。
要求提交的是一個(gè)整數(shù)。
注意：不要提交解答過程，或其它的輔助說明文字。
方法：斐波拉契數(shù)列，技巧用0，1表示左腳右腳
答案：51167078
#include<iostream>
using namespace std;
int f[40];
int fun(int n,int f)
{
if(n==1)//一步
{
if(f==1)//左腳
return 1;
return 0;
}
if(n==2)//不管第二個(gè)臺階只能是一種
{
return 1;
}
int r=fun(n-1,!f)+fun(n-2,!f);
return r;
}
int main()
{
cout<<fun(39,0);
return 0;
}
四、標(biāo)題: 黃金連分?jǐn)?shù)
黃金分割數(shù)0.61803... 是個(gè)無理數(shù)，這個(gè)常數(shù)十分重要，在許多工程問題中會出現(xiàn)。有時(shí)需要把這個(gè)數(shù)字求得很精確。
對于某些精密工程，常數(shù)的精度很重要。也許你聽說過哈勃太空望遠(yuǎn)鏡，它首次升空后就發(fā)現(xiàn)了一處人工加工錯(cuò)誤，對那樣一個(gè)龐然大物，其實(shí)只是鏡面加工時(shí)有比頭發(fā)絲還細(xì)許多倍的一處錯(cuò)誤而已，卻使它成了“近視眼”!!
言歸正傳，我們?nèi)绾吻蟮命S金分割數(shù)的盡可能精確的值呢？有許多方法。
比較簡單的一種是用連分?jǐn)?shù)：
1
黃金數(shù) = ---------------------
1
1 + -----------------
1
1 + -------------
1
1 + ---------
1 + ...
這個(gè)連分?jǐn)?shù)計(jì)算的“層數(shù)”越多，它的值越接近黃金分割數(shù)。
請你利用這一特性，求出黃金分割數(shù)的足夠精確值，要求四舍五入到小數(shù)點(diǎn)后100位。
小數(shù)點(diǎn)后3位的值為：0.618
小數(shù)點(diǎn)后4位的值為：0.6180
小數(shù)點(diǎn)后5位的值為：0.61803
小數(shù)點(diǎn)后7位的值為：0.6180340
（注意尾部的0，不能忽略）
你的任務(wù)是：寫出精確到小數(shù)點(diǎn)后100位精度的黃金分割值
答案： 0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375
思路 用數(shù)組來存斐波拉契數(shù)列 得到分子分母， 又用模擬除法求得后一百位小數(shù)
=========================================================
當(dāng)時(shí)我搜了好多博客，都是用斐波拉契數(shù)列 第39位 是正確答案，呵呵，精度不夠好嗎，博客抄來超去有意思嗎，也要挑正確的抄呀，哈哈哈哈
#include"stdio.h"
int a[101];//a保存小數(shù)結(jié)果
//輸出一個(gè)數(shù)組中保存的值
void print(int *x)
{
int i, j;
for (i = 99; i >= 0; i--)
if (x[i])
{
j = i;
break;
}
for (i = j; i >= 0; i--)
printf("%d", x[i]);
printf("\n");
}
void add(int *x, int *y)
{
int i, length_x, length_y;
int jinwei = 0;//記錄進(jìn)位
int temp_y[100];
for (i = 0; i<100; i++)//計(jì)算兩個(gè)數(shù)字的長度
{
if (x[i] == 0)
length_x = i;
if (y[i] == 0)
length_y = i;
temp_y[i] = y[i];
}
//x[0]保存最低位
for (i = 0; i<100; i++)//y=y+x,x=y
{
y[i] = x[i] + y[i] + jinwei;
jinwei = y[i] / 10;
y[i] = y[i] % 10;
}
for (i = 0; i<100; i++)
x[i] = temp_y[i];//把之前的分母傳給分子
}
//比較兩個(gè)數(shù)數(shù)組里面保存的數(shù)字的大小,x[0]是最低位
int subcmp(int *x, int *y)
{
int j_x, j_y, i;
for (i = 99; i >= 0; i--)//確定最高位
if (x[i])
{
j_x = i;
break;
}
for (i = 99; i >= 0; i--)//確定最高位
if (y[i])
{
j_y = i;
break;
}
if (j_x>j_y) return 1; //x中的值大于y中的
if (j_x<j_y) return -1;//x中的值小于y中的
if (j_x == j_y)//當(dāng)兩個(gè)數(shù)位數(shù)相同的時(shí)候
{
for (i = j_x; i >= 0; i--)
{
if (x[i]>y[i]) return 1;
if (x[i]<y[i]) return -1;
}
}
return 0;
}
//兩個(gè)數(shù)相減,結(jié)果保存在x[]中
void sub(int *x, int *y)
{
//這里保證x[]>y[]
int j_y, i;
for (i = 99; i >= 0; i--)//確定最高位
if (x[i])
{
j_y = i;
break;
}
//從數(shù)的低位到高位依次相減
for (i = 0; i <= j_y; i++)
{
if (x[i] >= y[i])
{
x[i] = x[i] - y[i];
continue;
}
if (x[i]<y[i])
{
x[i] = x[i] + 10 - y[i];
x[i + 1]--;
}
}
}
void xiaoshu(int *x, int *y)
{
int i, xx[100], yy[100];
for (i = 0; i<100; i++)//將兩個(gè)數(shù)組保存起來以防止干擾原數(shù)組的值
{
xx[i] = x[i];
yy[i] = y[i];
}
for (i = 0; i<101; i++)
{
if (-1 == subcmp(xx, yy))
{
a[i++] = 0;//分子小于分母，這一位為0
for (int j = 99; j >= 1; j--)
xx[j] = xx[j - 1];
xx[0] = 0;//擴(kuò)大十倍,相當(dāng)于分子成了一個(gè)10；
}
while (subcmp(xx, yy) >= 0)//a[i]為商；
{
a[i]++;
sub(xx, yy);
}
for (int j = 99; j >= 1; j--)//上面已經(jīng)算好了一位
xx[j] = xx[j - 1];
xx[0] = 0;//每算完一位,擴(kuò)大十倍
}
}
int main()
{
int x[100] = { 0 }, y[100] = { 0 };//x是被除數(shù),y是除數(shù)
int i, b[200];
b[0] = 1, b[1] = 2;
x[0] = 1, y[0] = 2;
for (i = 0; i<250; i++)
add(x, y);
printf("dsfsdf\n");
printf("此時(shí)被除數(shù)的值是:\n");
print(x);
printf("此時(shí)除數(shù)的值是:\n");
print(y);
xiaoshu(x, y);
printf("0.\n");
for (i = 1; i<101; i++)
{
printf("%d ", a[i]);
if (i % 10 == 0)
printf("\n");
}
return 0;
}
五、題目標(biāo)題：前綴判斷
如下的代碼判斷 needle_start指向的串是否為haystack_start指向的串的前綴，如不是，則返回NULL。
比如："abcd1234" 就包含了 "abc" 為前綴
char* prefix(char* haystack_start, char* needle_start)
{
char* haystack = haystack_start;
char* needle = needle_start;
while(*haystack && *needle){
if(______________________________) return NULL; //填空位置
}
if(*needle) return NULL;
return haystack_start;
}
請分析代碼邏輯，并推測劃線處的代碼，通過網(wǎng)頁提交。
注意：僅把缺少的代碼作為答案，千萬不要填寫多余的代碼、符號或說明文字??！
答案:haystack++!=needle++
第六題
標(biāo)題：三部排序
一般的排序有許多經(jīng)典算法，如快速排序、希爾排序等。
但實(shí)際應(yīng)用時(shí)，經(jīng)常會或多或少有一些特殊的要求。我們沒必要套用那些經(jīng)典算法，可以根據(jù)實(shí)際情況建立更好的解法。
比如，對一個(gè)整型數(shù)組中的數(shù)字進(jìn)行分類排序：
使得負(fù)數(shù)都靠左端，正數(shù)都靠右端，0在中部。注意問題的特點(diǎn)是：負(fù)數(shù)區(qū)域和正數(shù)區(qū)域內(nèi)并不要求有序。可以利用這個(gè)特點(diǎn)通過1次線性掃描就結(jié)束戰(zhàn)斗!!
以下的程序?qū)崿F(xiàn)了該目標(biāo)。
其中x指向待排序的整型數(shù)組，len是數(shù)組的長度。
void sort3p(int* x, int len)
{
int p = 0;
int left = 0;
int right = len-1;
while(p<=right){
if(x[p]<0){
int t = x[left];
x[left] = x[p];
x[p] = t;
left++;
p++;
}
else if(x[p]>0){
int t = x[right];
x[right] = x[p];
x[p] = t;
right--;
}
else{
__________________________; //填空位置
}
}
}
如果給定數(shù)組：
25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0
則排序后為：
-3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25
請分析代碼邏輯，并推測劃線處的代碼，通過網(wǎng)頁提交
注意：僅把缺少的代碼作為答案，千萬不要填寫多余的代碼、符號或說明文字??！
答案:p++
7、標(biāo)題：錯(cuò)誤票據(jù)
某涉密單位下發(fā)了某種票據(jù)，并要在年終全部收回。
每張票據(jù)有唯一的ID號。全年所有票據(jù)的ID號是連續(xù)的，但I(xiàn)D的開始數(shù)碼是隨機(jī)選定的。
因?yàn)楣ぷ魅藛T疏忽，在錄入ID號的時(shí)候發(fā)生了一處錯(cuò)誤，造成了某個(gè)ID斷號，另外一個(gè)ID重號。
你的任務(wù)是通過編程，找出斷號的ID和重號的ID。
假設(shè)斷號不可能發(fā)生在最大和最小號。
要求程序首先輸入一個(gè)整數(shù)N(N<100)表示后面數(shù)據(jù)行數(shù)。
接著讀入N行數(shù)據(jù)。
每行數(shù)據(jù)長度不等，是用空格分開的若干個(gè)（不大于100個(gè)）正整數(shù)（不大于100000）
每個(gè)整數(shù)代表一個(gè)ID號。
要求程序輸出1行，含兩個(gè)整數(shù)m n，用空格分隔。
其中，m表示斷號ID，n表示重號ID
例如：
用戶輸入：
2
5 6 8 11 9
10 12 9
則程序輸出：
7 9
再例如：
用戶輸入：
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
則程序輸出：
105 120
資源約定：
峰值內(nèi)存消耗 < 64M
CPU消耗 < 1000ms
剛開始是全部采用字符輸入，其實(shí)不用這么麻煩，%d%c，
==========================================================后面在藍(lán)橋杯官網(wǎng)跑了一遍，是錯(cuò)的呀，可能有事后數(shù)字末尾是空格 叭叭叭粑粑，后一個(gè)方法過了
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int nu[1000];
int main()
{
int n, m;
cin >> n;
int nn;
nn = n;
int i = 0;
char c;
while (n)
{
scanf("%d%c", &nu[i++], &c);
if (c == '\n')
n--;
}
sort(nu, nu + i);
int temp = nu[0];
int copy=0, disa=0;
for (int j = 1; j<i; j++)
{
if (temp == nu[j] -2)
{
disa = temp +1;
}
if (temp == nu[j])
{
copy = temp;
}
temp = nu[j];
}
cout << disa << " " << copy;
return 0;
}
字符串讀入，這個(gè)過了
#include <iostream>
#include <string>
#include<algorithm>
using namespace std;
int n;
char a;
char b;
int x;
int num[10005];
char s[10000];
int main()
{
string k;
cin >> n;
int nn = n;
getchar();
int i = 0;
int f = 0;
while (nn--)
{
getline(cin, k);
for (int j = 0; j< k.length(); j++)
{
a = k[j];
if (a >= '0'&&a <= '9')//數(shù)字
{
x = x * 10 + a - '0';
f = 1;
}
if (a ==' '&&f == 1)//等于空格，有數(shù)字
{
num[i] = x;
i++;
x = 0;
f = 0;
}
}
if (f)
{
num[i] = x;
i++;
x = 0;
f = 0;
}
}
sort(num, num + i);
int x1, x2,x3;
x1 = num[0];
for (int j = 1; j < i; j++)
{
if (x1 != num[j]-1)
{
if (x1 == num[j])
{
x3 = num[j];
}
else
x2 = num[j]-1;//斷號ID；
}
x1 = num[j];
}
cout << x2 << " " << x3 << endl;
return 0;
}
- 題目標(biāo)題：翻硬幣
小明正在玩一個(gè)“翻硬幣”的游戲。
桌上放著排成一排的若干硬幣。我們用 * 表示正面，用 o 表示反面（是小寫字母，不是零）。
比如，可能情形是：oooooo
如果同時(shí)翻轉(zhuǎn)左邊的兩個(gè)硬幣，則變?yōu)椋簅ooo**oooo
現(xiàn)在小明的問題是：如果已知了初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)，每次只能同時(shí)翻轉(zhuǎn)相鄰的兩個(gè)硬幣,那么對特定的局面，最少要翻動多少次呢？
我們約定：把翻動相鄰的兩個(gè)硬幣叫做一步操作，那么要求：
程序輸入：
兩行等長的字符串，分別表示初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)。每行的長度<1000
程序輸出：
一個(gè)整數(shù)，表示最小操作步數(shù)
例如：
用戶輸入：
o****o****
程序應(yīng)該輸出：
5
再例如：
用戶輸入：
ooo*
ooo***
程序應(yīng)該輸出：
1
資源約定：
峰值內(nèi)存消耗 < 64M
CPU消耗 < 1000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。
注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>， 不能通過工程設(shè)置而省略常用頭文件。
提交時(shí)，注意選擇所期望的編譯器類型。
方法：貪心，不同則翻一次硬幣
#include<iostream>
#include<string>
using namespace std;
string s;
string ss;
int main()
{
cin>>s>>ss;
int n=0;
for(int i=0;i<s.length();i++)
{
if(s[i]!=ss[i])
{
n++;
if(s[i]=='*')
{
s[i]='o';
}
else
{
s[i]='*';
}
if(s[i+1]=='*')
{
s[i+1]='o';
}
else
{
s[i+1]='*';
}
}
}
cout<<n;
return 0;
}
- 標(biāo)題：帶分?jǐn)?shù)
100 可以表示為帶分?jǐn)?shù)的形式：100 = 3 + 69258 / 714
還可以表示為：100 = 82 + 3546 / 197
注意特征：帶分?jǐn)?shù)中，數(shù)字1~9分別出現(xiàn)且只出現(xiàn)一次（不包含0）。
類似這樣的帶分?jǐn)?shù)，100 有 11 種表示法。
題目要求：
從標(biāo)準(zhǔn)輸入讀入一個(gè)正整數(shù)N (N<1000*1000)
程序輸出該數(shù)字用數(shù)碼1~9不重復(fù)不遺漏地組成帶分?jǐn)?shù)表示的全部種數(shù)。
注意：不要求輸出每個(gè)表示，只統(tǒng)計(jì)有多少表示法！
例如：
用戶輸入：
100
程序輸出：
11
再例如：
用戶輸入：
105
程序輸出：
6
資源約定：
峰值內(nèi)存消耗 < 64M
CPU消耗 < 3000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。
注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>， 不能通過工程設(shè)置而省略常用頭文件。
提交時(shí)，注意選擇所期望的編譯器類型。
思路：使用全排列，判斷啊，數(shù)字的取值范圍
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int ans = 0;
int b = 0, c = 0, d = 0;
int bb, cc, dd;
int num = 0;
int a[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };//n= b+c/d;
do{
num++;
for (int i = 0; i<6; i++)//b 的取值 只能是1到6位
{
for (int j = 0; j <= i; j++)
{
b = b * 10 + a[j];//求得b的值
bb = b;
}
b = 0;
if (bb<n)//b要小于n
{
for (int k = i + 1; k<9; k++)//結(jié)束位置 c 的結(jié)束2位置
{
if ((k - i) >= (8 - k)) //c的個(gè)數(shù)要比d多
{
for (int kk = i + 1; kk <= k; kk++)//計(jì)算c的值
{
c = c * 10 + a[kk];//c的大小
}
cc = c;
c = 0;
for (int kk = k + 1; kk <= 8; kk++)
{
d = d * 10 + a[kk];//c的大小
}
dd = d;
d = 0;
if (cc>dd)
{
if ((n - bb)*dd == cc)
{
//cout << n << " " << bb << " " << cc << " " << dd << endl;
ans++;
}
}
}
}
}
}
} while (next_permutation(a, a + 9));
cout << ans;
return 0;
}
- 標(biāo)題：連號區(qū)間數(shù)
小明這些天一直在思考這樣一個(gè)奇怪而有趣的問題：
在1~N的某個(gè)全排列中有多少個(gè)連號區(qū)間呢？這里所說的連號區(qū)間的定義是：
如果區(qū)間[L, R] 里的所有元素（即此排列的第L個(gè)到第R個(gè)元素）遞增排序后能得到一個(gè)長度為R-L+1的“連續(xù)”數(shù)列，則稱這個(gè)區(qū)間連號區(qū)間。
當(dāng)N很小的時(shí)候，小明可以很快地算出答案，但是當(dāng)N變大的時(shí)候，問題就不是那么簡單了，現(xiàn)在小明需要你的幫助。
輸入格式：
第一行是一個(gè)正整數(shù)N (1 <= N <= 50000), 表示全排列的規(guī)模。
第二行是N個(gè)不同的數(shù)字Pi(1 <= Pi <= N)， 表示這N個(gè)數(shù)字的某一全排列。
輸出格式：
輸出一個(gè)整數(shù)，表示不同連號區(qū)間的數(shù)目。
示例：
用戶輸入：
4
3 2 4 1
程序應(yīng)輸出：
7
用戶輸入：
5
3 4 2 5 1
程序應(yīng)輸出：
9
解釋：
第一個(gè)用例中，有7個(gè)連號區(qū)間分別是：[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
第二個(gè)用例中，有9個(gè)連號區(qū)間分別是：[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
資源約定：
峰值內(nèi)存消耗 < 64M
CPU消耗 < 5000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。
注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>， 不能通過工程設(shè)置而省略常用頭文件。
提交時(shí)，注意選擇所期望的編譯器類型。
法一：技巧 區(qū)間中最大值減最小值就是 區(qū)間數(shù)目 就是連號區(qū)間
法二： 比較高級的辦法，但是好像時(shí)間還要用的多一些樣,
法二：啦啦啦啦，超時(shí)了，在藍(lán)橋杯上 跑了一遍80 分 哈哈哈哈，裝逼失敗
法一：暴力
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int num[50000];
int n,m,k;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>num[i];
}
int minn=n;
int maxn=0;
int ans=0;
for(int i=0;i<n;i++)
{
minn=n;
maxn=0;
for(int j=i;j<n;j++)
{
minn=min(num[j],minn);
maxn=max(maxn,num[j]);
if((j-i)==(maxn-minn))
{
ans++;
}
}
}
cout<<ans;
return 0;
}
法二： RMQ 區(qū)間詢問，保留區(qū)間的最大值，與最小值。
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int dp[50000][16];//每個(gè)區(qū)間最大的
int num[50000];
int dp2[50000][16];
int fun1(int i,int j)
{
int sum=j-i+1;
int n=log2(sum);//n的幾次方
int maxn=dp[i][n];
int nn;
nn=n;
int ii=i;
sum-=(1<<n);
while(sum!=0)
{
ii+=(1<<n);
n=log2(sum);
maxn=max(maxn,dp[ii][n]);
sum-=(1<<n);
}
return maxn;
}
int fun2(int i,int j)
{
int ii=i;
int sum=j-i+1;
int n=log2(sum);
int minx=dp2[ii][n];
sum-=(1<<n);
while(sum!=0)
{
ii+=(1<<n);
n=log2(sum);
minx=min(minx,dp2[ii][n]);
sum-=(1<<n);
}
return minx;
}
int main()
{
int n;
cin>>n;
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
int ans=0;
for(int i=0;i<n;i++)
{
cin>>num[i];
dp[i][0]=num[i];
dp2[i][0]=num[i];
}
for(int j=1;j<=log2(n);j++)
{
for(int i=0;(1<<j)+i-1<n;i++)
{
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
}
}
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if((fun1(i,j)-fun2(i,j))==(j-i))
{
ans++;
}
}
}
cout<<ans;
return 0;
}
