2019-08-06（甲级1题，乙级5题）

甲级

1002

这道题有个坑，就是系数为0的时候不算，这个需要在算完之后再逐项挑出来。此题是姥姥和何老师开的的数据结构慕课里，何老师讲授的多项式的求和。下意识地用了链表来写，无奈于突然忘了链表怎么构建，想到可以用vector，搭配struct结构体来快速模拟。于是有了第一种方法（这种方法有点麻烦，因为其实原题目中指数N的范围只有[0,1000]，少得可怜，完全可以直接开数组来做，但确实会有点浪费空间就是了。）：

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int main(){
    typedef struct{
        int k;
        float a;
    }node;
    vector<node> p1,p2;
    //输入，分别存到p1,p2
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        node temp;
        cin>>temp.k>>temp.a;
        p1.push_back(temp);
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        node temp;
        cin>>temp.k>>temp.a;
        p2.push_back(temp);
    }
    //遍历，把p2的元素插入到p1
    int i1=0,i2=0;
    while(i1<p1.size()&&i2<p2.size()){
        if(p1[i1].k<p2[i2].k){
            p1.insert(p1.begin()+i1,p2[i2]);
            i1++;
            i2++;
        }
        else if(p1[i1].k==p2[i2].k){
            p1[i1].a+=p2[i2].a;
            i1++;
            i2++;
        }
        else{
            i1++;
        }
    }
    //p2剩下的继续插入到p1的尾部
    while(i2<p2.size()){
        p1.insert(p1.end(),p2[i2]);
        i2++;
    }
    //在这里卡了大半天，细心点啊，数个数的时候也要判断是否为0
    int cnt=0;
    for(int i=0;i<p1.size();i++){
        if(p1[i].a!=0) cnt++;
    }
    cout<<cnt;
    for(int i=0;i<p1.size();i++){
        if(p1[i].a!=0) printf(" %d %.1f",p1[i].k,p1[i].a);
    }
    return 0;
}

然后是第二种方法，直接开数组，空间换时间的方法（其实也换不了多少时间）：

#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
    float b[1001];
    for(int i=0;i<1001;i++) b[i]=0;
    //输入
    int n,m;
    cin>>n;
    for(int i=0;i<n;i++){
        int k;
        float a;
        scanf("%d%f",&k,&a);
        b[k]+=a;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int k;
        float a;
        scanf("%d%f",&k,&a);
        b[k]+=a;
    }
    //输出，记得算个数和输出项的时候都要判断是否为0
    int cnt=0;
    for(int i=1000;i>=0;i--){
        if(b[i]!=0)cnt++;
    }
    cout<<cnt;
    for(int i=1000;i>=0;i--){
        if(b[i]!=0) printf(" %d %.1f",i,b[i]);
    }
    return 0;
}

乙级

1036 跟奥巴马一起编程

这题就算了。。

1037 在霍格沃茨找零钱

这题也算了，有点类似时间的转换。

1038 统计同成绩学生

本题要求读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。

输入格式：
输入在第 1 行给出不超过 10^5的正整数 N，即学生总人数。随后一行给出 N 名学生的百分制整数成绩，中间以空格分隔。最后一行给出要查询的分数个数 K（不超过 N 的正整数），随后是 K 个分数，中间以空格分隔。

输出格式：
在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。

输入样例：
10
60 75 90 55 75 99 82 90 75 50
3 75 90 88

输出样例：
3 2 0

这道题要说一下，关于数组统一初始化的问题，对于整数数组，可以直接使用int a[10]={0}来将其全部初始化为0，但是若使用memset函数统一初始化为0或-1的话，需要用到#include <cstring>头文件和memset(a,0,10*sizeof(int))（顺便提及，memory.h和string.h都能对应memset，而malloc函数要用stdlib.h或malloc.h）。非0非-1的初始化，其实循环赋值也挺好的，复杂度就一个O(n)。

#include <iostream>
using namespace std;

int main(){
    int n,k,a[100001];
    cin>>n;
    //这里是将数组初始化
    for(int i=0;i<100001;i++){
        a[i]=0;
    }
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        a[temp]++;
    }
    cin>>k;
    for(int i=0;i<k;i++){
        int temp;
        cin>>temp;
        cout<<a[temp];
        if(i!=k-1) cout<<" ";
    }
    return 0;
}

1039 到底买不买

这道题简而言之就是求两串字符串中各个字符是否符合要求。
因为字符只有[0_9]、[az]、[A~Z]，直接开两个256的数组来统计各个字符出现的次数，遍历每个字符串，以字符为下标进行统计，出现一次就++，之后再遍历一遍，用两个变量计算满足条件与否就ok了。

1040 有几个PAT

这题有个坑，就是要取余%1000000007，看看柳神的讲解：链接
就是这个坑，又耗了一段时间。。

#include <iostream>
using namespace std;

int main(){
    string a;
    cin>>a;
    int index=-1,P=0,A=0,T=0,n=0,len=a.length();
    int *sum = new int[100001];
    for(int i=0;i<100001;i++) sum[i]=0;
    //从前往后或从后往前数其实都一样，这里是从后开始数
    for(int i=len-1;i>=0;i--){
        //先从后往前数T有多少个
        if(a[i]=='T'){
            T++;
            T=T%1000000007;
        }
        //逢A就赋值，说明它后面有N个T了
        else if(a[i]=='A'){
            A+=T;
            A=A%1000000007;
        }
        //逢P就又赋值，告诉它后面能组成M个AT了
        else if(a[i]=='P'){
            P+=A;
            P=P%1000000007;
        }
        //cout<<a[i]<<sum[i]<<endl;
    }
    cout<<P%1000000007;
    return 0;
}