目录

  1. 第一题
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析
  2. 题目二
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析

第一题

题目描述

在狸星数字里，数字1到9被表示为：’I’、’II’、’III’、’IV’、’V’、’VI’、’VII’、’VIII’、’IX’，数字10、20、30、40、50、60、70、80、90被表示为’X’、’XX’、’XXX’、’XL’、’L’、’LX’、’LXX’、’LXXX’、’XC’。

任何小于100的正整数都可以通过这样的方式转成狸星数字：将个位数和十位数拆开，分别转成狸星数字再合起来，十位在左个位在右。

你的任务：给出一个小于100的狸星数字，将其中的字母重新排列，使得重排后的结果仍然是一个合法的狸星数字，且使其尽可能小。

输入描述

一行，一个大写字母表示的合法狸星数字，且为小于100的正整数。

输出描述

一行，最小的重新排列后的狸星数字。

分析

  • 思路：直接用暴力dfs将所有的情况罗列出来，然后再进行比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
unordered_map<string, int> numMap{ 
    { "I",  1 },  { "II", 2 }, { "III",  3 }, { "IV", 4 }, { "V", 5 },
    { "VI", 6 }, { "VII", 7 }, { "VIII", 8 }, { "IX", 9 },
    { "X",  10 }, { "XX", 20 },{ "XXX",  30 },{ "XL", 40 },{ "L", 50 },
    { "LX", 60 },{ "LXX", 70 },{ "LXXX", 80 },{ "XC", 90 } 
};


// 根据给定猩星数字，返回阿拉伯数字
int getNum(const string& num) {
    string digit = "";
    int curNum = 100; // 如果不满足狸星数字的条件，则返回100
    int i = 0;
    for (; i < num.size(); ++i) {
        if (num[i] != 'I' && num[i] != 'V') //十位与个位的分界线一定是'V'或'I'
            digit += num[i];
        else
            break;
    }
    if (i == 0) {
        if (numMap.find(num) != numMap.end())
            curNum = numMap[num];
    }
    else {
        string unit = num.substr(i, num.size());
        if (numMap.find(digit) != numMap.end() && numMap.find(unit) != numMap.end())
            curNum = numMap[unit] + numMap[digit];
    }
    return curNum;
}


void swap(string& s, int i, int j) {
    char c = s[i];
    s[i] = s[j];
    s[j] = c;
}
// 全排列
void fullArray(string& num, int idx, string& minStr, int& minNum) {
    if (idx >= num.size()) {
        int tmp = getNum(num);
        if (tmp < minNum) {
            minNum = tmp;
            minStr = num;
        }
        return;
    }

    for (int i = idx; i < num.size(); ++i) {
        swap(num, i, idx);
        fullArray(num, idx + 1, minStr, minNum);
        swap(num, i, idx);
    }
}

int main() {
    string num;
    while (cin >> num) {
        int cur = getNum(num);
        int minNum = cur;
        string minStr = num;

        fullArray(num, 0, minStr, minNum);
        cout << minStr << endl;
    }
    return 0;
}

题目二

题目描述

小依每天下班后都会玩骰子来放松心情，小依一共有n个骰子，每个骰子有6面，每一个面上都有一个数字，一个骰子的6个面上的数字互不相同。现在小依想知道，小依可以任意让每个骰子的某一面朝上，n个骰子有多少种组合方式使得所有骰子向上的面上的数字加起来的和等于k。

注意：如果有两个骰子，（第一个骰子数字2向上，第二个骰子数字3向上）和（第一个骰子数字3向上，第二个骰子数字2向上）算两种不同的组合方式。

输入描述

第一行输入为n和k，n表示小依的骰子数（1<=n<=14），k如题目描述所示，接下来的n行每行有6个正整数，每个数字的大小不超过100。

输出描述

输出一个正整数表示答案

分析

  • 思路一：暴力dfs，时间复杂度较高，牛客上通过率仅为70%。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void recursive(const int& n, const int& k, const vector<vector<int> >& vec, int& cnt , int curCnt, int curIdx) {
    if (curIdx == n) {
        if (curCnt == k)
            ++cnt;
        return;
    }
    if (curCnt >= k)
        return;

    for (int i = 0; i < 6; ++i) {
        int curVal = vec[curIdx][i];
        curCnt += curVal;
        recursive(n, k, vec, cnt, curCnt, curIdx + 1);
    }
}


int main() {
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int> > data(n, vector<int>(6, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 6; ++j)
                cin >> data[i][j];
        }

        int cnt = 0;
        recursive(n, k, data, cnt, 0, 0);
        cout << cnt << endl;
    }
    return 0;
}
  • 思路二：动态规划
    • dp[i][j]表示前i个骰子向上那面数字之和为j的组合数
    • 状态转换方程：
1
2
3
4
5
6
for(int p=0; p<6; p++)
{
    int curVal = data[i-1][p];
    if(j>=curVal)
        dp[i][j] += dp[i-1][j-curVal];
}
  • 思路二代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main()
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int> > data(n, vector<int>(6, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 6; ++j)
                cin >> data[i][j];
        }

        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
        dp[0][0] = 1; 
        for(int i=1; i<dp.size(); i++)
        {
            for(int j=0; j<dp[i].size(); j++)
            {
                for(int p=0; p<6; p++)
                {
                    int curVal = data[i-1][p];
                    if(j>=curVal)
                        dp[i][j] += dp[i-1][j-curVal];
                }
            }
        }
        cout << dp[n][k];
    }
    
    return 0;
}