A-小鱼的航程

一道简单的模拟题，根据题意写循环即可。

用变量t来表示当前是星期几，然后循环n次，表示经历n天。

当t<=5时，表明当前是工作日，于是总路程sum+=250；否则，sum不改变。

一天结束后应该将t++进入下一天，但一个星期只有t天，星期天过了是星期一，所以如果t++之后t==8，应该回到星期一。

最后输出sum即为答案。

#include<bits/stdc++.h>
using namespace std;
int t,n,sum;
int main()
{
 cin>>t>>n;
 for(int i=1;i<=n;i++)
 {
   if(t<6) sum+=250;
   t++;
   if(t==8) t=1;
 }
 cout<<sum;
return 0;
}

B-A-B数对

注意到一个关键条件：数串中所有数和C均小于等于100。

所以可以用桶去保存每个数，这样我们就只需要枚举A或B，然后用桶相乘累积答案就行了，具体见代码。

#include<bits/stdc++.h>
using namespace std;
int a[110];
int main()
{
int n,c;
 cin>>n>>c;
 int t;
 for(int i=0; i<n; i++)
 {
  scanf("%d",&t);
  a[t]++;
 }
 int sum=0;
 for(int i=1; i<=100-c; i++) sum+=a[i]*a[i+c];
 cout<<sum;
 return 0;
}

C-合并果子

这道题可以用贪心来解决，每次取最小的两堆再合成即可。

关键问题在于，怎么找到最小的两堆。

排序是可行的方法，但是合成新堆之后会打乱顺序，我们不可能每次都重新排序。

这时需要一个新的数据结构来解决这个问题：堆。

在C++中，我们一般用STL里的优先队列来实现堆的功能。优先队列的定义方式如下：

priority_queue < int > q;//定义一个大根堆，即最大的元素在top的堆

大根堆表示每次取q.top()时取出的是最大的元素。

在这道题中，我们需要的是小根堆，定义方式如下：

priority_queue < int, vector<int>, greater<int> > q;

所以我们只需要一开始把所有元素放入小根堆，每次取出最小的两堆，合并后再放入小根堆，直到只剩一堆为止。

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

priority_queue < int, vector<int>, greater<int> > q;
int x;
int n;
int a[11000];
long long s=0;

int main()
{
scanf("%d",&n);
 for(int i=1;i<=n;i++)
 scanf("%d",&a[i]);
 for(int i=1;i<=n;i++) q.push(a[i]);//果子入队
 for(int i=1;i<=n-1;i++)
 {
   int t1=q.top();//取队首元素
    q.pop();//出队
   int t2=q.top();//取队首元素
    q.pop();//出队
   int t=t1+t2;
    s+=t;
    q.push(t);//入队
 }
 printf("%lld",s);
 return 0;
}

D-求先序排列

首先需要知道三种遍历方式的基本知识，如果不是很清楚的同学要先复习这部分内容。

容易知道，给你一个后序遍历，那么最后一个就是根（如ABCD，则根为D）。题目求先序，意味着要不断找根。

那么我们来看这道题（示例：中序ACGDBHZKX，后序CDGAHXKZB）

首先可找到主根B；

那么我们找到中序遍历中的B，由这种遍历的性质，可将中序遍历分为ACGD和HZKX两棵子树，

那么对应可找到后序遍历CDGA和HXKZ（从头找即可）

从而问题就变成求：

1.中序遍历ACGD，后序遍历CDGA的树 

2.中序遍历HZKX，后序遍历HXKZ的树

接着递归，按照原先方法，找到：

1.子根A，再分为两棵子树

2.子根Z，再分为两棵子树。

就这样一直递归做下去。

递归的方法为：

step1:找到根并输出

step2:将中序，后序各分为左右两棵子树；

step3:递归，重复step1,2；

具体见代码。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after)
{
 if (in.size()>0)
 {
  char ch=after[after.size()-1];
  cout<<ch;//找根输出
  int k=in.find(ch);
  beford(in.substr(0,k),after.substr(0,k));
   beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；
 }
}
int main()
{
 string inord,aftord;
 cin>>inord;
 cin>>aftord;
 beford(inord,aftord);
 cout<<endl;
return 0;
}