文章目录
1.第几天
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
2000 年的 1 月 1 日，是那一年的第 11 天。
那么，2000 年的 5 月 4 日，是那一年的第几天？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
125
2.方格计数
题目描述
在二维平面上有无数个1x1的小方格。我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。 你能计算出这个圆里有多少个完整的小方格吗？
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Amsxf9jX-1642567528918)(2018-9.assets/20180402222610158.png)]
注意：需要提交的是一个整数，不要填写任何多余内容。
3137548
public class Main {
public static void main(String[] args) {
int d = 1000, ans = 0;
for(int i = 1; i <= d; i++) {
for(int j = 1; j <= d; j++) {
if(i * i + j * j <= d * d)ans++;
}
}
System.out.println(ans * 4);
}
}
3.复数幂
题目描述
设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。
求 (2+3i)^123456等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。
答案写成 “实部±虚部i” 的形式，实部和虚部都是整数（不能用科学计数法表示），
中间任何地方都不加空格，实部为正时前面不加正号。
(2+3i)^2 写成: -5+12i，
{2+3i)^5 的写成: 122−597i
数据类型
BigInteger
正常情况下一个整数最多只能放在long类型之中，但是如果现在有如下的一个数字：
1111111111111111111111111111111111111111111111111
根本就是无法保存的，所以为了解决这样的问题，在java中引入了两个大数的操作类：
操作整型：BigInteger
操作小数：BigDecimal
当然了，这些大数都会以字符串的形式传入。
BigInteger
如果在操作的时候一个整型数据已经超过了整数的最大类型长度long的话，则此数据就无法装入，所以，此时要使用BigInteger类进行操作。
import java.math.BigInteger;
public class BigIntegerDemo1 {
public static void main(String[] args) {
BigInteger bi1 = new BigInteger("123456789") ; // 声明BigInteger对象
BigInteger bi2 = new BigInteger("987654321") ; // 声明BigInteger对象
System.out.println("加法操作：" + bi2.add(bi1)) ; // 加法操作
System.out.println("减法操作：" + bi2.subtract(bi1)) ; // 减法操作
System.out.println("乘法操作：" + bi2.multiply(bi1)) ; // 乘法操作
System.out.println("除法操作：" + bi2.divide(bi1)) ; // 除法操作
System.out.println("最大数：" + bi2.max(bi1)) ; // 求出最大数
System.out.println("最小数：" + bi2.min(bi1)) ; // 求出最小数
BigInteger result[] = bi2.divideAndRemainder(bi1) ; // 求出余数的除法操作
System.out.println("商是：" + result[0] +
"；余数是：" + result[1]) ;
}
}
题解
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.math.BigInteger;
/**
* @Description
* @Author:PrinceHan
* @CreateTime:2022/1/14 10:56
*/
public class T3 {
public static void main(String[] args) throws FileNotFoundException {
BigInteger two = BigInteger.valueOf(2);
BigInteger three = BigInteger.valueOf(3);
BigInteger a = BigInteger.valueOf(2);
BigInteger b = BigInteger.valueOf(3);
//(a+bi)*(2+3i) = (2a - 3b) + (3a + 2b)i
BigInteger aa = null;
BigInteger bb = null;
for (int i = 1; i < 123456; i++) {
aa = a.multiply(two).subtract(b.multiply(three));
bb = a.multiply(three).add(b.multiply(two));
a = aa;//如果不设置临时变量，后面b的值会出错
b = bb;
}
PrintStream out = System.out;
PrintStream ps = new PrintStream(new File("ans.txt"));//默认在项目的路径
System.setOut(ps);//输出在ans.txt里
// System.out.println(a.toString()+b.toString()+"i");
// System.setOut(out);//注释了下面就不会输入到控制台里
// System.out.println(a.toString()+b.toString()+"i");
System.out.println(a.toString() + (b.compareTo(BigInteger.ZERO) < 0 ? '-' : '+') + b + 'i');
}
}
4.测试次数
题目描述
x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，
并且评定出一个耐摔指数来，之后才允许上市流通。
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。
塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
为了减少测试次数，从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
请填写这个最多测试次数。
题目分析
最坏运气，从每一层开始使得测试次数最多
最佳策略，最坏运气中选择测试次数最少的
算法
动态规划
题解
/**
* @Description
* @Author:PrinceHan
* @CreateTime:2022/1/14 17:39
*/
public class T4 {
static int N = 1000;
static int[] f1 = new int[N + 1];
static int[] f2 = new int[N + 1];
static int[] f3 = new int[N + 1];
public static void main(String[] args) {
for (int i = 0; i < N; i++) {
f1[i] = i;
}
for (int i = 1; i <= N; i++) {
int ans = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
int max = 1 + Math.max(f2[i - j], f1[j - 1]);
ans = Math.min(ans, max);
}
f2[i] = ans;
}
for (int i = 1; i <= N; i++) {
int ans = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
int max = 1 + Math.max(f3[i - j], f2[j - 1]);
ans = Math.min(ans, max);
}
f3[i] = ans;
}
System.out.println(f3[1000]);
}
}
5.快速排序
题目描述
以下代码可以从数组a[]中找出第k小的元素。
它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。
仔细阅读分析源码，填写划线部分缺失的内容
题目分析
该算法与快速排序相似，当k大于数组长度时，要对数组长度取余
题解
import java.util.Random;
public class Main {
public static int quickSelect(int a[], int l, int r, int k) {
Random rand = new Random();
int p = rand.nextInt(r - l + 1) + l;
int x = a[p];
int tmp = a[p];
a[p] = a[r];
a[r] = tmp;
int i = l, j = r;
while (i < j) {
while (i < j && a[i] < x) i++;
if (i < j) {
a[j] = a[i];
j--;
}
while (i < j && a[j] > x) j--;
if (i < j) {
a[i] = a[j];
i++;
}
}
a[i] = x;
p = i;
if (i - l + 1 == k) return a[i];
if (i - l + 1 < k) return quickSelect(a, i, r - 1, k % (i - l + 1));
else return quickSelect(a, l, i - 1, k);
}
public static void main(String args[]) {
int[] a = {1, 4, 2, 8, 5, 7};
System.out.println(quickSelect(a, 0, 5, 4));
}
}
6.递增三元组
题目描述
给定三个整数数组
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN],
请你统计有多少个三元组(i, j, k) 满足：
- 1 <= i, j, k <= N
- Ai < Bj < Ck
输入
第一行包含一个整数N。
第二行包含N个整数A1, A2, … AN。
第三行包含N个整数B1, B2, … BN。
第四行包含N个整数C1, C2, … CN。
输出
一个整数表示答案
输入样例
3
1 1 1
2 2 2
3 3 3
输出样例
27
题目分析
如果从A数组着手的话，需要三重循环，会影响时间性能，所以从第二层着手。
题解
C++的代码在我校OJ上AC，使用Java在最后一个评测点上超时，故附上两种代码，核心思想一样。
#include<iostream>
#include<algorithm>
using namespace std;
int n;
long long ans;
int main()
{
cin >> n;
int A[n], B[n], C[n];
long ans = 0;
for(int i = 0; i < n; i++)
{
cin >> A[i];
}
for(int i = 0; i < n; i++)
{
cin >> B[i];
}
for(int i = 0; i < n; i++)
{
cin >> C[i];
}
sort(A, A + n);
sort(B, B + n);
sort(C, C + n);
int p = 0, q = 0;
for(int i = 0; i < n; i++)
{
while(p < n && A[p] < B[i])p++;
while(q < n && C[q] <= B[i])q++;
ans += 1L * p * (n - q);
}
cout << ans;
return 0;
}
import java.util.Arrays;
import java.util.Scanner;
/**
* @Description
* @Author:PrinceHan
* @CreateTime:2022/1/14 19:53
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] A = new int[n];
int[] B = new int[n];
int[] C = new int[n];
long ans = 0;
for(int i = 0; i < n; i++) {
A[i] = scanner.nextInt();
}
for(int i = 0; i < n; i++) {
B[i] = scanner.nextInt();
}
for(int i = 0; i < n; i++) {
C[i] = scanner.nextInt();
}
Arrays.sort(A);
Arrays.sort(B);
Arrays.sort(C);
int p = 0, q = 0;
for(int i = 0; i < n; i++) {
while(p < n && A[p] < B[i])p++;
while(q < n && C[q] <= B[i])q++;
ans += 1L * p * (n - q);
}
System.out.println(ans);
}
}
7.螺旋折线
题目描述
如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。
对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？
输入
X和Y
对于40%的数据，-1000 <= X, Y <= 1000
对于70%的数据，-100000 <= X， Y <= 100000
对于100%的数据, -1000000000 <= X, Y <= 1000000000
输出
输出dis(X, Y)
输入样例
0 1
输出样例
3
题目分析
直接暴力求解本题会超时超int，因此我们需要把它算出来。以右下角为基准，算出右下角的每一点沿螺旋折线到原点的距离，根据输入的点的坐标选择一个离它最近的基准点的距离，减去或加上这个距离，既为dis(X, Y)的值。四条边上每个点的操作不同，需要根据情况计算。
sum(1L, 2 * n, 1) * 2 - d
我们只记录了对角线上的上一部分 圈数计为n，加上下半部分的话就是2n。对角线上半部分由两段组成，我们可以只算一段最后在 * 2如上图所示，最后再加上减去路程差即可。
题解
import java.util.Scanner;
/**
* @Description
* @Author:PrinceHan
* @CreateTime:2022/1/16 09:55
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long x = scanner.nextLong();
long y = scanner.nextLong();
long d = 0;//距离
long n = 0;//第几圈
if (y > 0 && Math.abs(x) <= y) {
n = y;
d = y - x + 2 * y;
} else if (x > 0 && Math.abs(y) <= x) {
n = x;
d = y + x;
} else if (y <= 0 && x >= y - 1 && x <= -y) {
n = -y;
d = -(-y - x);
} else if (x < 0 && y >= x + 1 && y <= -x) {
n = -x - 1;
d = - (y + Math.abs(x) - 1 + 2 * Math.abs(x) - 1);
}
System.out.println(sum(1L, 2 * n, 1) * 2 - d);
}
public static long sum(long a0, long n, long d) {
return (2 * a0 + (n - 1) * d) * n / 2;
}
}
8.日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
ts id
表示在ts时刻编号id的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入
第一行包含三个整数N、D和K。
以下N行每行一条日志，包含两个整数ts和id。
对于50%的数据，1 <= K <= N <= 1000
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
输出
按从小到大的顺序输出热帖id。每个id一行。
输入样例
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例
1
3
题目分析
首先可以根据热帖的时间先后进行排序，依次遍历每一个热帖。算法为尺取法，滑动窗口。
题解
我怀疑我们学校评测系统有毒，得靠C++才能AC，Java题解在AcWing以及蓝桥杯官方测试系统显示AC
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
struct Post
{
int ts;
int id;
};
int cmp(Post p1, Post p2)
{
return p1.ts < p2.ts;
}
const int maxn = 100005;
Post posts[maxn];
int nums[maxn];
set<int> hots;
int main()
{
int n, d, k;
cin >> n >> d >> k;
for(int i = 0; i < n; i++)
{
int ts, id;
cin >> ts >> id;
posts[i].ts = ts;
posts[i].id = id;
}
sort(posts, posts + n, cmp);
for(int i = 0, j = 0; i < n; i++)
{
int id = posts[i].id;
nums[id]++;
while(posts[i].ts - posts[j].ts >= d)
{
nums[posts[j].id]--;
j++;
}
if(nums[id] == k)hots.insert(id);
}
set<int>::iterator it;
for(it = hots.begin(); it != hots.end(); it++)
{
cout << (*it) << endl;
}
return 0;
}
import java.util.*;
/**
* @Description
* @Author:PrinceHan
* @CreateTime:2022/1/10 16:05
*/
public class Main {
static class Post implements Comparator<Post>{
int ts;
int id;
Post(int ts, int id) {
this.ts = ts;
this.id = id;
}
@Override
public int compare(Post o1, Post o2) {
return o1.ts - o2.ts;
}
}
static int[] nums = new int[100005];
static boolean[] flag = new boolean[100005];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<Post> posts = new ArrayList<>();
TreeSet<Integer> hots = new TreeSet<>();
int N = scanner.nextInt();
int D = scanner.nextInt();
int K = scanner.nextInt();
int ts, id;
for (int i = 1; i <= N; i++) {
ts = scanner.nextInt();
id = scanner.nextInt();
posts.add(new Post(ts,id));
}
Collections.sort(posts, new Comparator<Post>() {
@Override
public int compare(Post o1, Post o2) {
return o1.ts - o2.ts;
}
});
int tmp = 0;
for (int i = 0, j = 0; i < N; i++) {
nums[posts.get(i).id]++;
while (posts.get(i).ts - posts.get(j).ts >= D) {
nums[posts.get(j).id]--;
j++;
}
if(nums[posts.get(i).id] >= K)
hots.add(posts.get(i).id);
}
for(Integer e : hots) {
System.out.println(e);
}
}
}
9.全球变暖
题目描述
你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
输出
一个整数表示答案。
输入样例
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例
1
题目分析
该题是一个连通块的问题，考虑时间性能，使用BFS算法求解。判断一个岛屿是否会被淹没关键在于陆地个数以及与海洋相邻的路地块数是否相等，若相等则该块岛屿会被完全淹没。
题解
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @Description
* @Author:PrinceHan
* @CreateTime:2022/1/19 11:01
*/
public class Main {
static char[][] map;
static int[][] vis;
static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static int n;
static int ans;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
vis = new int[n][n];
map = new char[n][n];
scanner.nextLine();
for (int i = 0; i < n; i++) {
map[i] = scanner.nextLine().toCharArray();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '#' && vis[i][j] == 0) BFS(i, j);
}
}
System.out.println(ans);
}
public static void BFS(int x, int y) {
Queue<Point> queue = new LinkedList<>();
int cntland = 0;
int cntsead = 0;
queue.add(new Point(x, y));
vis[x][y] = 1;
while (!queue.isEmpty()) {
Point tmp = queue.poll();
cntland++;
boolean flag = false;
for (int i = 0; i < 4; i++) {
int dx = tmp.x + dir[i][0];
int dy = tmp.y + dir[i][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < n) {
if (map[dx][dy] == '.') flag = true;
if (map[dx][dy] == '#' && vis[dx][dy] == 0) {
queue.add(new Point(dx, dy));
vis[dx][dy] = 1;
}
}
}
if (flag) cntsead++;
}
if (cntsead == cntland) ans++;
}
static class Point {
public int x;
public int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
10.堆的计数（无题解，超出能力范围了）
题目描述
我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。
每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。
假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？
例如对于N=4有如下3种：
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。
输入
一个整数N。
对于40%的数据，1 <= N <= 1000
对于70%的数据，1 <= N <= 10000
对于100%的数据，1 <= N <= 100000
输出
一个整数表示答案。
输入样例
4
输出样例
3
感谢大家支持！！！