ccf-csp 2017冬季真题题解

最小差值
问题描述
给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。
输入格式
输入第一行包含一个整数n。
第二行包含n个正整数，相邻整数之间使用一个空格分隔。
输出格式
输出一个整数，表示答案。
样例输入
5
1 5 4 8 20
样例输出
1
样例说明
相差最小的两个数是5和4，它们之间的差值是1。
样例输入
5
9 3 6 1 3
样例输出
0
样例说明
有两个相同的数3，它们之间的差值是0.
数据规模和约定
对于所有评测用例，2 ≤ n ≤ 1000，每个给定的整数都是不超过10000的正整数。

代码：

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;
const int MAXN = 1010;
int arr[MAXN];

int main(){
    int n, ans = INT_MAX;

    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> arr[i];

    sort(arr, arr + n);
    for(int i = 1; i < n; i ++)
        if(abs(arr[i] - arr[i - 1]) < ans)
            ans = abs(arr[i] - arr[i - 1]);
    cout << ans;
    return 0;
}

游戏
问题描述
有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。
游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。
例如，当n=5, k=2时：
1号小朋友报数1；
2号小朋友报数2淘汰；
3号小朋友报数3；
4号小朋友报数4淘汰；
5号小朋友报数5；
1号小朋友报数6淘汰；
3号小朋友报数7；
5号小朋友报数8淘汰；
3号小朋友获胜。
给定n和k，请问最后获胜的小朋友编号为多少？
输入格式
输入一行，包括两个整数n和k，意义如题目所述。
输出格式
输出一行，包含一个整数，表示获胜的小朋友编号。
样例输入
5 2
样例输出
3
样例输入
7 3
样例输出
4
数据规模和约定
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

代码：

#include <iostream>
#include <list>

using namespace std;

list<int> ls;

int main() {
    int n, k, tmp = 1;

    cin >> n >> k;
    for (int i = 0; i < n; i++)
        ls.push_back(i);

    list<int>::iterator it = ls.begin();
    while (ls.size() > 1) {
        list<int>::iterator t = it;
        t ++;
        if(t == ls.end())
            t = ls.begin();

        if (tmp % k == 0 || tmp % 10 == k) 
            ls.erase(it);
        it = t;
        ++ tmp;
    }
    cout << (*it) + 1 << endl;
    return 0;
}

Crontab

样例输入
3 201711170032 201711222352
0 7 * * 1,3-5 get_up
30 23 * * Sat,Sun go_to_bed
15 12,18 * * * have_dinner
样例输出
201711170700 get_up
201711171215 have_dinner
201711171815 have_dinner
201711181215 have_dinner
201711181815 have_dinner
201711182330 go_to_bed
201711191215 have_dinner
201711191815 have_dinner
201711192330 go_to_bed
201711200700 get_up
201711201215 have_dinner
201711201815 have_dinner
201711211215 have_dinner
201711211815 have_dinner
201711220700 get_up
201711221215 have_dinner
201711221815 have_dinner

代码：

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cstring>

using namespace std;

int n, WK;
string tstart, ted;
//<minutes> <hours> <day of month> <month> <day of week> <command>
unordered_map<string, int> map;

struct node {
    string ans;
    bool minutes[60]{}, hours[24]{}, days[32]{}, months[13]{}, weeks[7]{};

    node() {
        memset(minutes, false, sizeof(minutes));
        memset(hours, false, sizeof(hours));
        memset(days, false, sizeof(days));
        memset(months, false, sizeof(months));
        memset(weeks, false, sizeof(weeks));
    };
};

node arr[30];

void init() {
    map["jan"] = 1;
    map["feb"] = 2;
    map["mar"] = 3;
    map["apr"] = 4;
    map["may"] = 5;
    map["jun"] = 6;
    map["jul"] = 7;
    map["aug"] = 8;
    map["sep"] = 9;
    map["oct"] = 10;
    map["nov"] = 11;
    map["dec"] = 12;

    map["sun"] = 0;
    map["mon"] = 1;
    map["tue"] = 2;
    map["wed"] = 3;
    map["thu"] = 4;
    map["fri"] = 5;
    map["sat"] = 6;
}

void deal(string &s, bool *v, const int lim, const int base) {
    for (char &c : s)
        c = tolower(c);
    if (s == "*") {
        for (int j = 0 + base; j < lim + base; j++)
            v[j] = true;
        return;
    }
    int pos = 0;
    while (pos < s.length()) {
        int len = 0;
        while (isdigit(s[pos + len]) || isalpha(s[pos + len]))
            ++len;
        if (pos + len == s.length() || s[pos + len] == ',') {
            if (isdigit(s[pos]))
                v[stoi(s.substr(pos, len))] = true;
            else {
                v[map[s.substr(pos, len)]] = true;
            }
            pos += len + 1;
        } else {
            int st;
            if (isdigit(s[pos]))
                st = stoi(s.substr(pos, len));
            else
                st = map[s.substr(pos, len)];
            pos += len + 1;
            len = 0;
            while (isdigit(s[pos + len]) || isalpha(s[pos + len]))
                ++len;
            int ed;
            if (isdigit(s[pos]))
                ed = stoi(s.substr(pos, len));
            else
                ed = map[s.substr(pos, len)];
            for (int j = st; j <= ed; j++)
                v[j] = true;
            pos += len + 1;
        }
    }
}

int dd[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int cal(int y, int m) {
    if (m == 2 && ((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0)))
        return 29;
    else
        return dd[m];
}

void fun(int y, int m, int d) {
    int a = 1970, b = 1, c = 1;
    WK = 4;
    while (a < y || b < m || c < d) {
        WK = (WK + 1) % 7;
        ++c;
        if (c > cal(a, b)) {
            c = 1;
            ++b;
        }
        if (b == 13) {
            b = 1;
            ++a;
        }
    }

}

int main() {
    init();
    cin >> n >> tstart >> ted;
    for (int i = 0; i < n; i++) {
        string s;
//        <minutes> 是分钟数，取值范围是 0−59;
        cin >> s;
        deal(s, arr[i].minutes, 60, 0);

//        <hours> 是小时数，取值范围是 0−23;
        cin >> s;
        deal(s, arr[i].hours, 24, 0);

//        <day of month> 是月份中的天数，取值范围是 1−31;
        cin >> s;
        deal(s, arr[i].days, 31, 1);

//        <month> 是月份，取值范围是 1−12，或 Jan - Dec ;
//这里需要在输出的时候判断日期是否可行
        cin >> s;
        deal(s, arr[i].months, 12, 1);

//        <day of week> 是星期几，取值范围是 0−6，或 Sun - Sat。
        cin >> s;
        deal(s, arr[i].weeks, 7, 0);

        //合成日期 yyyy mmddHHMM week
        cin >> s;
        arr[i].ans = s;
    }

    int y_st = stoi(tstart.substr(0, 4)), mon_st = stoi(tstart.substr(4, 2)), d_st = stoi(
            tstart.substr(6, 2)), h_st = stoi(tstart.substr(8, 2)), min_st = stoi(tstart.substr(10, 2));
    int y_ed = stoi(ted.substr(0, 4)), mon_ed = stoi(ted.substr(4, 2)), d_ed = stoi(
            ted.substr(6, 2)), h_ed = stoi(ted.substr(8, 2)), min_ed = stoi(ted.substr(10, 2));

    //得到周几
    fun(y_st, mon_st, d_st);

    while (y_st < y_ed || mon_st < mon_ed || d_st < d_ed || h_st < h_ed || min_st < min_ed) {
        for (int i = 0; i < n; i++)
            if (arr[i].weeks[WK] && arr[i].months[mon_st] && arr[i].days[d_st] && arr[i].hours[h_st] &&
                arr[i].minutes[min_st])
                printf("%04d%02d%02d%02d%02d %s\n", y_st, mon_st, d_st, h_st, min_st, arr[i].ans.c_str());

        ++min_st;
        h_st += min_st / 60;
        min_st %= 60;
        if (h_st >= 24) {
            h_st = 0;
            ++d_st;
            WK = (WK + 1) % 7;
        }
        if (d_st > cal(y_st, mon_st)) {
            d_st = 1;
            ++mon_st;
        }
        if (mon_st == 13) {
            mon_st = 1;
            ++y_st;
        }
    }
    return 0;
}

行车路线
问题描述
小明和小芳出去乡村玩，小明负责开车，小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。
例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=16+2+4=22。
现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。
输入格式
输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。
接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。
输出格式
输出一个整数，表示最优路线下小明的疲劳度。
样例输入
6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1
样例输出
76
样例说明
从1走小道到2，再走小道到3，疲劳度为52=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。
数据规模和约定
对于30%的评测用例，1 ≤ n ≤ 8，1 ≤ m ≤ 10；
对于另外20%的评测用例，不存在小道；
对于另外20%的评测用例，所有的小道不相交；
对于所有评测用例，1 ≤ n ≤ 500，1 ≤ m ≤ 105，1 ≤ a, b ≤ n，t是0或1，c ≤ 105。保证答案不超过106。

代码：

#include <iostream>
#include <cstring>
#include <queue>
#include <climits>

using namespace std;

const int N = 510, M = 2e5 + 10, INF = 1e6;

int head[N], ver[M], nxt[M], edge[M], cnt = 0, n, m;
long long dist[N][1010];
bool type[M], vis[N][1010];   //1-小道  0-大道
struct node {
    long long d;
    int u, p;

    bool operator<(const node &t) const {
        return d > t.d;
    };
};

void add(bool t, int a, int b, int c) {
    ver[++cnt] = b;
    type[cnt] = t;
    edge[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));

    priority_queue<node> Q;
    dist[1][0] = 0;
    Q.push({0, 1, 0});
    while (!Q.empty()) {
        node cur = Q.top();
        Q.pop();
        if (vis[cur.u][cur.p] || cur.d > INF)
            continue;
        vis[cur.u][cur.p] = true;
        for (int i = head[cur.u]; i; i = nxt[i]) {
            int u = ver[i];
            if (!type[i]) {
                if (dist[u][0] > dist[cur.u][cur.p] + edge[i]) {
                    dist[u][0] = dist[cur.u][cur.p] + edge[i];
                    if (dist[u][0] <= INF)
                        Q.push({dist[u][0], u, 0});
                }
            } else {
                if (cur.p + edge[i] > 1000)
                    continue;
                if (dist[u][cur.p + edge[i]] >
                    dist[cur.u][cur.p] - (long long) cur.p * cur.p +
                    (long long) (cur.p + edge[i]) * (cur.p + edge[i])) {
                    dist[u][cur.p + edge[i]] = dist[cur.u][cur.p] - (long long) cur.p * cur.p +
                                               (long long) (cur.p + edge[i]) * (cur.p + edge[i]);
                    if (dist[u][cur.p + edge[i]] <= INF)
                        Q.push({dist[u][cur.p + edge[i]], u, cur.p + edge[i]});
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        bool t;
        cin >> t >> a >> b >> c;
        add(t, a, b, c);
        add(t, b, a, c);
    }

    dijkstra();

    long long ans = LONG_LONG_MAX;
    for (int i = 0; i < 1000; i++)
        ans = min(ans, dist[n][i]);
    cout << ans << endl;
    return 0;
}

商路

代码：

//60 分
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;
const LL MOD = 1e18;

int n;
LL v[N];
int p[N], w[N], f[N];
LL ans[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(ans, 0, sizeof ans);
        for (int i = 1; i <= n; i ++ )
            scanf("%d%d%lld%d", &p[i], &w[i], &v[i], &f[i]);
        for (int i = n; i; i -- )
        {
            int k = p[i], d = w[i];
            while (k)
            {
                ans[k] = max(ans[k], v[k] - (LL)(f[k] - d) * (f[k] - d) + ans[i]);
                d += w[k];
                k = p[k];
            }
        }
        LL res = 0;
        for (int i = 1; i <= n; i ++ )
            res = (res + ans[i]) % MOD;
        printf("%lld\n", res);
    }
    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/952194/

更多历年题解戳这里：ccf-csp 历年真题题解

原文链接：https://blog.csdn.net/Raymond_YP/article/details/115188814