問題描述
A 市的車牌由六位組成：
-
其中前三位可能為數字 0 至 9，或者字母 A 至 F，每位有 16 種可能，
-
后三位只能是數字 0 至 9，
-
為了減少攀比，車牌中不能有連續三位是相同的字符，
例如，202020 是合法的車牌，AAA202 不是合法的車牌，因為前三個字母相同，
請問，A 市有多少個合法的車牌？
答案提交
這是一道結果填空的題，你只需要算出結果后提交即可，
本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案：4002750
題解一
DFS：
#include <iostream>
#include <vector>
using namespace std;
int ans;
vector<int> path;
void dfs(int u)
{
if(u == 7)
{
bool flag = true;
for (int i = 5; i >= 2; i --)
if(path[i] == path[i - 1] && path[i - 1] == path[i - 2])
flag = false;
if(flag) ans ++;
return;
}
int n = u <= 3? 15 : 9;
for (int i = 0; i <= n; i ++)
{
path.push_back(i);
dfs(u + 1);
path.pop_back();
}
}
int main()
{
dfs(1);
cout << ans << endl;
return 0;
}
題解二
DFS（剪枝）：
#include <iostream>
using namespace std;
int ans;
void dfs(int u, int a, int b)
{
if(u == 7)
{
ans ++;
return;
}
int n = u <= 3? 15 : 9;
for (int i = 0; i <= n; i ++)
{
if(a == b && b == i) continue;
dfs(u + 1, b, i);
}
}
int main()
{
dfs(1, -1, -1);
cout << ans << endl;
return 0;
}
藍橋杯C/C++組省賽歷年題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277135.html
標籤：其他
上一篇：Unity 多語言文本
下一篇：Java 與 動態規劃