A. 牛牛扔牌

题目形容

牛牛当初有 n 张扑克牌，每张扑克牌都有点数和花色两局部组成。点数为‘1’–‘9’的正整数，花色为 ‘C’, ‘D’, ‘H’, ‘S’ 其中的一个，别离示意梅花、方块、红桃、黑桃。当初牛牛想按肯定的程序把这 n 张牌扔掉。扔牌程序的规定如下：

1. 如果当初还剩素数张牌，则将牌顶的牌扔掉
2. 如果当初还剩非素数张牌，则将牌底的牌扔掉

牛牛想晓得他的扔牌程序是什么，请返回扔牌程序的字符串

备注:

对于 100% 的数据，1 ≤ n ≤ 10。

示例 1

输出

"3C8D6H3D"

输入

"3D3C8D6H"

阐明

开始 n = 4，为非素数，扔掉牌底的牌 3D
n = 3，为素数，扔掉牌顶的牌 3C
n = 2，为素数，扔掉牌顶的牌 8D
n = 1，为非素数，扔掉牌底的牌 6H

示例 2

输出

"8S8S8S8S8S8S8S"

输入

"8S8S8S8S8S8S8S"

阐明

因为全是 8S，所以扔牌程序的每一张牌也都是 8S

解法

思路剖析

因为 n 在 [1, 10] 上，故本题间接把所有素数列出来即可。没什么难度。

工夫复杂度：O(n)

空间复杂度：O(n)

代码实现

/**
 * 
 * @param x string 字符串 字符串从前到后别离是从上到下排列的 n 张扑克牌
 * @return string 字符串
 */
public String Orderofpoker (String x) {int n = x.length() / 2;
    int top = 0, bot = x.length() - 2;
    String res = "";
    while(n > 0){if(n == 2 || n == 3 || n == 5 || n == 7){res += x.substring(top, top + 2);
            top += 2;
        }else{res += x.substring(bot, bot + 2);
            bot -= 2;
        }
        n--;
    }
    return res;
}

B. 疯狂过山车

题目形容

明天牛牛去游乐园玩过山车我的项目，他感觉过山车在上坡下坡的过程是十分刺激的，回到家之后就受到启发，想到了一个问题。如果把整个过山车的轨道当作是一个长度为 n 的数组 num，那么在过山车上坡时数组中的值是出现递增趋势的，到了最高点当前，数组中的值出现递加的趋势，牛牛把合乎这样先增后减法则的数组定义为金字塔数组，请你帮牛牛在整个 num 数组中找出长度最长的金字塔数组，如果金字塔数组不存在，请输入 0。

备注:

1 <= n <= 1000000，且 num 数组中的数 0 <= num[i] <= 1000000。

示例 1

输出

4,[1,2,3,1]

输入

4

示例 2

输出

5,[1,5,3,3,1]

输入

3

解法一：直观解法

思路剖析

在遍历的时候判断是否是金字塔数组即可。以后数字 i 和前一个数字 j 比拟有三种状况：

1. i > j，阐明数组处于俯冲阶段，若 j 是低谷则对长度 len 初始化为 1。len++。
2. i = j，必然不是金字塔，初始化 len 为 1。
3. i < j，若之前处于俯冲阶段，阐明是金字塔，len++，并且和金字塔最大长度 res 作比拟。

工夫复杂度：O(n)

空间复杂度：O(1)

代码实现

/**
 * 
 * @param n int 整型 
 * @param num int 整型一维数组 
 * @return int 整型
 */
public int getMaxLength (int n, int[] num) {
  // write code here
  int res = 0;
  int len = 1;
  boolean up = false;
  for(int i = 1; i < n; i++) {if(num[i] > num[i - 1]) {
      up = true;
      if(i > 1 && num[i - 1] < num[i - 2]) len = 1;
      len++;
    }else if(num[i] == num[i - 1]) {
      len = 1;
      up = false;
    }else {if(up) {
        len++;
        res = Math.max(len, res);
      }
    }
  }
  return res;
}

解法二：寻找金字塔顶法

思路剖析

金字塔数组长度 = 俯冲阶段长度 + 1 (塔顶) + 降落阶段长度。

而 降落阶段 相当于 从右往左遍历时的俯冲阶段。

因而别离用 l 数组 和 r 数组 记录 从左到右 和从右到左 的俯冲阶段长度。

若 l[i] 和 r[i] 都不为 0，阐明 i 是塔顶。

工夫复杂度：O(n)

空间复杂度：O(n)

代码实现

/**
 * 
 * @param n int 整型 
 * @param num int 整型一维数组 
 * @return int 整型
 */
public int getMaxLength (int n, int[] num) {
  int res = 0;
  int[] l = new int[n];
  int[] r = new int[n];
  for(int i = 1; i < n; i++){if(num[i] > num[i - 1]) l[i] = l[i - 1] + 1;
  }
  for(int i = n - 2; i >= 0; i--){if(num[i] > num[i + 1]) r[i] = r[i + 1] + 1;
  }
  for(int i = 0; i < n; i++){if(l[i] != 0 && r[i] != 0) res = Math.max(res, l[i] + r[i] + 1);
  }
  return res;
}

C. 牛牛的棋盘

题目形容

牛牛最近在家里看到一个棋盘，有 n m 个格子，在棋盘旁边还放着 k 颗棋子，牛牛想把这 k 颗棋子全副放在 n m 的棋盘上，然而有一个限度条件：棋盘的第一行、第一列、最初一行和最初一列都必须有棋子。牛牛想晓得这样的棋子放法到底有多少种，答案须要对 1e9 + 7取模。

备注:

2 <= n, m <= 30; 1 <= k <=1000

示例 1

输出

2,3,1

输入

0

阐明

就 1 颗棋子，所以无奈满足条件。

示例 2

输出

2,2,2

输入

2

阐明

咱们能够把第 1 颗棋子放在左上角，第 2 颗棋子放在右下角；也能够把第 1 颗棋子放在右上角，第 2 颗棋子放在左下角。故而有 2 种放法。

解法：容斥原理

思路剖析

本题须要具备高中的数学知识：容斥原理和排列组合数。波及的数学公式会在题解中给出，如果有看不明确的中央能够自行查问相干数学概念。

记行 i 上无棋子的汇合为 $S_{ri}$，列 j 上无棋子的汇合为 $S_{cj}$。依据容斥原理，有

$$
\begin{aligned}
res &= ∣S_{r1} ∩ S_{rn} ∩ S_{c1} ∩ S_{cm}∣ \hspace{100cm}\\
&= all – |S_{r1} ∪ S_{rn} ∪ S_{c1} ∪ S_{cm}∣\\
&= all – \sum_{C \subseteq U}(-1)^{size(C) – 1}|\cap_{e \in C} e|
\end{aligned}
$$

其中，$U = \{S_{r1}, S_{rn}, S_{c1}, S_{cm}\}$。

因为 $U$ 中只蕴含四个汇合，因而能够用 4 个 bit 别离示意是否交汇合 $S_i$。

总共有 $2^4 – 1 = 15$ 种交加状况，再加上 all，共计 16 种状况。

排列组合数能够利用公式 $C_m^n = C_{m – 1}^n + C_{m – 1}^{n – 1}$ 迭代计算得出。

代码实现

final int mod = (int)1e9 + 7;
/**
 * 
 * @param n int 整型 
 * @param m int 整型 
 * @param k int 整型 
 * @return int 整型
 */
public int solve (int n, int m, int k) {if(k < 2) return 0;
  int[][] C = initC();
  int res = 0;
  for(int i = 0; i < 16; i++){
    int r = n, c = m, cnt = 0;
    if((i & 1) != 0) {r--; cnt++;}
    if((i & 2) != 0) {r--; cnt++;}
    if((i & 4) != 0) {c--; cnt++;}
    if((i & 8) != 0) {c--; cnt++;}
    res = (res - ((cnt & 1) * 2 - 1) * C[r * c][k]) % mod;
  }
  return (res + mod) % mod;
}

public int[][] initC(){
  int n = 1000;
  int[][] C = new int[1001][1001];
  for(int i = 1; i <= n; i++) C[i][0] = C[i][i] = 1;
  for(int i = 2; i <= n; i++){for(int j = 1; j < i; j++){C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
  }
  return C;
}

写在最初

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