A. 牛牛的 Fib 序列

题目描述

牛牛重新定义了斐波那契数列，牛牛定义 $f(n)=f(n-1)+f(n+1),f(1)=a,f(2)=b$，现在给定初始值 $a,b$，现在求第 $n$ 项 $f(n)\mathrm{m}\mathrm{o}\mathrm{d}1000000007$ 的值。

其中 $1\le |a|,|b|,n\le 10^9$

输入

a,b,n

输出

f(n) % 1000000007

备注:

最终的答案应是一个非负整数，如 -1 % 1000000007 = 1000000006

示例1

输入

1, 2, 3

输出

1

说明

f(2) = f(3) + f(1), 所以 f(3) = f(2) - f(1) = 2 - 1 = 1

示例2

输入

-1, -2, 3

输出

1000000006

说明

同例1：f(3)= -1 % 1000000007 = 1000000006

解法

思路分析

手写一下前几个数，就会发现这个数列 6 个数一循环。

时间复杂度：O(1)

空间复杂度：O(1)

代码实现

public int solve (int a, int b, int n) {
final int mod = 1000000007;
int[] fib = new int[]{a, b, (b - a) % mod, -a, -b, (a - b) % mod};
return (fib[(n - 1) % 6] + mod) % mod ;
}

B. 破译密码

题目描述

题面：

​ 牛牛收到了一个任务，任务要求牛牛破译一个密码。牛牛将被给予两个字符串 s1 和 s2，均由四个小写字母构成。需要破译的密码为从s1 变换到 s2 最少需要的变换次数。

​ 变换的方式是这样：每次变换可以选择当前字符串中的一个位置，然后剩下的三个位置的字符从左到右分别加上 2，3，5，若是超出 ‘z’，则重新从 ‘a’ 开始，例如：对于字符串 “abcd”，我们选择 ‘c’ 的位置进行变换，则变换之后的字符串为 “ceci”; 对于字符串 “qyzr”, 我们选择 ‘r’ 位置进行变换，则变换之后的字符串为 “sber”。

输入

s1, s2

输出

s1 变换到 s2 最少需要的变换次数

备注:

s1, s2 均由四个小写字母组成

示例1

输入

"aaaa", "ccgk"

输出

2

说明

第一次变换选择第一个'a'，变成 "acdf"，第二次变换选择第二个 'c'，变成 "ccgk"，故答案为2

解法一：BFS

思路分析

在之前的文章中，【魔法数字】一题也用到了 BFS。本题和那题的思路一致。穷举所有变换的可能性，通过备忘录剪枝来减少搜索空间。

对每一个字符串都有四种变换情况，即选择第 $i$ 位 $(0\le i\le 3)$ 进行变换。

这里可以自行画一下四叉树，更能直观的体会这种方法的流程。（才不是因为我懒得画图，【逃】）

第一次变换到 s2 的那一层 j，即为最少变换次数。（根节点 s1 所在层为 0）

时间复杂度：$O(lo{g}_{4}26^4)$. 最坏情况下把所有字符串 ($26^4$ 个) 都搜索了一遍。

空间复杂度：$O(26^4)$. 额外空间主要是备忘录和队列的空间开销，最坏情况下把所有字符串都存进去了。

代码实现

int[] add = new int[] {2,3,5};
public int solve(String s1, String s2) {
Set<String> visited = new HashSet();
Queue<String> q = new LinkedList();
q.offer(s1);
int res = 0;
while(!q.isEmpty()) {
int size = q.size();
while(size-- > 0) {
String cur = q.poll();
if(cur.equals(s2)) return res;
if(visited.contains(cur)) continue;
visited.add(cur);
for(int i = 0; i < 4; i++) q.offer(convert(cur,i));
}
res++;
}
return res;
}
public String convert(String s, int i) {
char[] str = s.toCharArray();
int index = 0;
for(int j = 0; j < 4; j++) {
if(j == i) continue;
str[j] = (char)('a' + (str[j] - 'a' + add[index]) % 26);
index++;
}
return String.valueOf(str);
}

解法二：数学方法

思路分析

因为 s1 到 s2 的距离为固定值，因此可以用数组 dis[4] 记录四位字符分别的距离。

记 a, b, c, d 分别为选择第 i (0 <= i <= 3) 位字符的次数。以下四个公式成立，即可说明这种情况下可以从 s1 变换到 s2：

$2\ast (b+c+d)\mathrm{m}\mathrm{o}\mathrm{d}26=dis[0]$

$(2\ast a+3\ast (c+d))\mathrm{m}\mathrm{o}\mathrm{d}26=dis[1]$

$(3\ast (a+b)+5\ast d)\mathrm{m}\mathrm{o}\mathrm{d}26=dis[2]$

$5\ast (a+b+c)\mathrm{m}\mathrm{o}\mathrm{d}26=dis[3]$

所需变换次数为 $cnt=a+b+c+d$，取其中结果最小的即可。

代码实现

public int solve (String s1, String s2) {
int[] dis = new int[4];
for(int i = 0; i < 4; i++) dis[i] = (s2.charAt(i) - s1.charAt(i) + 26) % 26;
int res = 26 * 4;
for(int a = 0; a < 26; a++)
for(int b = 0; b < 26; b++)
for(int c = 0; c < 26; c++)
for(int d = 0; d < 26; d++)
if(dis[0] == 2 * (b + c + d) % 26 && dis[1] == (2 * a + 3* (c + d)) % 26 && dis[2] == (3 * (a + b) + 5 * d) % 26 && dis[3] == 5 * (a + b + c) % 26)
res = Math.min(res, a + b + c + d);
return res;
}

C. 卡牌问题

问题描述

有 $n\ast m$ 张牌叠在一起，称之为旧牌库。

牌由旧牌库底部的第一张从 1 开始编号，旧牌库顶的牌编号就是 $n\ast m$.

每张牌上有一个数字，设编号为 $i$ 的牌上的数字为 $a[i]$, 保证满足 $a[i]=((i-1)\mathrm{m}\mathrm{o}\mathrm{d}m)+1$。

现给出 $a$ 和 $b$，进行两个操作：

1、每次将旧牌库最底下的一张牌拿出来，放到旧牌库顶，重复 $a$ 次。

2、建一个新牌库，初始新牌库没有卡牌，每次先将旧牌库最底下的牌拿出来，放在新牌库顶，再将旧牌库最顶上的牌拿出来，放到新牌库顶，重复 $b$ 次，保证 $2\ast b\le n\ast m$，最后将旧牌库所有剩余卡牌直接放到新牌库顶。

再给出数字 $x$ 和 $y$，求新牌库从牌库底起第 $x$ 张牌到第 $y$ 张牌上的数字之和。

这个答案可能很大，输出答案对 998244353 取模后的结果。

备注:

输入包含 6 个整数 n, m, a, b, x, y，且保证数据一定合法可行。
输出一行，一个整数。
n <= 1e9; m <= 1e5; a <= n * m; b * 2 <= n * m; x <= y <= n * m

示例1

输入

4, 5, 17, 6, 3, 14

输出

39

示例2

输入

2, 3, 4, 1, 2, 5

输出

7

解法：前缀和

思路分析

乍看本题的小伙伴可能一头雾水，待本汪花 3 分钟细细讲解之后，小学生也能做出来！

咱们先分析新牌堆是什么样的，知道它长啥样，之后的计算思路就一目了然了。

依题意，原牌堆自底向上看牌上数字是这样一个序列：$(1,2,\dots ,m{)}^n$。

经过操作 1 之后，变成了牌堆 A ，序列为：$s_1,s_1+1,\dots ,m,(1,2,\dots ,m{)}^{n-1},1,2,\dots ,s_1-1$。其中 $s_1=a\mathrm{m}\mathrm{o}\mathrm{d}m+1$。

对牌堆 A 进行操作 2 之后，得到新牌堆。新牌堆可分成两个序列：$B_1,B_2$。

首先看 $B_1$，它包含了 $2b$ 张牌，并且奇数牌和偶数牌的规律如下：

1. 奇数牌：自底向上的第 $2k-1$ 张牌，对应牌堆 A 自底向上的第 $k$ 张牌。
2. 偶数牌：自底向上的第 $2k$ 张牌，对应牌堆 A 自顶向下的第 $k$ 张牌。

$B_2$ 就很简单了，序列为：$s_2,s_2+1,\dots ,m,1,2,\dots ,m,1,2,\dots$。其中 $s_2=(s_1-1+b)\mathrm{m}\mathrm{o}\mathrm{d}m+1$。

现在知道新牌堆长什么样了，很显然 $B_2$ 的部分和是很好计算的。

$B_1$ 相当于牌堆 A 前向和后向各数了 b 张牌。因此用前缀和+ 后缀和便可以计算出 $B_1$ 的部分和。

到这里，熟悉 前缀和 的小伙伴就可以自己动手写代码体验 AC 的快感了。不熟悉 前缀和 的小伙伴也别担心，贴心的往西汪只用 1 分钟就能给你讲的明明白白。

给定参数 $st,l$ ，分别代表序列的初始数字，和序列的长度。

1. 前缀和，计算序列 $st,st+1,\dots ,m,1,2,\dots ,m,1,2,\dots$ 的和。
2. 后缀和，计算序列 $st,st-1,\dots ,1,m,m-1,\dots ,1,m,m-1,\dots$ 的和。

针对序列 $B_1$，记 $sum(x)$ 表示区间 $[1,x]$ 的牌的数字和，$sum(x)=前缀和(st=s_1,l=\lceil r/2\rceil )+后缀和(st=s_1-1,l=\lfloor r/2\rfloor )$ 。

区间 $[x_1,x_2]$ 的和为：$sum(x_2)-sum(x_1-1)$。

至此本题再无难度。

代码实现

class Solution {
long m;
final long mod = 998244353;
public long work (long n, long m, long a, long b, long x, long y) {
this.m = m;
long res = 0;
long s1 = a % m + 1, s2 = (s1 - 1 + b) % m + 1;
if(x <= 2 * b){
res = modAdd(res, mod - b1Sum(s1, x - 1));
res = modAdd(res, b1Sum(s1, Math.min(2 * b, y)));
}
if(y > 2 * b){
res = modAdd(res, mod - b2Sum(s2, Math.max(2 * b, x - 1) - 2 * b));
res = modAdd(res, b2Sum(s2, y - 2 * b));
}
return res;
}
public long addTo(long l, long r){//计算[l, r]的区间和
if(r < l) return 0;
return ((l + r) * (r - l + 1) >> 1) % mod;
}
public long modAdd(long n1, long n2){
return (n1 + n2) < mod ? (n1 + n2) : (n1 + n2 - mod);
}
public long preSum(long st, long l){//这里的 l 表示序列长度
if(l <= 0) return 0;
if(l <= m - st + 1) return addTo(st, st + l - 1);
long k = (l - (m - st + 1)) / m;
long end = (l - (m - st + 1)) % m;
long res = modAdd(addTo(st, m), addTo(1, end));
return modAdd(res, (k * addTo(1, m)) % mod);
}
public long backSum(long st, long l){
if(l <= 0) return 0;
if(l <= st) return addTo(st - l + 1, st);
long k = (l - st) / m;
long end = m - ((l - st) % m) + 1;
long res = modAdd(addTo(1, st), addTo(end, m));
return modAdd(res, (k * addTo(1, m)) % mod);
}
public long b1Sum(long s1, long l){// l 表示序列长度
if(l <= 0) return 0;
long half = l >> 1;
return modAdd(preSum(s1, l - half), backSum(s1 - 1, half));
}
public long b2Sum(long s2, long l){
if(l <= 0) return 0;
return preSum(s2, l);
}
}

写在最后

大家好，我是往西汪，一位坚持原创的新人博主。
如果本文对你有帮助，请点赞、评论二连。你的支持是我创作路上的最大动力。
谢谢大家！
也欢迎来公众号【往西汪】找我玩耍～

最后

以上就是义气冰棍为你收集整理的算法题解 - 牛客编程巅峰赛S1第2场 - 黄金&钻石组A. 牛牛的 Fib 序列B. 破译密码C. 卡牌问题写在最后的全部内容，希望文章能够帮你解决算法题解 - 牛客编程巅峰赛S1第2场 - 黄金&钻石组A. 牛牛的 Fib 序列B. 破译密码C. 卡牌问题写在最后所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。