2020第11回ブルーブリッジカップ模擬試合(JAVA)

文書ディレクトリ

一、メモリ変換

問題説明

解題構想

二、約数

を求める

問題説明

解題構想

三、九

問題説明

解題構想

四、木

問題説明

解題構想

五、増分数

問題説明

解題構想

六、四段アルファベット

問題説明

解題構想

七、増分三元組

問題説明

解題構想

8、正整数シーケンス

問題説明

解題構想

九、種草

問題説明

解題構想

十、パーティー番組

問題説明

解題構想

一、メモリ変換
問題の説明
コンピュータのストレージの中で、15.125 GBは何MBですか?答えの提出これは結果が空欄になった問題で、結果を算出して提出すればいいだけです.本題の結果は1つの整数で、解答を提出する時にこの整数だけを記入して、余分な内容を記入して得点することができません.
問題を解く構想.
答え:15488
二、約数を求める
問題の説明
1200,000は何個の約数がありますか(正の約数だけを計算します).答えの提出これは結果が空欄になった問題で、結果を算出して提出すればいいです.本題の結果は整数で、答えを提出するときにこの整数だけを記入し、余分な内容を記入すると得点できません.
問題を解く構想.
列挙

/**
 * @author sjf
 * @date 2020/3/23 20:07
 */



public class demo02    {
    public static void main(String[] args) {

        int num = 1200000;
        int count = 0;
        for (int i = 1; i <= num ; i++) {
            if(num%i == 0){
                count++;
                System.out.println(i);
            }
        }
        System.out.println(count);  //96
    }
}

三、九
問題の説明
1から2019の中で、何個の数の桁に数字9が含まれていますか?注意、ある数の中の数位には複数の9が含まれており、この数は一度だけ計算されます.例えば、1999という数は数字9を含み、計算では1つの数にすぎない.答えの提出これは結果が空欄になった問題で、結果を算出して提出すればいいだけです.本題の結果は1つの整数で、解答を提出する時にこの整数だけを記入して、余分な内容を記入して得点することができません.
問題を解く構想.
一人一人を求めて

/**
 * @author sjf
 * @date 2020/3/23 20:13
 */



public class demo03   {
    public static void main(String[] args) {
        int count = 0;
        for (int i = 1; i <= 2019 ; i++) {
            int temp = i;
            while (temp != 0){
                int yu = temp%10;
                temp/=10;
                if(yu == 9) {
                    count++;
                    System.out.println(i);
                    break;
                }
            }

        }
        System.out.println(count);  //544
    }
}

四、木
問題の説明
2019個のノードを含む木で、最大何個の葉ノードが含まれていますか?答えの提出これは結果が空欄になった問題で、結果を算出して提出すればいいだけです.本題の結果は1つの整数で、解答を提出する時にこの整数だけを記入して、余分な内容を記入して得点することができません.
問題を解く構想.
//子ノードのないノードをリーフノード//親ノードのないノードをルートノードSystemと呼ぶ.out.println(2018);//せいぜいこの木は2階しかありません
五、増分数
問題の説明
1つの正の整数右隣の数よりも大きな数ビットがない場合、1つの数ビットの増加数と呼ばれます.例えば1135は1桁の増分数であり、1024は1桁の増分数ではない.
正の整数nを与えて、整数の1からnの中で何個の数桁の増加する数がありますか?入力フォーマット入力の最初の行には整数nが含まれます.出力フォーマット出力行には、答えを表す整数が含まれます.サンプル入力30サンプル出力26評価サンプル規模と40%の評価サンプルについて、1<=n<=1000と約束した.80%の評価例では、1<=n<=100000であった.すべての評価例について、1<=n<=1000000である.
時間1 s
問題を解く構想.
変換文字のソート比較各ビット(例えば404はビット比較の方法では容易ではない)を求める必要はありません具体的にコードを見てみましょう

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author sjf
 * @date 2020/3/23 20:21
 */



//       
//           
public class demo05    {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s;
        s = sc.next();
        char[] num = s.toCharArray();

        char[] numTemp =s.toCharArray();

        Arrays.sort(numTemp);
        int i =0 ;
        for (i = 0; i <num.length ; i++) {
            if(num[i]!=numTemp[i])
                break;
        }

        if(i==num.length)
            System.out.println(s);

    }
}

六、四段文字
問題の説明
明ちゃんはhelloのような単語に興味を持っています.この単語はちょうど4つのセグメントに分けることができます.最初のセグメントは1つ以上の補音アルファベットで構成され、2番目のセグメントは1つ以上の元音アルファベットで構成され、3番目のセグメントは1つ以上の補音アルファベットで構成され、4番目のセグメントは1つ以上の元音アルファベットで構成されています.単語を1つ与えて、この単語もこの単語かどうかを判断して、yesを出力してください.そうしないとnoを出力してください.母音アルファベットはa,e,i,o,uの5つを含み,その他はいずれも補音アルファベットである.入力フォーマットは、小文字の英字のみを含む単語を含む行を入力します.出力フォーマットは答えを出力します.yesかnoです.サンプル入力lanqiaoサンプル出力yesサンプル入力worldサンプル出力no評価例規模と約束すべての評価例に対して、単語中のアルファベット個数は100を超えない.
問題を解く構想.
アルファベットを繰り返しましょう問題の要求に応じてセグメント化します

import java.util.Scanner;

/**
 * @author sjf
 * @date 2020/3/23 20:35
 */



public class demo06     {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String sF = sc.next();

        String s = sF+"6";
        int flag = 0;
        int count = 0;
        for (int i = 0; i < s.length(); ) {
            char c = s.charAt(i);
            //  
            while (i < s.length() - 1 && (c != 'a' && c != 'e' && c != 'i' && c != 'o' && c != 'u')) {
                i++;
                c = s.charAt(i);
            }
            flag++;
            if(i == sF.length())
                break;
            //  
            while (i < s.length() - 1  && (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')){
                i++;
                c = s.charAt(i);
            }
            flag++;
            if(i == sF.length())
                break;

        }

        if (flag == 4)
            System.out.println("yes");
        else
            System.out.println("no");
    }
}

七、増分三元グループ
問題の説明
数列a[1],a[2],...,a[n]では,下付きi,j,kが0を満たす場合はa[i],a[j],a[k]を1組の増分三元群,a[j]を増分三元群の中心と呼ぶ.数列を指定します.数列の要素の数が3元グループの中心になる可能性があります.入力フォーマット入力の最初の行には整数nが含まれます.2行目はn個の整数a[1],a[2],...,a[n]を含み,隣接する整数間はスペースで区切られ,与えられた数列を表す.出力フォーマット出力行には、答えを表す整数が含まれます.サンプル入力5 1 2 5 3 5サンプル出力2サンプルは、a[2]およびa[4]が三元群の中心である可能性があることを示す.評価例の規模は、50%の評価例に対して、2<=n<=100、0<=数列の数<=1000と約束されている.すべての評価例について、2<=n<=1000、0<=数列の数<=10000である.
問題を解く構想.
列挙注意カウントはピットです

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author sjf
 * @date 2020/3/23 22:25
 */


public class demo07      {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int i=0,j=0,k =0 ;
        ArrayList<Integer> ans = new ArrayList<>();
        for ( i = 0; i < n-2; i++) {
            for ( j = i+1; j < n-1 ; j++) {
                if(arr[i]<arr[j])
                for (k = j+1; k < n; k++) {
                    if ( arr[j]<arr[k]){
                        if(!ans.contains(j))
                            ans.add(j);
                        break;
                    }
                }
            }
        }
        System.out.println(ans.size());
    }
}

八、正の整数シーケンス
問題の説明
明ちゃんは、以下の条件を満たす正の整数シーケンスの数を知りたいです:1.第1項はnである.　　2. 第2項はnを超えない.　　3. 3番目の項目から、各項目は前の2つの項目の差の絶対値より小さい.与えられたnに対して、条件を満たすシーケンスがどれだけあるかを計算してください.入力フォーマット入力行には整数nが含まれます.出力フォーマットは、答えを表す整数を出力します.答えは大きいかもしれませんが、答えを10000で割った余りを出力してください.サンプル入力4サンプル出力7サンプル説明以下は条件を満たすシーケンスである:4 1 4 1 4 1 4 2 4 4 2 1 4 4 4 4 4評価用例規模と約束20%評価用例に対して、1<=n<=5;50%の評価例について、1<=n<=10;80%の評価例について、1<=n<=100;すべての評価例について、1<=n<=1000である.
問題を解く構想.
規則正しい水を探す.

import java.util.Scanner;

/**
 * @author sjf
 * @date 2020/3/23 22:41
 */



/*
         

  
f(n) = f(n-1)+f(n-2)+f(n-3);
 */
public class demo08      {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        int a1 = 2;
        int a2 = 2;
        int a3 = 3;
        int a4 = 0;
        if(num == 1)
            System.out.println(a1);
        if(num == 2)
            System.out.println(a2);
        if(num == 3)
            System.out.println(a3);
        for (int i = 4; i <= num ; i++) {
            a4 = (a1+a2+a3)%10000;
            a1 = a2;
            a2 = a3;
            a3 =a4;
        }
        if(num>=4)
        System.out.println(a4);

    }



}

九、草を植える
問題の説明
明ちゃんは空き地を持っていて、彼はこの空き地をn行m列の小さな塊に分けて、各行と各列の長さはすべて1です.明ちゃんはその中のいくつかの小さな空き地を選んで、草を植えて、他の小さな塊は依然として空き地を維持しています.これらの草は成長が速く、毎月、草は外に少し生えています.もし小さな塊が草を植えたら、自分の上、下、左、右の4つの小さな空き地に広がり、この4つの小さな空き地は草のある小さな塊になります.明ちゃんに、kヶ月後の空き地に草があるところを教えてください.入力フォーマット入力の最初の行は、2つの整数n,mを含む.次にn行、各行にm文字が含まれ、初期の空き地状態を表し、文字間にスペースがない.小数点であれば空き地、アルファベットgであれば草を植えたことを表す.次に整数kを含む.出力フォーマットはn行を出力し、各行にm文字を含み、kヶ月後の空き地の状態を表す.小数点であれば空き地、アルファベットgであれば草が生えていることを示します.サンプル入力4 5.g......g......2サンプル出力ggg.gggg. ggggg .ggg. 評価例の規模と約束は30%の評価例に対して,2<=n,m<=20であった.評価例の70%に対して2<=n,m<=100であった.すべての評価例について、2<=n、m<=1000、1<=k<=1000である.
問題を解く構想.
経典dfsは水の標識を書いて草の拡張の出力を行います

import java.util.Scanner;

/**
 * @author sjf
 * @date 2020/3/23 22:55
 */


/*
   dfs      
 */
public class demo09   {
    static char[][] map = new char[1001][1001];
    static int[][] book = new int[1001][1001];
    static int n,m;
    static int k;
    static int[][] swap = {{0,1},{1,0},{0,-1},{-1,0}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         n=sc.nextInt();
         m=sc.nextInt();

        for (int i = 0; i <n ; i++) {
            String s = sc.next();
            map[i] =s.toCharArray();
        }
        k = sc.nextInt();
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j] == 'g')
                    book[i][j] = 1;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m ; j++) {
                if(book[i][j] == 1)
                    dfs(i,j,0);
            }
        }


        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    public static void dfs(int x ,int y ,int month){
        if(month == k)
            return;

        int tx = 0,ty = 0 ;
        for (int i = 0; i < 4 ; i++) {
            tx = x + swap[i][0];
            ty = y + swap[i][1];

            if(tx<0||tx>=n||ty<0||ty>=m)
                continue;

                map[tx][ty] = 'g';
                dfs(tx, ty, month + 1);
        }

    }

}

十、パーティー番組
問題の説明
明ちゃんはパーティーを組織して、全部でnつの番組を用意しました.そしてパーティーの時間は限られていて、彼は最終的にその中のm番組を選ぶしかありません.このn番组は明ちゃんが想定した顺番で与えられたもので、顺番は変えられない.明ちゃんは、観客の夜の好きさと前のいくつかの番組の美しさには非常に大きな関係があることを発見しました.彼は選んだ最初の番組ができるだけきれいになることを望んでいます.その前提の下で、2番目の番組ができるだけきれいになることを望んでいます.明ちゃんは各番組にきれいな値を定義しました.明ちゃんがm番組を選んで、彼の要求を満たすのを助けてください.入力フォーマット入力の第1行は、番組の数と選択する数を表す2つの整数n,mを含む.2行目はn個の整数を含み,各番組の見栄え値の順である.出力フォーマット出力1行にm個の整数を含み、選択した番組の見栄え値である.サンプル入力5 3 3 1 2 5 4サンプル出力3 5 4サンプル説明第1,4,5番組を選択した.評価用例の規模と約束は30%の評価用例に対して、1<=n<=20である.60%の評価例について、1<=n<=100;全ての評価例について、1<=n<=100000、0<=番組の見栄え<=100000である.
問題を解く構想.
動的計画に関する問題解は更新されません