1.14选学生会（计数排序），选数（dfs),全排列（dfs)

P1271 【深基9.例1】选举学生会

#include<iostream>
using namespace std;
const int maxn = 1e5 + 5;
int n, arr[maxn], m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int t;
        cin >> t;
        arr[t]++;
    }
    for (int i = 1; i <= n; i++) {
        while (arr[i]) {
            cout << i << " ";
            arr[i]--;
        }
    }
    return 0;
}

P1036 [NOIP2002 普及组] 选数

在每次迭代的时候都保留此时的起点，可以实现从头往后的不重不漏的所有检测

#include<iostream>
using namespace std;
const int maxn = 1e5 + 5;
int n, arr[maxn], m, ans = 0;
bool isp(int a) {
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0)return false;
    }
    return true;
}
void dfs(int k, int sum, int b) {
    if (k == m) {
        if (isp(sum))ans++;
        return;
    }
    for (int i = b ; i <= n; i++) {
        dfs(k + 1, sum + arr[i], i + 1);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    dfs(0, 0, 1);
    cout << ans;
    return 0;
}

就是所谓不降原则?

P1157 组合的输出

vector可以尾删，可以尾插

不知道哪错了版

没输出?

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, arr[maxn], m;
vector<int>ss;
void dfs(int k, int b) {
    if (k == n) {
        if (ss.size() == m) {
            for (int i = 0; i < ss.size(); i++) {
                cout << setw(3) << ss[i];
            }
        }
    }
    for (int i = b; i <= n; i++) {
        ss.push_back(i);
        dfs(k + 1, i + 1);
        ss.pop_back();
    }
}
int main() {
    cin >> n >> m;
    dfs(0, 1);
    return 0;
}

?错了，在递归结束的地方，k和size的检测应该都是m，是要选择的数字的数量

下面这个是用数组

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, arr[maxn], m;
void dfs(int k, int b) {
    if (k == n) {
            for(int i=1;i<=n;i++){

        }
    }
    for (int i = b; i <= n; i++) {
        ss.push_back(i);
        dfs(k + 1, i + 1);
        ss.pop_back();
    }
}
int main() {
    cin >> n >> m;
    dfs(0, 1);
    return 0;
}