民生科技秋招 2023.10.29 编程题目与题解

发表于 2023-10-30 分类于笔试阅读次数：本文字数： 1.7k 阅读时长 ≈ 2 分钟

1、小红的相似密码

小红有两个银行卡密码，对于“相似”的密码，小红给出以下判断的规则：

小红可以对任意一个密码进行最多\(k\)次操作，每次操作选择该密码所有字符，并将每个字符都加一(例如，"abc"加得到"bcd"，"zzz"加一得到"aaa")。如果能通过这些操作后，使得两个密码变得相等，那么小红就认为这两个密码是相似的。

小红想知道自己的两个密码是否是相似的。你能帮帮她吗？

输入

对于每组测试教据，第一行输入两个正整数\(n,k\)，分别表示密码的长度和模作次数。

第二行输入一个长度为\(n\)的字符串\(s\)，表示小红第一个银行卡密码，仅包会小写字母。

第三行输入一个长度为\(n\)的字符串\(t\)，表示小红第二个银行卡密码，仅包会小写字母。

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

输出

一行输出一个字符串，表示答案。如果两个密码是相似的，则输出"YES"。否则输出"NO"。

样例

输入：
4 3
abcd
cdef

输出：
YES

输入：
4 1
abcd
cdef

输出：
NO

解答

假设不考虑炒作次数\(k\)，那么一个字符串\(s\)能够变成字符串\(t\)，当且仅当这两个字符串的相邻两个字符的编号差值都相同，因为无论进行多少次操作，相邻字符编号之差总是不变的。

那么接下来考虑操作次数。我们要么对\(s\)进行操作，要么对\(t\)进行操作。令\(d'=(s_0-t_0)\bmod 26\)，并且令\(d=\min\{d',26-d'\}\)，这两种选择是要么选择\(s\)，要么选择\(t\)进行操作（选择一个最优的），只要步数\(d\le k\)是正确的即可。

代码

def solve(s, t, k):
    def diff(s):
        return [(ord(s[i + 1]) - ord(s[i])) % 26 for i in range(len(s) - 1)]

    if diff(s) != diff(t):
        return False
    d = abs(ord(s[0]) - ord(t[0]))
    d = min(d, 26 - d)
    return d <= k


n, k = map(int, input().split())
s, t = input(), input()
print("YES" if solve(s, t, k) else "NO")

2、小红走排列

数轴上有\(n\)个点\(a_i\)，小红初始在原点，希望按照一定的顺序访问这些点，小红想知道在所有的不同的访问顺序，走过的路径的总和是多少。例如有三个点\([1,3,5]\)，按照\(a_1,a_2,a_3\)的顺序访问，那么走过的路径为\(|1-0|+|3-1|+|5-3|=5\)。按照\(a_1,a_3,a_2\)的顺序访问，走过的路径为\(|1-0|+|5-1|+|3-5|=7\)。一共有\(n!\)种访问顺序。

输入

警一行一个整数\(n\)。表示点的个数。

第二行\(n\)个整数，表示点的位置，按照升序给出。

\(1\le n\le 10^5\)
\(1 \le a_1 \le \dots\le a_n \le 10^9\)

输出

输出一行一个整数表示答案，答案可能很大，输出答案对\(10^9+7\)取模的结果。

样例

输入：
3
1 3 5

输出：
50

提示：
顺序为a1,a2,a3时，路径为|1-0|+|3-1|+|5-3|=5。
顺序为a1,a3,a2时，路径为|1-0|+|5-1|+|3-5|=7。
顺序为a2,a1,a3时，路径为|3-0|+|1-3|+|5-1|=9。
顺序为a2,a3,a1时，路径为|3-0|+|5-3|+|1-5|=9。
顺序为a3,a1,a2时，路径为|5-0|+|1-5|+|3-1|=11。
顺序为a3,a2,a1时，路径为|5-0|+|3-5|+|1-3|=9。
所以答案为5+7+9+9+11+9=50。

解答

可见，由于所有路径都出现了恰好一次，因此对于任意一对\(i,j(i\neq j)\)，小红先在\(a_i\)，然后立刻走到\(a_j\)的出现次数都是相同的。

假设不考虑处在\(0\)的起点，由于每个路径的步数都是\(n-1\)，因此所有路径的步数之和为\(n!\cdot(n-1)\)。不同的满足\(i\neq j\)的二元组\((i,j)\)一共有\(n(n-1)\)个，因此从\(a_i\)到\(a_j\)的走向的出现次数为\(n!\cdot(n-1)/(n(n-1))=(n-1)!\)。

算上\(0\)作为起点的情况。令\(a\)的前缀和为\(\displaystyle{s_i=\sum_{j=1}^i a_i,s_0=0}\)。这\(n!\)条路径中，每个节点作为起点都恰好出现了\((n-1)!\)次，因此这部分的答案为\(\displaystyle{(n-1)!\cdot s_n}\)。

因此，这道题的答案为：

\(\begin{aligned} (n-1)!\cdot s_n+(n-1)!\cdot\sum_{i=1}^n\sum_{j=1}^n|a_i-a_j|&=(n-1)!\cdot\left(s_n+\sum_{i=1}^n\sum_{j=1}^i (a_i-a_j)\right)\\ &=(n-1)!\cdot\left(s_n+\sum_{i=1}^n(i\cdot a_i-s_i)\right) \end{aligned}\)

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
ll a[N],s[N],mod=1e9+7;
int n;
int main(){
    scanf("%d",&n);
    ll sum=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s[i]=(s[i-1]+a[i])%mod;
        sum=(sum+a[i]*i%mod-s[i]+mod)%mod;
    }
    ll fac=1;
    for(int i=1;i<n;i++)
        fac=fac*i%mod;
    ll ans=(fac*s[n]%mod+fac*2*sum)%mod;
    printf("%lld\n",ans);

}