SDUT - 2017年寒假集训 阶段测试赛3(个人)解题报告

2017-02-19 234 次浏览 解题报告

比赛 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;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/02/19/sdut-c2016.dream

还不快抢沙发

添加新评论