NOIP 2012 年普及组初赛试题整理「建议收藏」

全栈程序员站长

发布于 2022-09-23 10:12:00

1390

发布于 2022-09-23 10:12:00

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

问题求解

题目答案：

5

题目解析：

贪心法。构造出最坏情况下至多选4点、不在同一条直线上，此时再添加任意一个点，则一定出现3点一线。

题目答案：

2880

题目解析：

圆排列问题。

5名大陆选手的排列方案数为：5 ! 5名港澳选手安排在大陆选手之间的5个空位的排列方案数为：5 ! 总的排列方案数为：5 ! × 5 ! 。

但每位选手左边相邻的选手均相同，为重复方案。最终结果为：

阅读程序

#include <iostream>
using namespace std;
int n, i, j, a[100][100];
int solve(int x, int y){
    int u, v;
    if (x == n)return a[x][y];
    u = solve(x + 1, y);
    v = solve(x + 1, y + 1);
    if (u > v)
        return a[x][y] + u;
    else
        return a[x][y] + v;
}
int main(){
    cin>>n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            cin>>a[i][j];
    cout<<solve(1, 1)<<endl;
    return 0;
}

输入：

5 2 -1 4 2 -1 -2 -1 6 4 0 3 2 -1 5 8

输出：________

题目答案：

14

题目解析：

这个程序是在找一条从 (1,1) 到 (n,x)(1≤x≤n)开始的和最大的路径，每次只能从 (i, j) 走到 (i+1, j) 或 (i+1, j+1)。

完善程序

#include<iostream>
using namespace std;
const int SIZE = 100;
int x[SIZE], y[SIZE], f[SIZE];
int n, i, j, max_f, ans;
int main(){
    cin>>n;
    for (i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    max_f = 0;
    for (i = 1; i <= n; i++){
        f[i] =①;
        for (j = 1; j <= n; j++){
            if (x[j] < x[i] && ②)
                ③;
        }
        if (④){
            max_f = f[i];
            ⑤;
        }
    }
    for (i = 1; i <= n; i++)
        cout<<f[i]<<endl;
    cout<<ans<<endl;
}

填空④： f[i] >= max_f

题目解析：

若填 f[i] > max_f ，则当战斗力并列时不会更新最大值，题目要求为战斗力相同时，输出最大的编号，所以填f[i] >= max_f

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main(){
    cin>>n>>m;
    memset(used, false, sizeof(used));
    for (i = 1; i <= m; i++){
        data[i] = i;
        used[i] = true;
    }
    flag = true;
    while (flag){
        for (i = 1; i <= m-1; i++)cout<<data[i]<<"";
        cout << data[m] << endl;
        flag =①;
        for (i = m; i >= 1; i--){
            ②;
            for (j = data[i]+1; j <= n; j++)
                if (!used[j]){
                    used[j] = true;
                    data[i] =③;
                    flag = true;
                    break;
                }
            if (flag){
                for (k = i+1; k <= m; k++)
                    for (j = 1; j <=④; j++)
                        if (!used[j]){
                            data[k] = j;
                            used[j] = true;
                            break;
                        }
                ⑤;
            }
        }
    }
}

题目解析：

通过枚举的方式，输出排列。

空①，初始化标志变量 flag = false 空②，从最后一个位置的数字开始，将data[i]设置为未使用，used[data[i]] = false 空③，将位置i设置为数j 空④，枚举1~n所有可选数字，n 空⑤，枚举到一组方案，跳出for (i = m; i >= 1; i–)进行输出，break

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/172078.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java