甲級
1002
這道題有個坑，就是系數(shù)為0的時候不算，這個需要在算完之后再逐項挑出來。此題是姥姥和何老師開的的數(shù)據(jù)結構慕課里，何老師講授的多項式的求和。下意識地用了鏈表來寫，無奈于突然忘了鏈表怎么構建，想到可以用vector，搭配struct結構體來快速模擬。于是有了第一種方法（這種方法有點麻煩，因為其實原題目中指數(shù)N的范圍只有[0,1000]，少得可憐，完全可以直接開數(shù)組來做，但確實會有點浪費空間就是了。）：
#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剩下的繼續(xù)插入到p1的尾部
while(i2<p2.size()){
p1.insert(p1.end(),p2[i2]);
i2++;
}
//在這里卡了大半天，細心點啊，數(shù)個數(shù)的時候也要判斷是否為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;
}
然后是第二種方法，直接開數(shù)組，空間換時間的方法（其實也換不了多少時間）：
#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;
}
//輸出，記得算個數(shù)和輸出項的時候都要判斷是否為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 統(tǒng)計同成績學生
本題要求讀入 N 名學生的成績，將獲得某一給定分數(shù)的學生人數(shù)輸出。
輸入格式：
輸入在第 1 行給出不超過 10^5的正整數(shù) N，即學生總人數(shù)。隨后一行給出 N 名學生的百分制整數(shù)成績，中間以空格分隔。最后一行給出要查詢的分數(shù)個數(shù) K（不超過 N 的正整數(shù)），隨后是 K 個分數(shù)，中間以空格分隔。輸出格式：
在一行中按查詢順序給出得分等于指定分數(shù)的學生人數(shù)，中間以空格分隔，但行末不得有多余空格。輸入樣例：
10
60 75 90 55 75 99 82 90 75 50
3 75 90 88輸出樣例：
3 2 0
這道題要說一下，關于數(shù)組統(tǒng)一初始化的問題，對于整數(shù)數(shù)組，可以直接使用int a[10]={0}來將其全部初始化為0，但是若使用memset函數(shù)統(tǒng)一初始化為0或-1的話，需要用到#include <cstring>頭文件和memset(a,0,10*sizeof(int))（順便提及，memory.h和string.h都能對應memset，而malloc函數(shù)要用stdlib.h或malloc.h）。非0非-1的初始化，其實循環(huán)賦值也挺好的，復雜度就一個O(n)。
#include <iostream>
using namespace std;
int main(){
int n,k,a[100001];
cin>>n;
//這里是將數(shù)組初始化
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的數(shù)組來統(tǒng)計各個字符出現(xiàn)的次數(shù)，遍歷每個字符串，以字符為下標進行統(tǒng)計，出現(xiàn)一次就++，之后再遍歷一遍，用兩個變量計算滿足條件與否就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;
//從前往后或從后往前數(shù)其實都一樣，這里是從后開始數(shù)
for(int i=len-1;i>=0;i--){
//先從后往前數(shù)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;
}
