1354 lines
37 KiB
Markdown
1354 lines
37 KiB
Markdown
# D1 第十届蓝桥javaB组
|
||
|
||
## A组队 白给题
|
||
|
||
|
||
|
||
## B 不同字串 智障题 不多赘述
|
||
|
||
|
||
|
||
```java
|
||
import java.util.HashSet;
|
||
import java.util.Set;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
String s = "0100110001010001";
|
||
Set hashSet = new HashSet();
|
||
int n = 1;
|
||
while (n <= s.length()) {
|
||
for (int i =n; i <=s.length(); i++) {
|
||
String str = s.substring(i - n, i);
|
||
hashSet.add(str);
|
||
}
|
||
n++;
|
||
}
|
||
System.out.println(hashSet.size());
|
||
}
|
||
}
|
||
```
|
||
|
||
**hashset有去重的功能 ** 集合的知识点
|
||
|
||
# 第十一届蓝桥杯 javaB
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
import static java.lang.Math.abs;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
static int dir[][] = {{1,0}, {1, 1}};
|
||
static int[][] f = new int[105][105];
|
||
static int ans = 0;
|
||
static int n;
|
||
|
||
static void dfs(int x, int y, int sum, int left, int right) {
|
||
if (x == n && abs(left - right) <= 1) {
|
||
ans = Math.max(ans, sum);
|
||
return;
|
||
}
|
||
for (int i = 0; i < 2; i++) {
|
||
int nx = x + dir[i][0];
|
||
int ny = y + dir[i][1];
|
||
if (nx >= 1 && nx <= n && ny >= 1 && ny <= nx) {
|
||
if (i == 0) dfs(nx, ny, sum + f[nx][ny], left + 1, right);
|
||
else dfs(nx, ny, sum + f[nx][ny], left, right + 1);
|
||
}
|
||
}
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
// 去掉重复定义
|
||
n = sc.nextInt();
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = 1; j <= i; j++) {
|
||
f[i][j] = sc.nextInt();
|
||
}
|
||
}
|
||
// 从 (1, 1) 开始调用
|
||
dfs(1, 1, f[1][1], 0, 0);
|
||
System.out.println(ans);
|
||
}
|
||
|
||
}
|
||
```
|
||
|
||
## I 字串分值和
|
||
|
||
|
||
|
||
```java
|
||
利用hashset 来存字串不同的字符
|
||
|
||
import java.util.HashMap;
|
||
import java.util.HashSet;
|
||
import java.util.Scanner;
|
||
|
||
import static java.lang.Math.abs;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
String s= sc.nextLine();
|
||
int ans=0;
|
||
for(int i=0;i<s.length();i++){
|
||
HashSet<Character> set = new HashSet<>();
|
||
for(int j=i;j<s.length();j++){
|
||
set.add(s.charAt(j));
|
||
ans+=set.size();
|
||
}
|
||
}
|
||
System.out.println(ans);
|
||
}
|
||
|
||
}
|
||
```
|
||
|
||
# 第十二届蓝桥杯javaB组
|
||
|
||
## B卡片 数学
|
||
|
||
|
||
|
||
```
|
||
import java.util.Arrays;
|
||
// 1:无需package
|
||
// 2: 类名必须Main, 不可修改
|
||
|
||
public class Main {
|
||
|
||
public static void main(String[] args) {
|
||
int[] a = new int[10];
|
||
Arrays.fill(a, 3);
|
||
long num = 1;
|
||
boolean flag = true;
|
||
while (flag) {
|
||
char[] str = String.valueOf(num).toCharArray();
|
||
for (char c : str) {
|
||
if (a[c - '0'] <= 0) {
|
||
flag = false;
|
||
break;
|
||
} else {
|
||
a[c - '0']--;
|
||
}
|
||
}
|
||
num++;
|
||
}
|
||
System.out.println(num-2);
|
||
}
|
||
|
||
}
|
||
```
|
||
|
||
## D货物摆放 set集合的应用
|
||
|
||
|
||
|
||
```java
|
||
import java.util.HashSet;
|
||
import java.util.Set;
|
||
|
||
// 类名必须为 Main，不可修改
|
||
public class Main {
|
||
|
||
public static void main(String[] args) {
|
||
long end = 2021041820210418L;
|
||
long ans=0;
|
||
Set<Long>set = new HashSet<>();
|
||
for(long i=1;i*i<end;i++){
|
||
if(end%i==0){
|
||
set.add(i);
|
||
set.add(end/i);
|
||
}
|
||
}
|
||
for(Long i:set){
|
||
for(Long j:set){
|
||
for(Long k:set){
|
||
if(i*j*k==end){
|
||
ans++;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
System.out.println(ans);
|
||
}
|
||
}
|
||
```
|
||
|
||
# 第十三届蓝桥杯javaB
|
||
|
||
## A 星期计算 (白给题)
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
import static java.lang.Math.pow;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scanner = new Scanner(System.in);
|
||
int num=6;
|
||
int a=1;
|
||
for(int i=1;i<=22;i++){
|
||
a=(a*20)%7;
|
||
}
|
||
System.out.println(a+num);
|
||
}
|
||
}
|
||
```
|
||
|
||
## B 山 （回文串 + JAVA api）
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static boolean iscircle(int num) {
|
||
String str = String.valueOf(num);
|
||
String re=String.valueOf(new StringBuilder(str).reverse());
|
||
if(!str.equals(re))return false;
|
||
int len=(str.length()+1)/2;
|
||
char []c=str.toCharArray();
|
||
for(int i=1;i<len;i++){
|
||
if(c[i]<c[i-1])return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
Scanner scanner = new Scanner(System.in);
|
||
int num = 0;
|
||
for (int i = 2022; i <=2022222022; i++) {
|
||
if (iscircle(i)) {
|
||
num++;
|
||
}
|
||
}
|
||
System.out.println(num);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
## C字符统计 （白给题）
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
char[] ch = in.nextLine().toCharArray();
|
||
int[] arr = new int[26];
|
||
int max = 0;
|
||
for (int i = 0; i < ch.length; i++) {
|
||
arr[ch[i] - 'A']++;
|
||
max = Math.max(max, arr[ch[i] - 'A']);
|
||
}
|
||
for (int i = 0; i < arr.length; i++) {
|
||
if (arr[i] == max) {
|
||
System.out.print((char) (i + 'A'));
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
## D最少刷题数 （单调队列+二分查找）
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
```
|
||
|
||
```
|
||
|
||
|
||
|
||
## E 求阶乘 （模拟+二分）
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
public class Main {
|
||
static long f(int x){
|
||
int num=0;
|
||
while(x>0){
|
||
num+=x/5;
|
||
x/=5;
|
||
}
|
||
return num;
|
||
}
|
||
final static int N = (int)1e7 ;
|
||
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n = in.nextInt();
|
||
for(int i=1;i<=N;i++){
|
||
if(f(i)>=n){
|
||
if(f(i)==n){
|
||
System.out.println(i);
|
||
}else{
|
||
System.out.println(-1);
|
||
}
|
||
return;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
暴力解题
|
||
=======================
|
||
利用二分查找
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
static long f(long x) {
|
||
long num = 0;
|
||
while (x > 0) {
|
||
num += x / 5;
|
||
x /= 5;
|
||
}
|
||
return num;
|
||
}
|
||
|
||
final static long N = (long) 9e18;
|
||
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n = in.nextInt();
|
||
long l = 1, r = N;
|
||
while (l < r) {
|
||
long mid = (l + r) >> 1;
|
||
if(f(mid)>=n)r=mid;
|
||
else l=mid+1;
|
||
}
|
||
if(f(l)==n)System.out.println(l);
|
||
else System.out.println(-1);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
```JAVA
|
||
import java.util.Scanner;
|
||
|
||
|
||
去他娘的暴力解决一切
|
||
public class Main {
|
||
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n = in.nextInt();
|
||
int m = in.nextInt();
|
||
int[][] arr = new int[n + 1][m + 1];
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = 1; j <= m; j++) {
|
||
arr[i][j] = in.nextInt();
|
||
}
|
||
}
|
||
int ans = 0;
|
||
|
||
int limit = in.nextInt();
|
||
// 遍历所有可能的子矩阵左上角 (i, j)
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = 1; j <= m; j++) {
|
||
// 遍历所有可能的子矩阵右下角 (a, b)
|
||
for (int a = i+1; a <= n; a++) {
|
||
for (int b = j+1; b <= m; b++) {
|
||
int maxVal = Integer.MIN_VALUE;
|
||
int minVal = Integer.MAX_VALUE;
|
||
// 计算子矩阵的最大值和最小值
|
||
for (int x = i; x <= a; x++) {
|
||
for (int y = j; y <= b; y++) {
|
||
maxVal = Math.max(maxVal, arr[x][y]);
|
||
minVal = Math.min(minVal, arr[x][y]);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
System.out.println(ans);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
## F 最大子矩阵（窗口滑动问题 +双端队列 ）
|
||
|
||
|
||
|
||
```
|
||
窗口滑动问题 +双端队列
|
||
|
||
```
|
||
|
||
## **G 数组切分（线性DP 上升子序列问题？）**
|
||
|
||
题目描述
|
||
|
||
已知一个长度为 N 的数组：A1, A2, A3, ...AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
|
||
|
||
例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法：
|
||
|
||
{1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) **一段连续的自然数**。
|
||
|
||
{1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 **一段连续的自然数**，另外 {1} 和 {4} 显然也是。
|
||
|
||
{1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 **一段连续的自然数**，另外 {1} 显然也是。
|
||
|
||
{1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 **一段连续的自然数**，另外 {4} 显然也是。
|
||
|
||
{1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 **一段连续的自然数**。
|
||
|
||
输入格式
|
||
|
||
第一行包含一个整数 N。第二行包含 N 个整数，代表 A 数组。
|
||
|
||
输出格式
|
||
|
||
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
|
||
|
||
样例输入
|
||
|
||
```
|
||
4
|
||
1 3 2 4
|
||
```
|
||
|
||
样例输出
|
||
|
||
```
|
||
5
|
||
```
|
||
|
||
提示
|
||
|
||
对于 30% 评测用例，1 ≤ N ≤ 20.
|
||
|
||
对于 100% 评测用例，1 ≤ N ≤ 10000.
|
||
|
||
|
||
|
||
```java
|
||
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int n = sc.nextInt(), mod = (int) (1e9 + 7);
|
||
int[] arr = new int[n + 1], f = new int[n + 1];
|
||
for (int i = 1; i <= n; i++) arr[i] = sc.nextInt();
|
||
f[0] = 1;
|
||
for (int i = 1; i <= n; i++) {
|
||
int max = arr[i], min = arr[i];
|
||
for (int j = i; j > 0; j--) {
|
||
max = Math.max(max, arr[j]);
|
||
min = Math.min(min, arr[j]);
|
||
if (max - min == i - j) f[i] = (f[i] + f[j - 1]) % mod;
|
||
/**
|
||
* 假定当前处于第 i 个元素，你要考虑把数组从第 j 个元素到第 i 个元素划分成一个子数组（1 ≤ j ≤ i）。要是这个子数组（arr[j], arr[j + 1], ..., arr[i]）
|
||
* 里的整数可以构成一段连续的自然数，那么把前 i 个元素进行切分的方法数量，就等于把前 j - 1 个元素进行切分的方法数量。
|
||
* 具体说明如下：
|
||
* 若子数组 [j, i] 中的整数能构成一段连续的自然数，那么在计算前 i 个元素的切分方法时，就可以把前 j - 1 个元素的每一种切分方法与子数组 [j, i] 组合起来。
|
||
* 也就是说，前 j - 1 个元素的每一种切分方法，都能够通过添加子数组 [j, i] 得到前 i 个元素的一种切分方法。
|
||
* 而 f[j - 1] 代表的是前 j - 1 个元素的切分方法数量，所以当子数组 [j, i] 满足条件时，就可以把 f[j - 1] 累加到 f[i] 里。
|
||
*/
|
||
}
|
||
}
|
||
System.out.println(f[n]);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
|
||
|
||
# 第十四届蓝桥杯javaB
|
||
|
||
## A 阶乘求和（找规律 高进度）
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
## B 幸运数字 （模拟+进制转换）
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
|
||
static boolean ten(int x) {
|
||
int num=x;
|
||
int cnt = 0;
|
||
while (x > 0) {
|
||
cnt+=x%10;
|
||
x/=10;
|
||
}
|
||
return num%cnt==0;
|
||
}
|
||
static boolean eight(int x){
|
||
int num=x;
|
||
int cnt = 0;
|
||
while (x > 0) {
|
||
cnt+=x%8;
|
||
x/=8;
|
||
}
|
||
return num%cnt==0;
|
||
}
|
||
static boolean tow(int x){
|
||
int num=x;
|
||
int cnt = 0;
|
||
while (x > 0) {
|
||
cnt+=x%2;
|
||
x/=2;
|
||
}
|
||
return num%cnt==0;
|
||
}
|
||
|
||
static boolean sixteen(int x){
|
||
int num=x;
|
||
int cnt = 0;
|
||
while (x > 0) {
|
||
cnt+=x%16;
|
||
x/=16;
|
||
}
|
||
return num%cnt==0;
|
||
}
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int sum=0,i=0;
|
||
for(i=1;;i++){
|
||
if(ten(i)&&eight(i)&&sixteen(i)&&tow(i)){
|
||
System.out.println(i);
|
||
sum++;
|
||
}
|
||
if(sum==2023){
|
||
break;
|
||
}
|
||
}
|
||
System.out.println(i);
|
||
}
|
||
}
|
||
|
||
很简单的模拟+遍历
|
||
```
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
## **C:** 数组分割（数学+读题）
|
||
|
||
【问题描述】
|
||
小蓝有一个长度为 N 的数组 A = [ A 0 , A 1 , . . . , A N − 1 ] 。现在小蓝想要从 A 对应的数组下标所构成的集合 I = { 0 , 1 , 2 , . . . , N − 1 } 中找出一个子集 R 1 ，那么 R 1在 I 中的补集为 R 2 。记 S 1 = ∑ r ∈ R 1 A r ， S 2 = ∑ r ∈ R 2 A r，我们要求 S 1 和 S 2 均为 偶数，请问在这种情况下共有多少种不同的 R 1。当 R1 或 R 2 为空集时我们将 S 1 或 S 2 视为 0。
|
||
【输入格式】
|
||
第一行一个整数 T ，表示有 T 组数据。 接下来输入 T 组数据，每组数据包含两行：第一行一个整数 N ，表示数组 A 的长度；第二行输入 N 个整数从左至右依次为 A 0 , A 1 , . . . , A N − 1 ，相邻元素之 间用空格分隔。
|
||
【输出格式】
|
||
对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你
|
||
需要将答案对 1000000007 进行取模后输出。
|
||
【样例输入】
|
||
2
|
||
2
|
||
6 6
|
||
2
|
||
1 6
|
||
【样例输出】
|
||
4
|
||
0
|
||
|
||
```java
|
||
|
||
import java.math.BigInteger;
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
static BigInteger mod = new BigInteger("1000000007");
|
||
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int t = sc.nextInt();
|
||
while (t-- > 0) {
|
||
int n = sc.nextInt();
|
||
int odd = 0, even = 0;
|
||
for (int i = 0; i < n; i++) {
|
||
int x = sc.nextInt();
|
||
if (x % 2 == 0) {
|
||
even++;
|
||
} else {
|
||
odd++;
|
||
}
|
||
}
|
||
if (odd % 2 != 0) {
|
||
System.out.println(0);
|
||
continue;
|
||
}
|
||
even = even + (odd == 0 ? 0 : odd - 1);
|
||
BigInteger ans = new BigInteger("2");
|
||
BigInteger dp = new BigInteger("1");
|
||
|
||
for (long i = 1, j = even; i < even; i++, j--) { // 排列组合无顺序 C
|
||
BigInteger u = new BigInteger(String.valueOf(j));
|
||
BigInteger v = new BigInteger(String.valueOf(i));
|
||
dp = dp.multiply(u).divide(v);
|
||
ans = ans.add(dp);
|
||
}
|
||
System.out.println(ans.mod(mod));
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
|
||
|
||
## D、矩形总面积(数学)
|
||
|
||
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int x1 = sc.nextInt();
|
||
int y1 = sc.nextInt();
|
||
int x2 = sc.nextInt();
|
||
int y2 = sc.nextInt();
|
||
int x3 = sc.nextInt();
|
||
int y3 = sc.nextInt();
|
||
int x4 = sc.nextInt();
|
||
int y4 = sc.nextInt();
|
||
long area1 = (long) (x2 - x1) * (y2 - y1); // 计算第一个矩形的面积
|
||
long area2 = (long) (x4 - x3) * (y4 - y3); // 计算第二个矩形的面积
|
||
long overlapArea=0;
|
||
long l = Math.min(x2, x4) - Math.max(x1, x3);
|
||
long w= Math.min(y2,y4)-Math.max(y1,y3);
|
||
if (l >=0&&w >=0){
|
||
overlapArea= l * w;
|
||
}
|
||
long Area = area1 + area2 - overlapArea; // 总面积
|
||
System.out.println(Area); // 输出总面积
|
||
}
|
||
}
|
||
```
|
||
|
||
## E 蜗牛（动态规划）
|
||
|
||
这天，一只蜗牛来到了二维坐标系的原点。
|
||
|
||
在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0，横坐标分别为 x1, x2, ..., xn。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x 轴上或者竹竿上爬行，在 x 轴上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。
|
||
|
||
为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传送门（0 < i < n），如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)，就可以瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1, bi+1)，请计算蜗牛最少需要多少秒才能到达目的地。
|
||
|
||
输入格式
|
||
|
||
输入共 1 + n 行，第一行为一个正整数 n；
|
||
|
||
第二行为 n 个正整数 x1, x2, . . . , xn；
|
||
|
||
后面 n − 1 行，每行两个正整数 ai , bi+1。
|
||
|
||
输出格式
|
||
|
||
输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。
|
||
|
||
样例输入
|
||
|
||
```
|
||
3
|
||
1 10 11
|
||
1 1
|
||
2 1
|
||
```
|
||
|
||
样例输出
|
||
|
||
```
|
||
4.20
|
||
```
|
||
|
||
|
||
|
||
```java
|
||
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner sc = new Scanner(System.in);
|
||
int n = sc.nextInt();
|
||
int[] arr = new int[n+1];
|
||
for (int i = 1; i <= n; i++) arr[i] = sc.nextInt();
|
||
int []a=new int[n+1];
|
||
int []b=new int[n+1];
|
||
for(int i=1;i<n;i++){
|
||
a[i]=sc.nextInt();
|
||
b[i]=sc.nextInt();
|
||
}
|
||
double [][]dp=new double[n+1][2];//第 i 根杆子的最短用时，j 表示状态。 j=0表示走到底部 ，j=1表示走到传送门处
|
||
|
||
dp[1][0]=arr[1];
|
||
dp[1][1]=arr[1]+a[1]/0.7;
|
||
for(int i=2;i<=n;i++){
|
||
dp[i][0]=Math.min(dp[i-1][0]+arr[i]-arr[i-1],dp[i-1][1]+b[i-1]/1.3);
|
||
dp[i][1]=Math.min(dp[i][0]+a[i]/0.7,dp[i-1][1]+((b[i-1]>a[i])?(b[i-1]-a[i])/1.3: (a[i]-b[i-1])/0.7));
|
||
/**
|
||
* ((b[i-1]>a[i]) 前一个相比现在的高还是矮了
|
||
* (a[i]-b[i-1])/0.7) 向上爬
|
||
* (b[i-1]-a[i])/1.3 向下爬
|
||
*/
|
||
|
||
}
|
||
System.out.printf("%.2f",dp[n][0]);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
## F买二赠一（二分+贪心）
|
||
|
||
|
||
|
||
某商场有 N 件商品，其中第 i 件的价格是 Ai。现在该商场正在进行 “买二赠一” 的优惠活动，具体规则是：
|
||
|
||
每购买 2 件商品，假设其中较便宜的价格是 P（如果两件商品价格一样，则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P/2的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。
|
||
|
||
小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？
|
||
|
||
|
||
|
||
第一行包含一个整数 N。
|
||
|
||
第二行包含 N 个整数，代表 A1, A2, A3, . . . ，AN。
|
||
|
||
|
||
|
||
输出一个整数，代表答案。
|
||
|
||
|
||
|
||
```
|
||
7
|
||
1 4 2 8 5 7 1
|
||
```
|
||
|
||
|
||
|
||
```
|
||
25
|
||
```
|
||
|
||
```JAVA
|
||
import java.util.Arrays;
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
int n = in.nextInt();
|
||
int[] arr = new int[n];
|
||
for (int i = 0; i < n; i++)
|
||
arr[i] = in.nextInt();
|
||
long res = 0;
|
||
boolean[] flag = new boolean[n];
|
||
int item = 0;
|
||
Arrays.sort(arr);
|
||
int k = n - 1;
|
||
for (int i = n - 1; i >= 0; i--) {
|
||
if (flag[i]) continue;
|
||
item++;
|
||
if (item == 2) {
|
||
int l = 0;
|
||
int r = k;
|
||
while (l < r) {
|
||
int mid = l + r + 1 >> 1;
|
||
if (arr[mid] * 2 <= arr[i])
|
||
l = mid;
|
||
else r = mid - 1;
|
||
}
|
||
if (arr[l] * 2 <= arr[i]) {
|
||
flag[l] = true;//二分出的点可以报销，标记此点不需要统计答案；
|
||
k = r - 1;//二分临界端点左移
|
||
}
|
||
item = 0;
|
||
}
|
||
}
|
||
for (int i = 0; i < n; i++) if (!flag[i]) res += arr[i];//统计没有标记的答案，被标记过的都是报销价格的。
|
||
System.out.println(res);
|
||
|
||
}
|
||
}
|
||
|
||
|
||
```
|
||
|
||
|
||
|
||
|
||
|
||
## G合并石子（区间DP变形）
|
||
|
||
题目描述
|
||
|
||
在桌面从左至右横向摆放着 N 堆石子。每一堆石子都有着相同的颜色，颜色可能是颜色 0，颜色 1 或者颜色 2 中的其中一种。
|
||
|
||
现在要对石子进行合并，规定每次只能选择位置相邻并且颜色相同的两堆石子进行合并。合并后新堆的相对位置保持不变，新堆的石子数目为所选择的两堆石子数目之和，并且新堆石子的颜色也会发生循环式的变化。具体来说：两堆颜色 0 的石子合并后的石子堆为颜色 1，两堆颜色 1 的石子合并后的石子堆为颜色 2，两堆颜色 2 的石子合并后的石子堆为颜色 0。本次合并的花费为所选择的两堆石子的数目之和。
|
||
|
||
给出 N 堆石子以及他们的初始颜色，请问最少可以将它们合并为多少堆石子？如果有多种答案，选择其中合并总花费最小的一种，合并总花费指的是在所有的合并操作中产生的合并花费的总和。
|
||
|
||
输入格式
|
||
|
||
第一行一个正整数 N 表示石子堆数。
|
||
|
||
第二行包含 N 个用空格分隔的正整数，表示从左至右每一堆石子的数目。
|
||
|
||
第三行包含 N 个值为 0 或 1 或 2 的整数表示每堆石头的颜色。
|
||
|
||
输出格式
|
||
|
||
一行包含两个整数，用空格分隔。其中第一个整数表示合并后数目最少的石头堆数，第二个整数表示对应的最小花费。
|
||
|
||
样例输入
|
||
|
||
```
|
||
5
|
||
5 10 1 8 6
|
||
1 1 0 2 2
|
||
```
|
||
|
||
样例输出
|
||
|
||
```
|
||
2 44
|
||
```
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
static int N = 305;
|
||
static int n;
|
||
static int INF = (int) 1e9 + 7;
|
||
static int a[] = new int[N]; // 前缀和数组（a[i]表示前i堆石子总和）
|
||
static int w[][] = new int[N][N]; // w[i][j]表示合并区间[i,j]的最小总花费（无论颜色）
|
||
static int c[][] = new int[N][N]; // c[i][j]表示区间[i,j]合并后的最少堆数
|
||
static int f[][][] = new int[N][N][3]; // f[i][j][col]表示将区间[i,j]合并成颜色col的最小花费
|
||
|
||
public static void main(String[] args) {
|
||
Scanner in = new Scanner(System.in);
|
||
n = in.nextInt();
|
||
for (int i = 1; i <= n; i++) {
|
||
a[i] = in.nextInt() + a[i - 1]; // 计算前缀和
|
||
}
|
||
init();
|
||
for (int i = 1; i <= n; i++) {
|
||
int color = in.nextInt();
|
||
f[i][i][color] = 0; // 单堆无需合并，花费为0
|
||
}
|
||
|
||
for (int len = 1; len <= n; len++) {
|
||
for (int l = 1; l + len - 1 <= n; l++) {
|
||
int r = l + len - 1;
|
||
for (int color = 0; color <= 2; color++) {
|
||
// tmp 表示尝试将区间[l,r]合并成颜色(color+1)%3的最小花费
|
||
int tmp = INF;
|
||
for (int k = l; k < r; k++) {
|
||
if (f[l][k][color] != INF && f[k + 1][r][color] != INF) {
|
||
// 合并后的总花费 = 左区间花费 + 右区间花费 + 合并操作的花费（即总石子数）
|
||
tmp = Math.min(tmp, f[l][k][color] + f[k + 1][r][color] + a[r] - a[l - 1]);
|
||
}
|
||
}
|
||
if (tmp != INF) { // 如果存在合法合并方式
|
||
c[l][r] = 1; // 合并后堆数变为1
|
||
// 更新合并后的颜色为(color+1)%3的状态（因为两堆color合并后颜色会循环变化）
|
||
f[l][r][(color + 1) % 3] = Math.min(tmp, f[l][r][(color + 1) % 3]);
|
||
// 同时更新全局最小花费（无论颜色）
|
||
w[l][r] = Math.min(w[l][r], f[l][r][(color + 1) % 3]);
|
||
}
|
||
}
|
||
|
||
// 处理分割点：可能不合并成一堆，而是分割成两个子区间
|
||
// 此时需要更新c[l][r]和w[l][r]的可能更优解
|
||
for (int k = l; k < r; k++) {
|
||
// 如果分割后的堆数更少
|
||
if (c[l][r] > c[l][k] + c[k + 1][r]) {
|
||
c[l][r] = c[l][k] + c[k + 1][r]; // 更新最少堆数
|
||
w[l][r] = w[l][k] + w[k + 1][r]; // 更新总花费
|
||
} else if (c[l][r] == c[l][k] + c[k + 1][r]) {
|
||
// 堆数相同，取花费更小的方案
|
||
w[l][r] = Math.min(w[l][r], w[l][k] + w[k + 1][r]);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
System.out.println(c[1][n] + " " + w[1][n]);
|
||
}
|
||
|
||
static void init() {
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = i; j <= n; j++) {
|
||
c[i][j] = j - i + 1; // 初始化为未合并时的堆数
|
||
if (i != j) w[i][j] = INF; // 初始化花费为极大值（表示不可合并）
|
||
for (int color = 0; color <= 2; color++)
|
||
f[i][j][color] = INF; // 初始化所有颜色状态为不可达
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
#
|
||
|
||
|
||
|
||
# 第十五届蓝桥杯javaB
|
||
|
||
## A:报数游戏 （找规律）
|
||
|
||
|
||
|
||
```java
|
||
找规律 20的倍数是奇数 24的倍数是偶数
|
||
所以地2024202420242是24的倍数
|
||
```
|
||
|
||
## B：类斐波那契循环数（找规律+读题）
|
||
|
||
|
||
|
||
```
|
||
签到题目 就是把这个数放在数组中 然后按照题目给的要求算就是 如果》了当前的数 就false ==ture
|
||
```
|
||
|
||
```java
|
||
import java.util.ArrayList;
|
||
import java.util.List;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
for (int i = (int) 1e7; i > 0; i--) {
|
||
if (ans(i)) {
|
||
System.out.println(i);
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
public static boolean ans(int n) {
|
||
String num= Integer.toString(n);
|
||
ArrayList<Integer> arr=new ArrayList<>();
|
||
int len=num.length();
|
||
for (int i = 0; i < len; i++) {
|
||
arr.add(num.charAt(i)-'0');
|
||
}
|
||
while(true){
|
||
int sum=0;
|
||
for (int i = arr.size()-len; i < arr.size(); i++) {
|
||
sum+=arr.get(i);
|
||
}
|
||
arr.add(sum);
|
||
if(sum>n){return false;}
|
||
if(sum==n){return true;}
|
||
}
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
题目 3227:
|
||
|
||
## C:分布式队列
|
||
|
||
时间限制: 2s 内存限制: 512MB 提交: 2229 解决: 523
|
||
|
||
题目描述
|
||
|
||
小蓝最近学习了一种神奇的队列：分布式队列。简单来说，分布式队列包含 N 个节点（编号为 0 至 N − 1，其中 0 号为主节点），其中只有一个主节点，其余为副节点。主/副节点中都各自维护着一个队列，当往分布式队列中添加元素时都是由主节点完成的（每次都会添加元素到队列尾部）；副节点只负责同步主节点中的队列。可以认为主/副节点中的队列是一个长度无限的一维数组，下标为 0, 1, 2, 3 . . . ，同时副节点中的元素的同步顺序和主节点中的元素添加顺序保持一致。
|
||
|
||
由于副本的同步速度各异，因此为了保障数据的一致性，元素添加到主节点后，需要同步到所有的副节点后，才具有可见性。
|
||
|
||
给出一个分布式队列的运行状态，所有的操作都按输入顺序执行。你需要回答在某个时刻，队列中有多少个元素具有可见性。
|
||
|
||
输入格式
|
||
|
||
第一行包含一个整数 N，表示节点个数。接下来包含多行输入，每一行包含一个操作，操作类型共有以下三种：add、sync 和 query，各自的输入格式如下：
|
||
|
||
1. add element：表示这是一个添加操作，将元素 element 添加到队列中；
|
||
2. sync follower_id：表示这是一个同步操作，follower_id 号副节点会从主节点中同步下一个自己缺失的元素；
|
||
3. query：查询操作，询问当前分布式队列中有多少个元素具有可见性。
|
||
|
||
输出格式
|
||
|
||
对于每一个 query 操作，输出一行，包含一个整数表示答案。
|
||
|
||
样例输入
|
||
|
||
复制
|
||
|
||
```
|
||
3
|
||
add 1
|
||
add 2
|
||
query
|
||
add 1
|
||
sync 1
|
||
sync 1
|
||
sync 2
|
||
query
|
||
sync 1
|
||
query
|
||
sync 2
|
||
sync 2
|
||
sync 1
|
||
query
|
||
```
|
||
|
||
```java
|
||
这个题就是看你呢更不能读懂题目的含义了
|
||
该题目也属于基础题目，采用模拟的形式，这个题有一个小技巧在于查询操作只显示元素同步个数，所以添加add操作时，只需要在每次add时count+1，而不需要注意具体添加的是什么值。还有一个注意点是他的测试用例，1≤N≤10,所以直接定义大小为10的数组存储数量即可
|
||
|
||
package moni15;
|
||
|
||
|
||
//1:无需package
|
||
//2: 类名必须Main, 不可修改
|
||
|
||
//分布式队列
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scanner = new Scanner(System.in);
|
||
int n = scanner.nextInt();
|
||
int[] count = new int[n];
|
||
while(scanner.hasNext()) {
|
||
String str = scanner.next();
|
||
if(str.equals("add")) {
|
||
count[0]++;
|
||
continue;
|
||
}
|
||
if(str.equals("sync")) {
|
||
int num = scanner.nextInt();
|
||
//同步操作时，被同步的节点数量必须小于主节点
|
||
if(count[0] > count[num])count[num]++;
|
||
continue;
|
||
}
|
||
if(str.equals("query")) {
|
||
int m = Integer.MAX_VALUE;
|
||
for(int i = 0; i < n;i++) {
|
||
//可见数量即最小的元素
|
||
m = Math.min(m,count[i]);
|
||
}
|
||
System.out.println(m);
|
||
}
|
||
}
|
||
scanner.close();
|
||
}
|
||
}
|
||
```
|
||
|
||
## D:最优分组 （贪心）
|
||
|
||
S 学校里一共有 a2 个两人寝、a3 个三人寝，a4个四人寝，而食堂里有 b4个四人桌和 b6
|
||
个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐，请问这个食堂最多同时满足多少同学用餐？ 输入格式
|
||
|
||
采用多组数据输入。
|
||
|
||
输入共 q+1 行。
|
||
|
||
第一行为一个正整数 qq 表示数据组数。
|
||
|
||
后面 qq 行，每行五个非负整数 a2,a3,a4,b4,b6 表示一组数据。 输出格式
|
||
|
||
输出共 qq 行，每行一个整数表示对应输入数据的答案。 样例输入
|
||
|
||
2 3 0 1 0
|
||
|
||
样例输出
|
||
|
||
6
|
||
|
||
```java
|
||
优先坐满6人桌，再坐满4人桌。
|
||
先考虑配满情况 3+3 ，4 + 2， 2 + 2 + 2， 4，2+2
|
||
**再考虑不满配的情况 3 + 2 ，4装6，3装4 2装6 2装4
|
||
package moni15;
|
||
|
||
import java.util.Scanner;
|
||
|
||
//食堂
|
||
//贪心加暴力
|
||
public class Main4 {
|
||
public static void main(String[] args) {
|
||
Scanner scanner = new Scanner(System.in);
|
||
//在此输入您的代码...
|
||
int q = scanner.nextInt();
|
||
for(int i = 0;i < q;i++) {
|
||
int total = 0;
|
||
int a2 = scanner.nextInt();
|
||
int a3 = scanner.nextInt();
|
||
int a4 = scanner.nextInt();
|
||
|
||
int b4 = scanner.nextInt();
|
||
int b6 = scanner.nextInt();
|
||
//先考虑能配对情况
|
||
//先考虑六人桌
|
||
//再考虑四人桌
|
||
|
||
//3+3
|
||
while(a3 >= 2 && b6 >= 1) {
|
||
a3 = a3 - 2;
|
||
b6--;
|
||
total = total + 6;
|
||
}
|
||
//4+2
|
||
while(a4 >= 1 && a2 >= 1 && b6 >= 1) {
|
||
a4--;
|
||
a2--;
|
||
b6--;
|
||
total = total + 6;
|
||
}
|
||
//1个4
|
||
while(a4 >= 1 && b4 >= 1) {
|
||
a4--;
|
||
b4--;
|
||
total = total + 4;
|
||
}
|
||
//3个2
|
||
while(a2 >= 3 && b6 >= 1) {
|
||
a2 = a2 - 3;
|
||
b6--;
|
||
total = total + 6;
|
||
}
|
||
//2个2
|
||
while(a2 >= 2 && b4 >= 1) {
|
||
a2 = a2 - 2;
|
||
b4--;
|
||
total = total + 4;
|
||
}
|
||
|
||
//匹配不配对的情况
|
||
//1个3 一个2
|
||
while(a3 >= 1 && a2 >= 1 && b6 >= 1) {
|
||
a3--;
|
||
a2--;
|
||
b6--;
|
||
total = total + 5;
|
||
}
|
||
//一个4
|
||
while(a4 >= 1 && b6 >= 1) {
|
||
a4--;
|
||
b6--;
|
||
total = total + 4;
|
||
}
|
||
//一个3
|
||
while(a3 >= 1 && b4 >= 1) {
|
||
a3--;
|
||
b4--;
|
||
total = total + 3;
|
||
}
|
||
//一个3
|
||
while(a3 >= 1 && b6 >= 1) {
|
||
a3--;
|
||
b6--;
|
||
total = total + 3;
|
||
}
|
||
//一个2
|
||
while(a2 >= 1 && b6 >= 1) {
|
||
a2--;
|
||
b6--;
|
||
total = total + 2;
|
||
}
|
||
//一个2
|
||
while(a2 >= 1 && b4 >= 1) {
|
||
a2--;
|
||
b4--;
|
||
total = total + 2;
|
||
}
|
||
System.out.println(total);
|
||
}
|
||
scanner.close();
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
|
||
|
||
## E：最优分组（数学期望问题）
|
||
|
||
小蓝开了一家宠物店，最近有一种 X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。为了减少使用的测试剂数目，小蓝想到了一个好方法：将 N 个宠物平均分为若干组，使得每组恰好有 K 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有 K 只宠物单独检测，需要再消耗 K 支测试剂（当 K = 1 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。
|
||
|
||
现在我们已知小蓝的宠物被感染的概率为 p，请问 K 应该取值为多少才能使得期望的测试剂的消耗数目最少？如果有多个答案输出最小的 K。
|
||
|
||
输入格式
|
||
|
||
第一行，一个整数 N。
|
||
|
||
第二行，一个浮点数 p。
|
||
|
||
输出格式
|
||
|
||
输出一行，一个整数 K 表示答案。
|
||
|
||
样例输入
|
||
|
||
```
|
||
1000
|
||
0.05
|
||
```
|
||
|
||
样例输出
|
||
|
||
```
|
||
5
|
||
```
|
||
|
||
```java
|
||
|
||
就是数学期望问题 至少一个狗 感染是P E(X)=1*K+(1-(1-P)^K)*K
|
||
所以说 要用的试剂的期望就是 (1-(1-p)^k)*k*(n/k)+n/k
|
||
然后比大小就可以了
|
||
import java.util.*;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner in=new Scanner(System.in);
|
||
double a=in.nextInt();
|
||
double p=in.nextDouble();
|
||
int best=0;
|
||
double min=Double.MAX_VALUE;
|
||
for(int i=1;i<=a;i++){
|
||
if(a%i==0){
|
||
double res=(1-Math.pow((1-p),i)*i*a/i+a/i);
|
||
if(res<min){
|
||
min=res;
|
||
best=i;
|
||
}
|
||
}
|
||
}
|
||
System.out.println(best);
|
||
}
|
||
}
|
||
```
|
||
|
||
## F:**星际旅行（图论？）**
|
||
|
||
题目描述
|
||
|
||
小明国庆节准备去某星系进行星际旅行，这个星系里一共有 n 个星球，其中布置了 m 道双向传送门，第 i 道传送门可以连接 ai，bi 两颗星球（ai , bi 且任意两颗星球之间最多只有一个传送门）。
|
||
|
||
他看中了一款 “旅游盲盒”，一共有 Q 个盲盒，第 i 个盲盒里的旅行方案规定了旅行的起始星球 xi 和最多可以使用传送门的次数 yi。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。
|
||
|
||
小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道**能旅行到的不同星球的数量**的期望是多少。
|
||
|
||
输入格式
|
||
|
||
输入共 m + Q + 1 行。
|
||
|
||
第一行为三个正整数 n，m，Q。
|
||
|
||
后面 m 行，每行两个正整数 ai，bi。
|
||
|
||
后面 Q 行，每行两个整数 xi，yi。
|
||
|
||
输出格式
|
||
|
||
输出共一行，一个浮点数（四舍五入保留两位小数）。
|
||
|
||
样例输入
|
||
|
||
复制
|
||
|
||
```
|
||
3 2 3
|
||
1 2
|
||
2 3
|
||
2 1
|
||
2 0
|
||
1 1
|
||
```
|
||
|
||
样例输出
|
||
|
||
复制
|
||
|
||
```
|
||
2.00
|
||
```
|
||
|
||
提示
|
||
|
||
【样例说明】
|
||
|
||
第一个盲盒可以旅行到 1, 2, 3。
|
||
|
||
第二个盲盒可以旅行到 2。
|
||
|
||
第三个盲盒可以旅行到 1, 2。
|
||
|
||
所以期望是 (3 + 1 + 2)/3 = 2.00。
|
||
|
||
【评测用例规模与约定】
|
||
|
||
对于 20% 的评测用例，保证 n ≤ 300。
|
||
|
||
对于 100% 的评测用例，保证 n ≤ 1000，m ≤ min{n(n−1)/2, 5n}，Q ≤ 50000，0 ≤ yi ≤ n。
|
||
|
||
```
|
||
暂时不会 图论的知识了
|
||
|
||
```
|
||
|
||
|
||
|
||
|
||
|
||
## H：拼十字（暴力拿9分 啊啊啊啊啊）
|
||
|
||
|