[蓝桥杯 2013 省 B] 连号区间数

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 $1$ ~ $N$ 的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：

如果区间 $[L,R]$ 里的所有元素（即此排列的第 $L$个到第 $R$ 个元素）递增排序后能得到一个长度为 $R-L+1$ 的“连续”数列，则称这个区间连号区间。

当 $N$ 很小的时候，小明可以很快地算出答案，但是当 $N$ 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 $N(1\le N\le 50000)$， 表示全排列的规模。

第二行是 $N$ 个不同的数字 $P_i(1\le P_i\le N)$， 表示这 $N$ 个数字的某一全排列。

输出格式

输出一个整数，表示不同连号区间的数目。

样例 #1

样例输入 #1

4
3 2 4 1

样例输出 #1

7

样例 #2

样例输入 #2

5
3 4 2 5 1

样例输出 #2

9

提示

第一个用例中，有 $7$ 个连号区间分别是：$[1,1]$, $[1,2]$, $[1,3]$, $[1,4]$, $[2,2]$, $[3,3]$, $[4,4]$。

第二个用例中，有 $9$ 个连号区间分别是：$[1,1]$, $[1,2]$, $[1,3]$, $[1,4]$, $[1,5]$, $[2,2]$, $[3,3]$, $[4,4]$, $[5,5]$。

原题时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛

分析

题目要求的是连续号区间数，因为这个题目的数据有个特点，就是数据不重复，所以如果说某个区间是连续的，那么这个区间的最大值-最小数必须等于下标差即(max-min==b-a)如果满足这个，则说明(a,b)为连续区间,将res++即可。那么如何求取每个区间的最大和最小值呢，我们不妨定下l，不断地去枚举r，这样我们只需要每次比较最大最小值和新加入元素的大小即可。

代码实现

import java.util.*;
public class Main{static int N = 10010;static int[] a = new int[N];public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();for(int i = 1; i <= n;i++) a[i]=scan.nextInt();int res = 0;for(int i = 1;i <= n;i++){int minv = Integer.MAX_VALUE;int maxv = Integer.MIN_VALUE;for(int j = i;j <= n;j++){minv = Math.min(minv, a[j]);maxv = Math.max(maxv, a[j]);if(maxv - minv == j - i) res ++;}}System.out.println(res);}
}

[蓝桥杯 2015 省 A] 饮料换购

题目描述

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料，凭 $3$ 个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 $n$ 瓶饮料，最后他一共能喝到多少瓶饮料。

输入格式

一个整数 $n$，表示开始购买的饮料数量。（$0<n<10000$）

输出格式

一个整数，表示实际得到的饮料数。

样例 #1

样例输入 #1

100

样例输出 #1

149

样例 #2

样例输入 #2

101

样例输出 #2

151

提示

2015 年蓝桥杯省赛 A 组 H 题。

分析

这道题主要是要求思路清晰，直接去算就可以，先喝完手中的饮料，res+=n，剩下n个瓶盖，三个饮料盖可以换一瓶饮料，那么我们就又可以喝n/3瓶饮料，每次我们喝过饮料后会剩下 n/3+n%3个瓶盖，我们只需要不断重复过程，直至n<3

代码实现

import java.util.*;
public class Main{public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();int res = n;while(n>=3){res+=n/3;n = n / 3 + n%3;}System.out.println(res);}
}

[蓝桥杯 2014 省 AB] 地宫取宝

题目描述

X 国王有一个地宫宝库。是 $n\times m$ 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。

输入格式

输入一行 $3$ 个整数，用空格分开：$n$，$m$，$k(1\le n,m\le 50,1\le k\le 12)$。

接下来有 $n$ 行数据，每行有 $m$ 个整数 $C_i(0\le C_i\le 12)$ 代表这个格子上的宝物的价值。

输出格式

要求输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。该数字可能很大，输出它对 $1000000007(10^9+7)$ 取模的结果。

样例 #1

样例输入 #1

2 2 2
1 2
2 1

样例输出 #1

2

样例 #2

样例输入 #2

2 3 2
1 2 3
2 1 5

样例输出 #2

14

提示

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛

分析

很明显的dp问题，我们将每个状态划分：

当走到某个格子上的时候：
（1）如果格子上宝贝的价值大于已有宝贝的最大值，那么可以选择拿或者不拿
（2）如果格子上宝贝的价值小于或者等于已有宝贝的最大值，那么只能选择不拿。
必须从左上角走到右下角，且只要到达右下角时物品个数满足条件即算一种方案。
只能选择向下或者向右走
不是必须到出口时，宝贝数量恰好满足条件，而是可以在任意位置就宝贝数量就可以满足条件，只需保证到达出口时宝贝数量仍然满足条件即可

import java.util.Scanner;public class Main {public static void main(String[] args) {int N = 55;int w[][] = new int[N][N];int f[][][][] = new int[N][N][13][14];//所有从起点走到(i, j)，且已经取了k件物品，且最后一件物品的价值是C的合法方案的集合。int mod = 1000000007;Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {w[i][j] = sc.nextInt();w[i][j]++;//为了初始化，因为最终统计的是方法数}}f[1][1][1][w[1][1]] = 1;f[1][1][0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if(i==1 && j==1) continue;for (int u = 0; u <= k; u++) {for (int v = 0; v <= 13; v++) {f[i][j][u][v] = (f[i][j][u][v]+f[i-1][j][u][v])%mod;//最后一步是从上往下走，并且不取这个宝贝f[i][j][u][v] = (f[i][j][u][v]+f[i][j-1][u][v])%mod;//最后一步是从左往右走，并且不取这个宝贝if(u>0 && v==w[i][j])当前的方案数量=上一步的所有价值的方案数量之和{for (int c = 0; c < v; c++) {f[i][j][u][v] = (f[i][j][u][v] + f[i-1][j][u-1][c])%mod;//最后一步是从上往下走，并且取这个宝贝f[i][j][u][v] = (f[i][j][u][v] + f[i][j-1][u-1][c])%mod;//最后一步是从左往右走，并且不取这个宝贝}}}}}}int res = 0;for (int i = 0; i <= 13; i++) {res = (res + f[n][m][k][i])%mod;}System.out.println(res);}
}