PAT甲级题解1091-1120
1091
样例
输入:
3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0输出:
26思路和坑点
实际上是一个三维空间中“图”的bfs搜索，通过bfs搜索找到节点数大于指定阈值的连通分量的个数，借鉴《算法笔记》上的写法，使用增量矩阵来对一个坐标点周围的点进行遍历判别。主要在于理解题意，难点在于坐标点有效性的判定。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int x,y,z;
node():x(0),y(0),z(0){}
node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}
}Node;
int n,m,slice,T;
int G[1290][130][61]; //记录像素的坐标
bool inq[1290][130][61]={false}; //记录是否已被访问
int X[6]={1,-1,0,0,0,0,}; //六个方向坐标的增量矩阵
int Y[6]={0,0,1,-1,0,0,};
int Z[6]={0,0,0,0,1,-1,};
bool judge(int x,int y,int z); //判断是否应该访问该点
int BFS(int x,int y,int z); //返回对该坐标BFS遍历得到的中风核心中1的个数
int main(){
scanf("%d%d%d%d",&m,&n,&slice,&T);
for(int i=0;i<slice;i++){
for(int j=0;j<m;j++){
for(int k=0;k<n;k++){
scanf("%d",&G[j][k][i]);
}
}
}
int ans=0;
for(int i=0;i<slice;i++){
for(int j=0;j<m;j++){
for(int k=0;k<n;k++){
if(G[j][k][i]==1&&inq[j][k][i]==false){
ans+=BFS(j,k,i);
}
}
}
}
cout<<ans;
return 0;
}
bool judge(int x,int y,int z) //坐标判定
{
if(x<0||x>=m||y<0||y>=n||z<0||z>=slice) return false;//坐标越界不访问
else if(G[x][y][z]==0||inq[x][y][z]==true) return false; //像素是0，正常区域，或者已被访问，则不访问
else return true; //除了以上情况都进行访问
}
int BFS(int x,int y,int z){ //bfs遍历函数
int total=0; //统计该块中1的个数
queue<Node> q; //BFS的队列
q.push(node(x,y,z));
inq[x][y][z]=true;
while(!q.empty()){
Node now=q.front();
q.pop();
total++;
for(int i=0;i<6;i++){
int nx=now.x+X[i]; int ny=now.y+Y[i]; int nz=now.z+Z[i];
if(judge(nx,ny,nz)==true){
q.push(node(nx,ny,nz));
inq[nx][ny][nz]=true;
}
}
}
if(total>=T) return total; //如果超过阈值，返回1的个数，否则不计算在内，返回0
else return 0;
} 1092
样例
样例1
输入:
ppRYYGrrYBR2258
YrR8RrY输出:
Yes 8样例2
输入:
ppRYYGrrYB225
YrR8RrY输出:
No 2思路和坑点
使用map容器映射每一个字符串的字符个数，进行统计，分两种情况进行讨论即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
string a,b; //分别记录两个字符串
int ans=0,tag=1;
getline(cin,a); getline(cin,b);
unordered_map<char,int> shop,eva; //使用map统计字符的个数
for(int i=0;i<a.size();i++)
shop[a[i]]++;
for(int i=0;i<b.size();i++)
eva[b[i]]++;
for(auto it=eva.begin();it!=eva.end();it++){ //遍历eva的map容器，如果商店提供的不够，tag为0，表示不够
int s=shop[it->first],e=it->second;
if(s<e){
tag=0; ans+=(e-s); //统计不够的数量
}
}
if(tag) { //如果够了计算多购买的个数
printf("Yes ");
ans=a.size()-b.size();
}
else printf("No ");
printf("%d",ans);
return 0;
} 1093
样例
输入:
APPAPT输出:
2思路和坑点
计算字符串中的PAT个数。使用数学中的排列组合知识，对于一个序列来说，如果PPPPPPATTTTTTTT，类似的字符串中，对于每一个A来说，若左边有np个P，右边有nt个T，则从左侧挑出一个P有np种可能，右侧挑出一个T有nt种可能，则它可以组成np*nt个“PAT”。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main(void){
int cntP=0,cntT=0,ans=0; //分别统计T和P的个数
string pat;
getline(cin,pat);
for(int i=0;i<pat.size();i++) //统计T的个数
if(pat[i]=='T') cntT++;
for(int i=0;i<pat.size();i++){ //遍历字符串
if(pat[i]=='P') cntP++; //统计当前位置之前P的个数
else if(pat[i]=='T') cntT--; //计算当前位置之后T的个数
else {
ans+=cntT*cntP; //如果当前位置为A，根据排列组合的知识，组成的PAT个数为：A左侧的P的个数*A右侧的T的个数
ans%=mod; //每次计算过后取模
}
}
cout<<ans;
return 0;
} 1094
样例
输入:
23 13
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18输出:
9 4思路和坑点
由于多叉树结点不含信息，且使用1-n表示每个结点，因此使用二维vector来表示多叉树，v[i]中既是i的孩子。使用层次遍历记录每一层的节点个数，统计出结点最多的一层的层号。对于层序遍历来说，当一层结束的时候，队列中保存的是下一侧的全部节点，由此可以作为更新时候的统计方法。
坑点:
注意特判只有一个根的情况；
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,m;
scanf("%d%d",&n,&m);
if(n==1){ //特判只有根的情况
printf("1 1");return 0;
}
vector<int> v[n+1]; //使用二维数组记录多叉树，v[i]表示i的孩子
for(int i=0;i<m;i++){ //读入有孩子的结点信息
int id,num;
scanf("%d%d",&id,&num);
for(int j=0;j<num;j++){
int temp;
scanf("%d",&temp);
v[id].push_back(temp);
}
}
int layer=1,last=1,tail,maxn=1,maxl; //layer记录遍历时候的层数，初始化为1，last表示当前层的最后一个
queue<int> q; //tail用于更新last，maxn和maxl用于记录答案
q.push(1); //根结点入队
while(!q.empty()){ //层序遍历
int now=q.front();
q.pop();
for(int i=0;i<v[now].size();i++){ //如果有孩子孩子入队
q.push(v[now][i]);
tail=v[now][i];
}
if(now==last){ //如果当前层结束。此时队列中为全部下一层的结点
layer++; //更新layer和last
last=tail;
if(q.size()>maxn){ //如果下一层结点更多，更新maxn和maxl
maxn=q.size();
maxl=layer;
}
}
}
printf("%d %d",maxn,maxl); //输出结果
return 0;
} 1095
样例
输入:
16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00输出:
1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09思路和坑点
主要的难点在于：筛选有效信息，大规模数据的快速排序，查询的思路。
筛选有效信息时，将所有信息按照先车牌号，再时间的顺序，然后寻找到一组同一车辆的对应信息作为一组有效记录。
大规模的数据排序，尤其是结构体，建议使用下标的方式排序。
查询的时候按照是时间顺序排序，然后在查询时间点之前的所以记录进行统计，进入则数量加一，出去则数量减一，由于是按照时间先后顺序进行线性查询，所以一次遍历即可，注意遍历指针的定义和初始化要在循环外。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define time_int(hh,mm,ss) (hh*3600+mm*60+ss) //将时间转化为整形，定义成宏，速度更快些
typedef struct node{
string id; //车牌号
int time,tag=1; //时间和进出标记，默认1为进，0为出
}Car;
int cmptag=1; //排序标记
vector<Car> all; //所有数据
vector<int> sid,valid; //sid用于第一次下标排序，valid用于保存有效信息的下标，并用于第二次的下标排序
map<string,int> parktime; //记录每个车的停车时间
bool cmp(int a,int b){ //比较函数
if(cmptag==1){ //第一次排序，先按照车牌号排，再按照时间先后排
if(all[a].id!=all[b].id) return all[a].id<all[b].id;
else return all[a].time<all[b].time;
}
else{
return all[a].time<all[b].time; //第二次只按照时间排序
}
}
int main(void){
int n,k,hh,mm,ss,maxtime=-1; //初始化参数，maxtime表示停留的最长时间
scanf("%d%d",&n,&k);
all.resize(n); sid.resize(n); //初始化容器大小
for(int i=0;i<n;i++){
sid[i]=i; //初始化下标排序数组的下标
cin>>all[i].id; //读入信息
char temp[4];
scanf("%d:%d:%d %s",&hh,&mm,&ss,temp);
all[i].time=time_int(hh,mm,ss);
if(temp[0]=='o') all[i].tag=0; //如果是出，tag标记为0
}
sort(sid.begin(),sid.end(),cmp); //第一次排序
for(int i=0;i<n-1;i++){ //删选有效信息
int a=sid[i],b=sid[i+1]; //从排好序的序列中，取出相邻的两条信息
if(all[a].id==all[b].id&&all[a].tag==1&&all[b].tag==0){ //如果这两条是同一辆车，且前一个为进，后一个为出，表示一对有效信心
valid.push_back(a); valid.push_back(b); //记录有效记录的下标
int intime=all[b].time-all[a].time; //计算停车时间
parktime[all[a].id]+=intime; //总停车时间累加
maxtime=max(maxtime,parktime[all[a].id]);//更新最大停车时间
}
}
cmptag=0; //修改排序标记，对有效记录，进行第二次排序
sort(valid.begin(),valid.end(),cmp);
int j=0,numcnt=0; //j用于遍历有效记录，numcnt用于记录当前车辆个数
for(int i=0;i<k;i++){
scanf("%d:%d:%d",&hh,&mm,&ss); //读入查询信息
int qtime=time_int(hh,mm,ss);
for(j;j<valid.size();j++){ //遍历有效信息，因为查询是按照时间顺序的，因此只需要遍历一遍
int ind=valid[j]; //取出一条有效记录的下标
if(all[ind].time>qtime) break; //如果该记录在查询事件之后，则本次查询结束
if(all[ind].tag==1) numcnt++; //如果是进入，numcnt加一
else numcnt--; //如果是出去，numcnt减一
}
printf("%d\n",numcnt); //输出本次查询结果
}
for(auto it=parktime.begin();it!=parktime.end();it++){
if(it->second==maxtime) //遍历停车时间的容器，并输出和maxparktime相等的车辆id
printf("%s ",it->first.c_str()); //map自身有序，保证了id的有序
}
printf("%02d:%02d:%02d",maxtime/3600,maxtime%3600/60,maxtime%60);
return 0;
} 1096
样例
输入:
630输出:
3
5*6*7思路和坑点
直接对所有可能的连续因子进行统计，然后比较筛选出最合适的答案。考虑到对于一个非素数来说，其因子不会超过sqrt（）。
坑点:
注意特判素数的情况，个数为1，因子为自己本身。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
vector<int> out,temp; //使用数组保存因子，temp为临时结果，out为最终结果
int n;
cin>>n;
int sqr=(int)sqrt(1.0*n); //如果有连续因子，则因子小于等于n开根号
for(int i=2;i<=sqr;i++){
int t=n;
for(int j=i;;j++){ //从i开始获取连续的因子
if(t%j==0){
temp.push_back(j);
t/=j;
}
else break; //如果遇到不连续的则挑出循环
}
if(temp.size()>out.size()) //比较更新结果
out=temp;
temp.clear(); //temp清空，准备接受下一组结果
}
if(out.size()==0) //特判素数只有1和其自身
printf("1\n%d",n);
else{
int size=out.size(); //输出多因子的结果
printf("%d\n",size);
for(int i=0;i<size;i++){
if(i) putchar('*');
printf("%d",out[i]);
}
}
return 0;
} 1097
样例
输入:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854输出:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1思路和坑点
使用数组保存链表，记录结点本身的id，然后使用数组顺序存储链表结点，则输出时，一个链表结点的next便是紧挨着下一个结点的id，需要剔除不属于链表的结点，并顺带筛选分离保存下来和和删除的链表。链表输出时最后一个结点的next=-1，需要特殊处理。
坑点:
使用数组解题的时候需要过滤数据
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node{
int id,data,next;
}Node;
void Print(vector<Node> &v){ //打印链表
if(v.size()==0) return;
int i=0;
for(i;i<v.size()-1;i++) //最后一个特殊处理
printf("%05d %d %05d\n",v[i].id,v[i].data,v[i+1].id); //next用下一个结点的id代替
printf("%05d %d -1\n",v[i].id,v[i].data);
}
int main(void){
vector<Node> v(MAXN),re,rm; //v为所有的数据，re为剩余的结点，rm为益处的结点
unordered_map<int,bool> mp; //统计是否出现过该值
int head,n;
scanf("%d%d",&head,&n);
for(int i=0;i<n;i++){ //读入所给的所有结点
int id;
scanf("%d",&id); v[id].id=id;
scanf("%d%d",&v[id].data,&v[id].next);
}
for(int i=head;i!=-1;i=v[i].next){ //筛选结点
int temp=abs(v[i].data);
if(mp.find(temp)==mp.end()){ //如果是第一次出现，保留
mp[temp]=true;
re.push_back(v[i]);
}
else //否则，删除
rm.push_back(v[i]);
}
Print(re); //分别打印两个链表
Print(rm);
return 0;
} 1098
样例
样例1
输入:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0输出:
Insertion Sort
1 2 3 5 7 8 9 4 6 0样例2
输入:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9输出:
Heap Sort
5 4 3 1 0 2 6 7 8 9思路和坑点
利用插入排序的特征，前半部分有序，后半部分和原序列相同的特性。辨别是不是插入排序，如果是则在插入一个元素，否则是堆排序，可以直接利用c++11标准中的heap的相关操作，找到不满足堆的位置，然后将前边满足堆的部分弹出堆顶元素到尾巴上。heap的操作可以参考PAT总结那篇博客中的总结，也可以手动写函数实现。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,i=0,j;
cin>>n;
vector<int> v(n),mid(n); //存放原始序列和中间序列
for(i=0;i<n;i++) //读入数据
scanf("%d",&v[i]);
for(i=0;i<n;i++)
scanf("%d",&mid[i]);
for(i=0;i<n-1;i++){ //从中间序列开始，找到第一个不符合递增序列的下标j
if(mid[i]>mid[i+1]){
j=i+1;
i++;break;
}
}
for(j;j<n;j++) //从j开始，往后比较原始序列和中间序列
if(v[j]!=mid[j]) break;
if(j==n){ //如果后半部分和原始序列相同，则为插入排序
puts("Insertion Sort");
sort(mid.begin(),mid.begin()+i+1);
}
else{
puts("Heap Sort"); //否则为堆排序
auto pos=is_heap_until(mid.begin(),mid.end(),less<int>());
pop_heap(mid.begin(),pos); //查找第一个不满足堆的位置（大根堆），然后将前半部分的堆pop操作
}
for(int i=0;i<n;i++){ //输出结果
if(i) putchar(' ');
printf("%d",mid[i]);
}
return 0;
} 1099
样例
输入:
9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42输出:
58 25 82 11 38 67 45 73 42思路和坑点
二叉搜索树的中序遍历结果是有序的，因此先读入树的结构，然后得到中序遍历的结果，将结点的数值排序后安排入座，最后使用层序遍历输出。要学会使用静态数组表示的二叉树的写法和操作。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //结点结构体
int data; //数据
int left,right; //左右指针，初始化为-1
node(){
left=-1;
right=-1;
data=0;
}
}Node;
vector<Node> v; //保存所有结点
vector<int> num; //保存各结点的数据
vector<int> inorder; //中序遍历序列，用于对比安放结点数据
void Inorder(int root); //中序遍历
void laorder(int root); //层序遍历
int main(){
int n;
scanf("%d",&n); //读入树的结构
for(int i=0;i<n;i++){
Node temp;
scanf("%d%d",&temp.left,&temp.right);
v.push_back(temp);
}
for(int i=0;i<n;i++){ //读入结点数值
int temp;
scanf("%d",&temp);
num.push_back(temp);
}
sort(num.begin(),num.end());//搜索树的中序遍历有序
Inorder(0); //获取中序遍历序列
for(int i=0;i<n;i++){ //匹配各结点数值
int k=inorder[i];
v[k].data=num[i];
}
laorder(0); //层序遍历
return 0;
}
void Inorder(int root) //递归实现中序遍历
{
if(root==-1) return;
Inorder(v[root].left);
inorder.push_back(root);
Inorder(v[root].right);
}
void laorder(int root) //使用队列实现层序遍历
{
int cnt=0;
queue<int> q;
q.push(root);
while(!q.empty()){
int now=q.front();
if(cnt) putchar(' ');
printf("%d",v[now].data);
cnt++;
q.pop();
if(v[now].left!=-1) q.push(v[now].left);
if(v[now].right!=-1) q.push(v[now].right);
}
}1100
样例
输入:
4
29
5
elo nov
tam输出:
hel mar
may
115
13思路和坑点
进制转换，按照字符串读入，判断第一个字符是数字还是字母，进行相应的转换，这里使用map和string类数组进行双向的映射，也可以使用遍历数组的方式完成字符串到数字的映射关系，对数字进行处理时可以使用sscanf直接将string读成数字。（所给的字符串一定要拼写正确）
坑点
根据样例，如果是整13的倍数，只有高位，没有低位。
AC代码
#include<bits/stdc++.h>
using namespace std;
//字符数组
string low[]={"tret","jan","feb","mar","apr","may","jun","jly","aug","sep","oct","nov","dec"};
string high[]={"","tam","hel","maa","huh","tou","kes","hei","elo","syy","lok","mer","jou"};
map<string,int> lowmp,highmp; //字符到数字的映射
void string_int(string str){ //字符转成数字
int ans=0;
if(str.size()<5){
if(highmp.find(str)!=highmp.end()){ //如果只是单一的高位，即13的倍数
ans=13*highmp[str];
}
else
ans=lowmp[str]; //如果时只有低位
} //如果高位和低位同时存在
else ans=highmp[str.substr(0,3)]*13+lowmp[str.substr(4,3)];
cout<<ans<<'\n';
}
void int_string(string str){ //数字转成字符
int num;
sscanf(str.c_str(),"%d",&num);
if(num<13) //小于13的只有低位
cout<<low[num];
else{
cout<<high[num/13];
if(num%13) cout<<' '<<low[num%13]; //如果不是13的倍数，还需要输出低位
}
putchar('\n');
}
int main(void){
int n;
string temp;
for(int i=0;i<13;i++){ //初始化字符串到数字的映射
lowmp[low[i]]=i;
highmp[high[i]]=i;
}
cin>>n;
getchar(); //吸收第一行末尾的换行
for(int i=0;i<n;i++){
getline(cin,temp); //整行读入字符串
if(isalpha(temp[0]))
string_int(temp);
else
int_string(temp);
}
return 0;
} 1101
样例
输入:
5
1 3 2 4 5输出:
3
1 4 5思路和坑点
根据主元的特点，在排好序的所在位置上，且左侧的数都小于自身，右侧的数都大于自身，由于题目中的数字都不同，因此只需要验证一侧即可。排序后，遍历数组一一验证是否满足主元的特征。
坑点
最后要多加一个换行符，估计是0个的情况下，主元不用输出但是仍要占据一行。（这个真是谜之判定）
AC代码
#include<bits/stdc++.h>
using namespace std;
//快速排序的特性，最终所选的主元都在自己应该在的位置上
//并且保证左边的都小于主元，右边的都大于主元
int main(void){
int n;
vector<int> v,s,out;
scanf("%d",&n);
v.resize(n); s.resize(n);
for(int i=0;i<n;i++){ //读入数据
scanf("%d",&v[i]);
s[i]=v[i];
}
int max=-1; //记录左侧的最大值
sort(s.begin(),s.end()); //对其中一个数组进行排序
for(int i=0;i<n;i++){
if(v[i]==s[i]&&v[i]>max) //如果v中的一个元素在自己的排序后的位置上，且左边的数都小于自身
out.push_back(s[i]); //则为主元，因为题中所有的数均不相同，因此一定满足右边的数都大于自身
max=max>v[i]?max:v[i]; //更新左侧最大值
}
cout<<out.size()<<'\n'; //输出结果
for(int i=0;i<out.size();i++){
if(i) putchar(' ');
printf("%d",out[i]);
}
putchar('\n'); //谜之换行符，没有这一句，有一个测试点会格式错误
return 0;
} 1102
样例
输入:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6输出:
3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1思路和坑点
对树进行左右翻转，然后进行层序和中序的遍历。在读入孩子的时候按照先右后左的顺序读入。层序遍历使用队列实现，中序遍历使用递归方法实现，注意控制输出序列的空格。
坑点：
根未知，所以要根据树的结构筛选出根来，即没有被指向的结点（也就是没有父节点的）便是根。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //输的节点定义，使用二位数组存放数，左右孩子用下标序号表示
int l,r;
node():l(-1),r(-1){} //默认构造函数，初始化左右孩子为-1表示空
node(int _l,int _r):l(_l),r(_r){} //带参数的构造函数
}Node;
vector<Node> T; //用于存放树
int inocnt=0; //中序遍历控制空格的计数器
map<int,bool> mp; //记录是不是根，如果不是就从中删掉
void levelorder(int root); //层序遍历
void inorder(int root); //中序遍历
int main(){
int n;
scanf("%d",&n); //读入数据个数
for(int i=0;i<n;i++){
mp[i]=true; //初始化根的标记，假定所有的都是根
}
for(int i=0;i<n;i++){ //依次读入0-N-1的所有结点的孩子状况
string left,right; //由于存在- 这样的情况表示没有孩子，因此使用字符串读入（字符读入要考虑空格干扰）
Node temp; //创建一个临时的结点
cin>>right>>left; //结果要求翻转的树，因此按照先右后左的顺序读入
if(right!="-"){ //如果右孩子不是空
int num;
sscanf(right.c_str(),"%d",&num); //将其转化为数字记录进孩子
mp.erase(num); //同时剔除该顶点不是根
temp.r=num;
}
if(left!="-"){ //同理处理左孩子
int num;
sscanf(left.c_str(),"%d",&num);
mp.erase(num);
temp.l=num;
}
T.push_back(temp); //然后将其存入数组（如果两个孩子都没有，因为有默认初始化为-1，因此不用特殊处理）
}
int root=mp.begin()->first; //剩下的唯一一个标记就是根了
levelorder(root); //层序遍历
putchar('\n');
inorder(root); //中序遍历
return 0;
}
void levelorder(int root) //使用队列实现层序遍历
{
int cnt=0; //计数器，用于控制空格
queue<int> q;
q.push(root);
while(!q.empty()){
int now=q.front();
if(cnt) putchar(' ');
printf("%d",now);
cnt++;
q.pop();
if(T[now].l!=-1) q.push(T[now].l);
if(T[now].r!=-1) q.push(T[now].r);
}
}
void inorder(int root) //递归实现的中序遍历
{
if(root==-1) return ;
inorder(T[root].l);
if(inocnt) putchar(' '); //如果不是第一个输出，需要前置空格
printf("%d",root);
inocnt++;
inorder(T[root].r);
}1103
样例
样例1
输入:
169 5 2输出:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2样例2
输入:
169 167 3输出:
Impossible思路和坑点
这里的代码借鉴了柳神的代码。对一个树进行因式分解，这里使用打表的方法，构造从1~i的p次方数组。然后按照因子的从大到小的方式dfs搜索，知道找到一组可分解的结果，如果结果并列，则按照因子和的大小进行优化。（由于按照因子从大到小的结果进行的搜索，所以满足组合的大小关系要求中的大的序列优先考虑为答案）
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,k,p,maxfacsum=-1;
vector<int> v,ans,tempans;
void init();
void dfs(int index,int tempsum,int tempk,int facsum);
int main(void)
{
#ifdef ONLINE_JUDGE
#else
freopen("1.txt","r",stdin);
#endif
scanf("%d%d%d",&n,&k,&p); //输入
init(); //初始化1~i的p次方数组
tempans.resize(k); //答案数组大小初始化为k
dfs(v.size()-1,0,0,0); //dfs求解，从最大的p次方项开始，因此第一个参数为v.size-1
if(maxfacsum==-1){ //如果没有这样的解，则maxfacsum不变
puts("Impossible");
}
else{ //否则输出ans中的结果
printf("%d = ",n);
for(int i=0;i<ans.size();i++){
if(i) printf(" + ");
printf("%d^%d",ans[i],p);
}
}
return 0;
}
void init() //初始化1~i的p次方数组
{
int i=1;
v.push_back(0); //下标0位置的占位
while(1){
int temp=pow(i,p);
if(temp>n) //分解的每一个p次方项需要小于n，故以n为界进行初始化
break;
v.push_back(temp); //讲相应的p次方存入数组中
i++;
}
}
//index 为p次方数组的下标，也就代表了分解的一项的因子
//tempsum为当前求解的的因子p次方的总和，tempk为当前求解的个数，facsun为因子总和
void dfs(int index,int tempsum,int tempk,int facsum)
{
if(tempk==k){ //递归边界，得到k个因子
if(tempsum==n&&facsum>maxfacsum){ //如果满足分解要求，则保留因子和最大的结果
ans=tempans; //保存结果
maxfacsum=facsum; //更新因子最大和的数值
}
return ; //该层递归结束
}
while(index>=1){
if(tempsum+v[index]<=n){ //有于因子可以重复，故当循环选择当前的因子，直至不满足要求
tempans[tempk]=index; //想临时结果数组中存放一个p次方项
dfs(index,tempsum+v[index],tempk+1,facsum+index);
}
index--; // 不满足要求时，从大到小选择下一个因子
}
}1104
样例
输入:
4
0.1 0.2 0.3 0.4输出:
5.00思路和坑点
0.1
0.1 0.2
0.1 0.2 0.3
0.1 0.2 0.3 0.4
0.2
0.2 0.3
0.2 0.3 0.4
0.3
0.3 0.4此题需要进行观察，总结归纳便可以得到计算的规律。如果保存序列的下标从0开始，则对于第i个数字来说，首先考虑以第i个数开头的序列，这和第i个数后边的数字个数有关，显然以第i个数开头的序列有n-i个。然后考虑一共有多少个以i开头的序列组（单独开头的序列和包含的序列），这和i前边有多少个数字有关，显然一共有i+1组，故每一个数字出现的次数为（n-i）*（i+1）。由此，读入每一个数次计算并累加即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
long double sum=0;
cin>>n;
for(int i=0;i<n;i++){
long double temp;
cin>>temp;
sum+=temp*(n-i)*(i+1); //如果下标从0开始，对于第i个数，出现的次数为（n-i）*（i+1）次
}
printf("%.2llf",sum);
return 0;
}1105
样例
输入:
12
37 76 20 98 76 42 53 95 60 81 58 93输出:
98 95 93
42 37 81
53 20 76
58 60 76思路和坑点
按照从大到小的方法，以螺旋矩阵的格式输出数组。首先需要确定螺旋矩阵的规模m*n，由于满足m>=n且m和n尽可能的接近，所以从n的开方考虑，m和n必在其开方数值的两侧。
然后使用快速排序对数组进行排序。按照螺旋矩阵输出时，每次填充一层，不妨从外到内依次编号，从0层开始，也对应了每一层开始时的位置。每次按照先上方从左到右，右侧从上到下，下方从右到左，左侧从下到上的顺序进行填充，使用r，l记录每一个元素在矩阵中的位置，每层填充完毕后矩阵规模减小一层。并且需要检查是否在某行填充完毕后整个矩阵已经成型的情况，因为可能内部中心只有一层。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int N;
cin>>N;
vector<int> v(N);
for(int i=0;i<N;i++){
cin>>v[i];
}
int m,n;
for(int i=sqrt((float)N);i>=1;i--){ //m,n一定是分布在n开方附近的两个数，且m>=n
if(N%i==0){
m=N/i;n=i;break; //如果找到一个满足的矩阵大小规模，结束循环
}
}
sort(v.begin(),v.end()); //排序
int size=v.size();
int index=size-1;
vector<vector<int> > vc(m,vector<int> (n)); //创建一个二维数组
int Mt=m,Nt=n,cnt=0; //Mt，Nt表示内部小矩阵的规模，cnt是计数器，一旦装填完毕就结束循环
for(int i=0;;i++,Mt--,Nt--){ //没填满一个外层，矩阵规模减小，i表示当前层数，起始为0
int r,l; //r，l表示每次填充的坐标，r表示行，l表示列
for(r=i,l=i;l<Nt;l++){ //上方从左到右按行填充，l递增
vc[r][l]=v[index--];cnt++;
}
if(cnt==size) break;
for(l--,r++;r<Mt;r++){ //右侧按照列填充，需要将上一轮l循环边界多加的1减去，然后r递减
vc[r][l]=v[index--];cnt++;
}
if(cnt==size) break;
for(l--,r--;l>=i;l--){ //下方按行从右往左填充
vc[r][l]=v[index--];cnt++;
}
if(cnt==size) break;
for(l++,r--;r>=i+1;r--){ //左侧从下往上填充
vc[r][l]=v[index--];cnt++;
}
if(cnt==size) break; //如果有任何一次填充过程中，元素全部装填完毕则结束循环
}
for(int i=0;i<m;i++) //输出矩阵结果
for(int j=0;j<n;j++){
if(j) putchar(' ');
cout<<vc[i][j];
if(j==n-1)
cout<<'\n';
}
return 0;
}1106
样例
输入:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0输出:
1.8362 2思路和坑点
树的遍历，为了得到最低的加个，也就意味着零售商所在的层数最低，因此使用层序遍历，查找并统计层数最小的零售商所在的层数，并统计个数，如果不习惯使用变量来控制层数，可以直接在结点内部定义layer成员记录所在的层数。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node{ //多叉树结点
int layer; //记录所在的层数
bool tag; //零售商标记 ，默认都是零售商 ,如果有孩子则修改为false
vector<int> child;
node(){
tag=true;
}
}Node;
Node T[MAXN];
int n;
double p,r; //价格p和增值比例r
int main(){
scanf("%d%lf%lf",&n,&p,&r);
if(n==1){ //特判，只有一个的情况
printf("%.4f 1",p);
return 0;
}
for(int i=0;i<n;i++){ //读入数据并建树
int num;
scanf("%d",&num);
if(num){
for(int j=0;j<num;j++){
int temp;
scanf("%d",&temp);
T[i].child.push_back(temp);
T[i].tag=false; //如果有孩子，则修改标记不是零售商
}
}
}
int minlayer=MAXN; //用于记录叶子结点（零售商）所在的最小层数
int cnt=1; //记录所求零售商的个数
queue<int> q;
q.push(0);
T[0].layer=0;
while(!q.empty()){ //层序遍历
int now=q.front();
q.pop();
for(int i=0;i<T[now].child.size();i++){
int k=T[now].child[i];
T[k].layer=T[now].layer+1; //当前结点的孩子所在的层数为当前结点的层数+1
q.push(k);
}
if(T[now].tag==true){ //如果是零售商
if(T[now].layer<minlayer){ //如果有更小的层数的cnt重置为1
minlayer=T[now].layer;
cnt=1;
}
else if(T[now].layer==minlayer) //如果于最小的层数相同，cnt加一
cnt++;
}
}
printf("%.4f %d",p*pow(1.0+r/100,minlayer),cnt);
return 0;
}1107
样例
输入:
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4输出:
3
4 3 1思路和坑点
使用并查集统计不同的社团。对于每一个爱好，假设把数据中的第一个认为是该社团的代表，每次读取数据时，将相同爱好的人合并到同一个并查集（这里并查集的根指向一个负数——其绝对值代表该并查集的元素个数），最后遍历并查集，统计并查集的个数和人数，最后输出结果。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1003
int n;
vector<int> hobby(MAXN); //爱好数组，记录一个喜欢i的人的编号，作为该集团的根
vector<int> v(MAXN); //并查集 ，初始化为-1
int findfather(int a); //查询所属并查集的根结点
void Union(int a,int b); //合并两个并查集（由于此题规模比较小，可以不考虑合并时的大小）
int main(){
fill(hobby.begin(),hobby.end(),-1); //初始化hobby数组为-1，表示所有的爱好暂时都没有人
fill(v.begin(),v.end(),-1); //并查集初始化为-1，表示每一个元素单独构成一个并查集，其中只有自己一个元素
scanf("%d",&n);
for(int i=1;i<=n;i++){ //读入第i个人的爱好
int num;
scanf("%d:",&num); //第i个人的爱好数量
for(int j=0;j<num;j++){
int h;
scanf("%d",&h);
if(hobby[h]==-1){ //如果是第一个喜欢h活动的人，更新hobby数组，即等同于将这个人作为hobby[h]社团的社长
hobby[h]=i;
}
else
Union(i,findfather(hobby[h])); //否则把i号人合并进入h爱好的社群
}
}
vector<int> out; //out用于输出结果
for(int i=1;i<=n;i++){
if(v[i]<0){ //如果i是并查集的根则进行统计
out.push_back(v[i]);
}
}
sort(out.begin(),out.end()); //对结果进行排序，由于并查集的根指向负数（其绝对值表示并查集元素个数），从小到大，也就是人数从大到小排序
cout<<out.size()<<'\n'; //输出社团个数
for(int i=0;i<out.size();i++){
if(i) putchar(' ');
printf("%d",-out[i]); //输出每个社团的人数
}
return 0;
}
int findfather(int a)
{
while(v[a]>0){ //并查集查找根，其中根指向一个负值
a=v[a];
}
return a;
}
void Union(int a,int b) //合并两个并查集
{
int fa=findfather(a); //先要找到两个并查集的根
int fb=findfather(b);
if(fa!=fb){ //如果两个元素不再同一个并查集中，则合并两个并查集
v[fa]+=v[fb]; //可以考虑将小的并查集并入大的并查集中，以减小并查集规模，加快查询速度
v[fb]=fa;
}
}1108
样例
样例1
输入:
7
5 -3.2 aaa 9999 2.3.4 7.123 2.35输出:
ERROR: aaa is not a legal number
ERROR: 9999 is not a legal number
ERROR: 2.3.4 is not a legal number
ERROR: 7.123 is not a legal number
The average of 3 numbers is 1.38样例2
输入:
2
aaa -9999输出:
ERROR: aaa is not a legal number
ERROR: -9999 is not a legal number
The average of 0 numbers is Undefined思路和坑点
思路：
由于给的输入不仅包含纯数字，还包含字符，所以使用字符串进行存储和处理。主要的处理过程为：每次读入一个字符串，然后对字符串进行判定，看是否满足合法性的要求，不合法数字进行错误提示输出，合法的数字进行统计和累加，需要统计的原因是因为涉及到计算平均值的时候数字个数的计算，按照题目要求需要特判。
坑点：
对于数字合法性的判定有以下的标准：
1.首先必须是数字。
2.不多于两个小数位。可以没有小数位，但是如果有小数位，必须不多于两位。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool Isreal(char *s);
int main(){
double sum=0;
int cnt=0,n;
char temp[50]; //使用字符串读入每一个数据
scanf("%d",&n);
for(int i=0;i<n;i++){ //依次读入n个数据，然会对每一个数据进行判断
scanf("%s",temp);
if(Isreal(temp)){ //如果是一个合法输入，转化为浮点数然后进行累加并计数
double num;
sscanf(temp,"%lf",&num);
sum+=num;
cnt++;
}
else //不合法数字输出不合法提示
printf("ERROR: %s is not a legal number\n",temp);
}
if(cnt==1) //合法数字的单复数处理
printf("The average of 1 number is ");
else
printf("The average of %d numbers is ",cnt);
if(cnt==0) //平均数计算中的除0处理
printf("Undefined");
else
printf("%.2f",sum/cnt);
return 0;
}
bool Isreal(char *s) //判断输入字符串合法性的函数，合法输入位-1000到1000（闭区间）的不多于两位小数的数字
{
double num;
int point=0;
for(int i=0;s[i]!='\0';i++){ //统计小数点个数
if(s[i]=='.')
point++;
}
if(point>1) //如果小数点个数大于1，显然不是一个合法输入
return false;
if(sscanf(s,"%lf",&num)==1){ //读取检测，如果成功读取到一个数字
if(num>=-1000&&num<=1000){ //检验浮点数的范围
if(point==1&&strrchr(s,'\0')-strrchr(s,'.')>3)
return false; //如果有是一个浮点形式（即有一个小数点），对小数点的位数进行判断
else return true;
}
else return false; //如果不满足数字的区间范围
}
else
return false; //如果不是数字
}1109
样例
输入:
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159输出:
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John思路和坑点
思路：
显然这里需要对学生进行排序，根据排序结果进行位置的安排。第一步需要确定每一排的人数，因为剩余的直接都放在最后一排。假如我们以摄影师的角度看待学生位置，先放中间，然后再放摄影师角度的左边，再放摄影师角度的右边，直到这一排的学生放置满员。这里给出的思路是使用双指针，先放中间位置，然后依次放两次，判断边界就是左侧放置完毕，因为按照题目给出的条件，摄影师角度的左侧人数一定小于大于等于右侧，所以只需要判断左侧即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct student{ //学生信息结构体，名字和身高
string name;
int high;
}STU;
bool cmp(STU &a,STU &b){ //对学生的排序函数，先根据身高从高到低排序，再根据名字字典序排序
if(a.high!=b.high) return a.high>b.high;
else return a.name<b.name;
}
int main(){
int N,K;
scanf("%d %d",&N,&K);
STU DATA[N];
for(int i=0;i<N;i++) //读入数据
cin>>DATA[i].name>>DATA[i].high;
sort(DATA,DATA+N,cmp); //按照身高从高到低排序，同身高按照名字字典序排列
vector< vector<string> > out(K); //输出的二维数组
int num=N/K; //计算每一排人数
for(int i=0;i<K;i++){ //初始化每一排数组大小
if(i==0) out[i].resize(N-(K-1)*num);//如果有剩余放在最后一排
else out[i].resize(num);
}
num=0; //遍历学生数组的指针
for(int i=0;i<K;i++){
int cnt=out[i].size(); //获取每一排人数
int mid=cnt/2; //计算中间位置，题目中从1开始，如果这里用下标表示，则恰好不用+1
out[i][mid]=DATA[num++].name; //放置中间位置
int l=mid,r=mid; //左右两侧的位置指针，初始化为中间位置
while(1){
l--,r++;
if(l>=0) out[i][l]=DATA[num++].name; //在合法范围内放置，先放置摄影师视角的左侧
if(r<cnt)out[i][r]=DATA[num++].name; //再放置摄影师视角的右侧
if(l<0) break; //显然左侧的人数大于等于右侧（以摄影师视角的左右侧），所以只判定左侧到达边界说明这一排站位结束
}
}
for(int i=0;i<K;i++){ //输出结果并控制格式
for(int j=0;j<out[i].size();j++){
if(j) putchar(' ');
cout<<out[i][j];
}
putchar('\n');
}
return 0;
}1110
样例
样例1
输入:
9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -输出:
YES 8样例2
输入:
8
- -
4 5
0 6
- -
2 3
- 7
- -
- -输出:
NO 1思路和坑点
思路：
需要处理的有三个点：
1.需要找出树的根节点，这里使用标记检测的方法，如果某个节点有父亲节点则一定不是根，则最后剩下的那个节点便是根节点
2.需要判定是不是完全二叉树，并跟踪最后一个节点。这里使用静态树表示，所以需要适应这种写法和表示，使用-1表示空指针。采用层序遍历的方法进行判定，将所有包含空指针在内的节点都入队，如果某一次出队时遇到了空指针，则如果队列中剩余的都是空节点说明时完全二叉树，否则不是，遍历过程中跟踪最后一个非空节点，用于输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 25 //树的节点个数上限
typedef struct node{ //树的结点定义，这里由于采用的静态数组的表示方法，所以空指针使用-1表示
int l=-1,r=-1;
}Node;
vector<Node> v(MAXN);
bool isroot[MAXN]; //记录是否是根
void Judge(int root); //判断是不是完全二叉树的函数
int main(){
fill(isroot,isroot+MAXN,true); //默认所有结点都是根，如果有孩子，则修改标记
int n;
scanf("%d",&n);
if(n==1){ //特判
printf("YES 0");
return 0;
}
for(int i=0;i<n;i++){
string a,b;
cin>>a>>b;
if(a!="-"){ //如果a不是空，则转化为数字temp
int temp;
sscanf(a.c_str(),"%d",&temp);
isroot[temp]=false; //显然a代表的结点有父结点，所以不会是根，将根标记置为false
v[i].l=temp; //记录节点关系
}
if(b!="-"){ //对b也做类似的处理
int temp;
sscanf(b.c_str(),"%d",&temp);
isroot[temp]=false;
v[i].r=temp;
}
}
int root; //查找并记录根节点，一定再0~N-1范围内
for(root=0;root<n;root++)
if(isroot[root]==true)break;
Judge(root);
return 0;
}
void Judge(int root)
{
int pre; //用于记录最后一个节点
queue<int> q; //层次遍历的方法入队，包括空结点
q.push(root);
while(!q.empty()){
int now=q.front();
q.pop();
if(now!=-1){ //如果不是空结点，左右孩子入队
q.push(v[now].l);
q.push(v[now].r);
}
else{ // 如果遇到空结点，遍历队列如果后边还有非空结点则不是完全二叉树
while(!q.empty()){
int top=q.front();
q.pop();
if(top!=-1){
printf("NO %d",root); //如果不是，则输出NO和根节点的位置
return;
}
}
}
if(now!=-1) pre=now; //更新pre
}
printf("YES %d",pre); //YES的情况下输出最后一个节点
}1111
样例
样例1
输入:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5输出:
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5样例2
输入:
7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5输出:
Distance = 3; Time = 4: 3 -> 2 -> 5思路和坑点
思路:
使用邻接表存储图，对于第一组输出，使用迪杰斯特拉的双参数优化，一次获得路径，保证最短路径中花费最少的一个结果；对于第二组输出，使用迪杰斯特拉的一个参数优化+dfs对路径进行二次筛选的方法获得。难度不在思路上，而在于实现上，能够熟练运用最短路径算法即可，此题只是内容较多，参数和输出描述比较复杂，因此难度在于理解题目要求和代码实现上。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 502
#define INF 0x3fffffff
typedef struct edg{ //使用邻接表表示图，这里定义邻接表的边表节点，v表示边链接的另一个节点，l表示边的花费，t表示时间花费
int v,l,t;
edg(int _v,int _l,int _t):v(_v),l(_l),t(_t){} //边表的初始化函数
}EDG;
int n,m,st,ed; //顶点个数 ，边个数，起始顶点和结束顶点
vector<EDG> Adj[MAXN]; //邻接表储存图
bool vis[MAXN]; //访问标记
int dis[MAXN]; //最短距离
int cost[MAXN]; //最短时间花费
vector<int> pre[MAXN]; //前驱顶点数组
vector<int> spath,tpath; //最短路径，和临时路径
vector<int> fpath(MAXN); //最快路径中满足经过最少节点的路径
void dfs(int v); //最快路径的dfs函数
void Df(); //最快的dijkstra，单尺度优化
void Ds(); //最短距离的dijkstra ，双尺度优化，距离最短且时间花费最少，即第一个输出的要求
int main(){
scanf("%d%d",&n,&m); //读入数据并构建邻接表
for(int i=0;i<m;i++){
int v1,v2,tag,len,time; //v1，v2表示两个顶点，tag表示两个节点之间的路径是否为单向（oneway），len表示距离花费，time表示时间花费
scanf("%d%d%d%d%d",&v1,&v2,&tag,&len,&time);
if(tag!=1){ //如果不是单向，则双向记录
Adj[v1].push_back(edg(v2,len,time));
Adj[v2].push_back(edg(v1,len,time));
}
else{ //如果是单向街道，记录单向
Adj[v1].push_back(edg(v2,len,time));
}
}
scanf("%d%d",&st,&ed); //读入起点和终点
Ds(); //求最短
Df(); //求最快
dfs(ed); //求最快的最优解
if(fpath==spath){ //如果路径相同
printf("Distance = %d; Time = %d: ",dis[ed],cost[ed]);
for(int i=spath.size()-1;i>=0;i--){
if(i!=spath.size()-1) printf(" -> ");
printf("%d",spath[i]);
}
}
else{ //如果路径不同
printf("Distance = %d: ",dis[ed]);
for(int i=spath.size()-1;i>=0;i--){
if(i!=spath.size()-1) printf(" -> ");
printf("%d",spath[i]);
}
putchar('\n');
printf("Time = %d: ",cost[ed]);
for(int i=fpath.size()-1;i>=0;i--){
if(i!=fpath.size()-1) printf(" -> ");
printf("%d",fpath[i]);
}
}
return 0;
}
void Ds()
{
fill(dis,dis+MAXN,INF);
fill(cost,cost+MAXN,INF);
fill(vis,vis+MAXN,false);
cost[st]=0;
dis[st]=0;
for(int i=0;i<n;i++){
int u=-1,MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&dis[j]<MIN){
u=j;
MIN=dis[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<Adj[u].size();v++){
int k=Adj[u][v].v;
if(vis[k]==false){
if(dis[u]+Adj[u][v].l<dis[k]){
dis[k]=dis[u]+Adj[u][v].l;
cost[k]=cost[u]+Adj[u][v].t;
pre[k].clear();
pre[k].push_back(u);
}
else if(dis[u]+Adj[u][v].l==dis[k]&&cost[u]+Adj[u][v].t<cost[k]){
cost[k]=cost[u]+Adj[u][v].t;
pre[k].clear();
pre[k].push_back(u);
}
}
}
}
int index=ed;
while(index!=st){
spath.push_back(index);
index=pre[index][0];
}
spath.push_back(st);
}
void Df()
{
fill(cost,cost+MAXN,INF);
fill(vis,vis+MAXN,false);
cost[st]=0;
for(int i=0;i<n;i++){
int u=-1,MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&cost[j]<MIN){
u=j;
MIN=cost[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<Adj[u].size();v++){
int k=Adj[u][v].v;
if(vis[k]==false){
if(cost[u]+Adj[u][v].t<cost[k]){
cost[k]=cost[u]+Adj[u][v].t;
pre[k].clear();
pre[k].push_back(u);
}
else if(cost[u]+Adj[u][v].t==cost[k]){
pre[k].push_back(u);
}
}
}
}
}
void dfs(int v)
{
if(v==st){
tpath.push_back(st);
if(tpath.size()<fpath.size())
fpath=tpath;
tpath.pop_back();
return;
}
tpath.push_back(v);
for(int i=0;i<pre[v].size();i++){
dfs(pre[v][i]);
}
tpath.pop_back();
}1112
样例
输入:
3
caseee1__thiiis_iiisss_a_teeeeeest输出:
ei
case1__this_isss_a_teest补充样例
输入:
3
caseeeaaa1__thiiisa_iiisss_a_aaaaaateeeeeest输出:
ei
caseaaa1__thisa_isss_a_aaaaaateest思路和坑点
思路:
这个题目的问题在于如何准确辨别坏键，即理解坏键的情况，根据示例可知必须是每次都出现了连续k个或者k的整数倍个字符的才算做是坏键，因此需要对连续出现的字符进行计数并进行判定即可。因此需要计数器统计连续字符，还需要有一个Table来标记坏键，这里可能出现误判的情况，比如序列的前部分和后部分都出现了k整数倍的字符串，但是中间出现了非k整数倍的情况，说明这个键是好的（补充样例中的字符a就不是坏键，理解起来好理解，但是程序来判定上需要注意逻辑实现的时候不要漏掉），那么此处需要注意好键的标记优先级高于坏键，具体可以参考代码实现部分的注释说明。
坑点：
主要在于坏键和连续出现的好键之间的区分和判定。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
map<char,int> mp; //标识键是否损坏 ,1表示正常，2表示坏键 （最好不使用true和false，因为判定时，不存在的map键值为0，即false，影响判定）
string wrong="",real="",str; //wrong存放可疑的坏键,real真正的输出字符串,str用于存放读入的字符串
cin>>n>>str;
str+="E"; //为了结尾处的判定能够写在循环内，在末尾加上一个不属于统计范围的字符
int cnt=1; //统计重复次数，初始化为1；
for(int i=1;i<str.size();i++){ //从第二个字符开始，第一个字符默认统计在内，个数为cnt的初始值1
if(str[i]==str[i-1]) //如果与前一个字符相同，表示连续，cnt++
cnt++;
else{ //否则判定是否是坏键
if(cnt%n!=0) //如果不是整数倍，则证明是好键
mp[str[i-1]]=1; //好键可以覆盖误判的坏键标记，如果前面出现过一次整数倍，后边出现了不是整数倍，说明前边坏键判定不正确，需要修正
else{
if(mp.find(str[i-1])==mp.end())
wrong.push_back(str[i-1]); //当前的键被怀疑是坏键，则加入可疑坏键序列。其中可以坏键不要重复添加
if(mp[str[i-1]]!=1)
mp[str[i-1]]=2; //确定时坏键的时候需要优先判定是不是好键，如果已经提前被标记为好键，则此时进入坏键判定为后边整数倍序列误判所致
}
cnt=1; //更新计数器
}
}
cnt=1; //最终完全确定坏键以后，遍历统计一遍，对于重复的字符，如果是正常重复就输出cnt个，否则输出cnt/n个
for(int i=1;i<str.size();i++){
if(str[i]==str[i-1]) //连续部分进行计数
cnt++;
else{
if(mp[str[i-1]]==1) //如果是好键，正常重复cnt个
for(int j=0;j<cnt;j++)
real+=str[i-1];
else
for(int j=0;j<cnt/n;j++) //如果是坏键，需要除以卡键次数
real+=str[i-1];
cnt=1; //更新计数器
}
}
for(int i=0;i<wrong.size();i++){ //输出坏键
if(mp[wrong[i]]==2)
putchar(wrong[i]);
}
cout<<'\n'<<real; //输出真实的字符串
return 0;
}1113
样例
样例1
输入:
10
23 8 10 99 46 2333 46 1 666 555输出:
0 3611样例2
输入:
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85输出:
1 9359思路和坑点
思路:
此题其实就是对数组进行对半划分，小的部分在一侧，大的部分在另一侧，如果是偶数个元素，则对半划分，如果是奇数个元素，将位于中间的那个元素归在数值较大的部分。最后，对两部分进行累加求和并输出结果即可。可以直接对整个数组进行排序然后统计，也可以采用快排划分的思路进行划分（不需要全部排序），只要中间位置的元素划分划分，就可以满足题目要求的划分条件。
AC代码（暴力解法）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
vector<int> v(n);
for(int i=0;i<n;i++) //读入数据
scanf("%d",&v[i]);
//根据题意确定n1和n2，
int n1=n/2; //由题意可知，n1、n2需要尽可能的个数上接近；S1和S2的插值需要尽可能的大，所以也就是排序后的前一半和后一半
int n2=n-n1; //由于元素个数奇数个和偶数个的情况不同，偶数个则对半分，奇数个（从小到大排序），后半部分比前部分多一个元素
sort(v.begin(),v.end()); //从小到大排序
int s1=0,s2=0; //统计两部分的和
for(int i=0;i<n1;i++) s1+=v[i];
for(int i=n1;i<n;i++) s2+=v[i];
printf("%d %d",n2-n1,s2-s1); //按照要求进行输出
return 0;
}AC代码（划分解法）
其他同学提供的划分算法，顺利AC，划分方法的区别在此不做说明。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,n1,n2;
scanf("%d",&n);
int *v=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++) //读入数据
scanf("%d",&v[i]);
int low_tmp=0,high_tmp=n,tmp;
while(1){ //快排划分方法进行划分
int low=low_tmp,high=high_tmp;
tmp=v[low];
while(1){
while(v[--high]>tmp) if(high==low_tmp) break;
while(v[++low]<tmp) if(low==high_tmp) break;
if(low>=high) break;
swap(v[low],v[high]);
}
swap(v[low_tmp],v[high]);
if(high==n/2) break; //如果完成划分则停止
else if(high<n/2) low_tmp=++high;
else high_tmp=high;
}
n1=n/2;
n2=n-n1; //由于元素个数奇数个和偶数个的情况不同，偶数个则对半分，奇数个（从小到大排序），后半部分比前部分多一个元素
int s1=0,s2=0; //统计两部分的和
for(int i=0;i<n1;i++) s1+=v[i];
for(int i=n1;i<n;i++) s2+=v[i];
printf("%d %d",n2-n1,s2-s1); //按照要求进行输出
return 0;
}未AC代码（划分解法）
此方法测试点3超时，算法逻辑没有错误，但是应对超长有序（和划分的排序规则相同的有序）序列时耗时过长导致程序超时。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,n1,n2;
scanf("%d",&n);
int *v=(int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++) //读入数据
scanf("%d",&v[i]);
int low=0,high=n-1,tmp;
int low_tmp=low,high_tmp=high; //更新记录上一次划分的边界
while(1){ //快排划分方法进行划分
tmp=v[low];
while(low<high){
while(low<high&&v[high]>=tmp) high--;
v[low]=v[high];
while(low<high&&v[low]<=tmp) low++;
v[high]=v[low];
}
v[low]=tmp;
if(low==n/2) break; //如果完成划分则停止，如果未完成则继续对包含了中间值的哪个部分进行划分
else if(low<n/2) { low_tmp=++low,high=high_tmp; }
else { low=low_tmp,high_tmp=--high; }
}
n1=n/2;
n2=n-n1; //由于元素个数奇数个和偶数个的情况不同，偶数个则对半分，奇数个（从小到大排序），后半部分比前部分多一个元素
int s1=0,s2=0; //统计两部分的和
for(int i=0;i<n1;i++) s1+=v[i];
for(int i=n1;i<n;i++) s2+=v[i];
printf("%d %d",n2-n1,s2-s1); //按照要求进行输出
return 0;
}
/*
处理数据超时的情况：超大有序序列，在划分是时间花费比较多，比如
100000
全是1
*/1114
样例
输入:
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100输出:
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000思路和坑点
思路：
此题信息量较大，有一定的的阅读理解难度。题目的输入首先是正整数N，表示将要提供的人员数量。接下里N行，每行包含一个人的个人信息，其中依次包括个人身份编号、父亲编号、母亲编号、孩子个数、对应每个孩子的编号，个人房产套数，个人房产总面积。题目要求的输出结果是，输出家族个数（直系或者旁系的人都算为一个家族，也就是需要合并得到家族并查集），然后每行输出一组家族信息，包括最小成员的编号，家族总人数，平均房产套数，平均房产面积，要求输出的平均值精确到三位小数。
主要是需要处理的信息比较多，这里给出的思路是，凡是有关系的人如果还未合并都进行合并统计，统计包括：最小编号、房产等信息，同时还要通过数组保存并查集信息。具体实现见代码。
坑点：
注意每个信息的含义，以及输出要求。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct data{
int id,fid,mid,num,area; //记录每一条个人信息，其中包括个人账号id，父母的id，房产套数num，房产面积area
vector<int> cid; //孩子数组
int minid; //minid用于存放此人所在家族中最小的id号
}Data;
typedef struct node{
int id,people; //最小id 成员个数
double num,area; //排序和输出的数据
bool flag; //是否是根 标记 ，初始化为否，如果有家组信息，则改为true
node(){
id=10000; flag=false; //id初始化为10000也就是最大值，然后和家族中每一条记录比较，如果有更小，则更新
}
}Node;
Data all[1005]; //数据数组
Node ans[10000]; //答案数组，因为个人编号4位，所以代表可能存在的任务有10000个
int father[10000]; //并查集father数组，初始化为-1
int find(int x){ //查找所在编号x所在并查集的父节点
while(father[x]>=0){
x=father[x];
}
return x;
}
void Union(int a,int b){ //并查集的合并函数
int fa=find(a); //找到两个人所在家庭的根
int fb=find(b);
if(fa!=fb){ //如果两人不在同一个家族则进行合并，为了减小并查集路径，将小的合并在大的上边
if(father[fa]>father[fb]){
father[fb]+=father[fa];
father[fa]=fb;
}
else{
father[fa]+=father[fb];
father[fb]=fa;
}
}
}
bool cmp(Node a,Node b){ //排序函数
if(a.area!=b.area) return a.area>b.area;
else return a.id<b.id;
}
int main(){
int n,k,cnt=0; //n表示数据个数，k表示每一个人的孩子个数，cnt
scanf("%d",&n);
//读入数据并构建并查集关系
fill(father,father+10000,-1); //初始化并查集
for(int i=0;i<n;i++){ //读入数据
scanf("%d%d%d%d",&all[i].id,&all[i].fid,&all[i].mid,&k);
all[i].minid=all[i].id; //暂时初始化每个人所在家庭中最小的id是自己
if(all[i].fid!=-1){ //如果有父亲，就把自己和父亲所在家族合并
Union(all[i].id,all[i].fid);
if(all[i].fid<all[i].minid) //比较所有亲属的id，将自己的minid更新到最小，凡是遇到亲属就更新，这样每个人都能保证minid是家族中最小的
all[i].minid=all[i].fid; //这里更具父亲的id，更新minid
}
if(all[i].mid!=-1){ //对母亲采取和父亲同样的处理办法
Union(all[i].id,all[i].mid);
if(all[i].mid<all[i].minid)
all[i].minid=all[i].mid;
}
for(int j=0;j<k;j++){ //对儿子也采取和父亲同样的处理办法
int temp;
scanf("%d",&temp); //儿子需要记录在数组中
all[i].cid.push_back(temp);
Union(temp,all[i].id);
if(temp<all[i].minid)
all[i].minid=temp;
}
scanf("%d%d",&all[i].num,&all[i].area);
}
//数据统计计算
for(int i=0;i<n;i++){ //将每一个人的房产数据统计进入他所在的家庭组
int id=find(all[i].id); //找到所在家族（并查集）的根
if(all[i].minid<ans[id].id) //用自己小家族的minid更新整个家族的minid
ans[id].id=all[i].minid;
ans[id].num+=all[i].num; //累加房产套数
ans[id].area+=all[i].area; //累加房产面积
ans[id].flag=true; //更新标记
}
for(int i=0;i<10000;i++){ //遍历答案数组并计算最终的数值
if(ans[i].flag){ //对于是家族根的更新相关数据
cnt++; //统计家族个数
ans[i].people=-father[i];//统计家族人数和平均房产数量、平均房产面积
ans[i].num=(double) (ans[i].num*1.0/ans[i].people);
ans[i].area=(double)(ans[i].area*1.0/ans[i].people);
}
}
sort(ans,ans+10000,cmp); //按照规则进行排序
printf("%d\n",cnt);
for(int i=0;i<cnt;i++){ //输出最后的结果
printf("%04d %d %.3f %.3f\n",ans[i].id,ans[i].people,ans[i].num,ans[i].area);
}
return 0;
}1115
样例
输入:
9
25 30 42 16 20 20 35 -5 28输出:
2 + 4 = 6思路和坑点
思路：
主要的思路是先根据给出的序列建树，然后层序遍历统计每层节点个数和树的高度，这里提供两种思路解决：①为节点添加一个层数的成员变量，然后初始化根以后遍历过程中，每个节点根据父节点的层数更新自己所在的层数。②使用双指针跟踪每一层的最后一个节点，每层进行计数，每层统计结束后，更新计数数组和计数器以及层数。
坑点：
注意如何处理层数为1的情况，如果默认根为0层，则一个节点的时候需要特判。或者，根为1层，但是注意初始化每层节点个数的计数为0。
AC代码（节点存放层数信息）
#include<bits/stdc++.h>
using namespace std;
int layercnt[1003]={0}; //存放i层的个数，初始化为0，这样当最大高度为1时倒数第二层不会数组越界
typedef struct node{ //二叉树结点
int data;
int layer; //结点所在层
struct node *left,*right; //节点左右指针
}Node,*Tree;
void Insert(Node* &root,int x); //将节点插入二叉树中
int layorder(Node *root); //层序遍历获取树的高度
int main(){
int n;
Tree root=NULL;
scanf("%d",&n);
for(int i=0;i<n;i++){ //读取一个数据插入树中
int temp;
scanf("%d",&temp);
Insert(root,temp);
}
int ml=layorder(root); //层序遍历获取树高，并按照要求输出
printf("%d + %d = %d",layercnt[ml],layercnt[ml-1],layercnt[ml]+layercnt[ml-1]);
return 0;
}
void Insert(Node* &root,int x){ //插入函数
if(root==NULL){ //空树直接初始化为根即可
root=new Node;
root->data=x;
return;
}
if(x<=root->data){ //根据题目要求递归调用插入
Insert(root->left,x);
}
else if(x>root->data){
Insert(root->right,x);
}
}
int layorder(Node *root){ //层序遍历算法
int ret=0; //返回值，表示树的最大高度，默认高度从1开始，初始化为0
queue<Node *> q;
q.push(root);
root->layer=1; //初始化根节点高度
while(!q.empty()){
Node *now=q.front();
q.pop();
if(now->left!=NULL){
now->left->layer=now->layer+1;
q.push(now->left);
}
if(now->right!=NULL){
now->right->layer=now->layer+1;
q.push(now->right);
}
layercnt[now->layer]++;
ret=max(ret,now->layer);//更新高度
}
return ret;
}AC代码（使双指针标记层数增长）
#include<bits/stdc++.h>
using namespace std;
int layercnt[1003]={0}; //存放i层的个数，默认根为第一层，这样最大高度为1时，倒是第二层访问数组不会越界
typedef struct node{ //二叉树结点
int data;
struct node *left=nullptr,*right=nullptr; //节点左右指针
}Node,*Tree;
void Insert(Node* &root,int x); //将节点插入二叉树中
int layorder(Node *root); //层序遍历获取树的高度
int main(){
int n;
Tree root=NULL;
scanf("%d",&n);
if(n==1){ //特判
printf("1 + 0 = 1");return 0;
}
for(int i=0;i<n;i++){ //读取一个数据插入树中
int temp;
scanf("%d",&temp);
Insert(root,temp);
}
int ml=layorder(root); //层序遍历获取树高，并按照要求输出
printf("%d + %d = %d",layercnt[ml],layercnt[ml-1],layercnt[ml]+layercnt[ml-1]);
return 0;
}
void Insert(Node* &root,int x){ //插入函数
if(root==NULL){ //空树直接初始化为根即可
root=new Node;
root->data=x;
return;
} //根据规则插入
if(x<=root->data) Insert(root->left,x);
else Insert(root->right,x);
}
int layorder(Node *root){ //层序遍历算法
int layer=1,count=0; //层数layer,每层计数器count
Node *lastail=root,*tail=root;//lastail记录上一层的结尾，tail实时更新，一直变为本层的结尾，都初始化为根
queue<Node *> q;
q.push(root);
while(!q.empty()){
Node *now=q.front();
q.pop();
count++; //本层计数
//如果孩子不空则入队，这里tail先更新，然后顺带入队，可以写成一句，赋值时从右往左
if(now->left!=nullptr) q.push(tail=now->left);
if(now->right!=nullptr)q.push(tail=now->right);
if(now==lastail){ //如果发现上一层已经统计完
layercnt[layer++]=count;//更新计数统计，并增加层数，为下一层做准备
count=0; //重置计数器
lastail=tail; //更新lasttial为下一层的最后一个节点
}
}
return layer-1; //返回最大层数，因为最后一层统计结束后layer自动+1，所以这里要先减去
}1116
样例
输入:
6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222输出:
8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?思路和坑点
思路：
最主要的思路是需要考虑标记每个人的奖品类型，然后需要标记是否领过奖品。这里使用map进行标记每个人的奖品类型和是否领过奖品，然后按照查询结果进行输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10004
bool Prime[MAXN];
void getPrime();
int main(){
map<string,int> rank; //0为冠军奖品，1为MInions，2为ch
map<string,bool> check; //核查是否领奖
int n;
getPrime();
scanf("%d",&n);
string temp;
for(int i=1;i<=n;i++){ //读入数据并按照要求对其奖品进行标记
cin>>temp;
if(i==1)
rank[temp]=0;
else if(Prime[i])
rank[temp]=1;
else
rank[temp]=2;
}
scanf("%d",&n);
for(int i=0;i<n;i++){
cin>>temp;
cout<<temp<<": ";
if(rank.find(temp)!=rank.end()){ //如果在排名中
if(check.find(temp)==check.end()){ //如果未领奖
check[temp]=true; //标记领奖
switch(rank[temp]){ //根据奖品类型打印奖品内容
case 0 : puts("Mystery Award");break;
case 1 : puts("Minion");break;
case 2 : puts("Chocolate");break;
default :break;
}
}
else
puts("Checked"); //如果已经领过了，输出领取信息
}
else{
puts("Are you kidding?"); //如果不在排名中，输出错误信息
}
}
return 0;
}
void getPrime() //筛选法获取素数表
{
fill(Prime,Prime+MAXN,true);
Prime[0]=Prime[1]=false;
for(int i=2;i*i<=MAXN;i++){
if(Prime[i]){
for(int j=i+i;j<MAXN;j+=i){
Prime[j]=false;
}
}
}
}1117
样例
输入:
10
6 7 6 9 3 10 8 2 7 8输出:
6思路和坑点
思路:
按照题目的给定的概念先排序，然后计算出爱丁顿数。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int n,ans=0;
scanf("%d",&n);
int a[n]; //变量初始化数组需要编译器支持
for(int i=0;i<n;i++) scanf("%d",&a[i]); //读入数据
sort(a,a+n,cmp); //从大到小排序
while(ans<n&&a[ans]>ans+1) ans++; //在满足下标的范围内，统计满足的天数，为保证ans下标有效性，ans<n判定放在前边
printf("%d",ans); //由于从大到小排列，所以ans下标总共有ans+1天，所以如果有ans+1天的骑行超过ans+1，就统计计数
return 0;
}1118
样例
输入:
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7输出:
2 10
Yes
No思路和坑点
思路：
按照并查集的思路进行合并即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10004
int father[MAXN]; //并查集
bool inq[MAXN]={false}; //记录是否已被统计
void Union(int a,int b); //并查集合并
int find(int x); //查找并查集的根
int main(){
fill(father,father+MAXN,-1);//初始化并查集
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int num,first; //读入小鸟个数和第一个小鸟
scanf("%d%d",&num,&first);
inq[first]=true; //标记被统计过
for(int j=1;j<num;j++){ //读入后序小鸟编号，然后和第一支小鸟合并
int b;
scanf("%d",&b);
inq[b]=true;
Union(b,first);
}
}
int cntt=0,cntb=0; //统计树的个数，和小鸟的个数
for(int i=1;i<=10000;i++){
if(inq[i]==true){ //如果被统计在内，则计数器增加
cntb++;
if(father[i]<0) //如果某个节点的father是负值，表示这个点便是根，并查集个数增加
cntt++;
}
}
printf("%d %d\n",cntt,cntb); //按照题目要求输出结果
int k; scanf("%d",&k);
for(int i=0;i<k;i++){
int a,b;
scanf("%d%d",&a,&b);
a=find(a); b=find(b);
if(a==b) puts("Yes");
else puts("No");
}
return 0;
}
void Union(int a,int b){
int fa=find(a);
int fb=find(b);
if(fa!=fb){
if(father[fa]<father[fb]){
father[fa]+=father[fb];
father[fb]=fa;
}
else{
father[fb]+=father[fa];
father[fa]=fb;
}
}
}
int find(int x){
while(father[x]>=0){
x=father[x];
}
return x;
}1119
样例
样例1
输入:
7
1 2 3 4 6 7 5
2 6 7 4 5 3 1输出:
Yes
2 1 6 4 7 3 5样例2
输入:
4
1 2 3 4
2 4 3 1输出:
No
2 1 3 4思路和坑点
思路：
根据先序和后序建树，显然先序和后序不能唯一确定一棵二叉树，所以需要进行判定，然后输出其中可能的情况。因为当某个节点只有一棵子树的时候先序和后序不能确定这棵子树是左子树还是右子树，所以会由多种结果。我们只需要在遇到此种情况下直接修改判定标记即可。可以不用建好树之后再获取中序序列，直接通过先序和后序确定位置关系，再中序中找到位置即可，按照先序+中序建树的思路处理，稍作修改就行，具体看代码实现和注释。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 35
int n;
bool flag=true; //是否唯一确定的标记
int pre[MAXN],post[MAXN],in[MAXN]; //存放序列
void creat(int prl,int prr,int pol,int por,int st);
int find(int x); //在先序中到位置下标
int main(){
scanf("%d",&n); //读入数据
for(int i=0;i<n;i++) scanf("%d",&pre[i]);
for(int i=0;i<n;i++) scanf("%d",&post[i]);
creat(0,n-1,0,n-1,0); //得到in序列
if(flag) puts("Yes"); //判定输出
else puts("No");
for(int i=0;i<n;i++){
if(i) putchar(' ');
printf("%d",in[i]);
}
putchar('\n'); //结尾必须有回车，否则格式错误
return 0;
}
void creat(int prl,int prr,int pol,int por,int st) //递归填写in序列
{
//prl，prr分别当前子树在先序序列中的左右端点下标
//pol,por分别是当前字数在后序序列中的左右端点下标
//st表示当前子树在中序序列中的开始位置
int lnum=0,rnum=0;
if(prl>prr) return; //如果序列中没有顶点，返回
if(prl==prr) { //如果只有一个顶点，在st位置直接填写
in[st]=pre[prl];
return;
}
int k=find(post[por-1]); //后序序列的根前一位是子树的根，在此默认为右子树
//找到其在先序中的位置下标
lnum=k-prl-1; rnum=prr-k+1; // 由k计算左右子树的节点个数
if((lnum!=0&&rnum==0)||(lnum==0&&rnum!=0)){ //如果该子树只有右子树或者只有左子树，flag为否
flag=false;
}
int pos=st+lnum; //计算根结点在后序序列中的位置
in[pos]=pre[prl]; //填写根结点在后序中
creat(prl+1,prl+lnum,pol,pol+lnum-1,pos-lnum); //递归填写左右子树
creat(k,prr,por-rnum,por-1,pos+1);
}
int find(int x) //寻找x在先序中的下标位置
{
for(int i=0;i<n;i++){
if(pre[i]==x)
return i;
}
}1120
样例
输入:
8
123 899 51 998 27 33 36 12输出:
4
3 6 9 26思路和坑点
思路：
简单计算每个数字的每一位的和即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int getid(int n){ //获取数字n的id号，即把id的每一位都相加计
int ret=0;
while(n){
ret+=n%10;
n/=10;
}
return ret;
}
int main(){
map<int,bool> mp; //记录id并且按照从小到大保存id
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){ //读入数据并计算id
int temp,id;
scanf("%d",&temp);
id=getid(temp);
mp[id]=true;
}
cout<<mp.size()<<'\n'; //按照要求输出id
for(auto it=mp.begin();it!=mp.end();it++){
if(it!=mp.begin()) putchar(' ');
cout<<it->first;
}
return 0;
}
Comments | NOTHING