首页 > 编程语言 >Wust Java Club 2022-2023上半学年中期考核

Wust Java Club 2022-2023上半学年中期考核

时间：2022-11-20 23:14:22浏览次数：69  
标签：Java Scanner Club int static 2022 ans sc public

Wust Java Club 2022-2023上半学年中期考核

前言

提交时的注意事项

  1. 不可写入包名，如package edu.wust
  2. 必须有且只能有一个公有类public class Main，若有其他类，不应给其赋为公有，如class test
  3. 一定要导入使用的包名，如import java.util.Scanner;

OnlineJudge的各种返回

RE：运行时错误（紫紫的），一般是数组越界，类型转换错误，栈溢出

WA：答案错误（红红的），样例过了不代表这题能过

TLE：运行超时，检查算法时间复杂度，若超出时间限制不多，可进行些许常数优化（如位运算，输入输出优化）

MLE：超出空间限制，一般是数组开的过大，dp问题可以考虑进行维度优化

输入

Scanner在读入量小时效果还行

但在读入量十分大时，显得性能十分低下

这里建议使用BufferedReader或者StreamTokenizer

StreamTokenizer：优点是占用内存少，但是它只存储double及String类型，若要读入int或者long类型，只能进行强制转换，但是double类型存储多位整数的时候会转化为科学计数法，导致精度降低

更多细节请自行搜索

Maximum Path Sum

知识点考察：

  • 动态规划
  • 记忆化搜索

题目链接： T291913 Maximum Path Sum - 洛谷

原题链接：[P1216 USACO1.5][IOI1994]数字三角形 Number Triangles - 洛谷

想法来源： 第二周作业 018 最大和的路径Ⅰ

这题如果用Scanner读入数据，很容易会\(MLE\)，即超出空间限制

从上向下走

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[][] a = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            String[] line = in.readLine().split(" ");
            for (int j = 1; j <= i; ++j) {
                a[i][j] = Integer.parseInt(line[j - 1]);
            }
        }
        //dp[i][j]代表 从上向下走 到达i行j列的最大路径和
        int[][] dp = new int[n + 1][n + 1];
        //单独处理第一个值
        dp[1][1] = a[1][1];
        for (int i = 2; i <= n; ++i) {
            //单独处理i行第一个数和最后一个数，防止越界
            //第一个数只能从 上方 走来
            dp[i][1] = a[i][1] + dp[i - 1][1];
            for (int j = 2; j < i; ++j) {
                //第i行j列 只能 从i-1行的j-1列和j列 走来
                dp[i][j] = a[i][j] + Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
            }
            //最后一个数只能从 左上方 走来
            dp[i][i] = a[i][i] + dp[i - 1][i - 1];
        }
        int ans = Integer.MIN_VALUE;
        //我看到有的人是对最后一行dp数组排序
        //而排序的时间复杂度是O( nlog n )
        //不如一重循环 O(n)好
        for (int i = 1; i <= n; ++i) ans = Math.max(ans, dp[n][i]);
        System.out.println(ans);
    }
}

从下向上走

从上向下走和从下向上走结果是一致的

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[][] a = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            String[] line = in.readLine().split(" ");
            for (int j = 1; j <= i; ++j) {
                a[i][j] = Integer.parseInt(line[j - 1]);
            }
        }
        //dp[i][j]代表 从下向上走 到达i行j列的最大路径和
        int[][] dp = new int[n + 1][n + 1];
        //单独处理最后一行的值
        for (int i = 1; i <= n; ++i) dp[n][i] = a[n][i];
        for (int i = n - 1; i >= 1; --i) {
            for (int j = 1; j <= i; ++j) {
                //第i行j列的值由i+1行的j列和j+1列推得
                dp[i][j] = a[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        System.out.println(dp[1][1]);
    }
}

Eight Queens Puzzle

知识点考察：

  • \(DFS\)+回溯

题目链接：T291914 Eight Queens Puzzle - 洛谷

原题链接：[P1219 USACO1.5]八皇后 Checker Challenge - 洛谷

一个锻炼大家代码逻辑能力的题

Code

这份代码过不了最后一个测试点

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

public class Main {
    //map[i][j]表示i行j列是否已经有皇后了
    static boolean[][] map;
    static int[] ans;
    //记录有多少个解
    static int count = 0, n;

    //判断row行col列是否能放皇后
    static boolean check(int row, int col) {
        //判断(row,col)的 ↑ 上方是否有皇后
        for (int i = 1; i <= row; ++i) {
            if (map[i][col]) {
                return false;
            }
        }
        //判断(row,col)的 ↖ 对角线是否有皇后
        for (int i = row - 1, j = col - 1; i >= 1 && j >= 1; --i, --j) {
            //如果有皇后，则说明当前位置不能放皇后
            if (map[i][j]) {
                return false;
            }
        }
        //判断(row,col) ↗ 的对角线是否有皇后
        for (int i = row - 1, j = col + 1; i >= 1 && j <= n; --i, ++j) {
            //如果有皇后，则说明当前位置不能放皇后
            if (map[i][j]) {
                return false;
            }
        }
        //如果 ↖ ↑ ↗ 三个方向
        return true;
    }

    //寻找第row行的皇后
    static void dfs(int row) {
        //如果已经超出棋盘，则说明找到了一个可行解
        if (row > n) {
            ++count;
            //如果是前三个解，则输出
            if (count <= 3) {
                for (int i = 1; i <= n; ++i) System.out.print(ans[i] + " ");
                System.out.println();
            }
            return;
        }
        //判断row行i列能不能放皇后
        for (int i = 1; i <= n; ++i) {
            //如果(row,j)能放皇后，则继续向下搜索
            if (check(row, i)) {
                ans[row] = i;
                //标记这个地方放了皇后
                map[row][i] = true;
                //搜索下一行
                dfs(row + 1);
                //回溯，撤回标记
                map[row][i] = false;
            }
        }
    }

    public static void main(String[] args)throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        map = new boolean[n + 1][n + 1];
        ans = new int[n + 1];
        dfs(1);
        System.out.println(count);
    }
}

优化

原理（自行思考）：

  • 一个位置的主对角线↙↗的横纵坐标之和相同

  • 一个位置的次对角线↖↘的横纵坐标之差相同

根据这个性质，可以使用一个一维数组来标记某一个对角线是否存在皇后

竖直向上的位置同样可以用一个一维数组来标记

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

public class Main {
    static boolean[] upperLeft;
    static boolean[] upperRight;
    static boolean[] top;
    static int[] ans;
    //记录有多少个解
    static int count = 0, n;

    //判断row行col列是否能放皇后
    static boolean check(int row, int col) {
        if (top[col]) return false;
        if (upperLeft[row - col + n]) return false;
        if (upperRight[row + col]) return false;
        return true;
    }

    //寻找第row行的皇后
    static void dfs(int row) {
        //如果已经超出棋盘，则说明找到了一个可行解
        if (row > n) {
            ++count;
            //如果是前三个解，则输出
            if (count <= 3) {
                for (int i = 1; i <= n; ++i) System.out.print(ans[i] + " ");
                System.out.println();
            }
            return;
        }
        //判断row行i列能不能放皇后
        for (int i = 1; i <= n; ++i) {
            //如果(row,j)能放皇后，则继续向下搜索
            if (check(row, i)) {
                ans[row] = i;
                //标记这个地方放了皇后
                top[i] = true;
                upperLeft[row - i + n] = true;
                upperRight[row + i] = true;
                //搜索下一行
                dfs(row + 1);
                //回溯，撤回标记
                top[i] = false;
                upperLeft[row - i + n] = false;
                upperRight[row + i] = false;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        top = new boolean[n + 1];
        // 横纵坐标之差的范围在(-n,n)
        // 由于数组无负数下标，给其加上一个偏移量保证它一定在整数范围内
        upperLeft = new boolean[2 * n + 1];
        //横纵坐标之和的范围在[2,2n]
        upperRight = new boolean[2 * n + 1];
        ans = new int[n + 1];
        dfs(1);
        System.out.println(count);
    }
}

Whimsical 0-1 Knapsack Product Problem

知识点考察：

  • 数学推导

题目链接：T291909 Whimsical 0-1 Knapsack Product Problem - 洛谷

原题链接：P7223 01 背包 - 洛谷

想法来源：找 01背包 的题目时，误打误撞找到一个骗人的题目，疯狂折磨出题人

递归枚举所有方案

所有的方案个数为 \(nums\le2^{1000000}\)

理想情况下，最多只能拿到测试点编号2~5的分数

注意要对MOD使用finnal关键字

java中final 与效率_fa1d1的博客

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static int p;
    static int[] w;
    static long ans = 0;
    static final int MOD = 998244353;//一定要用final关键字！！！
    public static void main(String[] args) {
        n = sc.nextInt();
        p = sc.nextInt();
        w = new int[n];
        for (int i = 0; i < n; ++i) {
            w[i] = sc.nextInt();
        }
        dfs(0,0);
        System.out.println(ans);
    }
    static void dfs(int len, long sum) {
        if (len == n) {
            ans = (ans + pow(p, sum)) % MOD;
            return;
        }
        dfs(len + 1, sum);//如果不选择当前物品
        dfs(len + 1, sum + w[len]);//如果选择当前物品
    }
    static long pow(long x, long n) {//尽量使用位运算优化
        long ans = 1;
        for (; n != 0; n >>= 1, x = x * x % MOD) {
            if ((n & 1) == 1) ans = ans * x % MOD;
        }
        return ans;
    }
}

数学推导

前\(X\)个物品的总收益记为\(ans_x\)，前\(X-1\)个物品的总收益记为\(ans_{x-1}\)

以下关注\(ans_x\)的性质

设每种方案的总体积为\(k_i\)，其中 \(i\epsilon[1,2^x]\)

则\(ans_x=\sum_{i=1}^{2^x}p^{k_i}\)

对于所有方案都增加\(V\)体积

则总收益变为\(\sum_{i=1}^{2^x}p^{k_i+V}=p^{k_i+V}\times\sum_{i=1}^{2^x}p^{k_i}=p^{k_i+V}\times ans_x\)

所以，若每种方案的体积都增加\(V\)，相当于乘以\(p^{k_i+V}\)

考虑第\(X\)个物品的 \(ans_x\)

每种物品仅有两种情况

  1. 不选该物品，由于任意一种方案的物品总体积不变，则对\(ans_{x-1}\)无影响
  2. 选择该物品，对任意一种方案的物品总体积增加\(V_x\)，则\(ans_{x-1}\times p^{V_x}\)

\(ans_x\)为这两种情况的价值的和

则\(ans_x=ans_{x-1}+ans_{x-1}\times p^{V_x}=ans_{x-1}\times(1+p^{V_x})\)

\(\therefore \dfrac{ans_x}{ans_{x-1}}=1+p^{V_x}\)

由累乘法得：\(\dfrac{ans_x}{ans_0}=\prod_1^x(1+p^{V_x})\)

而\(ans_0\)表示当前无任何物品，即\(V=0\)

\(\therefore ans_0=p^V=p^0=1\)

\(\therefore ans_x=\prod_1^x(1+p^{V_x})\)

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static final long MOD = 998244353;
    static int n;
    static long ans = 1l, p;
    static int[] V;

    static long powMod(long a, int b) {
        long ret = 1;
        for (; b != 0; b >>= 1, a = a * a % MOD)
            if ((b & 1) == 1) ret = ret * a % MOD;
        return ret;
    }

    public static void main(String[] args) {
        n = sc.nextInt();
        p = sc.nextLong();
        V = new int[n];
        for (int i = 0; i < n; ++i) V[i] = sc.nextInt();
        for (int v : V) ans = ans * (1l + powMod(p, v)) % MOD;
        System.out.println(ans);
    }
}

Multiple

知识点考察：

  • 简单数论
  • 数学推导

题目链接：T291922 Multiple - 洛谷

原题链接：P1403 约数研究 - 洛谷

想法来源： 第一周题目 001 3或5的倍数

不可思议，纯暴力居然能拿\(80\)分，数据还得加强

思路

前置知识

  1. \(a\) 能整除 \(b\) 用符号表示为 \(b\mid a\)

  2. \(1\sim n\) 中约数（即因子）含 \(x\) 的个数 为 \(\left\lfloor\dfrac{n}{x}\right\rfloor\)

证明

对于 \(x\) 作为因子，\(x\) 一定为 \(2x，3x，4x，...，kx\) 的因子，则 \(k=\left\lfloor\dfrac{n}{x}\right\rfloor\)

所以 \(answer=k-1+1=k=\left\lfloor\dfrac{n}{x}\right\rfloor\)

解决该题

假设求\(f(6)\)

1 的约数：1
2 的约数：1，2
3 的约数：1， ，3
4 的约数：1，2， ，4
5 的约数：1， ， ， ，5
6 的约数：1，2，3， ， ，6

正常思路：求每个数的约数个数，再求和

换种思路：求 \(1\sim n\) 中有多少个数约数含 \(i\) ，其中\(i\in [1,n]\)

证明：

\[由题得，要求的值为\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d\mid i}1 \]

\[即\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d=1}^{n}{(d\mid i)} \]

\[交换求和顺序\sum_{i=1}^{n}f(i)=\sum_{d=1}^{n}\sum_{i=1}^{n}{(d\mid i)} \]

\[由前置知识2得 \sum_{i=1}^{n}f(i)=\sum_{d=1}^{n}\left\lfloor\dfrac{n}{d}\right\rfloor \]

Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += n / i;
        }
        System.out.println(ans);
    }
}

Climbing Stairs

知识点考察：

  • 线性动态规划
  • 递推
  • 递归+记忆化数组

题目链接：T291917 Climbing Stairs - 洛谷

原题链接：P1192 台阶问题 - 洛谷

想法来源： 第四周题目 031 货币面值的组合问题

思路

设到达第\(x\)级台阶的方案数为\(f(x)\)

由于最多能迈\(K\)级台阶，所以\(f(x)=f(x-1)+f(x-2)+...+f(x-k)\)

递归写法

与斐波那契数列递归写法相同，但是数据量很大，重复计算的数据更多，所以需要记忆化数组进行剪枝优化

import java.util.Scanner;

public class Main {
    static int[] memory;
    static int MOD = 100003;
    static int N, k;

    static int getAns(int n) {
        //如果这一级台阶的步骤数不为初值0，则说明已经计算过了
        if (memory[n] != 0) return memory[n];
        int ans = 0;
        //最小台阶为0，取max防止负数台阶出现
        for (int i = Math.max(0, n - k); i < n; ++i) {
            ans = (ans + getAns(i)) % MOD;
        }
        //返回该台阶方案数之前，先赋值给记忆化数组
        return memory[n] = ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        k = sc.nextInt();
        memory = new int[N + 1];
        //底部为0号台阶，不需要走，算一种方案
        //1号台阶同理
        memory[0] = memory[1] = 1;
        System.out.println(getAns(N));
    }
}

线性递推

与记忆化递归写法相同，只是求解顺序不同而已

import java.util.Scanner;

public class Main {
    static int MOD = 100003;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        //dp[i]代表到达第i级台阶的方案数
        int[] dp = new int[n + 1];
        //同理，0级与1级台阶方案数为1
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            //dp[i]=dp[i-1]+dp[i-2]+...+dp[i-k]
            for (int j = Math.max(0, i - k); j < i; ++j) {
                dp[i] += dp[j];
                dp[i] %= MOD;
            }
        }
        System.out.println(dp[n]);
    }
}

Exclusive or Lamp

知识点考察：

  • 异或性质

题目链接：T291916 Exclusive or Lamp - 洛谷

原题链接：P1161 开灯 - 洛谷

想法来源：136. 只出现一次的数字 - 力扣

本来想考察异或的，结果用暴力的数组判断也能过 T_T

思路

因为只剩下一个编号是开着灯的，所以对所有编号异或，剩下的值就是开着的灯

Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double t1;
        int t2, ans = 0;
        for (int i = 1; i <= n; ++i) {
            t1 = sc.nextDouble();
            t2 = sc.nextInt();
            for (int j = 1; j <= t2; ++j) {
                ans ^= (int) (t1 * j);
            }
        }
        System.out.println(ans);
    }
}

Euclidean‘s Jogging

知识点考察：

  • 最大公约数\(gcd\)
  • 最小公倍数\(lcm\)

题目链接：T291918 Euclidean‘s Jogging - 洛谷

原题链接：P4057 晨跑 - 洛谷

想法来源： 第一周题目 005 最小公倍数

思路

题目很长，但是最后仅要求三个数的最小公倍数

注意数据范围呀！！！

很多人\(85\)分就是因为没注意数据范围

int的最大值大约为\(2\times 10^9\)

而题目最后三个测试点的数据范围为\(1\leq a,b,c\leq 100000\)，即\(1\times 10^5\)

若三个数互质，则三个接近\(10^5\)的数相乘，会超过int范围

需要使用long类型

Code

import java.util.Scanner;

public class Main {
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong(), c = sc.nextLong();
        System.out.println(lcm(a, lcm(b, c)));
    }
}

标签：Java,Scanner,Club,int,static,2022,ans,sc,public
From： https://www.cnblogs.com/Cattle-Horse/p/16909986.html

相关文章

  • JAVA 代码优化
    1基本类型使用优化1.1尽量重用对象特别是对于String对象的使用，如需拼接字符串，使用如下例子：//拼接字符串，不重视效率的写法Stringstr1="aaa";str1=str1+"bbb"......
  • Java_JDBC
    JDBC一、JDBC简介1、概念：​ JDBC就是使用Java语言操作关系型数据库的一套API​ 全称：（JavaDataBaseConnectivity）Java数据库连接2、本质：为了使得Java代码可以......
  • 2022-2023-1 20221422 《计算机基础与程序设计》第十二周学习总结
    作业信息这个作业属于哪个课程<班级的链接>（https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP）这个作业要求在哪里<作业要求的链接>(https://www.cnblogs.......
  • 力扣33(java&python)-搜索旋转排序数组（中等）
    题目：整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在预先未知的某个下标k（0<=k<nums.length）上进行了旋转，使数组变为[nums[k],nums[k+1],......
  • 2022-2023-1 20221302《计算机基础与程序设计》第十二周学习总结
    作业信息这个作业属于那个班级 https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求  https://www.cnblogs.com/rocedu/p/9577842.html#WEEK12作业目标......
  • 2022－2023—1 20221306《计算机基础与程序设计》第十二周学习总结
    作业信息班级链接：https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求：https://www.cnblogs.com/rocedu/p/9577842.html#WEEK11作业目标：学习《C语言程序设计》......
  • 2022-11-20 Acwing每日一题
    本系列所有题目均为Acwing课的内容，发表博客既是为了学习总结，加深自己的印象，同时也是为了以后回过头来看时，不会感叹虚度光阴罢了，因此如果出现错误，欢迎大家能够指出错误，我......
  • NET7+c#11 2022.11.8日发布，新功能介绍
    c#11新功能原始字符串泛型特性net7新功能：use+add+required速率限制中间件：令牌桶固定窗口：2/s并发限制器用户限流的限制器：爬虫.NETMinimalAPI:没有控制器没有filte......
  • 2022.11.20
    T2：首先看出，答案肯定与\(X\)有关,所以肯定有一层循环用来枚举\(X\)然后考虑每个州对答案的贡献，只会是某个兵种的范围所以需要求出当前\(X\)下，某个兵种的范围，下面以......
  • Java学习一
    一.小结1.计算机是储存和处理数据的电子设备2.计算机包括硬件和软件两个部分3.硬件是计算机中可以看见的物理部分4.计算机程序，也就是通常所说的软件，是一些看不见的指令......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99