B.水果店

这道题没有什么技巧，只要会排序就能解决，但主要考察的是同学们的细心程度和代码能力，在此引用田泽恩的代码以供大家借鉴，希望同学们认真的慢慢将这道题打一遍，提高自己的代码能力。

#include <bits/stdc++.h>
using namespace std;
struct fruit
{
string plc,fru;
int num,f=0;
} a[101],bfore;
bool cmp(fruit b,fruit c)
{
if(b.plc!=c.plc) return b.plc<c.plc;
if(b.fru!=c.fru) return b.fru<c.fru;
return b.num>c.num;
}
int main()
{
int m;
cin>>m;
for(int i=0; i<m; i++)
{
cin>>a[i].fru>>a[i].plc>>a[i].num;
}
sort(a,a+m,cmp);
for(int i=0; i<m; i++)
{
for(int j=i+1; j<m; j++)
{
if(a[i].plc==a[j].plc&&a[i].fru==a[j].fru)
{
a[j].f=1;
a[i].num+=a[j].num;
}
else break;
}
}
bfore.f=a[0].f;
bfore.fru=a[0].fru;
bfore.num=a[0].num;
bfore.plc=a[0].plc;
cout<<a[0].plc<<endl<<" |----"<<a[0].fru<<"("<<a[0].num<<")\n";
for(int i=1; i<m; i++)
{
if(a[i].f) continue;
if(a[i].plc!=bfore.plc) cout<<a[i].plc<<endl;
cout<<" |----"<<a[i].fru<<"("<<a[i].num<<")\n";
bfore.f=a[i].f;
bfore.fru=a[i].fru;
bfore.num=a[i].num;
bfore.plc=a[i].plc;
}
return 0;
}

C.淘汰赛

这道题方法很多，可以用递归，可以用二叉树，可以用各种复杂的数据结构，但我们可以把它看做一个简单的队列问题，具体思路见代码：

#include<iostream>
#include<queue>
#include<map>
using namespace std;
int main(){
int n;
queue<pair<int,int> > q; //pair是stl中的数据结构，这里用first表示国家号，second表示国家实力
cin>>n;
n=1<<n; //位运算，等价与n=pow(2,n)(位运算更快)
for(int i=1;i<=n;i++){
int x;
cin>>x;
q.push(make_pair(i,x)); //make_pair(i,x)就是建立一个first为i，second为x的pair
}
while(q.size()>2){ //循环将比赛进行至只剩前两名(q.size()为2是时要跳出循环单独判断亚军)
pair<int,int> x,y;
x=q.front();
q.pop();
y=q.front();
q.pop();
if(x.second>y.second){ //从队头取出两个队，进行比较后将较强的队压入队尾
q.push(x);
}else{
q.push(y);
}
}
pair<int,int> x,y;
x=q.front();
q.pop();
y=q.front();
q.pop();
if(x.second>y.second){ //较弱的那队时亚军，将其国家号输出
cout<<y.first<<endl;
}else{
cout<<x.first<<endl;
}
return 0;
}

还有更简单的做法，因为只需要知道亚军是谁，我们并不需要模拟整个比赛的过程，把这2^n个国家分为左右两个部分，亚军一定是左半边最强的国家与右半边最强的国家之间较弱的那个，代码如下：

#include <bits/stdc++.h>

using namespace std;

//用结构体来存储国家信息

struct gj {

   int hm;//号码

   int nl=0;//能力值

};

int main() {

   int n;

   gj max_l, max_r;//左半边最强，右半边最强

   gj a;//读入时的临时变量a

   cin >> n;

   //找左半边最强

   for (int i = 0; i < 1<<(n-1); i++) {

       cin >> a.nl;

       if (a.nl > max_l.nl) {

           max_l.nl = a.nl;

           max_l.hm = i + 1;

       }

   }

   //找右半边最强

   for (int i = 1<<(n-1); i < 1<<n; i++) {

       cin >> a.nl;

       if (a.nl > max_r.nl) {

           max_r.nl = a.nl;

           max_r.hm = i + 1;

       }

   }

   //输出较弱的号码，即亚军。

   if (max_l.nl > max_r.nl)cout << max_r.hm;

   else cout << max_l.hm;

   return 0;

}

在此同样借用田泽恩的代码，给想要练习用递归进行模拟的同学提供借鉴：

#include <bits/stdc++.h>
using namespace std;
struct team
{
int pw,nm;
} a[128],b[128];
void match(int l)
{
if(l==2)
{
int ans=a[0].pw>a[1].pw?a[1].nm:a[0].nm;
cout<<ans;
return;
}
for(int i=0; i<l; i+=2)
{
b[i/2].pw=a[i].pw>a[i+1].pw?a[i].pw:a[i+1].pw;
b[i/2].nm=a[i].pw>a[i+1].pw?a[i].nm:a[i+1].nm;
}
for(int i=0; i<l/2; i++)
{
a[i].pw=b[i].pw;
a[i].nm=b[i].nm;
}
match(l/2);
}
int main()
{
int n;
cin>>n;
int l=pow(2,n);
for(int i=0; i<l; i++)
{
cin>>a[i].pw;
a[i].nm=i+1;
}
match(l);
return 0;
}

D.取数求和

这道题本质上是个暴力搜索的问题，但是纯暴力肯定会超时，我们需要在dfs函数中加入一些巧妙的优化。（但如果实在不会做，建议也打纯粹的暴力代码得到部分分）

首先，我们对每个数组排序，这样更方便我们找前n小的和。

其次，我们并不需要一次dfs就找出所有答案，这样会枚举到所有情况，耗费的时间是不可接受的。所以我们定义一个cur变量，表示在这次dfs里，我们只需要找比最小和大cur的那个答案，如果找到了就输出。每次循环后我们的cur+1，再进行下一轮dfs。这样一来，在dfs函数中就可以进行一些有效的剪枝优化，也保证了我们最后的答案是从小到大输出的，具体实现见代码。

这道题带有搜索问题中层次加深的思想，是一道很值得好好品味的题。

代码如下：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int m,n,k;//k表示当前已经找到了前k小的和
int a[110][2010];
void dfs(int arNum, int cur, int sum)
{
if (arNum >= m)
{
if (cur) return;//到最后时cur必须为0
if (k) putchar(' ');//除了第一次输出，之后的每一次都在前面输出一个空格
printf("%d", sum);
k++;
return;
}
for (int i = 0; i < n; i++)
{
if (k >= n || a[arNum][i] - a[arNum][0] > cur) return;
//如果已经找到了前n小的和，退出dfs
//由于最小值肯定是每个数组下标为0的数相加，那么如果 a[arNum][i]-a[arNum][0]>cur，这次找到的结果必然会比最小值+cur还大，不符合我们的要求
dfs(arNum + 1, cur - a[arNum][i] + a[arNum][0], sum + a[arNum][i]);
//cur要随着在每个数组中选择的数的改变而不断更新
//sum是此时选的总的值
}
}
int main()
{
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
sort(a[i], a[i] + n);
}
for (int i = 0; i <= 10000; i++)
{
if (k >= n) break;
dfs(0, i, 0);//此次dfs只找最小的和大i的结果
}
return 0;
}