第十二届蓝桥杯JavaB组省赛题解
1.ASC
76
2.卡片
public class Main {
static int[] num = {2021,2021,2021,2021,2021,2021,2021,2021,2021,2021};
static int check(int x){
while(x > 0){
int now = x % 10;
if(num[now] > 0) num[now]--;
else return 0;
x /= 10;
}
return 1;
}
public static void main(String[] args) {
for(int i = 1;;i++){
if(check(i) == 0){
System.out.println(i - 1);
break;
}
}
}
}
3.直线
import java.util.*;
public class Main {
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
Set<String> ans = new HashSet<>();
int x = 19, y = 20;
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= y; j++) {
set.add(i * 100 + j);
}
}
List<Integer> arr = new ArrayList<>(set);
int len = arr.size();
for (int i = 0; i < len; i++) {
int a = arr.get(i);
for (int j = i + 1; j < len; j++) {
int b = arr.get(j);
int x1 = a / 100, x2 = b / 100, y1 = a % 100, y2 = b % 100;
int up = y1 - y2, down = x1 - x2;
int c1 = gcd(up, down);
String K = (up / c1) + " " + (down / c1);
if (down == 0) {
ans.add("x = " + x1);
continue;
}
int kx = up * x1, Y = y1 * down;
int kb = Y - kx;
int c2 = gcd(kb, down);
String B = (kb / c2) + " " + (down / c2);
ans.add(K + " " + B);
}
}
System.out.println(ans.size());
}
}
4.货物摆放
//C++ TO JAVA CONVERTER WARNING: The following #include directive was ignored:
//#include <bits/stdc++.h>
public class Main {
private static final int maxn = 1010;
private static long[] a = new long[maxn];
public static void main(String[] args) {
long n = 2021041820210418L;
int len = 0;
for (long i = 1; i * i <= n; i++) {
if (n % i == 0) {
a[len++] = i;
if (i != n / i) {
a[len++] = n / i;
}
}
}
long cnt = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (a[i] * a[j] > n) {
continue;
}
for (int k = 0; k < len; k++) {
if (a[i] * a[j] * a[k] == n) {
cnt++;
}
}
}
}
System.out.println(cnt);
}
}
5.路径
public class Main {
static final int n = 2021;
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public static void main(String[] args) {
int[][] floyd = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n && j < i + 22; j++)
floyd[i][j] = floyd[j][i] = lcm(i + 1, j + 1);
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (floyd[i][k] != 0 && floyd[k][j] != 0 && (floyd[i][j] == 0 || floyd[i][k] + floyd[k][j] < floyd[i][j]))
floyd[i][j] = floyd[i][k] + floyd[k][j];
System.out.println(floyd[0][n - 1]);
}
}
6.时间显示
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
long n = cin.nextLong();
n /= 1000;
n %= (24 * 60 * 60);
System.out.printf("%02d:", n / 3600);
System.out.printf("%02d:", n / 60 % 60);
System.out.printf("%02d\n", n % 60);
cin.close();
}
}
7.最少砝码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
long x=sc.nextLong();
long sum=1,cur=1;
while(sum<x){
sum+=Math.pow(3, cur);
cur++;
}
System.out.println(cur);
}
}
8.杨辉三角形
import java.util.*;
public class Main {
private static int n;
private static long C(long a, long b) {
long res = 1;
for (long i = a, j = 1; j <= b; i--, j++) {
res = res * i / j;
if (res > n) {
return res;
}
}
return res;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
for (int k = 16; k >= 0; k--) {
int l = 2 * k, r = Math.max(n, l), res = -1;
while (l <= r) {
int mid = l + r >> 1;
if (C(mid, k) >= n) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (C(res, k) == n) {
System.out.println((long) (res + 1) * res / 2 + k + 1);
break;
}
}
cin.close();
}
}
9.双向排序
import java.io.IOException;
import java.util.*;
import java.io.*;
class InputReader {
private final static int BUF_SZ = 65536;
BufferedReader in;
StringTokenizer tokenizer;
public InputReader(InputStream in) {
super();
this.in = new BufferedReader(new InputStreamReader(in), BUF_SZ);
tokenizer = new StringTokenizer("");
}
private String next() {
while (!tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(in.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
class Tree {
public int l = 0;
public int r = 0;
public int sum = 0;
public int lazy = -1;
}
public class Main {
public static final int N = 100010;
public static int n;
public static int m;
public static int op;
public static int pos;
public static Tree[] tree = new Tree[N << 2];
public static void push_up(int rt) {
tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
public static void push_down(int rt) {
int x = tree[rt].lazy;
if (x != -1) {
int len1 = tree[rt << 1].r - tree[rt << 1].l + 1;
int len2 = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
tree[rt << 1].sum = len1 * x;
tree[rt << 1 | 1].sum = len2 * x;
tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = x;
tree[rt].lazy = -1;
}
}
public static void build(int l, int r, int rt) {
tree[rt].l = l;
tree[rt].r = r;
tree[rt].lazy = -1;
if (l == r) {
tree[rt].sum = 1;
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
push_up(rt);
}
public static void update1(int L, int R, int rt, int cnt) {
if (cnt == 0) {
return;
}
if (tree[rt].sum == cnt) {
tree[rt].sum = tree[rt].lazy = 0;
return;
}
push_down(rt);
if (cnt < tree[rt << 1].sum) {
update1(L, R, rt << 1, cnt);
} else {
update1(L, R, rt << 1 | 1, cnt - tree[rt << 1].sum);
tree[rt << 1].sum = 0;
tree[rt << 1].lazy = 0;
}
push_up(rt);
}
public static void update2(int L, int R, int rt, int cnt) {
if (cnt == 0) {
return;
}
int l = tree[rt].l;
int r = tree[rt].r;
int len = r - l + 1;
if (len - tree[rt].sum == cnt) {
tree[rt].sum = len;
tree[rt].lazy = 1;
return;
}
push_down(rt);
int cnt1 = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].sum;
if (cnt < cnt1) {
update2(L, R, rt << 1, cnt);
} else {
update2(L, R, rt << 1 | 1, cnt - cnt1);
tree[rt << 1].sum = tree[rt << 1].r - tree[rt << 1].l + 1;
tree[rt << 1].lazy = 1;
}
push_up(rt);
}
public static int query(int L, int R, int rt) {
int l = tree[rt].l;
int r = tree[rt].r;
if (L <= l && r <= R) {
return tree[rt].sum;
}
push_down(rt);
int mid = l + r >> 1;
int res = 0;
if (L <= mid) {
res += query(L, R, rt << 1);
}
if (R > mid) {
res += query(L, R, rt << 1 | 1);
}
return res;
}
public static void main(String[] args) {
for (int i = 0; i < (N << 2); i++) tree[i] = new Tree();
InputReader cin = new InputReader(System.in);
n = cin.nextInt();
m = cin.nextInt();
build(1, n, 1);
while ((m--) != 0) {
op = cin.nextInt();
pos = cin.nextInt();
if (op == 0) {
int cnt0 = n - tree[1].sum;
int cnt = Math.max(0, pos - cnt0);
update1(1, n, 1, cnt);
} else {
int cnt1 = tree[1].sum;
int cnt = Math.max(0, n - pos + 1 - cnt1);
update2(1, n, 1, cnt);
}
}
int vv1 = 0;
int vv2 = 0;
for (int i = n; i >= 1; i--) {
if (query(i, i, 1) == 0) {
System.out.print(i + " ");
}
}
for (int i = 1; i <= n; i++) {
if (query(i, i, 1) == 1) {
System.out.print(i + " ");
}
}
System.out.println();
}
}
10.括号序列
import java.util.*;
public class Main {
private static final int N = 5010;
private static final long mod = 1000000000 + 7;
private static char[] s;
private static final long[][] dp = new long[N][N];
private static final int[] sum = new int[N];
private static final long[] nex = new long[N];
private static final long[] pre = new long[N];
private static long calc(int cnt, boolean flag) {
if (cnt == 0) {
return 1;
}
for (long[] longs : dp) Arrays.fill(longs, 0);
Arrays.fill(sum, 0);
Arrays.fill(pre, 0);
if (!flag) {
for (int i = 0; i < s.length / 2; i++) {
char x = s[i];
s[i] = s[s.length - i - 1];
s[s.length - i - 1] = x;
}
for (int i = 0; i < s.length; i++) {
if (s[i] == ')') {
s[i] = '(';
} else {
s[i] = ')';
}
}
}
int n = 0, now = 0;
for (char c : s) {
if (c == ')') sum[++n] = now;
if (c == '(') now++;
}
if (sum[1] > 0) {
dp[1][0] = 1;
pre[0] = 1;
}
for (int i = 1; i <= cnt; i++) {
dp[1][i] = 1;
pre[i] = pre[i - 1] + 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= cnt; j++) nex[j] = 0;
for (int j = Math.max(0 , i - sum[i]); j <= cnt; j++) {
dp[i][j] = pre[j];
if(j - 1 < 0) nex[j] = dp[i][j];
else nex[j] = (nex[j - 1] + dp[i][j]) % mod;
}
if (cnt + 1 >= 0) System.arraycopy(nex, 0, pre, 0, cnt + 1);
}
return dp[n][cnt];
}
public static void main(String[] args) {
String S;
Scanner cin = new Scanner(System.in);
S = cin.next();
s = S.toCharArray();
int tot = 0, cnt1 = 0, cnt2 = 0;
for (var i : s) {
if (i == '(') {
tot++;
} else {
tot--;
}
if (tot < 0) {
cnt1++;
tot = 0;
}
}
cnt2 = tot;
System.out.println(calc(cnt1, true) * calc(cnt2, false) % mod);
cin.close();
}
}