Problem 1

Solution

只有同时进来的人才能保证不是同一个人，所以记录人数的最大值和最小值，做差就是要求的答案。

Code

#include <stdio.h>
#include <string.h>
int main() {
	int T; scanf("%d", &T);
	char c; getchar();
	while(T--) {
		int mx = 0, mi = 2000, cnt = 0;
		while(~scanf("%c", &c)) {
			if(c == '\n') break;
			if(c == '+') cnt++;
			else cnt--;
			mx = (mx >= cnt ? mx : cnt);
			mi = (mi <= cnt ? mi : cnt);
		}
		printf("%d\n", mx - mi);
	}
}

Problem 2

Solution

看上去是一个背包问题，但是由于物体的大小只有1和2，所以可以转换为贪心的方式去做。
首先考虑这样一个性质，若要装进物品，则对于相同体积的，一定优先考虑美味度大的，所以对两种物品分别按照美味度降序排序，那么一定是贪心地从大往小装入物品。
由于体积的不同，所以单位体积的物品有着不同的美味度，但是受到容量的限制，我们从单位体积这个角度去思考会很难处理诸如：若除以2来计算，那么存在精度问题；若乘2计算，还要考虑是否能放下原本体积为1的物品。
故考虑这样一个思路：对容量为 $V$ 的背包，若其中 $M$ 放体积为2的物品，则剩下 $V-M$ 的部分放体积为1的物品，这样我们就可以枚举在背包中放体积为2的物品的数量，统计最大的答案即可。
由于每次选择物品一定是这两个序列的前缀和，所以可以进行前缀和的优化，最终算法复杂度为 $O(n)$ 。

Code by V5ZSQ

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
#define maxn 100005
int n, V, a[maxn], b[maxn];
ll sa[maxn], sb[maxn];
int cmp(const void *a, const void *b) {
	return *(int *)b - *(int *)a;
}
int main() {
	scanf("%d%d", &n, &V);
	int na = 0, nb = 0;
	int x, y;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x, &y);
		if (x == 2) a[++na] = y;
		else b[++nb] = y;
	}
	qsort(a + 1, na, sizeof(int), cmp);
	qsort(b + 1, nb, sizeof(int), cmp);
	sa[0] = sb[0] = 0;
	for (int i = 1; i <= na; i++) sa[i] = sa[i - 1] + a[i];
	for (int i = 1; i <= nb; i++) sb[i] = sb[i - 1] + b[i];
	ll ans = 0;
	for (int i = 0; i <= na && 2 * i <= V; i++) {
		int j = V - 2 * i;
		if (j < 0) j = 0;
		if (j > nb) j = nb;
		if (sa[i] + sb[j] > ans) ans = sa[i] + sb[j];
	}
	printf("%lld\n", ans);
	return 0;
}

Code by CFhM_R in C++

#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
typedef long long ll;
const int maxn = 1e5 + 5;
// head
ll a[maxn], b[maxn];
int main() {
	int n, v; scanf("%d%d", &n, &v);
	int t, p, cnt1 = 1, cnt2 = 1;
	rep(i, 0, n) {
		scanf("%d%d", &t, &p);
		if(t == 1) a[cnt1++] = (ll)p;
		else b[cnt2++] = (ll)p;
	}
	sort(a + 1, a + cnt1, [&](ll a, ll b){ return a > b; });
	sort(b + 1, b + cnt2, [&](ll a, ll b){ return a > b; });
	ll ans = 0ll, sum = 0ll;
	rep(i, 2, cnt1) a[i] += a[i - 1];
	rep(i, 0, cnt2) {
		if(i * 2 > v) break;
		sum += b[i];
		int pos = (v - 2 * i >= cnt1 ? cnt1 - 1 : v - 2 * i);
		ans = max(ans, sum + (pos ? a[pos] : 0));
	}
	printf("%lld\n", ans);
	return 0;
}

Problem 3

Solution

可以看出这是一道01背包的模型题，不同的是本题要求背包用量大于等于 $m$ 时的最小值，故背包上限应为 $m$ 上限再加一个物品上限（不可能多两个物品构造最优解）。之后从 $m$ 到 2000的dp值取最小即可。

Code by V5ZSQ

#include <stdio.h>
#include <string.h>
#define maxn 1005
#define INF 1e7
#define min(x, y) ((x) < (y) ? (x) : (y))
int n, m, a[maxn], b[maxn], dp[2 * maxn];
int main() {
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
		for (int i = 0; i <= 2000; i++) dp[i] = INF;
		dp[0] = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 2000; j >= a[i]; j--)
				dp[j] = min(dp[j], dp[j - a[i]] + b[i]);
		int ans = dp[m];
		for (int i = m; i <= 2000; i++) ans = min(ans, dp[i]);
		if (ans == INF) printf("My small xueqi ended!\n");
		else printf("%d\n", ans);
	}
	return 0;
}

Problem 4

Solution

考虑b数组的下面一些性质：

b数组的元素代表的是出现的次数，因此这个次数一定不会超过 $n$ ，所以所有超过 $n$ 的 $a[i]$ 对应的 $b[i]$ 一律是0。
若 $a[i] == a[j](i \neq j)$ ，一定有 $b[i] == b[j]$ 。
对于所有不同的 $a[i]$ ， $b[i]$ 的和 $<=n$

通过上面的性质可以总结出一些剪枝的方法，由此可以暴力枚举dfs b数组的方案，加上上述剪枝，即可通过本题。

Code by V5ZSQ

#include <stdio.h>
#include <string.h>
#define maxn 25
int n, num[1000005], a[maxn], b[maxn], ans[maxn], flag;
int check(int k) {
	for (int i = 1; i <= k; i++)
		if (num[a[i]] > b[i])
			return 0;
	int sum = 0;
	for (int i = 1; i <= k; i++) {
		int mark = 0;
		for (int j = 1; j < i; j++)
			if (a[j] == a[i]) {
				if (b[i] != b[j]) return 0;
				mark = 1;
			}
		if (!mark) {
			sum += b[i];
			if (sum > n) return 0;
		}
	}
	return 1;
}
void dfs(int k)
{
	if (k == n + 1) {
		for (int i = 1; i <= n; i++)
			if (num[a[i]] != b[i])
				return;
		if (flag) {
			for (int i = 1; i <= n; i++)
				if (b[i] > ans[i])
					return;
		}
		flag = 1;
		for (int i = 1; i <= n; i++) ans[i] = b[i];
		return;
	}
	if (a[k] > n) {
		b[k] = 0;
		num[0]++;
		dfs(k + 1);
		num[0]--;
		return;
	}
	for (int i = 0; i <= n; i++) {
		b[k] = i;
		num[i]++;
		if (check(k)) dfs(k + 1);
		num[i]--;
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	memset(num, 0, sizeof(num));
	flag = 0;
	dfs(1);
	if (flag)
		for (int i = 1; i <= n; i++)
			printf("%d%c", ans[i], i == n ? '\n' : ' ');
	else
		printf("do not exist\n");
	return 0;
}