乐趣区

关于java:算法题解-牛客编程巅峰赛S1第2场-黄金钻石组

A. 牛牛的 Fib 序列

题目形容

牛牛从新定义了斐波那契数列,牛牛定义 $f(n) = f(n-1) + f(n+1), f(1) = a, f(2) = b$,当初给定初始值 $a, b$,当初求第 $n$ 项 $f(n) \mod 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(log_426^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 * (b + c + d) \mod 26 = dis[0]$

$(2 * a + 3* (c + d)) \mod 26 = dis[1]$

$(3 * (a + b) + 5 * d) \mod 26 = dis[2]$

$5 * (a + b + c) \mod 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 * m$ 张牌叠在一起,称之为旧牌库。

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

每张牌上有一个数字,设编号为 $i$ 的牌上的数字为 $a[i]$, 保障满足 $a[i] = ((i – 1) \mod m) + 1$。

现给出 $a$ 和 $b$,进行两个操作:

1、每次将旧牌库最底下的一张牌拿进去,放到旧牌库顶,反复 $a$ 次。

2、建一个新牌库,初始新牌库没有卡牌,每次先将旧牌库最底下的牌拿进去,放在新牌库顶,再将旧牌库最顶上的牌拿进去,放到新牌库顶,反复 $b$ 次,保障 $2*b \le n*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, …, m)^n$。

通过操作 1 之后,变成了牌堆 A,序列为:$s_1, s_1 + 1, …, m, (1, 2, …, m)^{n-1}, 1, 2, …, s_1-1$。其中 $s_1 = a \mod 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, …, m, 1, 2, …, m, 1, 2, …$。其中 $s_2 = (s_1 – 1 + b) \mod m + 1$。

当初晓得新牌堆长什么样了,很显然 $B_2$ 的局部和是很好计算的。

$B_1$ 相当于牌堆 A 前向和后向各数了 b 张牌。因而用 前缀和 + 后缀和 便能够计算出 $B_1$ 的局部和。

到这里,相熟 前缀和 的小伙伴就能够本人入手写代码体验 AC 的快感了。不相熟 前缀和 的小伙伴也别放心,贴心的 往西汪 只用 1 分钟就能给你讲的明明白白。

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

  1. 前缀和,计算序列 $st, st + 1, …, m, 1, 2, …, m, 1, 2, …$ 的和。
  2. 后缀和,计算序列 $st, st − 1, …, 1, m, m−1, …, 1, m, m−1, …$ 的和。

针对序列 $B_1$,记 $sum(x)$ 示意区间 $[1, x]$ 的牌的数字和,$sum(x) = 前缀和(st = s_1, l = ⌈r/2⌉) + 后缀和(st = s_1 – 1, l = ⌊r/2⌋)$。

区间 $[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);
    }
}

写在最初

大家好,我是往西汪,一位保持原创的新人博主。
如果本文对你有帮忙,请点赞、评论二连。你的反对是我创作路上的最大能源。
谢谢大家!
也欢送来公众号【往西汪】找我游玩~

退出移动版