遞歸與分治專題
MT2030 郵箱地址
難度：鉆石 ?? 時間限制：1秒 ?? 占用內(nèi)存：128M
題目描述
一個地址由
<username>@<hostname>[/resource]組成。
其中username和hostname之間只允許有一個@；尖括號< >內(nèi)包含的為必選項，方括號[ ]內(nèi)包含的為可選項。如果/出>現(xiàn)，則必須跟有resource字段。各字段要求如下：
username字段允許大寫字母、小寫字母、數(shù)字、下劃線，其長度應(yīng)在1到16。hostname字段類似網(wǎng)址，允許用零個或多個.來分割，但不允許連續(xù)兩個.連在一起。同時，hostname不允許以.開頭或結(jié)束。每一段的要求同username字段，hostname字段的總長度在1到32。resource字段要求同username字段，不限制長度。
現(xiàn)給出一個地址，請判斷是否合法。格式
輸入格式：一行，一個字符串，表示一個地址（保證地址的字符的ASCII在33到127間），地址長度不超過1000字符。
輸出格式：一行，如果合法輸出YES，否則輸出NO。樣例 1
輸入：123@npu.com
輸出：YES相關(guān)知識點：
模擬、字符串
題解
本題的目的是檢測待輸入字符串是否滿足給定的 3 個條件。最簡單的方法就是直接模擬這個檢測過程，即對輸入字符串進(jìn)行掃描（判斷各字段是否滿足給定條件）。由于該題并不是很難，因此將求解的步驟全部注釋在代碼中，如下（已 AC）：
/*
MT2030 郵箱地址
*/
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1005;
// username 字段長度上限
const int USERNAMEMAX = 16;
// hostname 字段長度上限
const int HOSTNAMEMAX = 32;
char address[MAX];
// 該函數(shù)用于檢測要求 1 所提限制
bool judgeLetter(char c)
{
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_') return true;
return false;
}
bool judgeMailAddress(char *str)
{
// p 為臨時指針、atNum 為 @ 符號的個數(shù)、resPos 為資源符號 / 的位置、resNum 為資源符號 / 的個數(shù)、strlen 為字串總長度寄存器
int p = 0, atPos = 0, atNum = 0, resPos = 0, resNum = 0, strlen = 0;
// 下面的循環(huán)將完成以下功能：
// 1、求出字串 str 的長度
// 2、獲取 @ 符號的位置并記錄最后一個 @ 符號的位置
// 3、獲取 / 符號的位置并記錄最后一個 / 符號的位置
while(str[p]){
if(str[p] == '@') {
atPos = p;
atNum++;
}
if(str[p] == '/'){
resPos = p;
resNum++;
}
p++;
}
// 將字串 str 的長度存入 strlen
strlen = p;
// 判斷符號的合法性：當(dāng) @ 符號個數(shù)不為 1 或 / 符號的個數(shù)大于 1 時，該郵箱地址非法
if(atNum != 1 || resNum>1) return false;
// 下面判斷 username 字段的合法性
// 判斷 username 的長度合法性： 當(dāng)username 字段長度為 0 或大于給定長度時，該郵箱地址非法
if(atPos == 0 || atPos > USERNAMEMAX) return false;
// 判斷 username 的字符合法性
p = 0;
while(p<atPos){
if( judgeLetter(str[p]) ) p++;
else return false;
}
// 下面判斷 hostname 的合法性
p++;
// 判斷 hostname 的長度合法性（至少為 1，至多不超過 HOSTNAMEMAX）：
// 1、當(dāng)無 resource 字段時，需要用整個字段的長度 strlen 來與 p 指針的位置進(jìn)行比較
// 2、當(dāng)有 resource 字段時，需要用資源字段的指針 resPos 來與 p 指針的位置進(jìn)行比較
if(( resNum == 0 && (strlen==p || strlen-p>HOSTNAMEMAX) ) || ( resNum == 1 && ( resPos==p || resPos-p>HOSTNAMEMAX))) return false;
// 判斷 hostname 內(nèi)"." 的合法性
if(str[p] == '.' || ( resNum == 0 && str[strlen-1] == '.') || ( resNum == 1 && str[resPos-1] == '.') ) return false;
// namelen 為每次掃描時，兩個 "." 內(nèi)的子串長度寄存器； plimit 為 hostname 字段指針 p 的限制長度（它應(yīng)該是 resPos 和 strlen 中的較大者）
int namelen, plimit = (resNum == 1 ? resPos : strlen);
// 下面的循環(huán)將取出 hostname 字段中被 "." 隔開的每一段
while(p<plimit){
namelen = 0;
// 只要當(dāng)前指針 p 未“走到盡頭” 或 遇到"." 就檢測當(dāng)前字符的合法性
while(p<plimit && str[p] != '.'){
if(judgeLetter(str[p])){
namelen++;
p++;
}
// 一旦某個字符非凡直接判當(dāng)前郵箱地址非法
else return false;
}
// 若當(dāng)前得到的某個子串長度為 0 或者超過 USERNAMEMAX 限制，則郵箱地址非法
if(namelen==0 || namelen>USERNAMEMAX ) return false;
// 只要當(dāng)前 p 指針還“未走到盡頭”就將 p 指針后移
if(p < plimit) p++;
}
// 判斷是否有 resource 字段
if(resNum == 1){
// 若有則將指針后推
p++;
// 條件3：當(dāng)資源符合 / 存在時，resource 字段長度至少為 1
if(p == strlen) return false;
// 判斷 存在時，resource 字段中的各字符是否合法
while(p<strlen){
if( judgeLetter(str[p]) ) p++;
else return false;
}
}
// 上面所有測試都能通過，則郵箱地址合法
return true;
}
int main( )
{
// 獲取輸入
cin>>address;
// 執(zhí)行判斷并輸出對應(yīng)結(jié)果
if(judgeMailAddress(address)){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}
MT2039 換換換
難度：鉆石 ?? 時間限制：1秒 ?? 占用內(nèi)存：128M
題目描述
機器人小R在看一個魔術(shù)表演，魔術(shù)師面前有一排共 N 個倒扣著的杯子，其中每一個下面都有一個小玩具 t i t_i ti? ，并且每個小玩具都是唯一的。魔術(shù)師飛快地變換杯子之后讓小 R 猜其中 M 個玩具 t j t_j tj? 在哪個杯子里。由于機器人小 R 內(nèi)置的程序只能記錄杯子的數(shù)量 N，小玩具初始的位置 p，以及魔術(shù)師每次變換杯子的位置 p 1 , p 2 p_1,p_2 p1?,p2? 。小 R 的主人希望你能寫一個程序，幫助小 R 找出玩具。
格式
輸入格式：第一行給定三個整數(shù)N , M , T，T為魔術(shù)師操作的次數(shù)；
?????接下來的 N 行，每行給定一個字符串 t i t_i ti?；
?????之后的 T 行，每行給定兩個位置 p 1 , p 2 p_1,p_2 p1?,p2? ，位置從1開始計數(shù)；
?????最后 M 行，每行給定一個字符串 t j t_j tj? 。
輸出格式：M 行，每行一個整數(shù)，表示杯子現(xiàn)在的序號。樣例1
輸入：5 5 5
???car
???van
???track
???dog
???cat
???1 2
???4 5
???3 2
???5 1
???1 4
???van
???car
???track
???dog
???cat
輸出：5
???3
???2
???4
???1備注
100 ≤ N , M , T ≤ 5 e 4 , 1 ≤ ∣ t i ∣ ≤ 20 , t j ∈ t i 100≤N,M,T≤5e4,1≤|t_i|≤20,t_j∈{t_i} 100≤N,M,T≤5e4,1≤∣ti?∣≤20,tj?∈ti?
相關(guān)知識點：
模擬
題解
本題中，假設(shè)構(gòu)建一個用于存放玩具與其位置的字符串型數(shù)組 string tricks[N] ，則當(dāng)對玩具進(jìn)行位置交換時，我們只需要將數(shù)組中對應(yīng)索引的值進(jìn)行交換。如，假設(shè)對樣例 1 中的 1 2 進(jìn)行交換時，實際上只需要：tmp= tricks[1], trick[1] = tricks[2], trick[2] = tmp; 即可。這樣一來，直接模擬整個交換過程就能在最后將所有玩具的位置信息都記錄下。
但是問題的關(guān)鍵在于，題目最后要求的映射關(guān)系是從“玩具名稱”得到“對應(yīng)所在杯子的序號”（即從字符串到整型數(shù)字）。那要怎么做呢？最直截了當(dāng)?shù)淖龇ㄊ敲看味急闅vtricks數(shù)組，去搜索輸入的某個指定字符串，然后再將找到的字符串對應(yīng)的序號（即索引）輸出，但是這樣的做法太繁瑣，并且超時無疑。最簡單的做法是再建立一個從“字符串”到“索引”的映射，并參與交換過程即可（跟蹤索引的變換情況），這樣就能直接得到從字符串到序號的映射。這種數(shù)據(jù)結(jié)構(gòu)可直接用 STL 提供的模板，如 map、pair 等。下面直接給出求解該題的完整代碼（已 AC）:
#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
// "索引" 到 "字符串" 的映射
string tricks[N];
// "字符串" 到 "索引" 的映射
map<string,int> mp;
int main( )
{
int n,m,t,p1,p2;
string tmp;
// 獲取輸入
cin>>n>>m>>t;
for(int i=1;i<=n;i++){
cin>>tmp;
tricks[i] = tmp;
mp[tmp] = i;
}
// 模擬交換過程
while(t--){
cin>>p1>>p2;
// 跟蹤玩具（字符串）的交換情況
swap(tricks[p1],tricks[p2]);
// 跟蹤序號（索引）的交換情況
swap(mp[tricks[p1]],mp[tricks[p2]]);
}
// 對 m 次詢問予以回復(fù)
while(m--){
cin>>tmp;
cout<<mp[tmp]<<endl;
}
return 0;
}
MT2040 銀行賬戶
難度：黃金 ?? 時間限制：1秒 ?? 占用內(nèi)存：128M
題目描述
據(jù)說對銀行賬戶進(jìn)行盜竊時，如果只盜取小數(shù)點下的數(shù)值，就不容易引起注意，所以你決定進(jìn)行嘗試。
銀行總共有 n 個賬戶，m 次轉(zhuǎn)賬，對每次轉(zhuǎn)賬，你可以盜?。ㄞD(zhuǎn)賬金額-轉(zhuǎn)賬金額下取整）的資金，并使轉(zhuǎn)入賬戶的警戒值增加相同數(shù)值，當(dāng)任意賬戶的警戒值 > 1，或者無法實現(xiàn)轉(zhuǎn)賬 (轉(zhuǎn)出賬戶余額不足)，或者 m 次轉(zhuǎn)賬全部完成，你停止盜取，請計算總盜取金額。格式
輸入格式：第一行 n, m，表示有 n 個賬戶，m 條轉(zhuǎn)賬記錄；
第二行 n 個實數(shù)，表示每個賬戶的資金；
接下來 m 行，每行有三個參數(shù)；
整數(shù) x，整數(shù) y，實數(shù) z，分別表示轉(zhuǎn)出賬戶，轉(zhuǎn)入賬戶，和轉(zhuǎn)賬金額。
輸出格式：輸出盜取金額，保留兩位小數(shù)。樣例 1
輸入：5 5
???2 2 2 2 2
???1 2 1.5
???2 1 1.5
???1 2 1.5
???2 1 1.5
???1 2 1.5
輸出：2.00備注
1 ≤ n ≤ 1000 , 1 ≤ m ≤ 1000 ； 1≤n≤1000,1≤m≤1000； 1≤n≤1000,1≤m≤1000；
0 < 每個賬戶初始資金 < 10 ； 0<每個賬戶初始資金<10； 0<每個賬戶初始資金<10；
1 ≤ x , y ≤ n , x ≠ y ； 1≤x,y≤n,x≠y； 1≤x,y≤n,x=y；
樣例解釋：
第一次轉(zhuǎn)賬后：0.5 3 2 2 2，已盜取金額 0.5，賬戶 2 警戒值 0.5；
第二次：1.5 1.5 2 2 2，已盜取 1，賬戶 1 警戒值 0.5；
第三次：0 2.5 2 2 2，已盜取 1.5，賬戶 2 警戒值 1；
第四次：1 1 2 2 2，已盜取 2，賬戶 1 警戒值 1；
第五次，賬戶 1 余額不足，轉(zhuǎn)賬無法進(jìn)行，停止。相關(guān)知識點：
模擬
題解
這道題應(yīng)該是這周最簡單的一道題，直接模擬整個過程就行，不需要任何技巧，只需要最后進(jìn)行下格式化輸出即可，AC 代碼如下：
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1005;
const int REDLINE = 1;
// 定義賬戶信息：維度 0 表示余額；維度 1 表示警戒值
float accounts[MAX][2];
int main( )
{
int n,m,x,y;
float money,delta,steal = 0;
// 錄入賬戶信息
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>accounts[i][0];
accounts[i][1] = 0;
}
// 執(zhí)行 m 次轉(zhuǎn)賬
while(m--){
cin>>x>>y>>money;
// 判斷當(dāng)前轉(zhuǎn)賬是否能執(zhí)行
if(accounts[x][0] < money) break;
// 發(fā)起轉(zhuǎn)賬的賬戶扣錢
accounts[x][0] -= money;
// 盜取其中的蠅頭小利
delta = money - int(money);
steal += delta;
// 接受轉(zhuǎn)賬的賬戶收錢
accounts[y][0] += int(money);
// 接受轉(zhuǎn)賬的賬戶增加警戒
accounts[y][1] += delta;
if(accounts[y][1] > REDLINE) break;
}
// 注意格式化輸出
cout<<fixed<<setprecision(2)<<steal;
return 0;
}
MT2041 三角形的個數(shù)
難度：鉆石 ?? 時間限制：1秒 ?? 占用內(nèi)存：128M
題目描述
最近璃月的海燈節(jié)到了，一位來自碼蹄集的小碼哥正好游歷至此，一種有趣的裝飾圖案引起了他的興趣：這種圖案將一個三角形每條邊分為 n 等分，然后將對應(yīng)的等分點相連，使得連成的線段平行于三條邊中的一條，這樣就構(gòu)成了大三角套小三角的繁復(fù)圖案?，F(xiàn)在有許多類似的圖案，這名學(xué)者想知道每個圖案中各包含了幾個三角形，請你幫幫他。
如圖所示是一個二等分的例子：
格式
輸入格式：第一行一個正整數(shù) N，代表圖案個數(shù)。
接下來 N 行每行一個正整數(shù) n i n_i ni? ，代表第 i 個三角形每條邊被分為了 n i n_i ni? 等分。
輸出格式：輸出 N 行，每行一個正整數(shù)代表第 i i i 個圖案中包含的三角形個數(shù)。樣例 1
輸入：2
???2
???3
輸出：5
???13備注
1 ≤ N ≤ 100 , 1 ≤ n ≤ 500 。 1≤N≤100,1≤n≤500。 1≤N≤100,1≤n≤500。
最大的三角形別忘了算哦！相關(guān)知識點：
遞推、遞歸、分治
題解
方法一
在求子三角形個數(shù)時，為了避免漏解，我們應(yīng)當(dāng)從某個 “連續(xù)” 的屬性出發(fā)，去一一算出在該情況下的解的個數(shù)，然后再進(jìn)匯總即可。一個很直觀的 “屬性” 是子三角形的邊長（也許第一次做題的你會很難想到，但當(dāng)你做多了這種類型的題后，你就會慢慢地習(xí)得這一技能了）。于是，從這一層面出發(fā)，該問題就轉(zhuǎn)變?yōu)?“求邊長為 1 的三角形個數(shù) + 求邊長為 2 的三角形個數(shù) + ……” 。
如果你能想到上一點，那么恭喜你，你已經(jīng)具備了基礎(chǔ)的 ACM 選手的思維能力。但是當(dāng)你用前面的結(jié)論在求解題目時，會發(fā)現(xiàn)依然很難找到各邊長的小三角形之間的迭代規(guī)律（一個通用的方程，或者說遞推式）。因此，我們還需要深挖這里面的細(xì)節(jié)。如果你足夠聰明，也許你會發(fā)現(xiàn)：大三角形內(nèi)部的小三角形其實有兩種類別：一種是 “角朝上” 的小三角形，另一種是 “角朝下” 的小三角形。于是，我們可對此再進(jìn)行一個劃分，并分別討論。
基于這樣的思路，可以將整個大三角形（設(shè)其邊長為 n ）中的小三角形分為以下 3 部分進(jìn)行統(tǒng)計：
- 邊長為 1 的所有小三角形個數(shù)為 n × n n×n n×n；
- 邊長為 2~n 的所有 “角朝上” 的小三角形個數(shù)為 ( 1 + 2 + . . . + n ? 1 ) + ( 1 + 2 + . . . n ? 2 ) + . . . + 1 = n ( n + 1 ) 2 + ( n ? 1 ) ( n ? 2 ) 2 + ? + 1 (1+2+...+n-1)+(1+2+...n-2)+...+1=\frac{n(n+1)}{2}+\frac{(n-1)(n-2)}{2}+\dots +1 (1+2+...+n?1)+(1+2+...n?2)+...+1=2n(n+1)?+2(n?1)(n?2)?+?+1；
- 當(dāng)邊長大于 3 時，“角朝下”的小三角形個數(shù)。由于在 1 中已經(jīng)統(tǒng)計了邊長為 1 的小三角形個數(shù)，因此在這里僅統(tǒng)計邊長不低于 2 的 “角朝下” 的小三角形。實際上，當(dāng) “角朝下” 的小三角形邊長為 i i i 時，其數(shù)量為（畫圖找規(guī)律，這個很顯而易見）： S u m i = 1 + 2 + … + i = i ( i + 1 ) 2 Sum_i=1+2+…+i=\frac{i(i+1)}{2} Sumi?=1+2+…+i=2i(i+1)?。
基于這樣的思路，可寫出以下代碼（已 AC）：
#include<bits/stdc++.h>
using namespace std;
int getTheTriangle(int n){
if(n==0) return 0;
int sum = 0;
if(n>=2){
sum += n*n;
for(int i=1; i<n; i++) sum += i*(i+1)/2;
if(n>=4)
for(int i=n-3;i>0;i-=2) sum += (1+i)*i/2;
}
return sum;
}
int main( )
{
int N, n;cin>>N;
while(N--){
cin>>n;
cout<<getTheTriangle(n)<<endl;
}
return 0;
}
方法二
對原問題進(jìn)行抽象，可將其轉(zhuǎn)換為以下問題：
將一個正三角形的各邊都
n
n
n 等分，過各分點作其它兩邊的平行線，一共可產(chǎn)生多少個三角形？
解：不妨設(shè)正 ΔABC 的邊長為 n，則該三角形僅含兩類子三角形：
??1、角朝上的子三角形（任意情況下都存在）；
??2、角朝下的子三角形（原三角形邊長 n≥2）。
從上圖中不難總結(jié)出：在邊長為n的三角形中對其進(jìn)行n等分時，其子三角形數(shù)量滿足：
第 1 類子三角形：
??邊長為 1 的三角形數(shù)量為：
1
+
2
+
?
+
n
=
n
(
n
+
1
)
2
1+2+?+n=\frac{n(n+1)}{2}
1+2+?+n=2n(n+1)?；
??邊長為 2 的三角形數(shù)量為：
1
+
2
+
?
+
(
n
?
1
)
=
n
(
n
?
1
)
2
1+2+?+(n-1)=\frac{n(n-1)}{2}
1+2+?+(n?1)=2n(n?1)?；
??……
??邊長為 n 的三角形數(shù)量為：1。
將上述所有式子求和可得到第1類子三角形的總數(shù)為：
n
(
n
+
1
)
(
n
+
2
)
6
\frac{n(n+1)(n+2)}{6}
6n(n+1)(n+2)?
第 2 類子三角形：
??邊長為 1 的三角形數(shù)量為：
1
+
2
+
?
+
(
n
?
1
)
=
n
(
n
?
1
)
2
1+2+?+(n-1)=\frac{n(n-1)}{2}
1+2+?+(n?1)=2n(n?1)?；
??邊長為 2 的三角形數(shù)量為：
1
+
2
+
?
+
(
n
?
1
)
=
(
n
?
3
)
(
n
?
2
)
2
1+2+?+(n-1)=\frac{(n-3)(n-2)}{2}
1+2+?+(n?1)=2(n?3)(n?2)?；
??……
??邊長為 m 的三角形數(shù)量為：
1
+
2
+
?
+
(
n
?
(
m
+
1
)
)
=
(
n
?
m
?
1
)
(
n
?
m
)
2
1+2+?+(n-(m+1))=\frac{(n-m-1)(n-m)}{2}
1+2+?+(n?(m+1))=2(n?m?1)(n?m)?。
將上述所有式子求和可得到第2類子三角形的總數(shù)，但是此值受n的奇偶性制約。
當(dāng)n為奇數(shù)時，此類子三角形的總數(shù)為：
(
n
?
1
)
(
n
+
1
)
(
2
n
+
3
)
24
\frac{(n-1)(n+1)(2n+3)}{24}
24(n?1)(n+1)(2n+3)?；
當(dāng)n為偶數(shù)時，此類子三角形的總數(shù)為：
n
(
n
+
1
)
(
2
n
?
1
)
24
\frac{n(n+1)(2n-1)}{24}
24n(n+1)(2n?1)?；
綜上可知，總的子三角形個數(shù)為
N
=
{
(
n
+
1
)
(
2
n
2
+
3
n
?
1
)
8
，
n
為偶數(shù)
n
(
n
+
2
)
(
2
n
+
1
)
8
，
n
為奇數(shù)
N=\begin{equation} \left\{ \begin{aligned} \nonumber &\frac{(n+1)(2n^2+3n-1)}{8} ，n 為偶數(shù)\\ &\frac{n(n+2)(2n+1)}{8}，n 為奇數(shù)\\ \end{aligned} \right. \end{equation}
N=?
?
???8(n+1)(2n2+3n?1)?，n為偶數(shù)8n(n+2)(2n+1)?，n為奇數(shù)??
基于這樣的思路，可寫出以下代碼（已 AC）：
#include<bits/stdc++.h>
using namespace std;
int getTheTriangle(int n){
if(n%2) return (n+1)*(2*n*n+3*n-1)/8;
else return n*(n+2)*(2*n+1)/8;
}
int main( )
{
int N, n, cnt; cin>>N;
while(N--){
cin>>n;
cout<<getTheTriangle(n)<<endl;
}
return 0;
}
MT2046 巨大的錯誤
難度：黃金 ?? 時間限制：1秒 ?? 占用內(nèi)存：128M
題目描述
提瓦特大陸上有一個貧窮的占星術(shù)士小碼哥，在占星的時候，小碼哥時常需要將命運啟示他的信息與手中命運之輪上的命星一一對應(yīng)，現(xiàn)在有n個啟示和n個命星需要一一對應(yīng)，有時，因為命運實在太過難以言明，小碼哥會將所有的啟示與命星都對應(yīng)錯了，此時稱小碼哥犯了一個巨大的錯誤，問一共有多少種情況可被稱為“巨大的錯誤”。
格式
輸入格式：輸入一個正整數(shù) n n n。
輸出格式：輸出一個正整數(shù)表示所求答案。樣例 1
輸入：2
輸出：1備注
其中 n ≤ 20 n≤20 n≤20。
相關(guān)知識點：
遞推、遞歸、分治、組合數(shù)學(xué)
題解
這個問題的本質(zhì)是：對
n
n
n 個數(shù)進(jìn)行排列，問每一個數(shù)都不待在原來位置的情況有多少種？該問題也被稱為 “全錯位排列” 問題，源自于當(dāng)時最有名的數(shù)學(xué)家約翰·伯努利 (Johann Bernoulli，1667－1748) 的兒子丹尼爾·伯努利 (DanidBernoulli，1700－1782) 提出的 “裝錯信封問題” 。
該問題通?？梢酝ㄟ^遞推公式進(jìn)行計算。假設(shè)現(xiàn)在對
n
n
n 個數(shù)進(jìn)行排列，設(shè)每個數(shù)都不在原來的位置的情況為
F
(
n
)
F(n)
F(n) 種 (
n
≥
2
n≥2
n≥2)。
先考慮第
n
n
n 個數(shù)，有
n
?
1
n-1
n?1 種選擇，假設(shè)第
n
n
n 個數(shù)的位置為
x
n
(
x
n
=
k
,
k
≠
n
)
x_n (x_n=k, k≠n)
xn?(xn?=k,k=n) ；接著考慮第
k
k
k 個數(shù)，這時需要分兩種情況討論：
- 若第 k k k 個數(shù)的位置 x k = n x_k=n xk?=n，則就相當(dāng)于將位置 k , n k,n k,n 的數(shù)進(jìn)行了對換，那么接下來就只需要對剩余的 n ? 2 n-2 n?2 個數(shù)進(jìn)行全錯位排列。這就相當(dāng)于將問題規(guī)模由 n n n 變?yōu)? n ? 2 n-2 n?2，即有 F ( n ? 2 ) F(n-2) F(n?2) 種排法；
- 若第 k k k 個數(shù)的位置 x k ≠ n x_k≠n xk?=n，（這就相當(dāng)于位置 n n n 不能與數(shù) x k x_k xk? 組合），那么對于當(dāng)前這 n ? 1 n-1 n?1 個數(shù)而言，其還是等價于對當(dāng)前 n ? 1 n-1 n?1 個數(shù)進(jìn)行全錯位排列。即將問題規(guī)模由 n n n 變?yōu)? n ? 1 n-1 n?1，即有 F ( n ? 1 ) F(n-1) F(n?1) 種排法。
綜上可得到該問題的遞推公式為：
F
(
n
)
=
(
n
?
1
)
?
(
F
[
n
?
1
]
+
F
[
n
?
2
]
)
F(n) = (n-1)*(F[n-1]+F[n-2])
F(n)=(n?1)?(F[n?1]+F[n?2])，其中：
n
>
2
n>2
n>2 ，初始情況下：
F
(
1
)
=
0
,
F
(
2
)
=
1
F(1)=0, F(2)=1
F(1)=0,F(2)=1。
例如：當(dāng)
n
=
3
n=3
n=3 時，對應(yīng)的情況有：(2,3,1)，(3,1,2)，共2種，而
F
(
3
)
=
2
?
(
F
(
2
)
+
F
(
1
)
)
=
2
F(3)=2*(F(2)+F(1))=2
F(3)=2?(F(2)+F(1))=2，公式成立;
???當(dāng)
n
=
4
n=4
n=4 時，對應(yīng)的情況有：(2,1,4,3)，(2,3,4,1)，(2,4,1,3)， (3,1,4,2)， (3, 4,1,2)，(3,4,2,1)，(4,1,2,3)，(4,3,1,2)，(4,3,2,1)，共9種，而
F
(
4
)
=
3
?
(
F
(
3
)
+
F
(
2
)
)
=
3
?
(
2
+
1
)
=
9
F(4)=3*(F(3)+F(2))=3*(2+1)=9
F(4)=3?(F(3)+F(2))=3?(2+1)=9，公式成立。文章來源：http://www.zghlxwxcb.cn/news/detail-419537.html
其他的情況可自行驗證。
基于此，可直接寫出以下代碼（已 AC）:文章來源地址http://www.zghlxwxcb.cn/news/detail-419537.html
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n, p = 3;
long num1 = 0, num2 = 1, num3;
// 獲取輸入
cin>>n;
// 特殊處理
if(n==2){
cout << num2;
return 0;
}
// 遞推
while(p <= n){
// 遞推
num3 = (p-1)*(num1+num2);
// 移位
num1 = num2;
num2 = num3;
// 指針移動
p++;
}
cout<<num3;
return 0;
}
END
到了這里，關(guān)于【馬蹄集】第五周作業(yè)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
