©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>[蓝桥杯 2013 省 B] 连号区间数
<>题目描述
小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1 1 1 ~ N N N 的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：
如果区间 [ L , R ] [L, R] [L,R] 里的所有元素（即此排列的第 L L L个到第 R R R 个元素）递增排序后能得到一个长度为
R − L + 1 R-L+1R−L+1 的“连续”数列，则称这个区间连号区间。
当 N N N 很小的时候，小明可以很快地算出答案，但是当 N N N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
<>输入格式
第一行是一个正整数 N ( 1 ≤ N ≤ 50000 ) N (1 \le N \le 50000) N(1≤N≤50000)， 表示全排列的规模。
第二行是 N N N 个不同的数字 P i ( 1 ≤ P i ≤ N ) P_i(1 \le P_i \le N) Pi(1≤Pi≤N)， 表示这
N NN 个数字的某一全排列。
<>输出格式
输出一个整数，表示不同连号区间的数目。
<>样例 #1
<>样例输入 #1
4 3 2 4 1
<>样例输出 #1
7
<>样例 #2
<>样例输入 #2
5 3 4 2 5 1
<>样例输出 #2
9
<>提示
第一个用例中，有 7 7 7 个连号区间分别是： [ 1 , 1 ] [1,1] [1,1], [ 1 , 2 ] [1,2] [1,2], [ 1
, 3 ] [1,3][1,3], [ 1 , 4 ] [1,4] [1,4], [ 2 , 2 ] [2,2] [2,2], [ 3 , 3 ]
[3,3][3,3], [ 4 , 4 ] [4,4] [4,4]。
第二个用例中，有 9 9 9 个连号区间分别是： [ 1 , 1 ] [1,1] [1,1], [ 1 , 2 ] [1,2] [1,2], [ 1
, 3 ] [1,3][1,3], [ 1 , 4 ] [1,4] [1,4], [ 1 , 5 ] [1,5] [1,5], [ 2 , 2 ]
[2,2][2,2], [ 3 , 3 ] [3,3] [3,3], [ 4 , 4 ] [4,4] [4,4], [ 5 , 5 ] [5,5] [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 3 3 个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n n n 瓶饮料，最后他一共能喝到多少瓶饮料。
<>输入格式
一个整数 n n n，表示开始购买的饮料数量。（ 0 < n < 10000 0<n<10000 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 × m n \times m n×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k k k 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k k k 件宝贝。
<>输入格式
输入一行 3 3 3 个整数，用空格分开： n n n， m m m， k ( 1 ≤ n , m ≤ 50 , 1 ≤ k ≤ 12 ) k(1 \le
n,m \le 50,1 \le k \le 12)k(1≤n,m≤50,1≤k≤12)。
接下来有 n n n 行数据，每行有 m m m 个整数 C i ( 0 ≤ C i ≤ 12 ) C_i(0 \le C_i \le 12) Ci(
0≤Ci≤12) 代表这个格子上的宝物的价值。
<>输出格式
要求输出一个整数，表示正好取 k k k 个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 ( 1 0 9 + 7 )
1000000007(10^9+7)1000000007(109+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); } }