🚀欢迎来到本文🚀
🍉个人简介：Hello大家好呀，我是陈童学，一个与你一样正在慢慢前行的普通人。
🏀个人主页：@陈童学哦`CSDN
💡所属专栏：PTA
🎁希望各位→点赞👍 + 收藏⭐️ + 留言📝
⛱️刷题的当下应是享受的！望与诸君共勉！🏄‍♂️

在这里插入图片描述

下面是PTA的OJ平台

PTA的OJ平台（点击我直跳）

题目汇总

题解
- L2-008 最长对称子串
- L2-009 抢红包
- L2-010 排座位
- L2-011 玩转二叉树
写在最后

题解

L2-008 最长对称子串

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：
输入在一行中给出长度不超过1000的非空字符串。

输出格式：
在一行中输出最长对称子串的长度。

输入样例：
Is PAT&TAP symmetric?
输出样例：
11

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;getline(cin,s);int ans,tmp,len=s.size();ans=tmp=0;for(int i=0;i<len;i++){tmp=1;for(int j=1;j<len;j++){if(i-j<0||i+j>=len||s[i-j]!=s[i+j])break;tmp+=2;}ans=max(ans,tmp);tmp=0;for(int j=1;j<len;j++){if(i-j+1<0||i+j>=len||s[i-j+1]!=s[i+j])break;tmp+=2;}ans=max(ans,tmp);	}cout<<ans<<endl;
}

L2-009 抢红包

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：
输入第一行给出一个正整数N（≤10
4
），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

KN
1

P
1

⋯N
K

P
K

其中K（0≤K≤20）是发出去的红包个数，N
i

是抢到红包的人的编号，P
i

（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：
按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10
输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
struct node{int id,cnt;double income;
};
node ns[N];
bool cmp(node a,node b)
{if(a.income!=b.income)return a.income>b.income;if(a.cnt!=b.cnt)return a.cnt>b.cnt;return a.id<b.id;
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;ns[i].id=i;while(k--){int a,b;cin>>a>>b;ns[a].income+=b;ns[a].cnt++;ns[i].income-=b;}}sort(ns+1,ns+n+1,cmp);for(int i=1;i<=n;i++){cout<<ns[i].id<<" ";printf("%.2lf\n",ns[i].income/100);}
}

L2-010 排座位

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：
输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：
对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but…；如果他们之间只有敌对关系，则输出No way。

输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but…
No way

AC代码：

#include<bits/stdc++.h>
using namespace std;
int f[101]={0};
int isf(int x)
{if(f[x]==x)return x;else{f[x]=isf(f[x]);return f[x];}
}
int main()
{int n,m,k;int a,b,c;int e[101][101]={0};cin>>n>>m>>k;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=m;i++){cin>>a>>b>>c;e[a][b]=e[b][a]=c;if(c==1){a=isf(a);b=isf(b);if(a!=b)f[a]=b;}}for(int i=1;i<=k;i++){cin>>a>>b;if(e[a][b]==-1){if(isf(a)==isf(b))printf("OK but...\n");elseprintf("No way\n");}else{if(isf(a)==isf(b))printf("No problem\n");elseprintf("OK\n");}}
}

L2-011 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
输出样例：
4 6 1 7 5 3 2

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int in[N],pre[N],n;
struct node{int l,r;
}tree[N];int build(int l1,int r1,int l2,int r2)
{if(l1>r1||l2>r2)return 0;int p=l1;while(in[p]!=pre[l2])p++;int len=p-l1;int root=pre[l2];tree[root].l=build(l1,p-1,l2+1,l2+len);tree[root].r=build(p+1,r1,l2+len+1,r2);return root;
}
vector<int>ans;void bfs(int x)
{queue<int>que;que.push(x);while(!que.empty()){int root=que.front();que.pop();ans.push_back(root);int l=tree[root].l,r=tree[root].r;if(r)que.push(r);if(l)que.push(l);}
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>in[i];for(int i=1;i<=n;i++)cin>>pre[i];build(1,n,1,n);bfs(pre[1]);for(int i=0;i<ans.size();i++){cout<<ans[i];if(i!=ans.size()-1)cout<<" ";	}
}