Luogu questionnaire: introduction to cycle structure

(1)P5718 [deep foundation 4. Example 2] find the minimum value
Thanks to the first question, it is really concise and clear. It's a for loop, maintaining a minimum value.

import java.util.Scanner;

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

(2)P5719 [deep foundation 4. Example 3] classification average
In loop traversal, several variables are used to store the sum of class A, the number of class A, the sum of class B, and the number of class B. After traversal, output a total / a number, B total / B number, and keep one decimal place.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),k=sc.nextInt();
		double A_sum=0,B_sum=0;
		int A_count=0,B_count=0;
		for(int i=1;i<=n;i++) {
			if(i%k==0) {
				A_sum+=i;
				A_count++;
			}
			else {
				B_sum+=i;
				B_count++;
			}
		}
		System.out.println(String.format("%.1f", A_sum/A_count)+" "+String.format("%.1f", B_sum/B_count));
	}
}

(3)P5721 [deep base 4. Example 6] digital right triangle
The title of this question is not clear. The meaning of this question is to give an N, which represents the number of rows and columns of this triangle, and then increase from 1 to n to fill this triangle. But it is stipulated that the number is two digits, that is to say, 1 should be written in the format of 01.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int count=1;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n-i;j++) {
				System.out.print(String.format("%02d", count++));
			}
			System.out.println();
		}
	}
	
}

(4)P1009 sum of factorials
It should be a basic operation to find the factorial of a number, that is to use a recursion, let n*f(n-1), until n is less than 1, stop recursion. Here is to find the factorial of many numbers by using the cycle. But as a popular difficult problem, this one must have its own reason, because it needs high precision, 50! It can't be saved at all, let alone the factorial sum of 1-50.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		BigInteger sum=new BigInteger("0");
		for(int i=1;i<=n;i++) {
			sum=sum.add(f(i));
		}
		System.out.println(sum);
	}
	public static BigInteger f(int n) {
		if(n==1)
			return new BigInteger("1");
		return new BigInteger(n+"").multiply(new BigInteger(f(n-1)+""));
	}
}

(5)P1980 counting problem
This question is 1-n, the number x appears several times in total. Here is a pit that if x appears many times in a number, then it must be counted many times. This question label gives high performance, but the amount of data is only 10 ^ 6, so you can use a cycle to scan it.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),x=sc.nextInt();
		int sum=0;
		for(int i=1;i<=n;i++) {
			int ii=i;
			while(ii>0) {
				if(ii%10==x) {
					sum++;
				}
				ii/=10;
			}
		}
		System.out.println(sum);
	}
}

(6)P1035 series summation
Now that it has this theorem, when n is big enough, Sn > K. We don't have to be afraid. We just add 1/i to an infinite loop, and then i + +. Until the sum of accumulation is greater than k, i will be output directly and the cycle will end.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		double sum=0;
		int i=1;
		while(true) {
			sum+=1.0/i;
			if(sum>k) {
				System.out.println(i);
				return;
			}
			i++;
		}
	}
}

(7)P2669 gold coin
A simulation topic, here we need to create several variables, store them separately, the total number of gold coins obtained, the number of gold coins that should be obtained in the current days, and there are several days left before the number of days to obtain the gold coins. When you have 0 days left, add 1 to the current gold coins you should get

import java.util.Scanner;

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

(8)P5722 [deep base 4. Example 11] sequence summation
It's interesting that we can't directly use the formula of the sequence of equal difference numbers, but it's the same. Anyway, it's calculated by computer, and it will come out after a cycle of accumulation.

import java.util.Scanner;

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

(9)P5723 [deep base 4. Example 13] prime number pocket
This question is a question about prime number. Its data range is very small here, so we can use the most common way to find prime number, time complexity O(NlogN). Cycle to determine whether each number is a prime. If the sum of prime flowers is in the pocket, when the pocket can't fit, the cycle will end. I use a set here as a pocket, and finally output the size of elements and sets in the set.

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

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		ArrayList<Integer> a=new ArrayList<Integer>();
		int sum=0;
		for(int i=2;i<=100000;i++) {
			if(prime(i)) {
				if(sum+i>n) {
					break;
				}
				sum+=i;
				a.add(i);
			}
		}
		for(int x:a) {
			System.out.println(x);
		}
		System.out.println(a.size());
	}
	public static boolean prime(int n) {
		for(int i=2;i*i<=n;i++) {
			if(n%i==0) {
				return false;
			}
		}
		return true;
	}
}

If the amount of data is a little larger, the algorithm of time complexity is not enough. We need to use the prime number screening method. The Angstrom is a kind of O(NloglogN) time complexity screening method. Although this problem can be used, it is not a problem to practice. In addition, there is a faster screening method, Euler screen. Time complexity O(N), you can go to the Internet Baidu, as a template back down.

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

public class Main {
	static int n;
	static boolean[] vis;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		vis=new boolean[n+1];
		prime();
		for(int x:a) {
			System.out.println(x);
		}
		System.out.println(a.size());
	}
	static ArrayList<Integer> a=new ArrayList<Integer>();
	public static void prime() {
		vis[0]=vis[1]=true;
		for(int i=2;i<=n;i++) {
			if(i*i>n) {
				break;
			}
			if(!vis[i]) {
				for(int j=i*i;j<=n;j+=i) {
					vis[j]=true;
				}
			}
		}
		int sum=0;
		for(int i=2;i<=n;i++) {
			if(!vis[i]) {
				if(sum+i>n) {
					break;
				}
				sum+=i;
				a.add(i);
			}
		}
		
	}
}

(10)P1217 [USACO1.5] palindrome Prime Palindromes
In fact, the problem itself is not difficult, but to write a function to determine the number of palindromes, and then write a function to determine whether it is a prime number, and then recycle and scan it. But it's definitely not good to do this, because the data scale is 100 million, so it must be over time. So we need to find some rules to narrow our search. Here are the rules:
One digit: all palindrome numbers, prime numbers are 1, 3, 5, 7. So the palindrome prime number is 1, 3, 5, 7
Double digits: palindromes are 11, 22, 33 But they are all multiples of 11, so the palindrome prime number is only 11
Three digits: the tip of this question tells us that only the first digit is an odd number can it be a palindrome number, so
Enumerate 101303505 like this
Four digits: the first digit is also the odd number 10013003, but we find that all four digits of palindromes are multiples of 11, that is to say, they cannot be prime numbers. Then all four digits need not be enumerated.
In the same way, 6-digit and 8-digit numbers are the same, without enumeration directly.
In this way, we can reduce the data size by more than half, and then loop through it.

import java.util.Scanner;

public class Main {
	static int[] a=new int[100000];
	public static boolean prime(int n) {
		for(int i=2;i*i<=n;i++) {
			if(n%i==0) {
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt(),y=sc.nextInt();
		int p=0;
		for(int i=2;i<10;i++) {  //One digit
			if(prime(i)) {
				a[p++]=i;
			}
		}
		a[p++]=11;   //Two digit number
		for(int i=1;i<10;i+=2) {  //Three digit number
			for(int j=0;j<10;j++) {
				if(prime(i*101+j*10)) {
					a[p++]=i*101+j*10;
				}
			}
		}
		for(int i=1;i<10;i+=2) {  //Five digit number
			for(int j=0;j<10;j++) {
				for(int k=0;k<10;k++) {
					if(prime(i*10001+j*1010+k*100)) {
						a[p++]=i*10001+j*1010+k*100;
					}
				}
			}
		}
		for(int i=1;i<10;i+=2) {  //Five digit number
			for(int j=0;j<10;j++) {
				for(int k=0;k<10;k++) {
					for(int l=0;l<10;l++) {
						if(prime(i*1000001+j*100010+k*10100+l*1000)) {
							a[p++]=i*1000001+j*100010+k*10100+l*1000;
						}
					}
				}
			}
		}
		for(int i=0;i<p;i++) {
			if(x<=a[i]&&a[i]<=y) {
				System.out.println(a[i]);
			}
		}
	}
}

(11)P1423 Xiaoyu is swimming
This problem is the same as the series and that problem. It defines an infinite cycle. It accumulates the length of swimming each time until it reaches the specified length. It exits the cycle.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		double n=sc.nextDouble();
		int count=0;
		double speed=2;
		double sum=0;
		while(true) {
			count++;
			sum+=speed;
			speed*=0.98;
			if(sum>=n) {
				break;
			}
		}
		System.out.println(count);
	}
}

(12)P1307 digital inversion
Number inversion can also be treated as string inversion, that is to judge the leading 0 and negative number. But a simpler way is to cycle through the modules and multiply by 10.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int sum=0;
		while(n!=0) {
			sum=sum*10+n%10;
			n/=10;
		}
		System.out.println(sum);
	}
}

(13)P1720 counting money after a dark day
The title descriptions of this question are all in a mess. It's better not to directly substitute the n-In formula to get the results. Just one line of code. It's said that this is a fiboracci series, but if we can solve the problems one line at a time, we won't engage in these fancy ones.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		System.out.println(String.format("%.2f",(Math.pow((1+Math.sqrt(5))/2,n)-Math.pow((1-Math.sqrt(5))/2,n))/Math.sqrt(5)));
	}
}

(14)P5724 [deep foundation 4. Xi 5] find the range
This question and the first question seem to be, but now it is not only to find a minimum value, but also a maximum value, and then a minus is the answer.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int min=1000;
		int max=0;
		for(int i=0;i<n;i++) {
			int x=sc.nextInt();
			min=Math.min(min, x);
			max=Math.max(max, x);
		}
		System.out.println(max-min);
	}
}

(15)P1420 longest serial number
Set a variable to store the longest hyphen. Scan these numbers once, set a variable to record the current hyphen length. In case of interruption, compare it with the variable with the longest hyphen. If the variable is larger, replace the longest hyphen, and then set the variable to 1.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int max=0;
		int last=sc.nextInt();
		int temp=1;
		for(int i=1;i<n;i++) {
			int x=sc.nextInt();
			if(x==last+1) {
				temp++;
			}
			else {
				max=Math.max(temp, max);
				temp=1;
			}
			last=x;
		}
		System.out.println(max);
	}
}

(16)P1075 quality factor decomposition
It's a bit of math. Since he said that the positive integer of this input can be decomposed into the product of two prime numbers, then we can get the smaller one and reverse the larger one. We don't need to judge the prime number here, because according to the unique decomposition theorem, a number can only be decomposed into a group of prime numbers, and this problem also says that it can be decomposed into two prime numbers, so it is impossible to have a sum less than this number divisible by this number. We can prove that if a sum less than n can be divided by N, then the sum can be divided into two smaller prime numbers. We know that only one set of solutions of prime product is equal to N, so if there is a sum, it means that there are more than one set of solutions, which contradicts the problem. Although this problem needs to be solved mathematically, the code is very simple.

import java.util.Scanner;

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

(17)P4956 [COCI2017-2018#6] Davor
First of all, we can get a problem and write a bivariate equation. 364x+1092k=n
Then, we can find the value of this equation in two loops. Because x needs to be as large as possible and k needs to be as small as possible, X needs to start from the big one and k needs to start from the small one

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for(int x=100;x>=0;x--) {
			for(int k=1;k<1000;k++) {
				if(364*x+1092*k==n) {
					System.out.println(x);
					System.out.println(k);
					return;
				}
			}
		}
	}
}


(18)P1089 Tianjin's savings plan
A simulation question. Set up a variable to store the money of mom, and then set up a variable to store the money of your own hands. Then cycle 12 times, add 300 yuan to your money every month, and then subtract the expenses, and give the more money than 100 yuan to mom. At last, I output my own money plus my mother's money multiplied by 1.2. During the cycle, I specially judge that the money is not enough to spend. I directly output the month and terminate the cycle.

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] arr=new int[12];
		for(int i=0;i<12;i++) {
			arr[i]=sc.nextInt();
		}
		int sum=0;
		int now=0;
		for(int i=0;i<12;i++) {
			now+=300;
			if(now<arr[i]) {
				System.out.println(-i-1);
				return;
			}
			now-=arr[i];
			sum+=now/100*100;
			now-=now/100*100;
		}
		System.out.println((int)(sum*1.2+now));
	}
}

13 original articles published, 15 praised, 3408 visited
Private letter follow

Tags: Java less

Posted on Sun, 15 Mar 2020 01:17:29 -0700 by Riotblade