^_^

子集

时空限制

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 128M，其他语言256M

题目描述

小强现在有$n$个物品,每个物品有两种属性$x_i$和$y_i$.他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品$i$和$j$,满足$x_i < x_j && y_i < y_j$或者$x_i > x_j && y_i > y_j$.问最多能挑出多少物品。

输入描述

第一行输入一个正整数T.表示有T组数据.
对于每组数据,第一行输入一个正整数n.表示物品个数.
接下来两行,每行有n个整数.
第一行表示n个节点的x属性.
第二行表示n个节点的y属性.
1 <= T <= 10
2 <= n <= 100000
0 <= x,y <= 1000000000

输出描述

1	输出T行,每一行对应每组数据的输出.

例子

输入1

2
3
1 3 2
0 2 3
4
1 5 4 2 
10 32 19 21

输出1

1
2

2
3

我的答案

错误！

import java.util.Scanner;

/**
 * @author LuckyQ
 * @create 2021-06-16 20:53
 */
public class Main {
    private static int getAnswer(int[] x, int[] y){
        int n = x.length;
        // 将xc冒泡排序(从小到大)，y跟着变化
        boolean flag = true;
        int i = 0;
        while(flag){
            flag = false;
            for(int j = i; j < n - 1; j++){
                if(x[j] > x[j + 1]){
                    int temp = x[j + 1];
                    x[j + 1] = x[j];
                    x[j] = temp;
                    temp = y[j + 1];
                    y[j + 1] = y[j];
                    y[j] = temp;
                    flag = true;
                }
            }
            i++;
        }
        int minNum = y[0];
        int ans = 1;
        for(int j = 1; j < n; j++){
            if(y[j] > minNum){
                ans++;
                minNum = y[j];
            }
        }
        return ans;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while(T-- != 0){
            int n = scanner.nextInt();
            int[] x = new int[n];
            for(int i = 0; i < n; i++){
                x[i] = scanner.nextInt();
            }
            int[] y = new int[n];
            for(int i = 0;i < n; i++){
                y[i] = scanner.nextInt();
            }
            System.out.println(getAnswer(x, y));
        }
    }
}

小强爱数学

时空限制

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 128M，其他语言256M

题目描述

小强发现当已知$xy=B$以及$x+y=A$,能很轻易的算出$x^2+y^2$的值.但小强想请你在已知$A$和$B$的情况下,计算出$x^n+y^n$的值.因为这个结果可能很大,所以所有的运算都在模1e9+7下进行.

输入描述

第一行输入一个正整数T.表示有T组数据
接下来T行,每行输入三个整数A,B和n.
1 <= T <= 100
0 <= A,B < 1e9+7
1 <= n <= 1e5

输出描述

1	输出T行,每一行表示每组数据的结果.

例子

输入1

输出1

1
2
3

16
999999993
9009

我的答案

没有思路┭┮﹏┭┮

二叉树

时空限制

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 128M，其他语言256M

题目描述

小强现在有$n$个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为$n$且树的高度不超过$m$的方案.因为答案很大,所以答案需要模上1e9+7后输出.
树的高度: 定义为所有叶子到根路径上节点个数的最大值.

输入描述

1 2	第一行输入两个正整数n和m. 1 <= m <= n <= 50

输出描述

1	输出一个答案表示方案数.

例子

输入1

3 3

输出1

输入2

3 2

输出2

输入3

4 3

输出3

我的答案

只能过 30%

import java.util.Scanner;

/**
 * @author LuckyQ
 * @create 2021-06-16 20:53
 */
public class Main {
    private static int getAnswer(int n, int m){
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        for(int k = 2; k <= n; k++){
            // 固定根结点后，根结点占一层，故剩余层数需要-1
            int maxLevel = Math.min(k, m) - 1;
            int i = maxLevel, j = k - 1 - i, ans = 0;
            if(j > maxLevel){
                continue;
            }
            while(i > j){
                ans += f[i] * f[j];
                i--;
                j++;
            }
            ans *= 2;
            if(i == j){
                ans += f[i] * f[i];
            }
            f[k] = ans;
        }
        return f[n];
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        System.out.println(getAnswer(n, m));
    }
}

对称飞行器

时空限制

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

题目描述

小强在玩一个走迷宫的游戏，他操控的人物现在位于迷宫的起点，他的目标是尽快的到达终点。
每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格，或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子，且每一次移动的目的地不能存在障碍物。
具体来说，设当前迷宫有$n$行$m$列，如果当前小强操控的人物位于点$A(x,y)$，那么关于点$A$中心对称的格子$B(x_1,y_1)$满足$x + x_1 = n + 1$且$y + y_1 = m + 1$。
需要注意的是，对称飞行器最多使用5次。

输入描述

第一行两个空格分隔的正整数n,m，分别代表迷宫的行数和列数。
接下来n行，每行一个长度为m的字符串来描述这个迷宫。
其中
.代表通路。
#代表障碍。
S代表起点。
E代表终点。
保证只有一个S和一个E。
2 <= n,m <= 500

输出描述

1 2	仅一行一个整数表示从起点最小花费多少时间单位到达终点。如果无法到达终点，输出 -1。

例子

输入1

4 4
#S..
E#..
#...
....

输出1

一种可行的路径是用对称飞行器到达 (4,3) 再向上走一步，再向右走一步，然后使用一次对称飞行器到达终点。

我的答案

没有思路┭┮﹏┭┮

知识竞赛

时空限制

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

题目描述

最近部门要选两个员工去参加一个需要合作的知识竞赛，每个员工均有一个推理能力值$A_i$，以及一个阅读能力值$B_i$。如果选择第$i$个人和第$j$个人去参加竞赛，那么他们在阅读方面所表现出的能力为$X = \frac{B_i + B_j}{2}$，他们在推理方面所表现出的能力为$Y = \frac{A_i + A_j}{2}$。
现在需要最大化他们表现较差一方面的能力，即让$min(X,Y)$尽可能大，问这个值最大是多少。

输入描述

第一行一个正整数n，代表员工数。
接下来n行每行两个正整数Ai,Bi，分别用来描述第i个员工的推理和阅读能力。
2 <= n <= 2 x 10^5
1 <= Ai,Bi <= 10^8

输出描述

仅一行一个一位小数用来表示答案。

例子

输入1

输出1

2.0

选择第一个和第二个员工或第一个和第三个时，较差方面的能力都是 1.5，选择第二个和第三个时较差方面能力是 2。

我的答案

超时！

import java.util.Scanner;

/**
 * @author LuckyQ
 * @create 2021-06-16 20:53
 */
public class Main {
    private static double getAnswer(int[] A, int[] B){
        int n = A.length;
        double ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                double x = (B[i] + B[j]) / 2.0;
                double y = (A[i] + A[j]) / 2.0;
                double t = Math.min(x, y);
                if(t > ans){
                    ans = t;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] A = new int[n], B = new int[n];
        for(int i = 0; i < n; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            A[i] = a;
            B[i] = b;
        }
        System.out.println(String.format("%.1f", getAnswer(A, B)));
    }
}

树上最短链

时空限制

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 256M，其他语言512M

题目描述

在一个地区有n个城市以及n-1条无向边，每条边的时间边权都是1，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。
现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。
但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

输入描述

第一行一个正整数n，含义如题面所述。
第二行 n 个正整数 Ai，代表每个城市的等级。
接下来 n - 1 行每行两个正整数u ，v代表一条无向边。
保证给出的图是一棵树。
1 <= n <= 5000
1 <= u,v <= n
1 <= Ai <= 10^9

输出描述

仅一行一个整数代表答案，如果无法满足要求，输出 -1。

例子

输入1

输出1