北京建设规划许可证网站,黑帽seo软件,如何提高网站的访问速度,单页网站上传教程视频[蓝桥杯 2013 省 B] 连号区间数
题目描述
小明这些天一直在思考这样一个奇怪而有趣的问题#xff1a;
在 111 ~ NNN 的某个全排列中有多少个连号区间呢#xff1f;这里所说的连号区间的定义是#xff1a;
如果区间 [L,R][L, R][L,R] 里的所有元素#xff08;即此排列的…[蓝桥杯 2013 省 B] 连号区间数
题目描述
小明这些天一直在思考这样一个奇怪而有趣的问题
在 111 ~ NNN 的某个全排列中有多少个连号区间呢这里所说的连号区间的定义是
如果区间 [L,R][L, R][L,R] 里的所有元素即此排列的第 LLL个到第 RRR 个元素递增排序后能得到一个长度为 R−L1R-L1R−L1 的“连续”数列则称这个区间连号区间。
当 NNN 很小的时候小明可以很快地算出答案但是当 NNN 变大的时候问题就不是那么简单了现在小明需要你的帮助。
输入格式
第一行是一个正整数 N(1≤N≤50000)N (1 \le N \le 50000)N(1≤N≤50000) 表示全排列的规模。
第二行是 NNN 个不同的数字 Pi(1≤Pi≤N)P_i(1 \le P_i \le N)Pi(1≤Pi≤N) 表示这 NNN 个数字的某一全排列。
输出格式
输出一个整数表示不同连号区间的数目。
样例 #1
样例输入 #1
4
3 2 4 1样例输出 #1
7样例 #2
样例输入 #2
5
3 4 2 5 1样例输出 #2
9提示
第一个用例中有 777 个连号区间分别是[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]。
第二个用例中有 999 个连号区间分别是[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-minb-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 型饮料凭 333 个瓶盖可以再换一瓶 C 型饮料并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下如果小明不浪费瓶盖尽量地参加活动那么对于他初始买入的 nnn 瓶饮料最后他一共能喝到多少瓶饮料。
输入格式
一个整数 nnn表示开始购买的饮料数量。0n100000n100000n10000
输出格式
一个整数表示实际得到的饮料数。
样例 #1
样例输入 #1
100样例输出 #1
149样例 #2
样例输入 #2
101样例输出 #2
151提示
2015 年蓝桥杯省赛 A 组 H 题。
分析
这道题主要是要求思路清晰直接去算就可以先喝完手中的饮料resn剩下n个瓶盖三个饮料盖可以换一瓶饮料那么我们就又可以喝n/3瓶饮料每次我们喝过饮料后会剩下 n/3n%3个瓶盖我们只需要不断重复过程直至n3
代码实现
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(n3){resn/3;n n / 3 n%3;}System.out.println(res);}
}[蓝桥杯 2014 省 AB] 地宫取宝
题目描述
X 国王有一个地宫宝库。是 n×mn \times mn×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角出口在右下角。
小明被带到地宫的入口国王要求他只能向右或向下行走。
走过某个格子时如果那个格子中的宝贝价值比小明手中任意宝贝价值都大小明就可以拿起它当然也可以不拿。
当小明走到出口时如果他手中的宝贝恰好是 kkk 件则这些宝贝就可以送给小明。
请你帮小明算一算在给定的局面下他有多少种不同的行动方案能获得这 kkk 件宝贝。
输入格式
输入一行 333 个整数用空格分开nnnmmmk(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)。
接下来有 nnn 行数据每行有 mmm 个整数 Ci(0≤Ci≤12)C_i(0 \le C_i \le 12)Ci(0≤Ci≤12) 代表这个格子上的宝物的价值。
输出格式
要求输出一个整数表示正好取 kkk 个宝贝的行动方案数。该数字可能很大输出它对 1000000007(1097)1000000007(10^97)1000000007(1097) 取模的结果。
样例 #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(i1 j1) 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(u0 vw[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);}
}
