洛谷官方提单——函数与结构入门题解（水题警告）

函数实际上就是我们将程序的语句分成不同的块，每一块都执行不同的操作，这样的“代码块”称之为函数(function)。通过将代码分割为一个又一个的函数，虽然在执行函数调用的时候存在开销，但是在后续对程序的修改和对功能的扩充比直接在main函数中方便得多。
顺带一提，在C++中，最好将接口写在main函数上面，这样就可以减少一行前置声明（具体相关请翻看相关书籍查找前置声明）。
结构体则是数据的集合，从数组，到链表，再到OS里的PCB，这些很多都是结构体。每个结构体由程序员自行设计，通过将数据“打包”，可以在进行某些操作（比如排序）会更加的方便。

接下来就是关于本题单的题解了。

题目0: 距离函数

就是简单的两点之间的距离公式的计算机实现，注意输出格式和数据类型就很简单了。

#include<stdio.h>
#include<math.h>
double dist(double x1,double x2,double y1,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
    double x1,y1,x2,y2,x3,y3;
    scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
    double ans=dist(x1,x2,y1,y2)+dist(x1,x3,y1,y3)+dist(x2,x3,y2,y3);
    return 0*printf("%.2lf\n",ans);
}

题目1：质数筛

模板题，筛选方法有欧拉筛或者埃筛，一般题目中埃筛就够了，碰到了欧拉筛再补充吧。
埃筛的过程是：开一个数组vis，0和1标记为“不是素数”的flag，然后从2开始遍历，如果vis[i]是质数，那么从这个质数开始的2倍，3倍直至最后边界范围内都不会质数，提前标记为“不是质数”；若“不是质数”，则直接进入下一轮循环，这样我们在调用是不是质数的时候，只需要简单的判断vis[num]的标记即可。

#include<stdio.h>
bool numlist[100050] = { 1,1 };
void work() {
    for (int i = 2; i <= 10000; i++) {
        if (numlist[i] == false) {
            for (int j = i; i * j <= 100000; j++)
                numlist[i * j] = true;
        }
    }
    return;
}
int main() {
    int n, temp;
    scanf("%d", &n);
    work();
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        if (numlist[temp] == false)
            printf("%d ", temp);
    }
    return 0;
}

题目2：闰年展示

判断闰年在题单1就有了，主要是在输出年之前需要count，因此需要存下来。

#include<iostream>
#include<vector>
int main() {
    int x, y, cnt = 0;
    std::vector<int> ans;
    std::cin >> x >> y;
    for (int i = x; i <= y; i++)
        if ((i % 4 == 0 && i % 100 != 0) || (i % 400 == 0))
            ans.push_back(i), cnt++;
    std::cout << cnt << std::endl;
    for (int i=0;i<cnt;i++) std::cout << ans[i] << ' ';
    return 0;
}

题目3：歌唱比赛

这道题没啥讲的= =，基本就是前面的题的组合。

#include<stdio.h>
#include<algorithm>
int memo[25];
double max(double x, double y) { return x > y ? x : y; }
int main() {
    int n, m;
    double mmax = -1;
    scanf("%d%d", &n, &m);
    while (n--) {
        double sum = 0.0;
        for (int i = 0; i < m; i++)
            scanf("%d", &memo[i]);
        std::sort(memo, memo + m);
        for (int i = 1; i < m - 1; i++) sum += memo[i];
        mmax = max(mmax, sum / (m - 2));
    }
    return 0 * printf("%.2lf", mmax);
}

题目4：阶乘

直接递归即可。(当n很大的时候建议使用之前写过的杨辉三角）

#include<stdio.h>
int jie(int x) {
    if (x == 0) return 1;
    else return x * jie(x - 1);
}
int main() {
    int n;
    scanf("%d", &n);
    int ans = jie(n);
    printf("%d", ans);
    return 0;
}

题目5：赦免战俘

这种带有典型的分形的题就是典型的递归题目。
另解，实际这道题也可以发现，ans[i][j]=ans[i][j-1]^ans[i+1][j-1]，这类题都会存在类似的规律，一般来说如果sample给的十分遮掩可以考虑试试这种方法来“凑”答案。

#include<stdio.h>
int n, ans[1050][1050];
void work(int n, int x, int y){
    if (n == 2){
        ans[x][y] = 0;
        return;
    }
    for (int i = x; i <= x + n / 2 - 1; i++)
        for (int j = y; j <= y + n / 2 - 1; j++) ans[i][j] = 0; 
    work(n / 2, x + n / 2, y);
    work(n / 2, x + n / 2, y + n / 2);
    work(n / 2, x, y + n / 2); 
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= 1<<n; i++)
        for (int j = 1; j <= 1 << n; j++) ans[i][j] = 1;
    work(1 << n, 1, 1);
    for (int i = 1; i <= 1 << n; i++) {
        for (int j = 1; j <= 1 << n; j++)
            printf("%d ", ans[i][j]);
        printf("\n");
    }
    return 0;
}

题目6：最厉害的学生

大家都应该知道在algorithm库里面有个sort函数，按照一般的升序我们只需要sort(s.begin(),s.end())，但是我们可以通过使用第三个可选参数来决定比较方式，通过写一个函数接口即可解决。

//比赛的时候没必要这么命名
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
struct hello {
    int Chinese, Math, English;
    string Name;
}student[1000];
bool cmp(hello student1, hello student2) { 
    return student1.Chinese + student1.Math + student1.English > student2.Chinese + student2.Math + student2.English; 
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> student[i].Name >> student[i].Chinese >> student[i].Math >> student[i].English;
    sort(student, student + n, cmp);
    cout << student[0].Name << " " << student[0].Chinese << " " << student[0].Math << " " << student[0].English << endl;
    return 0;
}

题目7：旗鼓相当的对手 - 加强版

也就是判断条件比较复杂，实际上还是很简单，但是注意总分的时候不要把之前算的三个差值直接加起来。

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
struct S {
    string Name;
    int Chinese, Math, English;
}student[1024];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)  
        cin >> student[i].Name >> student[i].Chinese >> student[i].Math >> student[i].English;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sub1 = abs(student[i].Chinese - student[j].Chinese);
            int sub2 = abs(student[i].Math - student[j].Math);
            int sub3 = abs(student[i].English - student[j].English);
            int sub4 = abs(student[i].English + student[i].Chinese + student[i].Math - student[j].Chinese - student[j].Math - student[j].English);
            if (sub1 <= 5 && sub2 <= 5 && sub3 <= 5 && sub4 <= 10) {
                if (student[i].Name > student[j].Name) cout << student[j].Name << " " << student[i].Name << endl;
                else cout << student[i].Name << " " << student[j].Name << endl;
            }
        }
    }
    return 0;
}

题目8：评级

emmm经过题目8，这道题就没必要讲了吧。

#include<iostream>
using namespace std;
struct student {
    int student_number, study_grade, other_grade;
}st[1010];
int main() {
    int n;
    double after_weight = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> st[i].student_number >> st[i].study_grade >> st[i].other_grade;
        after_weight = st[i].study_grade * 0.7 + st[i].other_grade * 0.3;
        if (after_weight > 80 && st[i].study_grade + st[i].other_grade > 140) cout << "Excellent" << endl;
        else cout << "Not excellent" << endl;
    }
    return 0;
}

题目9：质因数分解

循环结构的原题，自己回去看。

题目10：哥德巴赫猜想

因为要分解为质数之和，所以我们直接把质数先筛选出来（没错就是前面的质数筛），然后从小到大直接加就ok了。

#include <stdio.h>
int prime[10000] = { 1,1 }, n;
void filter() {
    for (int j = 2; j < 10000; j++)
        for (int k = j * 2; k < 10000; k += j) prime[k] = 1;
}
int main() {
    scanf("%d", &n);
    filter();
    for (int i = 4; i <= n; i += 2) {
        int j = 2;//这里要注意，一定每次进第一循环的时候初始化为2
        for (; prime[j] || prime[i - j]; j++);
        printf("%d=%d+%d\n", i, j, i - j);
    }
    return 0;
}

题目11：集合求和

这里大致说一下推理过程，首先我们知道对于每一个有n个元素的集合，其子集个数为2^n。
当子集只有一个元素的时候，每个元素被选中一次；当子集中只有两个元素的时候，恰好被选中C(n,2）次，依次类推，只需要对n对于1到n的所有组合数求和再乘以所有元素的和即为答案（这里涉及到二项式定理）。

#include <stdio.h>
int main() {
    long long ans = 0;
    int cnt = 0, temp;
    while (~scanf("%d", &temp)) ans += temp, cnt++;
    for (int i = 1; i < cnt; i++) ans *= 2;
    printf("%lld", ans);
    return 0;
}

题目12：回文质数

原题略。

题目13：猴子吃桃

纯模拟，会读题小学生都会。

#include<iostream>
using namespace std;
int main() {
    int n, ans = 1;
    cin >> n;
    for (int i = 1; i < n; i++) 
        ans = (ans + 1) * 2;
    cout << ans << endl;
    return 0;
}

题目14：培训

和上面那些比较分数的大同小异、

#include<iostream>
#include<string>
using namespace std;
struct student {
    string name;
    int age, score;
} candidate[100000];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> candidate[i].name >> candidate[i].age >> candidate[i].score;
        candidate[i].age++, candidate[i].score = candidate[i].score / 5 * 6;
        if (candidate[i].score > 600) candidate[i].score = 600;
        cout << candidate[i].name << " " << candidate[i].age << " " << candidate[i].score << endl;
    }
    return 0;
}

入门题刷完了，明天就要开始六大基础算法的刷题，争取一天两个吧（bushi）。