4月1日的美团笔试算法题解参考

第一题, 小美的加法

原题题意: 小美写下了n个数的加法式, 每次都只改动其中一个符号. 每次改动相互独立(也就是每一次改动都是从全加式开始)

样例如下

输入描述
第一行一个整数n，合义见题面。

接下来一行n个整数a1,a2,..,an，依次表示小美初始写下的连加算式中的每一个数。

接下来一个整数m，表示小美做了m次算数训练

接下来2m个以空格分开数字或符号 t1,o1, t2,o2, ... tm,om，其中ti为数字，oi是'+','-','*','/'(即加减乘除符号，不含引号)中的一个符号，表示第 i 次操作选定了第ti个加号，将其改变为了oi。

对于所有的的数据,2≤N≤50000，1≤M≤50000,1≤ai≤500,1≤ti<N,oi∈{+,-,*,/}

输出描述
输出一行m个整数，分别表示每次操作的答案，结果四舍五入到一位小数。


样例输入
5
1 2 4 2 5
3
1 - 2 * 4 /
样例输出
10.0 16.0 7.4

开局的送分题
参考解法如下

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    double a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    // 默认是加号
    int m;
    cin >> m;
    double result0 = 0;
    for (int i = 0; i < n; i++)
    {
        result0 += a[i];
    }
    for(int j=0;j<m;j++)
    {
        double result = result0;
        int index;
        cin.sync();
        cin >> index;
        char cha;
        cin >> cha;
        switch (cha)
        {
        case '+':
        {
            ;
            break;
        }
        case '/':
        {
            result += ((a[index - 1] / a[index]) - (a[index - 1] + a[index]));
            break;
        }
        case '*':
        {
            result += ((a[index - 1] * a[index]) - (a[index - 1] + a[index]));
            break;
        }
        case '-':
        {
            result += ((a[index - 1] - a[index]) - (a[index - 1] + a[index]));
            break;
        }
        }
        printf("%.1f ", result);
    }
}

第二题, 丑陋值

题意: 给一个数组, 计算把他们顺序摆放之后的丑陋值之和 (相邻的数的丑陋值等于他们之差的绝对值)

样例如下

样例输入
3
3 1 2
样例输出
2

提示
我们可以将3和1交换，得到

1 3 2

然后再将2和3交换，得到

1 2 3

可以证明，此时有最小丑陋值|1-2|+|2-3|=2

送分题+1, 排序之后求差值之和即可, 参考如下

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
#include<iostream>
#include<list>
#include<vector>
using namespace std;

int main()
{
    int n;
    cin>>n;
    list<long long int> ml;
    for (int i = 0; i < n; i++)
    {
        long long int temp;
        cin>>temp;
        ml.push_back(temp);
    }
    ml.sort();
    long long int res=0;
    long long int shangyige=0;
    shangyige=ml.front();
    ml.pop_front();
    for (int i = 1; i < n; i++)
    {
        res+=ml.front()-shangyige;
        shangyige=ml.front();
        ml.pop_front();
        /* code */
    }
    cout<<res;
}

第三题, 收藏夹的欣赏值

题意在样例中, 如下

第一行两个整数n和m，表示小美的收藏夹数量和小美的操作数量。初始时刻收藏夹都是空的，也即ai=0(i∈[1,n])

第二行m个整数op1,op2,...,opm。

第三行m个整数x1,x2,...,xm。

第四行m个整数y1,y2,...,ym，这些共同表示了m次操作。具体而言，对第i次操作，opi=0时表示为一次收藏夹更新操作，会将xi位置的收藏夹欣赏程度更新为yi，即axi=yi；opi=1时表示为一次查询操作，表示如果小美欣赏编号在区间[xi,yi]的收藏夹，能获得的满足感是多少，也即的值。

对于所有的数据，1≤n,m≤ 50000,opi∈{0,1},当opi=0 时,1≤xi≤n,0≤yi≤10000; 当opi=1 时，1≤xi≤yi≤n。保证至少有一次opi=1 的操作。

输出描述
对每个opi=1的操作，输出一个数表示对应答案。空格隔开所有答案。


样例输入
4 7
1 0 1 0 1 0 1
1 1 1 3 1 4 1
3 2 3 5 3 100 3
样例输出
0 2 7 7

提示
样例解释

操作记录为

0 0 0 0 (初始)

<询问[1,3],结果为0+0+0>

2 0 0 0 <1号更改为2>

<询问[1,3],结果为2+0+0>

2 0 5 0 <3号更改为5>

<询问[1,3],结果为2+0+5>

2 0 5 100 <4号更改为100>

<询问[1,3],结果为2+0+5>

普通的走流程的题, 参考如下

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<iostream>
using namespace std;
int main(){
    int n ,m;
    cin>>n>>m;
    int sth[n]={0};//收藏夹
    int op[m];
    int x[m];
    int y[m];
    // for(int i=0;i<n;i++){
    //     cin>> sth[i];
    // }
    for(int i=0;i<m;i++){
        cin>>op[i];
    }
    for(int i=0;i<m;i++){
        cin>>x[i];
    }
    for(int i=0;i<m;i++){
        cin>>y[i];
    }
    for(int i=0;i<m;i++){
        if(op[i]==1){// lookup
            int sum=0;
            for(int j=x[i]-1;j<y[i];j++){
                sum+=sth[j];
            }
            printf("%d ",sum);
        }
        else{ // update
            sth[x[i]-1]=y[i];
        }
    }
}

第四题, 魔法训练

完整原题见下

魔法训练室里有n个神奇的杯子，有着不同的大小，假设第i个杯子已满，向其倒水，多余的水会正正好好流向第i+1个杯子（如果i=n时没有下一个杯子，不会有杯子接住此时多余的水而溢出到魔法训练室的水池）。

这些杯子有着初始固定的水量，每次练习后杯子里的水都会还原到最初状态。每次练习时，魔法黑板会告诉小美需要将哪一个杯子倒满水。因为每个杯子的材质和形状有所不同，所以对其释放倒水魔法需要消耗的魔法值不同。小美想尽可能多练习，所以需要最小化每次消耗的魔法值的总量。

输入描述
第一行一个整数n，表示杯子数量。

第二行n个整数x1,x2,...,xn，依次表示第 i 个杯子能容纳水的量（单位为毫升）。

第三行n个整数y1,y2,...,yn，依次表示第 i 个杯子初始有的水量（单位为毫升）。

第四行n个整数z1,z2,...,zn，依次表示对第 i 个杯子每添加1毫升水需要消耗的法力值。

第五行一个整数m，表示练习的数量。

第六行m个整数q1,q2,...,qm，依次表示第i次练习时需要将第qi个杯子倒满。（每次练习过后，杯子里的水量都会还原为初始状态，不会影响到下一次练习）

1≤n,m≤3000 , 1≤yi≤xi≤109, 1≤zi≤300,1≤qi≤n

输出描述
输出第一行m个数，依次表示每次训练时需要消耗的最小法力值。如果杯子初始本身就是满的，则需要消耗的法力值为0。

样例输入
3
1 2 3
1 1 2
1 2 5
2
3 1
样例输出
2 0

需要思考一下的动态规划问题, 参考如下

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
41
42
43
44
45
46
47
#include <iostream>

using namespace std;
int getmin(int *vols, int *curt, int *takes, int index, int need)
{
    if (index == 0)
        return takes[index] * need;
    return min(getmin(vols, curt, takes, index - 1, need + (vols[index-1] - curt[index-1])),
               takes[index] * need);
    // min(min(倒满之前的并且让某个溢出(累加所需水量))，直接倒满现在)
}
int main()
{
    int bottles;
    cin >> bottles;
    int vols[bottles];
    int curt[bottles];
    int takes[bottles];
    for (int i = 0; i < bottles; i++)
    {
        cin >> vols[i];
    }
    for (int i = 0; i < bottles; i++)
    {
        cin >> curt[i];
    }
    for (int i = 0; i < bottles; i++)
    {
        cin >> takes[i];
    }
    int ops = 0;
    cin >> ops; // 操作次数
    while (ops--)
    {
        int target;
        cin >> target;
        if (curt[target - 1] == vols[target - 1])
        { // ful
            cout << 0 << ' ';
        }
        else
        { // not full
            cout << getmin(vols, curt, takes, target - 1, vols[target - 1] - curt[target - 1]) << ' ';
        }
    }
}

第五题,

原题如下

你现在有一棵树，树上的每个节点都有自己的价值。价值的计算规则如下所示：

① 若某节点N没有儿子节点，那么节点N价值为1；

② 若某节点N有两个儿子节点，那么节点N价值为两个儿子节点的价值之和，或者价值之按位异或。这取决于节点N的颜色，若N的颜色为红色，那么节点N价值为两个儿子节点的价值之和；若N的颜色为绿色，那么节点N价值为两个儿子节点的价值之按位异或。

保证这棵树要么没有儿子节点，要么有两个儿子节点。

注：树，是一种无向无环联通图。

按位运算就是基于整数的二进制表示进行的运算。按位异或用符号⊕表示，两个对应位不同时为1，否则为0。

如：

5=(101)2

6=(110)2

5⊕6=3，即 (101)2 ⊕ (110)2 = (011)2

输入描述
第一行一个正整数n表示节点个数。

第二行n-1个正整数p[i](2≤i≤n)表示第 i 个节点的父亲。1号节点是根节点。

第三行n个整数c[i](1≤i≤n)，当c[i] = 1时表示第 i 个节点是红色，c[i] = 2则表示绿色。

数据保证形成合法的树。

对于所有的数据，n≤50000

输出描述
输出一行一个整数表示根节点的值。

样例输入
3
1 1
2 2 2

时间不够了, 自己又菜, 不会

1
2
3
4
5
6
7
#include <iostream>

using namespace std;
int main()
{
  cout<<"我不会";
}

这道题以后有时间再补上…