1. What day
Title Description
This question is a blank filling question. You only need to calculate the result and use the output statement in the code to output the filled result.
January 1, 2000 is the 11th day of that year.
So, May 4, 2000, is the first day of that year?
Operating limits
- Maximum running time: 1s
- Maximum operating memory: 128M
125
2. Square counting
Title Description
There are countless 1x1 small squares on the two-dimensional plane. We draw a circle with a radius of 1000 with a vertex of a small square as the center of the circle. Can you work out how many complete squares there are in this circle?
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-Amsxf9jX-1642567528918)(2018-9.assets/20180402222610158.png)]
Note: what needs to be submitted is an integer. Do not fill in any redundant content.
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. Complex power
Title Description
Let i be an imaginary unit. For any positive integer n, the real and imaginary parts of (2+3i)^n are integers.
How much is (2+3i)^123456? That is, the 123456 power of (2+3i). This number is very large and requires accurate representation.
The answer is written in the form of "real part ± imaginary part i". Both real part and imaginary part are integers (which cannot be expressed by scientific counting method),
No space is added anywhere in the middle, and the real part is timing without a plus sign.
(2+3i)^2 is written as: - 5+12i,
{2+3i)^5 is written as 122 − 597i
data type
BigInteger
Under normal circumstances, an integer can only be placed in long Type, but if there is now a number as follows:
1111111111111111111111111111111111111111111111111
It can't be saved at all, so in order to solve this problem, in java Two operation classes with large numbers are introduced in:
Operation integer: BigInteger
Operation decimal: BigDecimal
Of course, these large numbers are passed in as strings.
BigInteger
If an integer data exceeds the maximum type length of an integer at the time of operation long This data cannot be loaded, so it should be used at this time BigInteger Class.
import java.math.BigInteger;
public class BigIntegerDemo1 {
public static void main(String[] args) {
BigInteger bi1 = new BigInteger("123456789") ; // Declare BigInteger object
BigInteger bi2 = new BigInteger("987654321") ; // Declare BigInteger object
System.out.println("Addition operation:" + bi2.add(bi1)) ; // Addition operation
System.out.println("Subtraction operation:" + bi2.subtract(bi1)) ; // Subtraction operation
System.out.println("Multiplication operation:" + bi2.multiply(bi1)) ; // Multiplication operation
System.out.println("Division operation:" + bi2.divide(bi1)) ; // Division Operation
System.out.println("Maximum number:" + bi2.max(bi1)) ; // Find the maximum number
System.out.println("Minimum decimal:" + bi2.min(bi1)) ; // Find the minimum number
BigInteger result[] = bi2.divideAndRemainder(bi1) ; // Division operation for finding remainder
System.out.println("The supplier is:" + result[0] +
"；The remainder is:" + result[1]) ;
}
}
Problem solution
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;//If the temporary variable is not set, the value of the following b will be wrong
b = bb;
}
PrintStream out = System.out;
PrintStream ps = new PrintStream(new File("ans.txt"));//Default path in project
System.setOut(ps);//Output in ans.txt
// System.out.println(a.toString()+b.toString()+"i");
// System.setOut(out);// Note that the following will not be entered into the console
// System.out.println(a.toString()+b.toString()+"i");
System.out.println(a.toString() + (b.compareTo(BigInteger.ZERO) < 0 ? '-' : '+') + b + 'i');
}
}
4. Test times
Title Description
The residents of Planet x have a bad temper, but fortunately, when they are angry, the only unusual action is to drop their mobile phones.
Major manufacturers have launched a variety of fall resistant mobile phones. The Quality Supervision Bureau of Planet x stipulates that mobile phones must pass the fall resistance test,
And assess a fall resistance index before it is allowed to be listed and circulated.
Planet x has many towering towers, which can be used for fall resistance test.
The height of each floor of the tower is the same. Slightly different from the earth, their first floor is not the ground, but equivalent to our second floor.
If the mobile phone is not broken when dropped from the 7th floor, but the 8th floor is broken, the falling resistance index of the mobile phone = 7.
In particular, if the mobile phone is broken when dropped from the first floor, the fall resistance index = 0.
If the n-th floor at the highest level of the tower is not damaged, the falling resistance index = n
In order to reduce the number of tests, 3 mobile phones are sampled from each manufacturer to participate in the test.
The tower height of a test is 1000 floors. If we always adopt the best strategy, how many times do we need to test at most under the worst luck to determine the fall resistance index of the mobile phone?
Please fill in the maximum number of tests.
Topic analysis
The worst luck, starting from each layer, makes the number of tests the most
The best strategy is to choose the one with the least test times from the worst luck
algorithm
dynamic programming
Problem solution
/**
* @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. Quick sort
Title Description
The following code can find the k-th smallest element from the array a [].
It uses a divide and conquer algorithm similar to that in quick sort, and the expected time complexity is O(N).
Read and analyze the source code carefully and fill in the missing content in the underlined part
Topic analysis
The algorithm is similar to quick sort. When k is greater than the length of the array, the length of the array should be remainder
Problem solution
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. Incrementing triples
Title Description
Given three integer arrays
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN],
Please count how many triples (i, j, k) satisfy:
- 1 <= i, j, k <= N
- Ai < Bj < Ck
input
The first line contains an integer N.
The second line contains N integers A1, A2,... AN.
The third line contains N integers B1, B2,... BN.
The fourth line contains N integers C1, C2,... CN.
output
An integer represents the answer
sample input
3 1 1 1 2 2 2 3 3 3
sample output
27
Topic analysis
If you start from the A array, you need A triple loop, which will affect the time performance, so start from the second layer.
Problem solution
The C + + code is AC on OJ of our university, and Java timeout on the last evaluation point. Therefore, two kinds of codes are attached, with the same core idea.
#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. Spiral polyline
Title Description
As shown in Figure P1 The spiral polyline shown in PGN passes through all integral points on the plane exactly once.
For the whole point (X, Y), we define its distance from the origin. dis(X, Y) is the length of the spiral line segment from the origin to (X, Y).
For example, dis(0, 1)=3, dis(-2, -1)=9
Given the coordinates of the whole point (X, Y), can you calculate dis(X, Y)?
input
X and Y
For 40% of data, - 1000 < = x, y < = 1000
For 70% of data, - 100000 < = x, y < = 100000
For 100% data, - 1000000000 < = x, y < = 1000000000
output
Output dis(X, Y)
sample input
0 1
sample output
3
Topic analysis
Solving this problem directly and violently will timeout more than int, so we need to calculate it. Take the lower right corner as the benchmark, calculate the distance from each point in the lower right corner along the spiral polyline to the origin, select the distance from the nearest benchmark according to the coordinates of the input point, subtract or add this distance, which is the value of dis(X, Y). The operation of each point on the four edges is different and needs to be calculated according to the situation.
sum(1L, 2 * n, 1) * 2 - d
We only recorded the upper part of the diagonal as n，If you add the lower half, it's 2 n. The upper half of the diagonal consists of two segments. We can only count one segment. At the end * 2 As shown in the figure above, add and subtract the distance difference at last.
Problem solution
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;//distance
long n = 0;//What lap
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. Log statistics
Title Description
Xiao Ming maintains a programmer forum. Now he has collected a "like" log with N lines. The format of each line is:
ts id
Indicates that the post with id number at ts time receives a "like".
Now Xiao Ming wants to count which posts used to be "hot posts". If a post has received no less than K likes in any time period of D, Xiaoming thinks that the post was once a "hot post".
Specifically, if there is a time when t satisfies that the post receives no less than K likes during the period of [T, T+D) (note that the left closed and right open interval), the post was once a "hot post".
Given the log, please help Xiao Ming count all the post numbers that were once "hot posts".
input
The first line contains three integers N, D, and K.
Each of the following N lines contains two integers ts and id.
For 50% of the data, 1 < = k < = n < = 1000
For 100% data, 1 < = k < = n < = 100000 0 < = TS < = 100000 0 < = ID < = 100000
output
Output the hot post id from small to large. One line per id.
sample input
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
sample output
1 3
Topic analysis
First, you can sort according to the time of hot posts, and traverse each hot post in turn. The algorithm is ruler taking method and sliding window.
Problem solution
I suspect that our school's evaluation system is toxic. We have to rely on C + + to ac. the Java problem solution shows AC in AcWing and the official Blue Bridge Cup test system
#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. Global warming
Title Description
You have a NxN pixel photo of a certain sea area, "." represents the ocean, "#" represents the land, as shown below:
....... .##.... .##.... ....##. ..####. ...###. .......
Among them, a piece of land connected in the four directions of "up, down, left and right" constitutes an island. For example, there are two islands in the figure above.
As the sea level rises due to global warming, scientists predict that a pixel of the edge of the island will be submerged by the sea in the next few decades. Specifically, if a land pixel is adjacent to the ocean (there is an ocean in the four adjacent pixels above, below, left and right), it will be submerged.
For example, the sea area in the above figure will look like the following in the future:
....... ....... ....... ....... ....#.. ....... .......
Please calculate: according to the prediction of scientists, how many islands in the picture will be completely submerged.
input
The first line contains an integer n. (1 <= N <= 1000)
The following n rows and N columns represent a sea area photo.
The picture ensures that the pixels in row 1, column 1, row N and column n are oceans.
output
An integer represents the answer.
sample input
7 ....... .##.... .##.... ....##. ..####. ...###. .......
sample output
1
Topic analysis
The problem is a connected block problem. Considering the time performance, it is solved by BFS algorithm. The key to judge whether an island will be submerged is whether the number of land and the number of road blocks adjacent to the ocean are equal. If equal, the island will be completely submerged.
Problem solution
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. Heap count (no problem, out of capacity)
Title Description
We know that a heap containing n elements can be regarded as a complete binary tree containing N nodes.
Each node has a weight. For the small root heap, the weight of the parent node must be less than that of its child nodes.
Assuming that the weights of N nodes are 1~N respectively, can you find out how many different small root heaps there are?
For example, for N=4, there are three types:
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
Since the number may exceed the integer range, you only need to divide the output result by the remainder of 100000009.
input
An integer N.
For 40% of data, 1 < = n < = 1000
For 70% of the data, 1 < = n < = 10000
For 100% data, 1 < = n < = 100000
output
An integer represents the answer.
sample input
4
sample output
3
Thank you for your support!!!