牛客竞赛语法入门班数组字符串习题C++版本参考代码及部分解析

牛客竞赛语法入门班数组字符串习题C++版本参考代码及部分解析

牛客竞赛语法入门班数组字符串习题

重点题：
1013 打印质数表(素数筛法)
1019 扫雷(初级搜索)

1013 打印质数表

#include 
using namespace std;
int prime[2010];
int main()
{
    int n;
    cin >> n;
    for (int i = 2;i <= n;i++)//从2开始判断
    {
        if (prime[i] == 0) 
        {
            cout << i << " ";
            for (int j = i + i;j <= n;j += i)
                prime[j] = 1;
        }
    }
    return 0;
}

1019 扫雷
（可以使用方向数组改进，DFS中常用）

#include 
#include 
using namespace std;

char a[1010][1010];
int cnt;//cnt表示当前位置的八个方向一共有多少个地雷

int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            cin >> a[i][j];
    
    for (int i = 1;i <= n;i++)//数组下标从1开始,相当于给数组加上一个边框,防止越界
    {
        for (int j = 1;j <= m;j++)
        {
            if (a[i][j] == '*') continue;//遇到地雷,跳过该点
            cnt = (a[i - 1][j - 1] == '*') + (a[i - 1][j] == '*') + (a[i - 1][j + 1] == '*')
                + (a[i][j - 1] == '*') +                          + (a[i][j + 1] == '*')
                +(a[i + 1][j - 1] == '*') + (a[i + 1][j] == '*') + (a[i + 1][j + 1] == '*');
            a[i][j] = cnt + '0';//将int类型的cnt转换为字符类型
        }
    }
    
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            cout << a[i][j];
        }
        puts("");
    }    
    return 0;
}

改进之后的代码：

#include 
#include 

using namespace std;

int cnt;
char a[1010][1010];
int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            cin >> a[i][j];
    
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            if (a[i][j] == '*') continue;
			cnt = 0;
            for (int k = 0;k < 8;k++)
			{
				if (a[i + dir[k][0]][j + dir[k][1]] == '*') cnt++;
			}
            a[i][j] = cnt + '0';
        }
    }
    
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            cout << a[i][j];
        }
        puts("");
    }    
    return 0;
}

1032 [NOIP2007] 奖学金

#include 
#include 
using namespace std;
struct student
{
    int id;
    int chi_score;
    int math_score;
    int e_score;
    int sum_score;
}s[310];
bool cmp(student a,student b)
{
    if (a.sum_score != b.sum_score) return a.sum_score > b.sum_score;
    if (a.sum_score == b.sum_score && a.chi_score != b.chi_score) 
        return a.chi_score > b.chi_score;
    return a.id < b.id; 
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)//注意学号无0号,从下标1开始存储
    {
        cin >> s[i].chi_score >> s[i].math_score >> s[i].e_score;
        s[i].sum_score = s[i].chi_score + s[i].math_score + s[i].e_score;
        s[i].id = i;
    }
    sort(s + 1,s + n + 1,cmp);
    for (int i = 1;i <= 5;i++) 
        cout << s[i].id << " " << s[i].sum_score << endl;
    return 0;
}