function

#include <bits/stdc++.h>
using namespace std;
#define int long long
int f[25][25][25];

int w(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;
	if (a > 20 || b > 20 || c > 20) {
		if (f[20][20][20])
			return f[20][20][20];
		f[20][20][20] =  w(20, 20, 20);
		return f[20][20][20];
	}

	if (a < b && b < c) {
		if ( f[a][b][c])
			return f[a][b][c];
		f[a][b][c] =  w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
		return f[a][b][c];
	}
	if ( f[a][b][c])
		return f[a][b][c];
	f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
	return f[a][b][c];
}

int a, b, c;
signed main() {
	while (1) {
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1)
			break;
		printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
	}
	return 0;
}

小A点菜

// 其实这里的核心也是组合问题，就是从n道菜里面选择菜
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[105][10005], n, m, v[105], ans;
// f[i][j]表示当前选中了第i道菜，还剩j块钱
// c 是当前考虑的菜的顺序，k 是剩下的钱
LL dfs(LL c, LL k) {
    // 之前计算过了
    if (f[c][k])return f[c][k];
    // 当前菜的价格超过了剩余的钱的数量
    if (v[c] > k)return 0;
    // 钱刚好相等，那就只有一种方案
    if (v[c] == k)return 1;
    for (LL i = c + 1; i <= n; i++)
        // 考虑选择当前的菜色的方案，然后再和其他菜配对的可能
        f[c][k] += dfs(i, k - v[c]);
    return f[c][k];
}
int main() {
    scanf("%lld%lld", &n, &m);
    for (LL i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    // 遍历每一个菜，看能否凑成m的钱数
    for (LL i = 1; i <= n; i++)
        ans += dfs(i, m);
    printf("%lld\n", ans);
    return 0;
}

黑白棋子的移动

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n;
char a[N];
// 当n等于4的时候是没有规律的，直接打表
string b[4] = {"ooo*o**--", "o--*o**oo", "o*o*o*--o", "--o*o*o*o"};

void shuchu(int l, int r) {
	for (int i = l; i <= r; i++)
		cout << a[i];
	cout << endl;
}

// 递归n的问题可以化简为n-1的问题
// 然后n等于四的时候是没有规律的，直接代表输出
void f(int step) {
	if (step == 3) {
		for (int i = 0; i < 4; i++) {
			cout << b[i]; //  输出前9个数字
			shuchu(10, 2 * n + 2);
		}
		return ;
	}
	// n的问题转化为n-1的问题,需要进行了两步操作
	shuchu(1, 2 * n + 2);
	swap(a[step], a[step * 2 + 1]);
	swap(a[step + 1], a[step * 2 + 2]);
	shuchu(1, 2 * n + 2);
	swap(a[step], a[step * 2 - 1]);
	swap(a[step + 1], a[step * 2]);
	f(step - 1);
}

int main() {
	cin >> n;
	// 重置开始状态
	for (int i = 1; i <= n; i++) {
		a[i] = 'o';
		a[i + n] = '*';
	}
	a[2 * n + 1] = '-';
	a[2 * n + 2] = '-';
	// 开始递归
	f(n);
	return 0;
}

奇迹

#include <bits/stdc++.h>
using namespace std;
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int f[100000005], res[6000005], cnt, date[15], num, ans;
char s[15];
bool is_run(int y) {
    if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
        return 1;
    return 0;
}
bool legal(int y, int m, int d) {
    if (m > 12 || m == 0 || d == 0 || y == 0)return 0;
    if (m == 2) {
        if (is_run(y)) {
            if (d > 29)return 0;
            return 1;
        } else {
            if (d > 28)return 0;
            return 1;
        }
    } else {
        if (d > day[m])return 0;
        return 1;
    }
}
void dfs(int d) {
    if (d == 8) {
        int y = num / 10000, m = (num % 10000) / 100, d = num % 100;
        if (legal(y, m, d))
            if ((!f[d]) && (!f[m * 100 + d]) && (!f[num]))ans++;
        return;
    }
    if (date[d] != -1) {
        num = num * 10 + date[d];
        dfs(d + 1);
        num /= 10;  // 回溯，可能这个执行完毕以后，虽然当前的价值在当前点不会影响，
		// 但是对之前的点可能会有影响
        return;
    }
    for (int i = 0; i <= 9; i++) {
        // 搜索优化，编号分别为： 0 1 2 3 4 5 6 7
        if (d == 4 && i == 2)break;
        if (d == 5 && i == 0 && date[d - 1] == 0)continue;
        if (d == 5 && date[4] * 10 + i > 12)break;
        if (d == 6 && i == 4)break;
        date[d] = i;
        num = num * 10 + i;
        dfs(d + 1);
        date[d] = -1;
        num /= 10;
    }
}
int main() {
    int t;
    scanf("%d", &t);
    f[0] = f[1] = 1;
    for (long long i = 2; i <= 99991231; i++) {
        if (!f[i])res[++cnt] = i;
        for (long long j = 1; j <= cnt && i * res[j] <= 99991231; j++) {
            f[i * res[j]] = 1;
            if (i % res[j] == 0)break;
        }
    }
    while (t--) {
        ans = 0;
        scanf("%s", s);
        for (int i = 0; i < 8; i++) {
            if (s[i] == '-')date[i] = -1;
            else date[i] = s[i] - '0';
        }
        dfs(0);
        printf("%d\n", ans);
    }
    return 0;
}