干物妹！小埋！第三弹 比赛题解

---

Problem A（小埋与NOIP）：

此题其实是计算加权平均数，模拟公式过程再输出最大值即可。

附标程：

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string name[6];
    int lv[1000]={0},s[6][1000]={0},sco[6]={0},a,alv=0,ansm=0,anss=0;
    /*输入*/
    cin>>a;
    for(int b=1;b<=a;b++)
    {
        cin>>lv[b];
        alv=alv+lv[b];
    }
    for(int b=1;b<=5;b++)
    {
        int p=0;
        cin>>name[b];
        /*模拟过程*/
        for(int c=1;c<=a;c++)
        {
            cin>>s[b][c];
            p=p+s[b][c];
        }
        sco[b]=p/alv;
        if(anss<sco[b])/*比较*/
        {
            anss=sco[b];
            ansm=b;/*最大值所在位置*/
        }
    }
    cout<<name[ansm]<<endl;/*输出*/
}

---

Problem B（小埋与数羊）：

裸DP题，可以通过求从第一行出发后每个点所能得出的最大值，转移方程为：q[a][b]=max(q[a][b],q[a-1][c]+_map[a][b]);

附标程（效率还是比较低，没压缩）：

#include<iostream>
#include<cmath>
using namespace std;
int pa,ans;
int n,_map[100010][5]={0},q[100010][5]={0};
int main()
{
  cin>>n;
  for(int a=1;a<=n;a++)
  {
    for(int b=1;b<=4;b++)
    {
      cin>>_map[a][b];
      q[a][b]=_map[a][b];
    }
  }
  pa=0;
  for(int a=2;a<=n;a++)
  {
    for(int b=1;b<=4;b++)
    {
      for(int c=1;c<=4;c++)
      {
        if(b==c)
        {
          continue;
        }
        else
        {
          q[a][b]=max(q[a][b],q[a-1][c]+_map[a][b]);
        }
      }
    }
  }
  for(int a=1;a<=4;a++)
  {
    ans=max(q[n][a],ans);
  }
  cout<<ans<<endl;
}

---

Problem C（小埋与二分法）：

又是字符串，不过这次复杂了很多，但脑洞就没有上次的Problem C（小埋与TSF的密信）那么大，可能很多人提交之后都会怀疑数据有问题，那你就错了，其实你们题目可能漏了一点没有看，那就是：

输入数据是密文！

本题的题意其实是让你按照加密过程的逆过程来解密，可能有人会连加密过程都看不懂，那我就图解一下吧：

再简单点说其实就是先序遍历转中序遍历

附标程：

#include<bits/stdc++.h>
using namespace std;
char a[201000],s[201000];
int k;

void dg(int l,int r)/*“逆”二分*/
{
    int mid=(l+r)>>1;/*位运算>>1其实是div2*/
    a[mid]=s[k];
    k++;
    if (l<mid)
    {
        dg(l,mid-1);
    }
    if (r>mid)
    {
        dg(mid+1,r);
    }
}

int main()
{

    k=0;
    scanf("%s",s);/*输入*/
    int l=strlen(s)-1;
    dg(0,l);
    /*输出*/
    for (int i=0;i<=l;i++) 
    {
        printf("%c",a[i]);
    }
    printf("\n");
}

---

比赛详见:https://www.luogu.org/contestnew/show/9387