liuchuo – 第53页 – 我不管，反正我最萌～

[Java] 蓝桥杯ADV-193 算法提高盾神与条状项链

问题描述
有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。
“哇这么恶心的项链你也做得出来！！！”
盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。
“这个嘛~首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧~”土方一下子说出了m个修改步骤。
盾神觉得这个用人工做太麻烦了，于是交给了你。
输入格式
第一行两个数，分别为n，m。
第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。
接下来m行，为以下形式之一：
ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。
DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。
输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。
输出格式
第一行为一个数len，为做完所有操作后，项链的长度。
第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。
样例输入
10 5
1 2 3 4 5 6 7 8 9 10
DEL 5
ADD 7 5
DEL 10
ADD 4 20
ADD 20 12
样例输出
11
1 2 3 12 20 4 6 5 7 8 9
数据规模和约定
表示颜色的数字不超过10^5的正数，1<=n<=10^4，1<=m<=10^4。

package adv193;

import java.util.LinkedList;
import java.util.List;
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();
        List<String> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.next());
        }
        for (int i = 0; i < m; i++) {
            String c = in.next();
            if (c.equals("DEL")) {
                String p = in.next();
                list.remove(p);
            } else if (c.equals("ADD")) {
                String p = in.next();
                String q = in.next();
                
                int site = list.indexOf(p);
                list.add(site, q);
            }
        }
        in.close();
        
        System.out.println(list.size());
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }

}

package adv193;

import java.util.LinkedList;

import java.util.List;

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();

List<String> list = new LinkedList<>();

for (int i = 0; i < n; i++) {

list.add(in.next());

}

for (int i = 0; i < m; i++) {

String c = in.next();

if (c.equals("DEL")) {

String p = in.next();

list.remove(p);

} else if (c.equals("ADD")) {

String p = in.next();

String q = in.next();

int site = list.indexOf(p);

list.add(site, q);

}

in.close();

System.out.println(list.size());

for (int i = 0; i < list.size(); i++) {

System.out.print(list.get(i) + " ");

}

[Java] 蓝桥杯ADV-205 算法提高拿糖果

问题描述
妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
现在小B希望知道最多可以拿多少糖。
输入格式
一个整数N
输出格式
最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000

package adv205;

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

public class Main {

    private static List<Integer> prime = new ArrayList<>();

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

        int[] dp = new int[n + 1];
        for (int i = 0; i < prime.size(); i++) {
            for (int j = 1; j <= n; j++) {
                if (j % prime.get(i) == 0 && (j >= 2 * prime.get(i))) {
                    dp[j] = Integer.max(dp[j], dp[j - 2 * prime.get(i)] + prime.get(i));
                }
            }
        }

        System.out.println(dp[n]);
    }

    private static void setPrime(int n) {
        boolean[] p = new boolean[n + 1];

        for (int i = 2; i < p.length; i++) {
            p[i] = true;
        }

        for (int i = 2; i < p.length; i++) {
            for (int j = 2; i * j < p.length; j++) {
                p[i * j] = false;
            }
        }

        for (int i = 2; i * i <= n; i++) {
            if (p[i]) {
                prime.add(i);
            }
        }
    }

}

package adv205;

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class Main {

private static List<Integer> prime = new ArrayList<>();

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

in.close();

setPrime(n);

int[] dp = new int[n + 1];

for (int i = 0; i < prime.size(); i++) {

for (int j = 1; j <= n; j++) {

if (j % prime.get(i) == 0 && (j >= 2 * prime.get(i))) {

dp[j] = Integer.max(dp[j], dp[j - 2 * prime.get(i)] + prime.get(i));

}

System.out.println(dp[n]);

}

private static void setPrime(int n) {

boolean[] p = new boolean[n + 1];

for (int i = 2; i < p.length; i++) {

p[i] = true;

}

for (int i = 2; i < p.length; i++) {

for (int j = 2; i * j < p.length; j++) {

p[i * j] = false;

}

for (int i = 2; i * i <= n; i++) {

if (p[i]) {

prime.add(i);

}

[Java] 蓝桥杯ADV-208 算法提高矩阵相乘

问题描述
小明最近在为线性代数而头疼，线性代数确实很抽象（也很无聊），可惜他的老师正在讲这矩阵乘法这一段内容。
当然，小明上课打瞌睡也没问题，但线性代数的习题可是很可怕的。
小明希望你来帮他完成这个任务。
现在给你一个ai行aj列的矩阵和一个bi行bj列的矩阵，
要你求出他们相乘的积（当然也是矩阵）。
(输入数据保证aj=bi,不需要判断)
输入格式
输入文件共有ai+bi+2行，并且输入的所有数为整数（long long范围内）。
第1行：ai 和 aj
第2~ai+2行：矩阵a的所有元素
第ai+3行：bi 和 bj
第ai+3~ai+bi+3行：矩阵b的所有元素
输出格式
输出矩阵a和矩阵b的积（矩阵c)
（ai行bj列）
样例输入
2 2
12 23
45 56
2 2
78 89
45 56
样例输出
1971 2356
6030 7141

package adv208;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = bufferedReader.readLine().split(" ");
        int ai = Integer.parseInt(temp[0]);
        int aj = Integer.parseInt(temp[1]);
        long[][] a = new long[ai][aj];
        for (int i = 0; i < ai; i++) {
            String[] string = bufferedReader.readLine().split(" ");
            for (int j = 0; j < aj; j++) {
                a[i][j] = Long.parseLong(string[j]);
            }
        }

        temp = bufferedReader.readLine().split(" ");
        int bi = Integer.parseInt(temp[0]);
        int bj = Integer.parseInt(temp[1]);
        long[][] b = new long[bi][bj];
        for (int i = 0; i < bi; i++) {
            String[] strings = bufferedReader.readLine().split(" ");
            for (int j = 0; j < bj; j++) {
                b[i][j] = Long.parseLong(strings[j]);
            }
        }
        bufferedReader.close();

        for (int i = 0; i < ai; i++) {
            for (int j = 0; j < bj; j++) {
                long multipy = 0;
                for (int k = 0; k < aj; k++) {
                    multipy += a[i][k] * b[k][j];
                }
                System.out.print(multipy + " ");
            }
            System.out.println();
        }
    }

}

package adv208;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] temp = bufferedReader.readLine().split(" ");

int ai = Integer.parseInt(temp[0]);

int aj = Integer.parseInt(temp[1]);

long[][] a = new long[ai][aj];

for (int i = 0; i < ai; i++) {

String[] string = bufferedReader.readLine().split(" ");

for (int j = 0; j < aj; j++) {

a[i][j] = Long.parseLong(string[j]);

}

temp = bufferedReader.readLine().split(" ");

int bi = Integer.parseInt(temp[0]);

int bj = Integer.parseInt(temp[1]);

long[][] b = new long[bi][bj];

for (int i = 0; i < bi; i++) {

String[] strings = bufferedReader.readLine().split(" ");

for (int j = 0; j < bj; j++) {

b[i][j] = Long.parseLong(strings[j]);

}

bufferedReader.close();

for (int i = 0; i < ai; i++) {

for (int j = 0; j < bj; j++) {

long multipy = 0;

for (int k = 0; k < aj; k++) {

multipy += a[i][k] * b[k][j];

}

System.out.print(multipy + " ");

}

System.out.println();

}

[Java] 蓝桥杯ADV-233 算法提高队列操作

问题描述
队列操作题。根据输入的操作命令，操作队列（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。
输入格式
第一行一个数字N。
下面N行，每行第一个数字为操作命令（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。
输出格式
若干行每行显示一个2或3命令的输出结果。注意：2.出队命令可能会出现空队出队（下溢），请输出“no”，并退出。
样例输入
7
1 19
1 56
2
3
2
3
2
样例输出
19
1
56
0
no
数据规模和约定
1<=N<=50

package adv233;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Queue queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int op = sc.nextInt();
            switch (op) {
            case 1:
                queue.add(sc.nextInt());
                break;
            case 2:
                if (queue.isEmpty()) {
                    System.out.println("no");
                    return ;
                } else {
                    System.out.println(queue.poll());
                }
                break;
            case 3:
                System.out.println(queue.size());
                break;
            default:
                break;
            }
        }
        sc.close();
    }
}

package adv233;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

Queue queue = new LinkedList<>();

for (int i = 0; i < n; i++) {

int op = sc.nextInt();

switch (op) {

case 1:

queue.add(sc.nextInt());

break;

case 2:

if (queue.isEmpty()) {

System.out.println("no");

return ;

} else {

System.out.println(queue.poll());

}

break;

case 3:

System.out.println(queue.size());

break;

default:

break;

}

sc.close();

}

[Java] 蓝桥杯ALGO-10 算法训练集合运算

问题描述
给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。
输入格式
第一行为一个整数n，表示集合A中的元素个数。
第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。
第三行为一个整数m，表示集合B中的元素个数。
第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。
集合中的所有元素均为int范围内的整数，n、m<=1000。
输出格式
第一行按从小到大的顺序输出A、B交集中的所有元素。
第二行按从小到大的顺序输出A、B并集中的所有元素。
第三行按从小到大的顺序输出B在A中的余集中的所有元素。
样例输入
5
1 2 3 4 5
5
2 4 6 8 10
样例输出
2 4
1 2 3 4 5 6 8 10
1 3 5
样例输入
4
1 2 3 4
3
5 6 7
样例输出
1 2 3 4 5 6 7
1 2 3 4

package algo10;

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        TreeSet<Integer> treeSetA = new TreeSet<Integer>();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            treeSetA.add(in.nextInt());
        }
        
        TreeSet<Integer> treeSetB = new TreeSet<Integer>();
        int m = in.nextInt();
        for (int i = 0; i < m; i++) {
            treeSetB.add(in.nextInt());
        }
        in.close();
        
        printDivide(treeSetA, treeSetB);
        printAdd(treeSetA, treeSetB);
        printRemain(treeSetA, treeSetB);
    }
    
    public static void printAdd(TreeSet<Integer> a, TreeSet<Integer> b) {
        a.addAll(b);
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    public static void printDivide(TreeSet<Integer> a, TreeSet<Integer> b) {
        
        @SuppressWarnings("unchecked")
        TreeSet<Integer> tempA = (TreeSet<Integer>) a.clone();
        a.removeAll(b);
        tempA.removeAll(a);
        for (int i : tempA) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    public static void printRemain(TreeSet<Integer> a, TreeSet<Integer> b) {
        a.removeAll(b);
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

}

package algo10;

import java.util.Scanner;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

TreeSet<Integer> treeSetA = new TreeSet<Integer>();

int n = in.nextInt();

for (int i = 0; i < n; i++) {

treeSetA.add(in.nextInt());

}

TreeSet<Integer> treeSetB = new TreeSet<Integer>();

int m = in.nextInt();

for (int i = 0; i < m; i++) {

treeSetB.add(in.nextInt());

}

in.close();

printDivide(treeSetA, treeSetB);

printAdd(treeSetA, treeSetB);

printRemain(treeSetA, treeSetB);

}

public static void printAdd(TreeSet<Integer> a, TreeSet<Integer> b) {

a.addAll(b);

for (int i : a) {

System.out.print(i + " ");

}

System.out.println();

}

public static void printDivide(TreeSet<Integer> a, TreeSet<Integer> b) {

@SuppressWarnings("unchecked")

TreeSet<Integer> tempA = (TreeSet<Integer>) a.clone();

a.removeAll(b);

tempA.removeAll(a);

for (int i : tempA) {

System.out.print(i + " ");

}

System.out.println();

}

public static void printRemain(TreeSet<Integer> a, TreeSet<Integer> b) {

a.removeAll(b);

for (int i : a) {

System.out.print(i + " ");

}

System.out.println();

}

[Java] 蓝桥杯ALGO-11 算法训练瓷砖铺放

问题描述
有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
例如，长度为4的地面一共有如下5种铺法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。
输入格式
只有一个数N，代表地板的长度
输出格式
输出一个数，代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5

package algo11;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.close();
        if (n == 1) {
            System.out.println(1);
            return;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[n]);
    }

}

package algo11;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

in.close();

if (n == 1) {

System.out.println(1);

return;

}

int[] dp = new int[n + 1];

dp[1] = 1;

dp[2] = 2;

for (int i = 3; i <= n; i++) {

dp[i] = dp[i - 1] + dp[i - 2];

}

System.out.println(dp[n]);

}