2025南昌大学软件学院雏鸟杯程序设计竞赛题解

题目链接：https://exam.nowcoder.com/cts/17482915/summary

1.hello,world!

签到题

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s="hello,world!";
    
    int n = s.size();
    for (int i = 0; i < n / 2; ++i) {
        char temp = s[i];
        s[i] = s[n - 1 - i];
        s[n - 1 - i] = temp;
    }
    
    cout << s << endl;
    return 0;
}

或者更直接一点

#include <iostream>
#include <string>
using namespace std;

int main() {
    printf("!dlrow,olleh");
    return 0;
}

2.进制转换

先将n进制转化为10进制，再从10进制转化为m进制。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

long long nToDec(string s, int n) {
    long long dec = 0;
    for (int i=0;i<s.size();i++) {
        char c = s[i];
        dec = dec * n + (c - '0');
    }
    return dec;
}

string decToM(long long dec, int m) {
    if (dec == 0) {
        return "0";
    }
    string res;
    while (dec > 0) {
        res += (dec % m) + '0';
        dec /= m;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int N, M;
    string n;
    cin >> N;
    cin >> n;
    cin >> M;
   
    long long decimal = nToDec(n, N);
    string m = decToM(decimal, M);
    
    cout << m << endl;
    return 0;
}

3.小鱼游啊游

将鱼塘对称展开，求边长和速率的最大公约数即可

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

long long gcd(long long a, long long b) {
    if(b==0) return a;
    return gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    long long L, W, X, Y;
    cin >> L >> W >> X >> Y;

    long long t1 = (2 * L) / gcd(2 * L, X);
    long long t2 = (2 * W) / gcd(2 * W, Y);

    long long t = lcm(t1, t2);
    double dist = t * sqrt((double)X * X + (double)Y * Y);

    cout << fixed << setprecision(2) << dist << endl;
    return 0;
}

4.鸡兔同笼

稍微困难一点的鸡兔同笼

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;

        int k = y - 2 * x; //x+2y=k
        if (k < 0) {
            cout << "0 0\n";
            continue;
        }

        int r_min = max(0, y - 3 * x); 
        int r_max = k / 2;

        cout << r_min << " " << r_max << "\n";
    }
    return 0;
}

5.滑动窗口

暴力遍历即可，本题也可使用单调队列解决，为最优解。

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    int nums[10000];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int resultSize = n - k + 1;
    int minResult[10000];
    int maxResult[10000];

    for (int i = 0; i < resultSize; i++) {
        int minVal = 10000;
        for (int j = i; j < i + k; j++) {
            if (nums[j] < minVal) {
                minVal = nums[j];
            }
        }
        minResult[i] = minVal;
    }

    for (int i = 0; i < resultSize; i++) {
        int maxVal = -1;
        for (int j = i; j < i + k; j++) {
            if (nums[j] > maxVal) {
                maxVal = nums[j];
            }
        }
        maxResult[i] = maxVal;
    }

    for (int i = 0; i < resultSize; i++) {
        if (i > 0) cout << " ";
        cout << minResult[i];
    }
    cout << endl;

    for (int i = 0; i < resultSize; i++) {
        if (i > 0) cout << " ";
        cout << maxResult[i];
    }
    cout << endl;

    return 0;
}

单调队列：

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> maxDeque;
    vector<int> maxResult;
    for (int i = 0; i < nums.size(); ++i) {
        while (!maxDeque.empty() && maxDeque.front() <= i - k) {
            maxDeque.pop_front();
        }
        while (!maxDeque.empty() && nums[maxDeque.back()] <= nums[i]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);
        if (i >= k - 1) {
            maxResult.push_back(nums[maxDeque.front()]);
        }
    }
    return maxResult;
}

vector<int> minSlidingWindow(vector<int>& nums, int k) {
    deque<int> minDeque;
    vector<int> minResult;
    for (int i = 0; i < nums.size(); ++i) {
        while (!minDeque.empty() && minDeque.front() <= i - k) {
            minDeque.pop_front();
        }
        while (!minDeque.empty() && nums[minDeque.back()] >= nums[i]) {
            minDeque.pop_back();
        }
        minDeque.push_back(i);
        if (i >= k - 1) {
            minResult.push_back(nums[minDeque.front()]);
        }
    }
    return minResult;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    vector<int> minResult = minSlidingWindow(nums, k);
    vector<int> maxResult = maxSlidingWindow(nums, k);

    for (int i = 0; i < minResult.size(); ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << minResult[i];
    }
    cout << endl;

    for (int i = 0; i < maxResult.size(); ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << maxResult[i];
    }
    cout << endl;
    return 0;
}

6.小猫浏览网页

暴力遍历即可

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    int links[500][500];  
    int cnt[500];         

    for (int i = 1; i <= N; i++) {
        cin >> cnt[i];
        for (int j = 0; j < cnt[i]; j++) {
            cin >> links[i][j];
        }
    }

    int visited[500] = {0};  
    visited[1] = 1;          

    for (int i = 0; i < cnt[1]; i++) {
        int v = links[1][i];
        visited[v] = 1;
    }

    for (int i = 0; i < cnt[1]; i++) {
        int v = links[1][i];
        for (int j = 0; j < cnt[v]; j++) {
            int w = links[v][j];
            visited[w] = 1;
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (visited[i]) ans++;
    }

    cout << ans << endl;
    return 0;
}

7.小猫找小鱼

考察快速排序和二分查找，熟悉C++的同学也可使用sort函数和find函数快速解决。

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  
    int i = low - 1;     
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;  
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 二分查找函数
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int N;
    cin >> N;

    vector<int> fish(N);
    for (int i = 0; i < N; ++i) {
        cin >> fish[i];
    }

    int M;
    cin >> M;

    quickSort(fish, 0, N - 1);
    int result = binarySearch(fish, M);

    cout << result << endl;
    return 0;
}

sort函数和find函数

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
int fish[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> fish[i];
    }
    int m;
    cin >> m;
    sort(fish, fish + n);
    int* pos = find(fish, fish + n, m);
    if (pos != fish + n) {
        cout << pos - fish << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}

8.小猫买鱼干

很典型的01背包问题

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> fish(n);
    for (int i = 0; i < n; ++i) {
        cin >> fish[i].first >> fish[i].second;
    }
    vector<int> dp(92,0);
    for (int i = 0; i < n; ++i) {
        int v = fish[i].first;
        int w = fish[i].second;
        for (int j = 91; j >= v; --j) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[91] << endl;
    return 0;
}

9.模拟计算

使用两个栈模拟计算器，一个栈存放数字，另一个栈存放符号；也可以使用数组模拟栈进行模拟计算；也可以使用python的eval函数进行转化

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;

int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

int calculate(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return 0;
    }
}

int main() {
    string s;
    getline(cin, s);
    stack<int> numStack;
    stack<char> opStack;
    int i = 0;
    int n = s.size();
    while (i < n) {
        if (s[i] == ' ') {
            i++;
            continue;
        }
        if (isdigit(s[i])) {
            int num = 0;
            while (i < n && isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            numStack.push(num);
        } else if (s[i] == '(') {
            opStack.push(s[i]);
            i++;
        } else if (s[i] == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                char op = opStack.top();
                opStack.pop();
                int b = numStack.top();
                numStack.pop();
                int a = numStack.top();
                numStack.pop();
                numStack.push(calculate(a, b, op));
            }
            if (!opStack.empty() && opStack.top() == '(') {
                opStack.pop();
            }
            i++;
        } else {
            while (!opStack.empty() && opStack.top() != '(' && getPriority(opStack.top()) >= getPriority(s[i])) {
                char op = opStack.top();
                opStack.pop();
                int b = numStack.top();
                numStack.pop();
                int a = numStack.top();
                numStack.pop();
                numStack.push(calculate(a, b, op));
            }
            opStack.push(s[i]);
            i++;
        }
    }
    while (!opStack.empty()) {
        char op = opStack.top();
        opStack.pop();
        int b = numStack.top();
        numStack.pop();
        int a = numStack.top();
        numStack.pop();
        numStack.push(calculate(a, b, op));
    }
    cout << numStack.top() << endl;
    return 0;
}

python代码如下：

s = input().strip()
print(eval(s))
# 没错，使用python的话只需要两行代码

10.安静的座位

连通块问题，使用DFS（深度优先搜索）解决。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dfs(vector<vector<int>>& matrix, int i, int j, int n, int m) {
    if (i < 0 || i >= n || j < 0 || j >= m || matrix[i][j] != 0) {
        return 0;
    }
    matrix[i][j] = 2;
    return 1 + dfs(matrix, i - 1, j, n, m) + dfs(matrix, i + 1, j, n, m) + dfs(matrix, i, j - 1, n, m) + dfs(matrix, i, j + 1, n, m);
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> matrix(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = row[j] - '0';
        }
    }

    int groupCount = 0;
    int maxGroupSize = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] == 0) {
                groupCount++;
                int currentSize = dfs(matrix, i, j, n, m);
                maxGroupSize = max(maxGroupSize, currentSize);
            }
        }
    }

    cout << groupCount << endl;
    cout << maxGroupSize << endl;
    return 0;
}