1130 Infix Expression(25 分)

题目:

1130 Infix Expression(25 分)

大概描述:

语法树进行解析,实质进行二叉树进行前序遍历

特征词:

树的遍历

使用语言:

C++

解题思想:

利用所给的二叉树,进行前序遍历

题目得分:

25

提交次数:

1

时间

50

代码

#include<iostream>
#include<string>
#include<map>
#include<set>
using namespace std;
struct node{
 string v;
 int l;
 int r;
};

map<int,node> ns;
int st;
void post(int a){
 //cout << a;
 if(a == -1) return;
 if(ns[a].l != -1 || (ns[a].l == -1 && ns[a].r != -1))
 if(st != a)
 cout << "(";
 post(ns[a].l);
 cout << ns[a].v;
 post(ns[a].r);
 if(ns[a].r != -1 || (ns[a].r == -1 && ns[a].l != -1))
 if(st != a)
 cout << ")";
 return;
}
int main(){
 int a,b,c;
 string s;
 cin >> a;

 set<int> se;
 for(int i = 0;i < a;i++){
 cin >> s >> b >> c;
 ns[i + 1] = node{s,b,c};
 se.insert(b);
 se.insert(c);
 }
 for(int i = 1;i < a + 1;i++){
 if(se.find(i) == se.end())
 st = i;
 }
 post(st);
 return 0;
}

 成长

熟练的使用map + struct的组合。

1139. First Contact (30)

题目:

1139. First Contact (30)

大概描述:

两人进行交往,注意并不只考虑异性,也考虑同性

特征词:

STL 模拟

使用语言:

C++

解题思想:

用map建立两个关系,一个是同性联系的map,一个是异性联系的map,而没有使用邻接表,化成两个map处理起来比较方便,直观

题目得分:

18

提交次数:

2

时间

60

代码

#include<map>
#include<cstdio>
#include<set>//利用set自动排序
using namespace std;

//建两个map进行存储
int main(){
 int a,b,c,e1,e2;

 map<int,set<int>> same;
 map<int,set<int>> diff;

 scanf("%d %d",&a,&b);

 for(int i = 0;i < b;i++){
 scanf("%d %d",&e1,&e2);
 if(e1 * e2 > 0){
 same[e1].insert(e2);
 same[e2].insert(e1);
 }
 else{//-0000与0000在diff中
 diff[e1].insert(e2);
 diff[e2].insert(e1);
 }
 }

 scanf("%d",&c);
 for(int i = 0;i < c;i++){
 scanf("%d %d",&e1,&e2);
 map<int,set<int>>ans;
 int t = 0;
 if(e1 * e2 <= 0){
 for(set<int>::iterator it = same[e1].begin();it != same[e1].end();it++){
 for(set<int>::iterator itt = diff[*it].begin();itt != diff[*it].end();itt++){
 if(same[e2].find(*itt) != same[e2].end() && *itt != *it){
 ans[abs(*it)].insert(abs(*itt));
 t++;
 }
 }
 }
 }else{
 for(set<int>::iterator it = same[e1].begin();it != same[e1].end();it++){
 for(set<int>::iterator itt = same[*it].begin();itt != same[*it].end();itt++){
 if(same[e2].find(*itt) != same[e2].end() && *itt != *it){
 ans[abs(*it)].insert(abs(*itt));
 t++;
 }
 }
 }


 }


 printf("%d\n",t);
 for(map<int,set<int>>::iterator it = ans.begin();it != ans.end();it++){
 for(set<int>::iterator itt = (it -> second).begin();itt != (it -> second).end();itt++){
 printf("%d %d\n",it->first,*itt);
 }
 }
 }




}

 成长

我下次一定记得用string进行读取

1081. Rational Sum (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1081

大概描述:

求解分数之和

特征词:

简单模拟

使用语言:

C++

解题思想:

先找到出公倍数,然后将每个分子相加

题目得分:

16/20

提交次数:

3

做题时间:

50分钟

具体代码如下:

代码1:

//两数最大公约数,必然是除数与余数的最大公约数,因此用递归
//其中数组使用long long 建立二位数时候,无法使用
//有一个测试点迟迟通不过,前面考虑可能是因为负数问题后来发现,似乎是在每次通分后的累计没有及时约分导致的感觉这个有点恐怖

#include<cstdio>

int gcd(int a,int b){//求解最大公约数
 if(b == 0)
 return a;
 else
 return gcd(b,a%b);

}
int main(){
 int num ;
 int i = 0;
 int s[2][102];
 long long re = 1;
 int e = 0;
 scanf("%d",&num);
 for(i = 0;i < num;i++){
 scanf("%d/%d",&s[0][i],&s[1][i]);
 }
 for(i = 0;i < num;i++){
 //printf("%d/%d",s[0][i],s[1][i]);
 }
 for(i = 0;i < num;i++){
 if(re % s[1][i] != 0){
 //printf("s[1][%d] = %d\n",s[1][i]);
 e = gcd(re,s[1][i]);
 // printf("%d * = (%d / %d)\n",re,s[1][i],e);
 re *= (s[1][i] / e);
 // printf("re = %d\n",re);
 }

 }
 // printf("%d\n",re);
 long long es = 0;
 for(i = 0;i < num;i++){
 es += re / s[1][i] * s[0][i];
 }

 if(es * re < 0)
 printf("-");
 if(es < 0)
 es = - es;
 if(re < 0)
 re = - re;
 int m = es / re;
 if(m != 0)
 printf("%d",m);
 int t = es % re;
 if(t != 0){
 if(m != 0)
 printf(" ");
 e = gcd(re,t);
 printf("%ld/%ld",t/e,re/e);
 }else{
 if(m == 0){
 printf("0");
 }
 }
}

代码2:

#include<cstdio>

long long a = 0,b = 0;

long gcd(long v,long c){//求解最大公约数
 if(c == 0)
 return v;
 else
 return gcd(c,v % c);
}
void sumR(long c,long d){
 //找出最大公因数
 // printf("NOW %d %d u\n",c,d);
 long long m = d,n = b;
 n = gcd(m,n);

 //此时n为最大公因数
 // printf("n = %d ",n);
 long long r = d / n;
 long long rr = r * b;
// printf("c = %d r = %d",c,r);
 long long r1 = rr / d;
 long long c1 = c * r1;
 // printf("a = %d rr = %d d = %d",a,rr,b);
 long long r2 = rr / b;
 long long c2 = a * r2;
 // printf("c1 = %d c2 = %d\n",c1,c2);
 a = c1 + c2;
 b = rr;
 // printf("a = %d b = %d",a,b);
}

int main(){
 int num = 0;
 scanf("%d",&num);
 int i;
 long long c,d;
 scanf("%lld/%lld",&a,&b);
 for(i = 1;i < num;i++){
 scanf("%lld/%lld",&c,&d);
 //printf("OOK\n");
 sumR(c,d);
 }
 if(a < 0){
 printf("-");
 a = -a;
 }
 long long n = gcd(a,b);
 // printf("n = %d ",n);
 if(a > b && a % b / n != 0){
 printf("%lld %lld/%lld",a / b,a % b / n,b / n);
 return 0;
 }
 if(a > b && a % b / n == 0){
 printf("%lld",a / b);
 return 0;
 }
 if(a != 0)
 printf("%lld/%lld",a / n,b / n);
 if(a == 0)
 printf("0");
}

运行结果

16/20

 成长

对于已经进行扩容用long long 型还要考虑的测试点是,在过程中如果ll * ll型容易溢出,所以对于

long long c1 = c * rr / d;
long long r1 = rr / d;
long long c1 = c * r1;

的转换处理。

另外对于寻找最短路径需要加强记忆

long gcd(long v,long c){//求解最大公约数
 if(c == 0)
 return v;
 else
 return gcd(c,v % c);
}

1041. Be Unique (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1041

大概描述:

找出不重复的第一个数字输出

特征词:

系数数组

使用语言:

C++

解题思想:

利用了嵌套的系数数组进行有序的累加,具体看代码

题目得分:

20

提交次数:

2

做题时间:

28分钟

具体代码如下:

//题目理解出现的不重复的第一个数字输出
//嵌套式 的系数数组结构处理
#include<cstdio>
int main(){
 int num = 0;
 scanf("%d",&num);
 int i = 0;
 int a[10000]={0};
 int s[10000]={0};
 for(i = 0;i < num;i++){
 scanf("%d",&a[i]);
 s[a[i]] ++;
 }
 for(i = 0;i < num;i++){
 if(s[a[i]] == 1){
 printf("%d",a[i]);
 break;
 }
 }
 if(i == num)
 printf("None");


}

运行结果

20

 成长

利用使用双数组,其中一个用存储输入顺序,a[100000],还有一个用于作为系数数组,进行值得累加。在输出得时候,就可以利用a的顺序进行值的输出。

1092. To Buy or Not to Buy (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1092

大概描述:

输入一个字符串,和一个目标字符串,看目标字符串中的字符是否都包含在第一个字符串中

特征词:

字符串

使用语言:

C++

解题思想:

 

就是逐个比较

题目得分:

20

提交次数:

2

做题时间:

28分钟

具体代码如下:

#include<cstdio>
#include<cstring>
int main(){
 char g[1010];
 char ne[1010];
 scanf("%s",g);
 scanf("%s",ne);
 int gw = strlen(g);
 int nw = strlen(ne);
 int i,j = 0;int que = 0;
 for(i = 0;i < nw;i++){
 for(j = 0;j < gw;j++){
 if(ne[i] == g[j]){
 g[j] = '_';
 break;
 }
 }
 if(j == gw)
 que ++;
 }
 if(que == 0)
 printf("Yes %d",gw-nw);
 else
 printf("No %d",que);
}

运行结果

20

 成长

1075. PAT Judge (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1075

大概描述:

就是将考试每次提交的成绩进行计算,并提交

特征词:

排序  系数数组

使用语言:

C++

解题思想:

大体思路就是依据代号建立数组,然后将数据进行更新,再排序

题目得分:

19

提交次数:

3

做题时间:

136分钟

具体代码如下:

#include<cstdio>
#include<algorithm>
const int N = 10010;
struct m{
int ti[5];
int id;
int fulls;
int sig;
int zong;
}p[N];

bool pp(m a,m b){
 if(a.zong != b.zong)
 return a.zong > b.zong;
 if(a.fulls != b.fulls)
 return a.fulls > b.fulls;
 else
 return a.id < b.id;
}

int main(){
 int pnum;
 int tnum;
 int tcnum;
 int i , j;
 int a, b, c;
 int tis[5] = {0};
 scanf("%d %d %d",&pnum,&tnum,&tcnum);
 for(i = 0;i < tnum;i++){
 scanf("%d",&tis[i]);
 }
 for(i = 0;i < N;i++){
 for(j = 0;j < 5;j++){
 p[i].ti[j] = -1;
 }
 }
 for(i = 0;i < tcnum;i++){
 scanf("%d %d %d",&a,&b,&c);
 p[a].id = a;
 if(c == tis[b-1] && p[a].ti[b-1] != tis[b-1]){
 printf("%d %d %d\n",i,p[a].id,p[a].ti[b-1]);
 p[a].fulls ++;
 }
 if(p[a].ti[b-1] <= c){
 p[a].sig = 1;
 p[a].ti[b-1] = c;
 }

 if(c == -1&&p[a].ti[b-1] == -1){
 p[a].ti[b-1] = -2;
 }
 }

 for(i = 0;i < N;i++){
 if(p[i].sig == 1){
 for(j = 0;j < tnum;j++){
 if(p[i].ti[j] == -1 || p[i].ti[j] == -2)
 p[i].zong += 0;
 else
 p[i].zong += p[i].ti[j];
 }
 }
 }
 std::sort(p,p+N,pp);
int u1 = 1;int u2 = 1;

 for(i = 0;i < N;i++){//等级排名
 if(p[i].sig == 1 && p[i].zong != 0){
 printf("%d ",u1);
 if(p[i].zong != p[i+1].zong){
 u1 = i+2;
 }


 printf("%05d %d",p[i].id,p[i].zong);
 for(j = 0;j <tnum;j++){
 if(p[i].ti[j] == -1){
 printf(" -");
 }
 else
 if(p[i].ti[j] == -2){
 printf(" 0");
 }
 else
 printf(" %d",p[i].ti[j]);
 }
 printf(" %d",p[i].fulls);
 printf("\n");
 }

 }


}

运行结果

19

 成长

 

其中实现的过程中一波三则,首先是建立了信息数组,利用编号是从1到N的整数型仿照之前写过的系数数组
// 其次是等级排序,因为之前看题时忽视了这一条件,导致再后来才看到,这里的等级排序,个人所想,较为巧妙,是利用与后一项的比较
// 最后运行时两个测试点没有通过,发现,错误原因,一个人他在提交成功,再次提交那题