比赛 ID: 2016
注：本题解参考代码均为 C++ 代码，如果你是 C 使用者，出现不认识的头文件时，若是 c 开头的，一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件，如 cstdio 在 C 中为 stdio.h ，其他的请自行搜索。另外，如果出现不认识的写法，如 sort（排序） 、 stack（栈） 等，请自行实现。
A - SDUT 2041 初级二十四点游戏
签到题，判断 m+n 和 m*n 即可。
参考代码：
#include <cstdio>
using namespace std;
int main(int argc, char const *argv[]) {
int m, n;
scanf("%d %d", &m, &n);
if(m+n==24 || m*n==24) printf("Yes\n");
else printf("No\n");
return 0;
}B - SDUT 3352 高数Umaru系列（3）——喵星人
用三层 for 循环枚举每种喵粮的购买数量，如果总花费小于等于 n，则记录一次方案，最后输出总方案数即可。
参考代码：
#include <cstdio>
using namespace std;
int main(int argc, char const *argv[]) {
int n;
while(~ scanf("%d", &n)) {
int ans = 0;
for(int i=0; i<=n/12; ++i) {
for(int j=0; j<=n/5; ++j) {
for(int k=0; k<=n/2; ++k) {
if(i*12+j*5+k*2 <= n) ans++;
}
}
}
printf("%d\n", ans);
}
return 0;
}C - SDUT 2887 RE选老婆
用数组记录每种字母是否出现过，最后遍历一遍即可得到不同字母的个数。
参考代码：
#include <cstdio>
using namespace std;
int main(int argc, char const *argv[]) {
char s[101];
while(~ scanf("%s", s)) {
bool h[26] = {false}; // 标记字母是否出现过
for(int i=0; s[i]; ++i) {
h[s[i]-'a'] = true;
}
int cnt = 0;
for(int i=0; i<26; ++i) { // 计算不同字母的数量
if(h[i]) cnt++;
}
if(cnt%2 == 0) printf("GET OUT!\n");
else printf("I WANT YOU!\n");
}
return 0;
}D - SDUT 2082 Bone Collector
裸的 01 背包题，不解释。
参考代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
const int MAXC = 1000;
int main(int argc, char const *argv[]) {
int t, n, c, w[MAXN+1], v[MAXN+1], dp[MAXC+1];
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &c);
for(int i=1; i<=n; ++i) {
scanf("%d", &v[i]);
}
for(int i=1; i<=n; ++i) {
scanf("%d", &w[i]);
}
memset(dp, 0, sizeof dp);
for(int i=1; i<=n; ++i) {
for(int j=c; j>=w[i]; --j) {
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
}
printf("%d\n", dp[c]);
}
return 0;
}E - SDUT 1021 考新郎
n 个里选 m 个的错排。应用错排公式和组合数公式即可。其中组合数公式为：n! / (m! * (n-m)!)。
参考代码：
#include <cstdio>
using namespace std;
const int MAX = 20;
int main(int argc, char const *argv[]) {
int c, n, m;
long long a[MAX+1] = {0, 0, 1,}, f[MAX+1] = {1,};
for(int i=3; i<=MAX; ++i) {// 预处理：错排
a[i] = (i-1)*(a[i-1]+a[i-2]);
}
for(int i=1; i<=MAX; ++i) { // 预处理：阶乘
f[i] = f[i-1] * i;
}
scanf("%d", &c);
while(c--) {
scanf("%d %d", &n, &m);
printf("%lld\n", a[m]*(f[n]/(f[m]*f[n-m])));
}
return 0;
}F - SDUT 3334 数据结构实验之栈七：出栈序列判定
设置一个栈，并设置 2 个变量来存储当前入栈序列和出栈序列的遍历位置。我们可以遍历一下出栈序列，每次循环时，如果当前栈顶符合出栈序列中当前要出栈的数，则直接出栈；否则按入栈序列继续 push。如果入栈完毕而出栈序列依然没有全部符合，则不是合法的出栈序列。
参考代码：
#include <cstdio>
#include <stack>
using namespace std;
int main(int argc, char const *argv[]) {
int n, t, a[10000], b[10000];
scanf("%d", &n);
for(int i=0; i<n; ++i) {
scanf("%d", &a[i]);
}
scanf("%d", &t);
while(t--) {
for(int i=0; i<n; ++i) {
scanf("%d", &b[i]);
}
stack<int> s;
int idx_a = 0, idx_b = 0;
while(idx_b < n) {
if(!s.empty() && s.top()==b[idx_b]) { // 栈顶符合，出栈
s.pop();
idx_b++;
}
else if(idx_a < n) s.push(a[idx_a++]); // 否则先按 a 入栈
else break; // 不满足，跳出
}
if(s.empty()) printf("yes\n"); // 如果栈已空，说明序列符合
else printf("no\n");
}
return 0;
}G - SDUT 3471 汤圆星の汤圆树
首先要使层数最少，则每层的汤圆必须尽可能连够 m 个汤圆。第 1 层为 1 个，第 2 层为 m 个，之后每一层上的汤圆都会与它的父汤圆和它的 m-1 个子汤圆连接，所以每多一层，都会多出 m-1 个子汤圆，这样，最外层的汤圆数是上一层的 m-1 倍。我们只需要不断累乘，直到最外层汤圆数不小于 n 即可。
另外需要注意特判 n=1 和 m=2 的情况（先自己思考一下为什么）。
参考代码：
#include <cstdio>
using namespace std;
int main(int argc, char const *argv[]) {
int m, n, ans;
while(scanf("%d %d", &m, &n), m|n) {
if(n == 1) ans = 1; // n = 1 时，只需要树根
else {
if(m == 2) { // m = 2 时，第 2 层之后每层数量不会增加
if(n == 2) ans = 2;
else ans = -1;
}
else {
ans = 2;
long long tmp = m;
while(tmp < n) { // 最外层汤圆数不足 n 时一直累乘
tmp *= (m-1);
ans++;
}
}
}
printf("%d\n", ans);
}
return 0;
}H - SDUT 1703 今年暑假不AC
贪心题，和「SDUT 2073 活动选择问题」几乎是一样的题，不解释。
参考代码：
#include <cstdio>
#include <algorithm>
using namespace std;
struct info {
int s;
int e;
} t[100];
bool cmp(info a, info b) {
return a.e < b.e;
}
int main(int argc, char const *argv[]) {
int n;
while(scanf("%d", &n) && n) {
for(int i=0; i<n; ++i) {
scanf("%d %d", &t[i].s, &t[i].e);
}
sort(t, t+n, cmp);
int st = 0, ans = 0;
for(int i=0; i<n; ++i) {
if(t[i].s >= st) {
ans++;
st = t[i].e;
}
}
printf("%d\n", ans);
}
return 0;
}