2022蓝桥杯Java A组、B组

[蓝桥杯2022初赛] 裁纸刀
443
[蓝桥杯2022初赛] 求和

import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    static Scanner cin;
    static PrintWriter cout;
    static long a[];
    static long sum[];
    public static void init() throws IOException{
        cin=new Scanner(System.in);
        cout=new PrintWriter(System.out);
        a=new long[(int)(7e5+5)];
        sum=new long[(int)(7e5+5)];
    }
    public static void solve() throws IOException{
        int n=cin.nextInt();
        for(int i=1;i<=n;i++) {
            a[i] = cin.nextInt();
            sum[i] = sum[i - 1] + a[i];
        }
        long ans=0;
        for(int i=1;i<n;i++)
            ans+=a[i]*(sum[n]-sum[i]);
        cout.println(ans);
    }
    public static void main(String[] args) throws IOException {
        init();
        solve();
        cout.close();
    }
}

[蓝桥杯2022初赛] 青蛙过河

import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
    static Scanner cin;
    static PrintWriter cout;
    static long a[];
    static long sum[];
    static long n,x;
    public static void init() throws IOException{
        cin=new Scanner(System.in);
        cout=new PrintWriter(System.out);
        a=new long[(int)(7e5+5)];
        sum=new long[(int)(7e5+5)];
    }
    public static int check(long d){
        long tmp=0;
        for(long i=1;i+d<=n;i++){
            tmp= (int) (sum[(int) (i+d-1)]-sum[(int) (i-1)]);
            if(tmp<x)
                return 0;
        }
        return 1;
    }
    public static void solve() throws IOException{
        n=cin.nextInt();
        x=cin.nextInt();
        x=x*2;
        for(int i=1;i<n;i++){
            a[i]=cin.nextInt();
            sum[i]=sum[i-1]+a[i];
        }
        sum[(int) n]=sum[(int) (n-1)];
        long l=0,r=(int)(1e9),mid,ans = 0;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid)!=0) {
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
            }
        }
        cout.println(ans);
    }
    public static void main(String[] args) throws IOException {
        init();
        solve();
        cout.close();
    }
}

[蓝桥杯2022初赛] GCD

import java.io.*;
import java.util.*;
public class Main {
    static Scanner cin;
    static PrintWriter cout;
    public static void init() throws IOException{
        cin=new Scanner(System.in);
        cout=new PrintWriter(System.out);
    }
    public static void solve(){
        long a,b,c;
        a=cin.nextLong();
        b=cin.nextLong();
        c=Math.abs(a-b);
        cout.println(c-a%c);
    }
    public static void main(String[] args) throws IOException {
        init();
        int t=cin.nextInt();
        while(t-->0){
            solve();
        }
        cout.close();
    }
}

2052: [蓝桥杯2022初赛] 全排列的价值
暴力全排列:10%

public static void dfs(int x){
        if(x==n+1){
            for(int i=2;i<=n;i++){
                int g=0;
                for(int j=1;j<i;j++){
                    if(a[j]<a[i]) g++;
                }
                ans+=g;
            }
        }
        for(int i=1;i<=n;i++){
            if(vis[i]!=0) continue;
            a[x]=i;
            vis[i]=1;
            dfs(x+1);
            vis[i]=0;
        }
    }

动态规划:

import java.io.*;
import java.util.*;
public class Main {
    static Scanner cin;static PrintWriter cout;
    public static void init() throws IOException{
        cin=new Scanner(System.in);cout=new PrintWriter(System.out);
    }
    public static void solve(){
        long n=cin.nextLong();
        long mod=998244353;
        long ans=0,g=1;
        for(long i=2;i<=n;i++) {
            ans=(ans*i%mod+i*(i-1)/2%mod*g%mod)%mod;
            g=g*i%mod;
        }
        cout.println(ans);
    }
    public static void main(String[] args) throws IOException {
        init();
        solve();
        cout.close();
    }
}

JAVA B组
[蓝桥杯2022初赛] 星期计算
7
2058: [蓝桥杯2022初赛] 字符统计

import java.io.*;
import java.util.*;
public class Main {
    static Scanner cin;static PrintWriter cout;
    public static void init() throws IOException{
        cin=new Scanner(System.in);cout=new PrintWriter(System.out);
    }
    public static void solve(){
        Map<Character,Integer> mp=new TreeMap<Character,Integer>();
        String str=cin.next();
        char s[]=str.toCharArray();
        int len=str.length();
        for(int i=0;i<len;i++) {
            if(mp.containsKey(s[i])==false)
                mp.put(s[i],1);
            else
                mp.put(s[i],mp.get(s[i])+1);
        }
        int tmp=0;
        for(Map.Entry<Character,Integer> entry:mp.entrySet()){
            if(tmp<entry.getValue())
                tmp=entry.getValue();
        }
        String ans="";
        for(Map.Entry<Character,Integer> entry:mp.entrySet()){
            if(tmp==entry.getValue())
                ans+=entry.getKey();
        }
        cout.println(ans);
    }
    public static void main(String[] args) throws IOException {
        init();
        solve();
        cout.close();
    }
}

2059: [蓝桥杯2022初赛] 最少刷题数

import java.io.*;
import java.util.*;
public class Main {
    static Scanner cin=new Scanner(System.in);
    static PrintWriter cout=new PrintWriter(System.out);
    static int N=100010;
    static int a[]=new int[N],b[]=new int[N];
    public static void solve(){
        int n=cin.nextInt();
        for(int i=1;i<=n;i++) {
            a[i]=cin.nextInt();
            b[a[i]]++;
        }
        for(int i=1;i<=100000;i++) b[i]+=b[i-1];
        for(int i=1;i<=n;i++){
            if(b[100000]-b[a[i]]<=b[Math.max(0,a[i]-1)]){
                cout.print(0+" ");continue;
            }
            int l=a[i]+1,r=100000,mid,ans=0;
            while(l<=r){
                mid=l+r>>1;
                if(b[100000]-b[mid]<=b[mid-1]-1){ //只处理大于情况，减一代表去除本身
                    r=mid-1;ans=mid;
                }
                else
                    l=mid+1;
            }
            cout.print(ans-a[i]+" ");
        }
    }
    public static void main(String[] args) throws IOException {
        solve();
        cout.close();
    }
}

2057: [蓝桥杯2022初赛] 山

import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
    static Scanner cin=new Scanner(System.in);
    static PrintWriter cout=new PrintWriter(System.out);
    static int N=100010;
    static int a[]=new int[N];
    public static boolean check(long x){
        String str=x+"";
        int len=str.length();
        char s[]=str.toCharArray();
        for(int i=0,j=len-1;i<j;i++,j--){
            if(s[i]!=s[j])
                return false;
        }
        for(int i=1;i<(len+1)/2;i++){
            if(s[i]<s[i-1])
                return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        int tmp=0;
        for(int i=2022;i<=2022222022;i++){
            if(check(i)){
                tmp++;
                cout.println(i);
            }
        }
        cout.println("tmp:"+tmp);
        cout.close();
    }
}

2060: [蓝桥杯2022初赛] 求阶乘

import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
    static Scanner cin=new Scanner(System.in);
    static PrintWriter cout=new PrintWriter(System.out);
    public static long cal(long x){
        long cnt=0;
        while(x>0){
            cnt+=x/5;
            x/=5;
        }
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        long k=cin.nextLong();
        long l=1,r=Long.MAX_VALUE-5,mid,ans=0;
        while(l<=r){
            mid=l+r>>1;
            if(cal(mid)>=k){
                r=mid-1;ans=mid;
            } else{
                l=mid+1;
            }
        }
        long tmp=cal(ans);
        if(tmp==k){
            cout.println(ans);
        }
        else{
            cout.println(-1);
        }
        cout.close();
    }
}

2062: [蓝桥杯2022初赛] 数组切分

import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
    static Scanner cin=new Scanner(System.in);
    static int N=(int)(1e6+5);
    static int mod=1000000007;
    static int a[]=new int[N];
    static int f[]=new int[N];
    public static void main(String[] args) throws IOException {
        int n=cin.nextInt();
        for(int i=1;i<=n;i++) a[i]=cin.nextInt();
        f[0]=1;
        for(int i=1;i<=n;i++){
            int mi=a[i],mx=a[i];
            for(int j=i;j>=1;j--){
                mi=Math.min(mi,a[j]);
                mx=Math.max(mx,a[j]);
                if(i-j==mx-mi)
                    f[i]=(f[i]+f[j-1])%mod;
            }
        }
        System.out.println(f[n]);
    }
}