/*
 * 给你一个可重集合，让你选出一个子集，使得任意两个数不连续，求最大的子集大小。
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, a[N], dp[N];

int main() {
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int m = unique(a + 1, a + n + 1) - a;
    dp[0] = 0, dp[1] = 1;
    for (int i = 2 ; i <= m ; i ++) {
        dp[i] = dp[i - 1]; // 不选这个数
        if (a[i] > a[i - 1] + 1) {
            dp[i] = max(dp[i], dp[i - 1] + 1); // 尝试把当前这个数加入到 i-1
        }
        dp[i] = max(dp[i], dp[i - 2] + 1);
    }
    int ans = 0;
    for (int i = 1 ; i <= m ; i ++) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}

第二题：

/*
 * 给你一个数组，可以对数组在任意位置翻转一次，也可以不翻转，让你求出最大连续和。
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, a[N], sum[N], mx[N], mval[N];

int main() {
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++)
        scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
    int ans = 0;
    for (int i = 1, s = 0 ; i <= n ; i ++) {
        s += a[i];
        if (s < 0) s = 0; // 求 1~i 的最大连续和
        mx[i] = max(mx[i - 1], s); // 最大连续和的前缀最大值
        mval[i] = max(mval[i - 1], mx[i] - sum[i]);
        ans = max(ans, sum[i] + mval[i - 1]);
    }
    cout << ans << "\n";
    return 0;
}

第三题：

/*
 * 给你一个边长为n的正方体，然后每次操作是对x，y，z轴的其中一个轴进行切割，切割的位置是距离左边为d的位置
 * 求出每次切割后的最大体积块
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m, d[N];
char op[N];
int v[3][N], tot[3], mx[3];

int main() {
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++) cin >> op[i];
    for (int i = 1 ; i <= m ; i ++) cin >> d[i];
    for (int i = 0 ; i < 3 ; i ++) tot[i] = 1, v[i][1] = mx[i] = n;
    for (int t = 1 ; t <= m ; t ++) {
        int id = op[t] - 'x';
        int idx = -1, L = -1, R = -1;
        for (int i = 1, l = 0 ; i <= tot[id] ; i ++) {
            int r = l + v[id][i];
            if (r > d[i]) {
                idx = i, L = d[i] - l, R = r - d[i];
                break;
            }
            l += v[id][i];
        }
        tot[id] ++;
        for (int i = tot[id] ; i > idx ; i --) v[id][i] = v[id][i - 1];
        // idx, idx + 1
        v[id][idx] = L;
        v[id][idx + 1] = R;
        mx[id] = 0;
        for (int i = 1 ; i <= tot[id] ; i ++) mx[id] = max(mx[id], v[id][i]);
        cout << mx[0] * mx[1] * mx[2] << endl;
    }
    return 0;
}            

#include <bits/stdc++.h>
using namespace std;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 5005;

int n, a[N], cnt[N], tag[N];
LL sum[N << 2], add[N << 2];

void pushup(int rt) {
	sum[rt] = sum[ls] + sum[rs];
}

void pushdown(int rt, int l, int r) {
	if (add[rt]) {
		int mid = (l + r) >> 1;
		sum[ls] += add[rt] * (mid - l + 1);
		sum[rs] += add[rt] * (r - mid);
		add[ls] += add[rt], add[rs] += add[rt];
		add[rt] = 0;
	}
}

void update(int rt, int l, int r, int ql, int qr, int x) {
	if (l == ql && qr == r) {
		sum[rt] += 1LL * x * (r - l + 1);
		add[rt] += x;
		return ;
	}
	pushdown(rt, l, r);
	int mid = (l + r) >> 1;
	if (qr <= mid) update(ls, l, mid, ql, qr, x);
	else if (ql > mid) update(rs, mid + 1, r, ql, qr, x);
	else update(ls, l, mid, ql, mid, x), update(rs, mid + 1, r, mid + 1, qr, x);
	pushup(rt);
}

LL query(int rt, int l, int r, int ql, int qr, int x) {
	if (l == ql && qr == r) return sum[rt];
	pushdown(rt, l, r);
	int mid = (l + r) >> 1;
	if (qr <= mid) return query(ls, l, mid, ql, qr);
	else if (ql > mid) return query(rs, mid + 1, r, ql, qr);
	else return query(ls, l, mid, ql, mid) + query(rs, mid + 1, r, mid + 1, qr);
}

int main() {
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) cin >> a[i];
	LL ans = 0;
	for (int i = 1 ; i <= m ; i ++) {
		int op, l, r, k; cin >> op >> l >> r;
		if (op == 1) {
			tag[l] ++, tag[r + 1] --;
			ans += query(1, 1, n, l, r);
		} else if (op == 2) {
			cin >> k;
			update(1, 1, n, l, r, k);
		}
	}
	for (int i = 1 ; i <= n ; i ++) cnt[i] = cnt[i - 1] + tag[i];
	sort(cnt + 1, cnt + n + 1);
	sort(a + 1, a + n + 1);
	for (int i = 1 ; i <= n ; i ++) ans += 1LL * cnt[i] * a[i];
	cout << ans << "\n";
    return 0;
}

第五题：

/*
 * 给你 m 个数字以及对应的 a 和 b
 * a 是猜的数字和这个数需要有 a 个位置相同的数，b 是两个数字都包含 b 个相同的数字，但这些数字所在的位置不相同
 * 让你选出一个最小的符合条件的数字，如果不存在这个数字，则输出一个"？"
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

struct node {
    string s;
    int a, b;
} v[N];
int n, m, ok, use[10];
string path, ans = "?";

void check() {  if (ok) return ;
    vector<int> pa(10, -1);
    for (int i = 0 ; i < n ; i ++) pa[path[i] - '0'] = i;
    for (int i = 1 ; i <= m ; i ++) {
        vector<int> pb(10, -1);
        for (int j = 0 ; j < n ; j ++) pb[v[i].s[j] - '0'] = j;
        int a = 0, b = 0;
        for (int j = 0 ; j < 10 ; j ++) {
            if (pa[j] != -1 && pb[j] != -1) {
                if (pa[j] == pb[j]) a ++;
                else b ++;
            }
        }
        if (v[i].a != a || v[i].b != b) return ;
    }
    if (ans == "?") ans = path, ok = 1;
}

void dfs(int x) {
    if (x > n) { check(); return ; }
    if (ok) return ;
    for (int i = 0 ; i <= 9 ; i ++) {
        if (use[i]) continue;
        path.push_back(i + '0');
        use[i] = 1;
        dfs(x + 1);
        use[i] = 0;
        path.pop_back();
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++) cin >> v[i].s >> v[i].a >> v[i].b;
    dfs(1);
    cout << ans << "\n";
    return 0;
}