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

发表于 | 更新于 | 阅读次数：
本文字数： 2.6k | 阅读时长 ≈ 2 分钟

Problem A（小埋与NOIP）：

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

$\bar{x}=\dfrac{x_1w_1+x_2w_2+…+x_nw_n}{w_1+w_2+…+w_n}$

附标程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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]);

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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的密信）那么大，可能很多人提交之后都会怀疑数据有问题，那你就错了，其实你们题目可能漏了一点没有看，那就是：

输入数据是密文！

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

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

附标程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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