1.15火星人（全排列+变进制数），涂国旗（搜索）

P1088 [NOIP2004 普及组] 火星人

首先是要得到当前排序的排名，其次是要得到它的排名

n进制就是说满n就进，该位上不可能保持为n，最多保持为n-1；

变进制数

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
const int maxn = 100005;
int n, m, arr[maxn], used[maxn];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];//原数字
        int x = arr[i];
        for (int j = 1; j <= arr[i]; j++) {
            if (used[j]) {
                x--;
            }//得到是当前的第几个选择，如果中间的数已经被用过，那就是当前的选择依次往前走
        }//表示说这个数都是被用过的了
        used[arr[i]] = 1;
        arr[i] = x - 1;
    }
    arr[n] = m;
    for (int i = n; i >= 1; i--) {
        arr[i - 1] = arr[i - 1] + arr[i] / (n - i + 1);
        arr[i] = arr[i] % (n - i + 1);
        used[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= arr[i]; j++) {
            arr[i] += used[j];
        }
        cout << arr[i] + 1 << " ";
        used[arr[i]] = 1;
    }
    return 0;
}

就是需要注意进制转换的时候的细节问题

还有就是转换为后序进制数时，arr[i]在转化过程中是逐渐增加的，

P3392 涂国旗

要搜索的话，关键在于怎么确定搜索的目标，

搜索的目的，就是搜两行，即两行分界线，然后去找代价最小的分界线位置

#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
using namespace std;
const int maxn = 100005;
int n, m, w[55], b[55], r[55], ans = 1e9;//表示的是前i行(包括这一行）要涂成这个颜色要花费的颜料数量
string s;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] != 'W') {
                w[i]++;
            }
            if (s[j] != 'R') {
                r[i]++;
            }
            if (s[j]!='B'){
                b[i]++;
            }
            w[i + 1] = w[i];
            b[i + 1] = b[i];
            r[i + 1] = r[i];
        }
    }
    for (int i = 1; i <= n-2; i++) {//这一行往上是白色
        for (int j = i + 1; j <= n-1; j++) {//这一行往上是蓝色（包括这一行）
            ans = min(ans, w[i] + b[j] - b[i] + r[n] - r[j]);
        }
    }
    cout << ans;
    return 0;
}