美团 秋招 2023.09.09 编程题目与题解

发表于 更新于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

1、小美的abc串

小美拿到了一个仅由"abc"三种字母组成的字符串，她每次操作会同时对所有字母进行如下变换：把'a'变成'bc'，把'b'变成'ca'，把'c'变成'ab'。小美将操作\(k\)次，请你输出最终的字符串

输入

第一行输入一个字符串，长度不超过\(100\)。

第二行输入一个正整数\(k\)。

  • \(1\le k\le5\)

输出

输出最终的字符串

样例

1
2
3
4
5
6
7
8
9
10
输入：
abc
2

输出：
caababbcbcca

提示：
第一次操作，字符串变成bccaab
第二次操作，字符串变成 caababbcbcca

解答

只需要简单地进行模拟即可，整个模拟过程迭代\(k\)次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int k;
    cin>>s>>k;
    for(int _=0;_<k;_++){
        string t;
        for(char ch:s){
            if(ch=='a') t+="bc";
            else if(ch=='b') t+="ca";
            else t+="ab";
        }
        s=t;
    }
    cout<<s<<"\n";
}

2、小美的加减法2.0

小美有一个数组\(a\)，她想把这个数组求和，即\(a_1+a_2+a_3+\dots+a_n\)。现在她想把其中一个加号变成减号，但小美是小学生，不会负数的加减法，因此计算过程中不能出现负数。

小美想知道改变符号后答案的最小值是案少，如果不能改变符号，则输出\(-1\)。

输入

第一行输入一个整数\(n(1\le n\le 10^5)\)表示数组长度。

第二行输入\(n\)个整数表示数组\(a(1\le a_i\le 10^9)\)。

输出

输出改变符号后的答案，若无法改变，则输出\(-1\)。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输入：
3
3 2 1

输出：
2

提示：
3-2+1：3-2=1，1+1=2
3+2-1：3+2=5，5-1-4
因此答案为2

输入：
3
1 2 4

输出：
-1

提示：
1-2+4：1-2=-1，-1+4=3
1+2-4：1+2=3，3-4=-1
两种变法都出现了负数。

解答

令数组\(a\)的前缀和为\(s\)：\(\displaystyle{s_i=\sum_{j=1}^i a_i},s_0=0\)。

接下来枚举每个\(i\in[1,n]\)。由于整个运算过程不能出现负数，因此如果要将\(a_i\)前面的符号转换为负号，那么就意味着\(s_{i-1}\ge a_i\)。由于后面的数都是正数，因此不需要考虑后续的影响。

将\(a_i\)从正号变成负号后，数组和从\(s_n\)变成\(s_n-2a_i\)，因此本题的答案为：

\[\min_{1\le i\le n,s_{i-1}\ge a_i}\{s_n-2a_i\}\]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int n;
ll s[N],a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    ll inf=1e18;
    ll ans=inf;
    for(int i=1;i<=n;i++){
        if(a[i]<=s[i-1]){
            ans=min(ans,s[n]-a[i]*2);
        }
    }
    if(ans==inf) ans=-1;
    printf("%lld\n",ans);
}

3、01串变幻

对于一个01串，每次可以选择两个相邻的相同字符删除，删除到不能删除为止。最终得到的字符串长度，即原串的价值。

现在给定了一个01串，你必须修改恰好\(k\)次，可以将某个'1'修改为'0'或者'0'修改为'1'，请问最后该串价值的最小值是多少?

输入

第一行输入两个正整数\(n\)和\(k\)，代表字符串的长度、修改次数。

第二行输入一个长度为\(n\)的字符串，保证仅由'0'和'1'构成。

  • \(1\le k\le n\le 10^5\)

输出

\(k\)次操作后字符串价值的最小值。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
3 1
101

输出：
1

提示：
将第一个字符修改为'0'，字符串变为"001"，可以将两个'0'删除，剩余长度是'1'。因此最小价值为'1'。

输入：
2 1
00

输出：
2

解答

需要注意的是，由于一次删除操作并不会引起其它字符的变化，因此，我们可以考虑边消除，边转换，从而贪心地得到最优解。

我们首先使用一个栈来模拟相同相邻字符串消失的过程：如果当前栈非空，并且当前字符和栈顶的字符相同，那么将栈顶弹出；否则将这个字符串置入栈中。

由此可见，消除操作完成后，剩下的字符串一定是一个形如010101...或者是101010...这种01相间的字符串。在这种字符串中，每使用\(1\)次操作转换这些字符，就可以将剩余的字符串长度减少\(2\)。

由于本题要求使用恰好\(k\)次操作。因此如果\(k\)次操作都完成，那么原串的最小价值为当前字符串的价值。否则需要按情况讨论，剩余的字符串长度要么是\(1\)，要么是\(0\)。如果其长度为\(1\)，那么无论剩下\(k\)次操作如何，它都不会发生变化，如果长度为\(0\)，并且还有剩余的操作，那么就需要将原本消失的两个相同字符进行复原，并对一个字符进行操作，从而使得字符串的价值变成\(2\)，在这种情况下，如果执行\(0,1,2,3,\dots\)次操作，那么字符串的价值会\(0,2,0,2,\dots\)不停的变化。最终按照奇偶性输出最小价值即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
char s[N];
int main(){
    int n,k;
    scanf("%d %d %s",&n,&k,s+1);
    stack<int>st;
    for(int i=1;i<=n;i++){
        if(st.empty()||st.top()!=s[i]) st.push(s[i]);
        else st.pop();
    }
    while(k>0&&st.size()>1){
        st.pop();
        st.pop();
        k--;
    }
    int ans;
    if(k==0) ans=st.size();
    else{
        if(n&1) ans=1;
        else ans=k&1?2:0;
    }
    printf("%d\n",ans);
}

4、数组的最大差异

对于一个严格递增的数组\(a\)，定义数组\(b,b_i= a_{i+1}-a_i\)，数组\(b\)中不同元素的数量就是数组\(a\)的差异。

对于数组\(a=[3,8,11,12,15]\)，可以得到数组\(b=[5,3,1,3]\) ，其中不同元素数量有三个，分别是\(1,3,5\)，那么数组\(a\)的差异值就是\(3\)。

请你构造一个长度为\(n\)的数组，要求\(1\le a_i\le m\)，并且差异最大。

输入

一行两个整数\(n,m\)，表示数组的长度和元素的最大值。

  • \(1\le n\le m\le 10^5\)

输出

一行\(n\)个整数，表示构造出的数组。

样例

1
2
3
4
5
6
7
8
9
输入：
4 12

输出：
2 3 5 10

提示：
可以得到数组b=[1,2,5]，差异值为3。
输出2 3 5 12也可以，差异值也为3。

解答

由于\(a\)是单调递增的，为了能够让\(b\)数组的元素和最大化，此时应该让\(a_1=1\)。

为了让\(b\)数组的不同元素尽量多，同时为了让\(a\)增长地尽量缓慢，因此要有\(b_1=1,b_2=2,b_3=3,\dots\)，由此构造出\(a\)数组满足\(a_i=a_{i-1}+i-1\)。

但是数组\(a\)中的元素的上界为\(m\)，但是\(a\)又是单调递增的，为了保证\(b\)的不同元素足够多，\(b\)后面的元素都只能填上\(1\)。

也就是说\(b\)的形态大致如下：\(b=[1,2,3,4,\dots,k-2,k-1,1,1,\dots,1]\)。如果\(b_{k}=k\)，那么\(a\)以后哪怕增长的也再慢，也会超过\(m\)。

因此，一开时首先构造出\(a\)，即\(a_1=1,a_i=a_{i-1}+i-1\)。然后找到一个最小的下标\(k\)满足\(m-a_k<n-k\)，那么接下来对于\(\forall i\ge k\)，都重新令\(a_i=a_{i-1}+1\)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int n;
ll a[N],m;
int main(){
    scanf("%d %lld",&n,&m);
    a[1]=1;
    for(int i=2;i<=n;i++){
        a[i]=a[i-1]+i-1;
    }
    int p;
    for(p=1;p<=n&&m-a[p]>=n-p;p++);
    for(int i=p;i<=n;i++)
        a[i]=a[i-1]+1;
    for(int i=1;i<=n;i++)
        printf("%lld%c",a[i]," \n"[i==n]);
}

5、小美的区间异或和

小美定义一个数组的权值为：数组中任选两个数的异或之和。例如，数组\([2,1,3]\)的权值为：\((2 \oplus 1)+(2 \oplus 3)+(1 \oplus 3)=3+1+2=6\)。

小美拿到了一个数组，她想知道该数组的所有连续子数组的权值和是多少？答案对\(10^9+7\)取模。

输入

第一行输入一个正整数\(n\)，代表数组的大小。 第二行输入\(n\)个正整数\(a_i\)，代表小美拿到的数组。

  • \(1\le n\le 10^5\)
  • \(1\le a_i\le 10^9\)

输出

所有子数组的权值之和，对\(10^9+7\)取模的值。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
4
2 3 1 2

输出：
28

提示：
长度为1的子数组无法取两个数，权值为0。
子数组[2,3]的权值为1。
子数组[3,1]的权值为2。
子数组[1,2]的权值为3。
子数组[2,3,1]的权值为6。
子数组[3,1,2]的权值为6。
子数组[2,3,1,2]的权值为10。
权值之和为1+2+3+6+6+10=28。

解答

可以发现，数组\(a\)中的每一个元素的每一位都是相互独立的，因此我们只需要计算每一位的贡献，然后再将它们进行组合即可。

由于\(a_i\le 10^9\)，因此令\(M=31\)。那么，我们定义数组\(b_{k,i}\)表示\(a_i\)的第\(k\)位。那么可见\(\forall k\in[0,M),i\in[1,n]\)，都有\(b_{k,i}\in\{0,1\}\)。我们将原数组分解成了多个布尔数组，来方便求解各个问题。

按照异或运算的特点，如果\(b_{k,i}\neq b_{k,j}\)（不失一般性，假设\(i<j\)），那么这一对\((i,j)\)将会做出贡献。由于现在计算的是各个子数组的权值和，因此\((i,j)\)将会做出\(i\cdot(n+1-j)\)的次贡献（只要这个区间的左侧小于等于\(i\)，右侧大于等于\(j\)，那么\((i,j)\)就会做出贡献，这样的区间一共有\(i\cdot(n+1-j)\)个）。最终数组\(b_k\)做出的贡献值\(v_k\)为：

\[v_k=\sum_{1\le i<j\le n,b_{k,i}\neq b_{k,j}} i\cdot(n+1-j)=\sum_{j=1}^n (n+1-j)\cdot\left(\sum_{1\le i<j,b_{k,i}\neq b_{k,j}} i\right)\]

最右边的式子可以使用一个指针就可以完成计算，因为当指针\(j\)固定时，我们可以计算出对应不同的所有比特的下标之和，最终只需要将已经准备好的和乘上\((n+1-j)\)即可。

因此，这道题目的最终答案为：

\[\sum_{i=0}^{M-1} v_k\cdot 2^k\]

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
ll mod=1e9+7;
int a[N],n,m=31;
ll c[2];
int main(){
    ll ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int k=0;k<m;k++){
        c[0]=c[1]=0;
        ll sum=0;
        for(int j=1;j<=n;j++){
            int b=a[j]>>k&1;
            sum=(sum+c[!b]*(n+1-j))%mod;
            c[b]=(c[b]+j)%mod;
        }
        ans=(ans+(sum<<k))%mod;
    }
    printf("%lld\n",ans);
}

如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝