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

发表于 2023-09-22 分类于笔试阅读次数： 84 本文字数： 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 \leq n \leq 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$ 。她可以进行任意次以下操作作：

选择字符串中的一个字母 $c h_{1}$ 和任意一个字母 $c h_{2}$ （ $c h_{2}$ 可以不在字符串中出现），将字符串 $s$ 中的所有 $c h_{1}$ 变成 $c h_{2}$ 。小红想知道，自己能否通过一些操作将字符串 $s$ 变成 $t$ ？

输入

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

对于每次查询输入 2 行：

第一行输入一个字符串 $s$ 。

第二行输入一个字符串 $t$ 。

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

$1 \to f (0, 0, 0)$
$f (i, j, k) \to f (i + 1, j, (k + d) mod 3) if d = n_{i}$
$f (i, j, k) \to f (i + 1, j + 1, (k + d) mod 3) if d \neq n_{i}$

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

再加上它是 $25$ 倍数的，因此 $n$ 的最后两位必须固定成一个组合。假设第 $i$ 种组合的倒数第二位和第一位的数字分别是 $a_{i}$ 和 $b_{i}$ ，那么前 $m - 2$ 位的数位之和模 $3$ 的值必须为 $(- a_{i} - b_{i}) mod 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());
}