甲级
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 到底买不买
这道题简而言之就是求两串字符串中各个字符是否符合要求。
因为字符只有[09]、[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;
}
网友评论