鄭州輕工業大學新生周賽2題解

可寫題應該有 A、B、C、D、F、G、H，其他題感興趣的同學可以看看，

問題 A: 年齡判斷

簽到題*1

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    if (n <= 3)
        printf("infant\n");
    else if (n <= 12)
        printf("child\n");
    else if (n <= 18)
        printf("youngster\n");
    else if (n <= 25)
        printf("youth\n");
    return 0;
}

問題 B: 大象喝水

簽到題*2，寫法很多，可以公式求答案，也可以while回圈暴力求解，

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    double n, h, r;
    scanf("%lf%lf%lf", &n, &h, &r);
    double sum = 0;
    int ans = 0;
    while (sum < n)
    {
        ans++;
        sum += r * r * 3.1415926 * h;
    }
    printf("%d\n", ans);
    return 0;
}

問題 C: 并聯電阻

簽到題*3

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    double n, m;
    scanf("%lf%lf", &n, &m);
    printf("%.2f\n", 1 / (1 / n + 1 / m));
    return 0;
}

問題 D: 學長自救計劃

題面有鍋，輸入的是n、m、pos而不是m、n、pos，

走廊有兩頭，那么我們考慮走兩邊逃跑哪邊需要的體力更少即可，

順便先提一下三目運算 ?:

a?b:c，其中a是一個運算式，b和c是一個陳述句，

等價于 

if(a)
b;
else 
c;

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m, pos;
        scanf("%d%d%d", &n, &m, &pos);
        int ans_left = 0, ans_right = 0;
        for (int i = 1; i <= n; i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            if (a <= pos) //怪物在左邊
                ans_left += b;
            else if (a >= pos) //怪物在右邊
                ans_right += b;
        }
        printf("%d\n", ans_left < ans_right ? ans_left : ans_right);
    }
    return 0;
}

問題 E: 花海

這題為了代碼美觀，思路清晰，用到了函式判斷素數，感興趣的同學可以先了解一下函式，本周會講解，

AC代碼：

#include <bits/stdc++.h>
using namespace std;

bool ispreme(int x) //函式判斷素數
{
    int i;
    for (i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}
int main()
{
    int n;
    scanf("%d", &n);
    int i, j, ans = 0;
    for (i = 2; i <= n; i++)
    {
        for (j = 2; j * i <= n; j++)
        {
            if (ispreme(i) && ispreme(j))
                ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

問題 F: 今夕何夕

將節日分別記作1、2、3、4，然后用二維陣列a[i][j]記錄 第i個人在第j個節日是否有空，

AC代碼：

#include <bits/stdc++.h>
using namespace std;

char s[10];
int a[10][10];
int main()
{
    for (int i = 1; i <= 6; i++)
    {
        int n;
        scanf("%d", &n);
        for (int j = 1; j <= n; j++)
        {
            scanf("%s", s);
            if (s[0] == 'N' && s[1] == 'Y')
                a[i][1] = 1;
            if (s[0] == 'I' && s[1] == 'L')
                a[i][2] = 1;
            if (s[0] == 'T' && s[1] == 'D')
                a[i][3] = 1;
            if (s[0] == 'N' && s[1] == 'D')
                a[i][4] = 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= 4; i++)
    {
        int sum = 0;
        for (int j = 1; j <= 6; j++)
            sum += a[j][i];
        if (sum == 6) //6個人都有空
        {
            ans = i;
            break;
        }
    }
    if (ans == 0)
        printf("What a shame!\n");
    else if (ans == 1)
        printf("New Year\n");
    else if (ans == 2)
        printf("International Labor Day\n");
    else if (ans == 3)
        printf("The Dragon Boat Festival\n");
    else if (ans == 4)
        printf("National Day\n");
    return 0;
}

問題 G: 一個餐廳

本題用到的abs(x)是math.h頭檔案中的一個函式，回傳x的絕對值，

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int a[310];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans1, ans2 = 100000000000;
    for (int i = n; i >= 1; i--)
    {
        int sum = 0;
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                sum += abs(a[j] - a[i]);
            }
        }
        if (sum < ans2) //先保證距離最近
        {
            ans1 = a[i];
            ans2 = sum;
        }
        else if (sum == ans2) //再保證坐標最小
        {
            if (a[i] < ans1)
            {
                ans1 = a[i];
            }
        }
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

問題 H: acm可好玩了

這題應該可以寫，需要注意的是，你的所有輸出最終都在一個檔案中，測評系統評判你的題目是否正確，就是對應預先就有的標準答案檔案和你的輸出檔案是否一樣，因此我們最后一次性輸出，和每次輸出，最后的效果一致，

AC代碼：

#include <bits/stdc++.h>
using namespace std;

char s[110];
int main()
{
    while (~scanf("%s", s))
    {
        int len = strlen(s);
        for (int i = len - 1; i >= 0; i--)
            printf("%c", s[i]);
        printf(" ");
    }
    return 0;
}

問題 I: 小H的面試難題

比較裸的對頂堆動態維護中位數，nlogn可寫，

對頂堆詳解博客

AC代碼：

#include <bits/stdc++.h>
using namespace std;

priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int>> q2;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int temp;
        scanf("%d", &temp);
        q2.push(temp);
        if (i & 1) //奇數
        {
            while (q1.size() != q2.size() + 1)
            {
                int res = q2.top();
                q2.pop();
                q1.push(res);
            }
            while (q1.top() > q2.top())
            {
                int res1 = q1.top();
                int res2 = q2.top();
                q1.pop(), q2.pop();
                q2.push(res1);
                q1.push(res2);
            }
            printf("%d\n", q1.top());
        }
    }
    return 0;
}

問題 J: 最大的差

此題卡時間，

常規解法就是列舉一個ai，再從后面找所有aj，更新答案，

這樣時間復雜度是 O ( n 2 ) O(n^2) O(n2)，資料范圍 100000 100000 100000，會TLE，我們可以預處理一個后綴最小值，這樣可以把時間復雜度降到 O ( n ) O(n) O(n)

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int a[100010];
int pre[100010]; //pre[i]表示區間[i,n]的最小值
int main()
{
    int n;
    scanf("%d", &n);
    pre[n + 1] = 2000000001;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = n; i >= 1; i--)
    {
        pre[i] = pre[i + 1] < a[i] ? pre[i + 1] : a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = ans > a[i] - pre[i] ? ans : a[i] - pre[i];
    }
    printf("%d\n", ans);
    return 0;
}