携程秋招 2023.09.21 编程题目与题解

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

1、游游的排列构造

游游拿到了一个排列\(a\)。她希望你构造一个长度相等的排列，满足\(a_i\neq b_i\)且\(b\)的字典序尽可能小。你能帮帮她吗？

所谓排列，即长度为\(n\)的数组，其中\(1\)到\(n\)每个正整数都恰好出现了\(1\)次。

排列的字典序定义如下：两个排列的字典序比较，将比较它们第一个不相等的元素，该元素小的那个排列字典序更小。例如\([2,1,3]\)的字典序小于\([2,3,1]\)。

输入

第一行输入一个正整数\(n\)，代表排列\(a\)的长度。

第二行输入\(n\)个正整数\(a_i\)，代表游游拿到的排列。

\(2 \le n \le 10^5\)

输出

\(n\)个正整数\(b_i\)，代表构造的排列。

样例

输入：
3
1 2 3

输出：
2 3 1

解答

我们先按照贪心算法构造出一个排列：即\(\forall i\in[1,n)\)，如果\(a_i\)和剩余未被填入\(b\)的最小数相等，那么\(b_i\)填入次小数，否则填入次小数。并且\(b_n\)填入剩下的那一个数中。

可见，这种填入方式对\(b_n\)可能不满足题目要求。可以发现，只有\(a_n=n\)的时候才有可能发生这种情况，因为\(1,2\)都只有可能在位置\(1,2\)填入，\(3\)只有有可能在\(2,3\)位置填入，\(4\)只有可能在\(3,4\)位置填入……\(n-1\)只有可能在\(n-2,n-1\)填入。

因此，如果按照上面的方式构造出来的排列是不对的，那么我们只需要求一个字典序和它相邻且比它大的一个排列即可，这时我们只需要对前一个求出来的排列，交换\(b_{n-1},b_n\)即可。因为\(a_n=n\)，所以\(a_{n-1}\neq n\)，并且交换后，有\(b_n\neq n,b_{n-1}=n\)，那么这就是一个满足题意得最小字典序排列。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=100004;
int a[N],b[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=i;
    }
    for(int i=1;i<n;i++){
        if(b[i]==a[i]){
            swap(b[i],b[i+1]);
        }
    }
    if(a[n]==b[n]){
        swap(b[n],b[n-1]);
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",b[i], " \n"[i==n]);
}

2、小红的字符串

小红拿到了一个字符串\(s\)。她可以进行任意次以下操作作：

选择字符串中的一个字母\(ch_1\)和任意一个字母\(ch_2\)（\(ch_2\)可以不在字符串中出现），将字符串\(s\)中的所有\(ch_1\)变成\(ch_2\)。小红想知道，自己能否通过一些操作将字符串\(s\)变成\(t\)？

输入

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

对于每次查询输入2行：

第一行输入一个字符串\(s\)。

第二行输入一个字符串\(t\)。

\(1\le q\le 10\)

保证\(s\)和\(t\)的长度相同，且均由小写字母组成，长度不超过\(10000\)。

输出

输出\(q\)行，每行输出一个字符串代表答案。如果可以把\(s\)变成\(t\)，则输出Yes，否则输出No。

样例

输入：
3
ab
ba
abc
aaa
aaaa
abcd

输出：
Yes
Yes
No

解答

如果字符串\(t\)使用了全部的\(26\)个字母，那么\(s\)只能和\(t\)相等，否则每做一次操作，\(s\)最多只会有\(25\)个不同的字母，它是没办法和\(t\)相同的。

否则，对于任意两对下标\((i,j)\)，如果\(s_i=s_j\)，那么必须有\(t_i=t_j\)。因为每一次操作都要将和\(s_i\)相同的字母进行变换，变换后也一定是相同的，因此如果\(t_i\neq t_j\)，那么这种情况是不可能达到的。

最后，由于\(t\)不超过\(25\)个字母，我们对\(s\)进行变化时，可以先将其中一个字母\(c\)变成\(t\)中不存在的字母，然后再将其余\(t\)包含\(c\)的位置进行变换即可，这样不会造成混淆。因此这时一定会成功。

代码

#include <bits/stdc++.h>
using namespace std;

int solve(){
    map<char,vector<int>>mp;
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.size();i++){
        mp[s[i]].push_back(i);
    }
    set<char>st(t.begin(),t.end());
    if(st.size()==26) return s==t;
    for(auto &[k,v]:mp){
        for(int i=0;i+1<v.size();i++){
            if(t[v[i+1]]!=t[v[i]]) return 0;
        }
    }
    return 1;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        puts(solve()?"Yes":"No");
    }
}

3、游游的字母矩阵

游游拿到了一个\(n\)行\(m\)列的字母矩阵，矩阵中所有字符都是小写字母。

游游想知道，有多少个子矩阵满足，每个字母最多出现一次？

输入

第一行输入两个正整数\(n\)和\(m\)，代表矩阵的大小。接下来的\(n\)行，每行输入一个长度为\(m\)的、仅包含小写字母的字符串。

\(1\le n,m \le 500\)

输出

每种字母只出现一次的子矩阵数量。

样例

输入：
2 3
aad
abc

输出：
13

提示：
除了满足条件的大小为1的六个子矩阵外，还有以下7个:
.a.     ..d     .ad     ...     .ad     ...     ...
.b.     ..c     ...     .bc     .bc     abc     ab.

解答

由于英语字母只有\(26\)个，因此这里的子矩阵的面积（即长和宽之积）不超过\(26\)。我们这里可以直接枚举每个子矩阵进行判断。

因此，我们首先枚举矩阵中的每个元素作为所求子矩阵的左上角，接下来枚举这个子矩阵的宽度\(k\)，然后向右边拓展边计数即可。

这里为了保证不会超时，采用了如下措施：

使用位运算记录哪些字母被使用。
边判断边计数，避免判断一个大矩阵是否合法时，重新开始判断。
发现矩阵不合法及时退出循环，因为包含这个子矩阵的子矩阵一定也是不合法的。

代码

#include <bits/stdc++.h>
using namespace std;

char s[504][504];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++)
            s[i][j]-='a';
    }
    int ans=0;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            for(int k=1;k<=26&&x+k-1<=n;k++){
                int st=0;
                bool ok=1;
                for(int j=1;y+j-1<=m&&ok;j++){
                    for(int i=1;i<=k&&ok;i++){
                        if(st>>s[x+i-1][y+j-1]&1) ok=0;
                        st|=1<<s[x+i-1][y+j-1];
                    }
                    if(ok) ++ans;
                }
            }
        }
    }
    printf("%d\n",ans);
}

4、游游改数组

游游拿到了一个正整数，她准备恰好修改其中\(k\)位，使得该正整数变成\(75\)的倍数。你能帮游游求出有多少种修改方案吗？修改后，仍是正整数，且不允许存在前导零，答案请对\(10^9+7\)取模。

输入

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

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

\(1 \le n \le 10^{1000}\)
\(1\le k\le 1000\)

输出

修改的方案数，对\(10^9+7\)取模。

样例

输入：
355
2

输出：
9

提示：
共有150、225、300、450、525、675、750、825、975这9种方案。

解答

如果一个数是\(75\)的倍数，那么它一定满足如下特征：

所有数位之和是\(3\)的倍数。
最后两位无非是\(00,25,50,75\)中的一个组合。

令\(m\)是\(n\)的位数，令\(n_i(0\le i< n)\)表示\(n\)的从高到低的第\(i\)个数位。由于最后两位是固定搭配，因此我们先只考虑第一个特征。可以知道这里可以使用动态规划来处理。令\(f(i,j,r)(0\le i\le m,0\le j\le k,0\le r<3)\)表示对这个数的前\(i\)位修改了\(j\)个位置后，所得到的数的数位之和对\(3\)取模的值为\(r\)的方案数。那么我们可以构造出如下转移：

\(1\rightarrow f(0,0,0)\)
\(f(i,j,k)\rightarrow f(i+1,j,(k+d)\bmod 3)\qquad\text{if}\qquad d=n_i\)
\(f(i,j,k)\rightarrow f(i+1,j+1,(k+d)\bmod 3)\qquad\text{if}\qquad d\neq n_i\)

其中，第一个行的转移表示初值，一个空的数字数组没有任何数位，它的数位和是\(0\)，操作次数是\(0\)；第二行表示对当前位不进行修改的决策，那么增加了当前位之后，修改次数依然是\(j\)，因此转移到状态\(f(i+1,j,(k+d)\bmod 3)\)。第三行表示对当前位进行修改，其决策\(d\)有\(9\)种，分别是\(\{0,1,2,\dots,9\}-\{n_i\}\)，因此转移到状态\(f(i+1,j+1,(k+d)\bmod 3)\)。

再加上它是\(25\)倍数的，因此\(n\)的最后两位必须固定成一个组合。假设第\(i\)种组合的倒数第二位和第一位的数字分别是\(a_i\)和\(b_i\)，那么前\(m-2\)位的数位之和模\(3\)的值必须为\((-a_i-b_i)\bmod 3\)，并且还要根据\(a_i,b_i\)是否和\(n_{m-2},n_{m-1}\)相同，减去相对应的修改次数。

最终，枚举每种组合并加起来，就得到了本题所需要的答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1004;
char s[N];
int f[N][N][3],mod=1e9+7;
void add(int &x,int y){
    x+=y;
    if(x>=mod) x-=mod;
}
int n,k;
int a[4]={0,2,5,7},b[4]={0,5,0,5};
int solve(){
    scanf("%s %d",&s,&k);
    int n=strlen(s);
    if(n==1) return 0;
    f[0][0][0]=1;
    for(int i=0;i<n;i++)
        s[i]-='0';
    for(int i=0;i<n-2;i++){
        int d=s[i];
        for(int j=0;j<=k;j++){
            for(int r=0;r<3;r++){
                for(int x=(i==0?1:0);x<10;x++){
                    if(x==d) add(f[i+1][j][(r+x)%3],f[i][j][r]);
                    else add(f[i+1][j+1][(r+x)%3],f[i][j][r]);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<4;i++){
        if(i==0&&n==2) continue;
        int nk=k-(s[n-2]!=a[i])-(s[n-1]!=b[i]),nr=(9-a[i]-b[i])%3;
        if(nk>=0) add(ans,f[n-2][nk][nr]);
    }
    return ans;
}
int main(){
    printf("%d\n",solve());
}