蚂蚁集团秋招 2023.09.14 编程题目与题解（）

发表于 2023-09-17 分类于笔试阅读次数：本文字数： 3k 阅读时长 ≈ 3 分钟

1、最优化存储（三）

支付宝服务亿级消费者，每个支付宝的用户有自己独特的信息，假设每个会员存储的成本为\(a_i\)，现在有\(n\)个会员，和\(m\)块存储容器，希望用该容器存储更多的会员信息；

存储优化是个相当复杂的过程，为了简化问题，存储规则如下：

每个会员的存储成本可以用长度\(a_i\)的线段表示。存储容器\(m\)块，每块可以用一段线段\(b_i\)表示。

存储容器有个特性，如果会员\(i\)存储在容器中间位置（非两端即为中间），存储成本为\(a_i\)本身，但是线段容器两端有存储压缩技术，存储在靠两端位置的会员存储成本可以压缩到一半，即\(a_i/2\)，而且每个会员只能压缩一次。

现在\(n\)个会员，每个会员存储成本为\(a_i\)，以及有\(m\)块存储资源\(b_i\)，希望你做存储优化，求能存储最大的会员数量是多少。

输入

第一行输入两个正整数\(n\)和\(m\)，用空格隔开。代表会员数量、最大存储空间。

第二行输入\(n\)个正整数\(a_i\)，代表每个会员的存储成本。

第三行输入\(m\)个正整数\(b_i\)，代表每块存储容器的长度。

\(1\le n,m\le 10^5\)
\(1\le a_i\le 2\)
\(1\le b_i\le 2\)

输出

一个整数，代表最大的信息量之和。

样例

输入：
5 2
1 2 2 1 2
2 1

输出：
4

提示：
选择前四个会员，将第二个和第三个的会员信息放在第一个容器的两端位置，将第一个和第四个会员的信息放在第二个容器的两端位置。

解答

对于长度为\(1\)的容器和长度为\(2\)的容器，无非有以下摆放方式：

1:

1(0.5)  1(0.5)
2(1)

2:

1(0.5)  1   1(0.5)
1(0.5)  2(1)
2(1)    2(1)

并且，由于长度为\(1\)的客户信息比长度为\(2\)的客户信息更好摆放，因此我们优先处理长度为\(1\)的情况。

本题使用的是贪心思想，先将长度\(1\)的信息摆入长度为\(1\)的容器中，每次可以摆\(2\)个，接下来如果没有长度\(1\)了，那就摆入容器\(2\)中，每次可以摆\(3\)个。在这时，如果只需要摆放长度\(1\)的信息进入长度\(2\)的容器，这时我们可以考虑顺便带入一个长度\(2\)的信息。

当长度\(1\)的信息安排满后，对长度\(2\)的信息贪心安排即可。

代码

#include <bits/stdc++.h>
using namespace std;
int s[3],t[3];
int main(){
    int n,m,x;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);++s[x];
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&x);++t[x];
    }
    int ans=0;
    for(;s[1]>0;){
        if(t[1]>0){
            int x=min(2,s[1]);
            ans+=x;s[1]-=x;--t[1];
        }
        else if(t[2]>0){
            int x=min(3,s[1]);
            if(x==1&&s[2]>0){
                ++ans;--s[2];
            }
            ans+=x;s[1]-=x;--t[2];

        }
        else break;
    }
    for(;s[2]>0;){
        if(t[1]>0){
            ++ans;--s[2];--t[1];
        }
        else if(t[2]>0){
            int x=min(2,s[2]);
            ans+=x;s[2]-=x;--t[2];
        }
        else break;
    }
    printf("%d\n",ans);
}

2、小红的牺牲契约

小红最近迷上了炉石传说。小红有一种卡牌：“虚空行者”，效果是：攻击力为\(1\)，血量为\(3\)，敌方会优先攻击这个“虚空行者”；

还有一张卡牌名字叫“牺牲契约”，效果是：牺牲一个“虚空行者”，为自己回复\(5\)点生命值。

现在敌方场上有\(a\)个攻击力为\(b\)的怪兽，每个怪兽只会进攻一次，只有在己方回合才能使用卡牌，每一回合使用的卡牌种类不限制。

小红手牌中有\(x\)个虚空行者，\(y\)个牺牲契约，小红的当前血量为\(h\)。

若小红场上有存活的虚空行者，敌方怪兽将直接攻击某个虚空行者。受到攻击的虚空行者血量将减去\(b\)。

若小红场上没有虚空行者，那么敌方怪兽可以直接攻击小红，小红将直接受到\(b\)点伤害。

虚空行者血量小于等于\(0\)的时候将死亡。

小红想知道，在所有的敌方攻击结束后，小红最多可以剩多少血量？

假设小红没有血量上限的限制。

输入

第一行输入一个正整数\(q\)，代表询问次数。

接下来的\(q\)行，每行输入五个正整数\(a,b,x,y,h\)，用空格障开。

\(1\le q\le 10^5\)
\(1\le a,b,x,y,h\le 10^9\)

输出

输出\(q\)行答案。

若该次询问小红会死亡（血量小于等于），则输出一个字符串"kou dead."

否则输出一个正整数，代表小红可以剩余的最大血量。

样例

输入：
3
6 4 5 2 10
4 4 3 4 10
100 100 1 1 100

输出：
8
9
kou dead.

提示：
第一个case
2个牺牲契约，血量+10。还剩3个“虚空行者”，抵挡3次攻击，还有3次攻击，最后的血量为10+10-3*4=8

第二个case
3个牺牲契约，血量+15，没有“虚空行者”了，还有4次攻击，最后的血量为10+3*5-4*4=9

解答

最优解无非就两种情况：

优先用完所有的“牺牲契约”后，恢复自己血量，再让“虚空行者”抗伤害，然后自己再抗伤害。（这种情况适用于怪兽的攻击力很小的情况）
优先让“虚空行者”抗伤害，再让自己抗伤害，如果有剩余的“虚空行者”，那么可以使用“牺牲契约”恢复伤害。（这种情况适用于怪兽的攻击力很大的情况）。

因此无非就两个过程谁先后进行。以下具体说明这两个过程：

对于一个“虚空行者”，它可以承受\(p=\lceil 3/b\rceil\)次怪兽的伤害。因此，至少需要\(n=\lceil a/p\rceil\)个虚空行者来抵挡伤害。实际上，我们只有\(e=\min\{n,x\}\)个“虚空行者”来抵挡伤害。仍然会有\(\max\{0,a-e\cdot p\}\)次攻击到自身，还剩下\(x-e\)个“虚空行者”来提升血量。
目前我们尽可能使用所有的“牺牲契约”来恢复血量，然后面对攻击。实际上，我们可以使用\(t=\min\{x,y\}\)个“牺牲契约”来恢复血量。此时还剩下\(x-t\)个“虚空行者”。

因此，最终答案是先执行过程1，再执行过程2；或者是先执行过程2，再执行过程1。

代码

def solve1(a, b, x, y, h):
    t = min(x, y)
    x -= t
    h += t * 5

    per = (3 + b - 1) // b
    need = (a + per - 1) // per
    exact = min(need, x)
    a = max(a - exact * per, 0)
    x -= exact
    h -= a * b

    return h


def solve2(a, b, x, y, h):
    per = (3 + b - 1) // b
    need = (a + per - 1) // per
    exact = min(need, x)
    a = max(a - exact * per, 0)
    x -= exact
    h -= a * b

    t = min(x, y)
    x -= t
    h += t * 5

    return h


T = int(input())
for _ in range(T):
    t = tuple(map(int, input().split()))
    ans = max(solve1(*t), solve2(*t))
    print(ans if ans > 0 else "kou dead.")

3、小红的字符串匹配区间

小红有两个字符串\(s,t\)，其中\(s\)最多有\(10\)个字符是不同的，两个字符串的长度都是\(n\)。如果对于区间\([l,r]\)，任选\(i\in[l,r]\)，满足\(s_i=t_i\)，那么称这是一个匹配区间。

小红每次操作可以选择\(s\)中的一个字符\(s_i\)，将\(s_i\)放到集合\(S\)中，再将 \(s_i\)改成任意字符。例如\(s=\texttt{"abcd"}\)，选择\(i=2\)，那么\(S=\{\texttt{'b'}\}\)，并将\(s_2\)改成\(\texttt{'z'}\)，得到\(s=\texttt{"azcd"}\)。

小红想知道，在集合\(S\)的不同元素数量不超过\(k\)的情况下，最多能有多少个匹配区间。

输入

一行两个正整数\(n,k\)，表示字符串的长度和集合\(S\)的最大大小。

一行一个字符串\(s\)，不同字符的数量不超过\(10\)。

一行一个字符串\(t\)。

\(1\le k\le 10\)
\(2\le n\le 10^4\)

输出

输出一个整数，表示最多的匹配区间数量。

样例

输入：
3 1
abc
azc

输出：
6

提示：
一次修改后，s=t="azc"，匹配区间数量为6个[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]。

解答

本题可以使用位运算，通过枚举解决。其基本思想是，假设某个字符\(c\)进入集合\(S\)，那么对于所有的下标\(\{i:s_i=c\}\)，这些下标的字符都可以被自由地替换，而不会额外的代价。

假设\(s\)有\(m\)个不相同的字符，这些不同字符的字符由集合\(C\)表示，即\(|C|=m\)。因此，\(S\)中包含不同元素的情况最多只有\(2^m\)种，由于\(m\le 10\)，因此我们直接暴力枚举\(S\)即可。

我们每次枚举集合\(S\subseteq C\)。依据贪心的思想，只需要枚举\(|S|=\min\{m,k\}\)的情况即可。

枚举出\(S\)后，我们可以构造出比特串\(b\)，满足\(b_i=\mathbf{1}\{s_i\in C\lor s_i=t_i\}\)，其中\(\mathbf{1}\{B\}\)是一个示性函数，用来表示布尔值\(B\)是否为真。

因此，一个区间\([l,r]\)是匹配区间，当且仅当满足\(\forall i\in[l,r],b_i=1\)，即是一个全\(1\)比特子串。

而求解\(b\)有多少个全\(1\)子串也很简单，假设\(b\)中包含了多个极大的全\(1\)子串，其中一个长度为\(c\)，那么这个极大全\(1\)子串有\(\dfrac{c(c+1)}{2}\)个子串，直接将它们添加到答案即可。

因此，整道题目的时间复杂度为\(O(\binom{m}{\min\{m,k\}}\cdot n+2^m)\)。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=10004;
char s[N],t[N];
int x[N],y[N];
int n,k,m=0;
int main(){
    scanf("%d %d %s %s",&n,&k,s+1,t+1);
    map<char,int>mp;
    for(int i=1;i<=n;i++)
        mp[s[i]]=0;
    for(auto &[k,v]:mp)
        v=m++;
    k=min(k,m);
    for(int i=1;i<=n;i++){
        x[i]=mp[x[i]];
        y[i]=mp.count(t[i])?mp[t[i]]:-1;
    }
    int ans=0;
    for(int st=0;st<(1<<m);st++){
        if(__builtin_popcount(st)!=k) continue;
        for(int i=1,j;i<=n;){
            if(st>>x[i]&1){
                for(j=i;j<=n&&((st>>x[j]&1)||x[j]==y[j]);j++);
                int c=j-i;
                ans+=(c+1)*c/2;
                i=j;
            }
            else i++;
        }
    }
    printf("%d\n",ans);
}

1、最优化存储 （三）

输入

输出

样例

解答

代码

2、小红的牺牲契约

输入

输出

样例

解答

代码

3、小红的字符串匹配区间

输入

输出

样例

解答

代码

1、最优化存储（三）