一、題目標(biāo)題: 高斯日記
大數(shù)學(xué)家高斯有個(gè)好習(xí)慣：無(wú)論如何都要記日記悟泵。
他的日記有個(gè)與眾不同的地方专钉，他從不注明年月日挑童，而是用一個(gè)整數(shù)代替，比如：4210
后來(lái)人們知道跃须，那個(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
請(qǐng)你算出高斯獲得博士學(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é)果卻很戲劇性孽江，他的答案竟然是對(duì)的！番电！
因?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級(jí)臺(tái)階
小明剛剛看完電影《第39級(jí)臺(tái)階》，離開電影院的時(shí)候洼冻，他數(shù)了數(shù)禮堂前的臺(tái)階數(shù)，恰好是39級(jí)! 站在臺(tái)階前隅很，他突然又想著一個(gè)問題：
如果我每一步只能邁上1個(gè)或2個(gè)臺(tái)階撞牢。先邁左腳率碾，然后左右交替，最后一步是邁右腳屋彪，也就是說(shuō)一共要走偶數(shù)步所宰。那么，上完39級(jí)臺(tái)階畜挥，有多少種不同的上法呢仔粥？
請(qǐng)你利用計(jì)算機(jī)的優(yōu)勢(shì)，幫助小明尋找答案蟹但。
要求提交的是一個(gè)整數(shù)躯泰。
注意：不要提交解答過程，或其它的輔助說(shuō)明文字华糖。
方法：斐波拉契數(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è)臺(tái)階只能是一種
{
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è)無(wú)理數(shù)诵竭，這個(gè)常數(shù)十分重要，在許多工程問題中會(huì)出現(xiàn)兼搏。有時(shí)需要把這個(gè)數(shù)字求得很精確卵慰。
對(duì)于某些精密工程，常數(shù)的精度很重要佛呻。也許你聽說(shuō)過哈勃太空望遠(yuǎn)鏡裳朋，它首次升空后就發(fā)現(xiàn)了一處人工加工錯(cuò)誤，對(duì)那樣一個(gè)龐然大物件相，其實(shí)只是鏡面加工時(shí)有比頭發(fā)絲還細(xì)許多倍的一處錯(cuò)誤而已再扭，卻使它成了“近視眼”!!
言歸正傳，我們?nèi)绾吻蟮命S金分割數(shù)的盡可能精確的值呢夜矗？有許多方法泛范。
比較簡(jiǎn)單的一種是用連分?jǐn)?shù)：
1
黃金數(shù) = ---------------------
1
1 + -----------------
1
1 + -------------
1
1 + ---------
1 + ...
這個(gè)連分?jǐn)?shù)計(jì)算的“層數(shù)”越多，它的值越接近黃金分割數(shù)紊撕。
請(qǐng)你利用這一特性罢荡，求出黃金分割數(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ù)組來(lái)存斐波拉契數(shù)列 得到分子分母， 又用模擬除法求得后一百位小數(shù)
=========================================================
當(dāng)時(shí)我搜了好多博客浪南，都是用斐波拉契數(shù)列 第39位 是正確答案笼才，呵呵，精度不夠好嗎络凿，博客抄來(lái)超去有意思嗎骡送，也要挑正確的抄呀昂羡，哈哈哈哈
#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ù)字的長(zhǎng)度
{
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];//把之前的分母?jìng)鹘o分子
}
//比較兩個(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ù)組保存起來(lái)以防止干擾原數(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;
}
請(qǐng)分析代碼邏輯篮愉，并推測(cè)劃線處的代碼腐芍，通過網(wǎng)頁(yè)提交。
注意：僅把缺少的代碼作為答案潜支，千萬(wàn)不要填寫多余的代碼甸赃、符號(hào)或說(shuō)明文字！冗酿！
答案:haystack++!=needle++
第六題
標(biāo)題：三部排序
一般的排序有許多經(jīng)典算法埠对，如快速排序、希爾排序等裁替。
但實(shí)際應(yīng)用時(shí)项玛，經(jīng)常會(huì)或多或少有一些特殊的要求。我們沒必要套用那些經(jīng)典算法弱判，可以根據(jù)實(shí)際情況建立更好的解法襟沮。
比如，對(duì)一個(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ù)組的長(zhǎng)度巫玻。
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
請(qǐng)分析代碼邏輯，并推測(cè)劃線處的代碼祠汇，通過網(wǎng)頁(yè)提交
注意：僅把缺少的代碼作為答案仍秤，千萬(wàn)不要填寫多余的代碼、符號(hào)或說(shuō)明文字？珊堋诗力！
答案:p++
7、標(biāo)題：錯(cuò)誤票據(jù)
某涉密單位下發(fā)了某種票據(jù)我抠，并要在年終全部收回姜骡。
每張票據(jù)有唯一的ID號(hào)导坟。全年所有票據(jù)的ID號(hào)是連續(xù)的，但I(xiàn)D的開始數(shù)碼是隨機(jī)選定的圈澈。
因?yàn)楣ぷ魅藛T疏忽，在錄入ID號(hào)的時(shí)候發(fā)生了一處錯(cuò)誤尘惧，造成了某個(gè)ID斷號(hào)康栈，另外一個(gè)ID重號(hào)。
你的任務(wù)是通過編程喷橙，找出斷號(hào)的ID和重號(hào)的ID啥么。
假設(shè)斷號(hào)不可能發(fā)生在最大和最小號(hào)。
要求程序首先輸入一個(gè)整數(shù)N(N<100)表示后面數(shù)據(jù)行數(shù)贰逾。
接著讀入N行數(shù)據(jù)悬荣。
每行數(shù)據(jù)長(zhǎng)度不等，是用空格分開的若干個(gè)（不大于100個(gè)）正整數(shù)（不大于100000）
每個(gè)整數(shù)代表一個(gè)ID號(hào)疙剑。
要求程序輸出1行氯迂，含兩個(gè)整數(shù)m n，用空格分隔言缤。
其中嚼蚀，m表示斷號(hào)ID，n表示重號(hào)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;//斷號(hào)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è)硬幣,那么對(duì)特定的局面，最少要翻動(dòng)多少次呢挖垛？
我們約定：把翻動(dòng)相鄰的兩個(gè)硬幣叫做一步操作痒钝，那么要求：
程序輸入：
兩行等長(zhǎng)的字符串秉颗，分別表示初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)。每行的長(zhǎng)度<1000
程序輸出：
一個(gè)整數(shù)送矩，表示最小操作步數(shù)
例如：
用戶輸入：
o****o****
程序應(yīng)該輸出：
5
再例如：
用戶輸入：
ooo*
ooo***
程序應(yīng)該輸出：
1
資源約定：
峰值內(nèi)存消耗 < 64M
CPU消耗 < 1000ms
請(qǐng)嚴(yán)格按要求輸出蚕甥，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(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
請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(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)題：連號(hào)區(qū)間數(shù)
小明這些天一直在思考這樣一個(gè)奇怪而有趣的問題：
在1~N的某個(gè)全排列中有多少個(gè)連號(hào)區(qū)間呢本砰？這里所說(shuō)的連號(hào)區(qū)間的定義是：
如果區(qū)間[L, R] 里的所有元素（即此排列的第L個(gè)到第R個(gè)元素）遞增排序后能得到一個(gè)長(zhǎng)度為R-L+1的“連續(xù)”數(shù)列碴裙，則稱這個(gè)區(qū)間連號(hào)區(qū)間。
當(dāng)N很小的時(shí)候，小明可以很快地算出答案舔株，但是當(dāng)N變大的時(shí)候莺琳，問題就不是那么簡(jiǎn)單了，現(xiàn)在小明需要你的幫助载慈。
輸入格式：
第一行是一個(gè)正整數(shù)N (1 <= N <= 50000), 表示全排列的規(guī)模惭等。
第二行是N個(gè)不同的數(shù)字Pi(1 <= Pi <= N)， 表示這N個(gè)數(shù)字的某一全排列办铡。
輸出格式：
輸出一個(gè)整數(shù)咕缎，表示不同連號(hào)區(qū)間的數(shù)目。
示例：
用戶輸入：
4
3 2 4 1
程序應(yīng)輸出：
7
用戶輸入：
5
3 4 2 5 1
程序應(yīng)輸出：
9
解釋：
第一個(gè)用例中料扰，有7個(gè)連號(hào)區(qū)間分別是：[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
第二個(gè)用例中，有9個(gè)連號(hào)區(qū)間分別是：[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
資源約定：
峰值內(nèi)存消耗 < 64M
CPU消耗 < 5000ms
請(qǐng)嚴(yán)格按要求輸出焙蹭，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(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ù)目 就是連號(hào)區(qū)間
法二： 比較高級(jí)的辦法，但是好像時(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;
}
