⭐ Introduction ⭐ ️
Hello, I'm Zhijie. There is only one month left for the countdown of the provincial competition of the Blue Bridge Cup. If you have practiced the real problem for nearly seven or eight years, you can obviously feel that the difficulty of the Blue Bridge Cup is becoming more and more difficult. Although it is far from being comparable to ACM, its average difficulty is increasing at a significant speed. For such changes, I wonder if you have mastered some high-frequency test sites that are particularly popular for the Blue Bridge Cup? Have you mastered some necessary abilities? Let me summarize for you.
⭐ Past highlights ⭐ ️
⭐ Table of contents ⭐ ️
🍋 1. Quickly find the greatest common divisor and greatest common multiple
🍋 2. Processing capacity for dates (key points)
☔ 2.1 the week at the end of the century
🍋 3. Super large data processing
⚡ 3.1 putting wheat on the chessboard
🍏 4. Table printing simulation ability
🍋 1. Quickly find the greatest common divisor and greatest common multiple
I believe you are familiar with this test site. Some people may also use traversal to query for the maximum common divisor. It may not matter if it takes a long time to fill in the blank, but if the big question involves the maximum common divisor or common multiple, the amount of data in the Blue Bridge Cup is famous (which will be reflected later), and the timeout is certain. So please recite the Euclidean formula and use it directly (the formula with known efficiency is the fastest to find the common multiple)
1.gcd function (principle of Euclidean algorithm)
//The return value is the maximum common divisor of a and b
int gcd(int a,int b){
return b == 0 ? a:gcd(b,a%b);
}2.lcm function (find the greatest common multiple quickly, and the principle is based on gcd function)
//The return value is the greatest common multiple of a and b
int lcm(int a, int b){
return a/gcd(a,b)*b;//Least common multiple = product of two numbers ÷ maximum common divisor of two numbers
}☀️ 1.1 reduced score
If the maximum common divisor of the numerator and denominator of a fraction is 1, the fraction is called a reduced fraction.
For example, 3 / 4, 1 / 8, 7 / 1} are reduced fractions.
How many reduced fractions, numerator and denominator, are integers between # 1 and # 2020 (including # 1 and # 2020)?
Title Link: reduced fraction
This question is a blank filling question. In the real examination environment, we can still throw out the answer even if we use the simple method of finding the maximum common divisor, but it will time out on the official oi platform of blue bridge. According to the meaning of the question, we can write the code directly by using Euclidean formula.
import java.util.Scanner;
public class Main {
static int ans=0;
public static void main(String[] args) {
for(int i=1;i<=2020;i++){
for(int j=1;j<=2020;j++){
if((gcd(i,j)==1)) ans++;
}
}
System.out.println(ans);//The answer is 2481215
}
static int gcd(int a,int b){
return b == 0 ? a:gcd(b,a%b);
}
}🌁 1.2 score
1/1+1/2+1/4+1/8+⋯
Each item is half of the previous item. If there are 20 ， items in total, find the sum and the result is expressed in scores.
Similar: 3 / 2, of course, this is just adding the first two items. The numerator and denominator require mutual prime.
Title Link: fraction
This problem is relatively simple. We can find the numerator and denominator. However, the topic requires coprime, so we can use gcd function to find the maximum common divisor of numerator and denominator.
public class fraction {
public static void main(String[] args) {
//x is the denominator
int x=1;
//count is the numerator
int count=1;
for(int i=2;i<=20;i++) {
x*=2;
count+=x;
}
//Print the numerator and denominator
System.out.println(x);//524288
System.out.println(count);//1048575
int a=gcd(x,count);//The maximum common divisor is found to be 1
int b=x/a;
int d=count/a;
//Print answers
System.out.println(d+"/"+b);//1048575/524288
}
static int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
}🍋 2. Processing capacity for dates (key points)
This is the date of the blue bridge inspection. I also mentioned this in the previous Blue Bridge real topic. You can see it through the link above. Students in the Java group must learn to use the Calendar function, which can quickly find the day of the week of a certain month, a certain year, which is an artifact for complex date processing problems.
☔ 2.1 the week at the end of the century
Title: some cults claim that December 31, 1999 is the end of the world. Of course, the rumor has been broken. It is also said that December 31, the end of a century in the future, if it is Monday, it will Interestingly, December 31 of any year at the end of the century cannot be Monday!!! So the "rumor maker" was revised to Sunday
December 31, 1999 is Friday. May I ask: which is the closest year from the end of the century (i.e. XX99) in the future? December 31 happens to be Sunday (i.e. Sunday)? Just answer the year
This is a long-standing Blue Bridge real question (or the first question). According to the truth, the first question of the blue bridge cup can be answered at a glance, but it is still a little troublesome to deal with this question according to the conventional method. But you can kill this problem through Calendar.
public class Week at the end of the century {
public static void main(String[] args) {
//Note how to obtain the Calendar instance
Calendar calendar = Calendar.getInstance();
for (int year = 1999; year <10000 ; year+=100) {
//Set year month day
calendar.set(Calendar.YEAR,year);
calendar.set(Calendar.MONTH,11);//It's actually December
calendar.set(Calendar.DAY_OF_MONTH,31);
//Judge the day of the week
if (calendar.get(Calendar.DAY_OF_WEEK)==1) {
//Sunday is the first day, so when it is 1, it is Sunday. View it through the source code
System.out.println(year);// 2299
break;
}
}
}
}☁️ 2.2 running exercise
Xiao Lan exercises every day.
Under normal circumstances, Xiaolan runs {1km every day. If one day is Monday or the beginning of the month (the 11th day), in order to motivate himself, Xiaolan has to run 2 km. If it's Monday or the beginning of the month at the same time, Xiaolan will also run {2km.
Xiaolan has been running for a long time, from Saturday, November 11, 2000 (inclusive) to Thursday, October 1, 2020 (inclusive). How many kilometers does Xiaolan run during this period?
Title Link: Running exercise
This topic requires us to simulate the date, use an array to represent the day of each month, and make a special judgment for the February of leap year.
public class Running exercise {
static int[] M={0,31,28,31,30,31,30,31,31,30,31,30,31};
public static void main(String[] args) {
int y = 2000, m = 1, d = 1, w = 6, ans = 0;
while(y!=2020 || m!=10 || d!=1){
if(y%400==0 || (y%4==0&&y%100!=0)){
M[2] = 29;
}
else{
M[2] = 28; //M is a global variable
}
d++;
w = (w + 1) % 7;//w = 0 = Sunday
if(d > M[m]){
d = 1;
m ++;
}
if(m>12){
m = 1;
y ++;
}
if(d==1 || w==1){
ans++; //It's the beginning of the month or Monday
}
ans++;
}
//This cycle adds value first and then date, so it has been added on January 10, 2020, but not on January 1, 2000, so it adds 2
ans+=2;
System.out.println(ans);//8879
}
}❄️ 2.3 Monday
How many Mondays are there in the whole 2020 Century (from January 1, 1901 to December 31, 2000)?
Title Link: Monday
It is also a problem of date simulation. We need to judge the number of Mondays. My idea for this question is to combine the above two date questions. First use Calendar to calculate the day of the week for the start date and end date. Then use the template of running exercise topic combined with simulation. It can be calculated that the answer is 5217.
Why do you want to know the day of the week?
Because this code template needs to know the start date, and the last day, December 31, 2000, is not judged in the cycle. We need a special judgment. Of course, we can also end the cycle on January 1, 2001, so we don't need a special judgment.
public class Monday {
static int[] M={0,31,28,31,30,31,30,31,31,30,31,30,31};
public static void main(String[] args) {
Calendar c=Calendar.getInstance();
c.set(Calendar.YEAR, 1901);
c.set(Calendar.MONTH, 0);
c.set(Calendar.DAY_OF_MONTH, 1);
System.out.println(c.get(Calendar.DAY_OF_WEEK));//So it's Tuesday
Calendar c2=Calendar.getInstance();
c2.set(Calendar.YEAR, 2000);
c2.set(Calendar.MONTH, 11);
c2.set(Calendar.DAY_OF_MONTH, 31);
System.out.println(c2.get(Calendar.DAY_OF_WEEK));//So it's Sunday
test();
}
static void test() {
int y = 1901, m = 1, d = 1, w = 2, ans = 0;
while(y!=2000 || m!=12 || d!=31){
if(y%400==0 || (y%4==0&&y%100!=0)){
M[2] = 29;
}
else{
M[2] = 28; //This must be added because M is a global variable
}
d++;
w = (w + 1) % 7;//w = 0 = Sunday
if(d > M[m]){
d = 1;
m ++;
}
if(m>12){
m = 1;
y ++;
}
if(w==1){
ans++; //Yes, on Monday
}
}
//We already know that December 31, 2000 is not Monday, so there is no need for special judgment
System.out.println(ans);//5217
}
}⛄ 2.4 guess birthday
On this year's Arbor Day (March 12, 2012), Xiao Ming went to plant trees with his uncle and friends. During the break, Xiao Ming's classmates asked his uncle how old he was. His uncle said, "I'll say a question and see who guesses it first!"
"Connect the month, year and day of my birth into an 8-digit number (fill in 0 before the month and day are less than two digits), which can be divided by today's year, month and day!"
He thought for a moment, then added: "give me another hint, I was born in June."
According to this information, please help Xiao Ming calculate the date of birth of his uncle.
The format is 88 ， digits connected by month, year and day. For example, if it is June 12, 1948, write: 1948 0612.
Title Link: Guess birthday
On the surface, the test of this question is related to the date, but it has told us the month, which greatly reduces the difficulty. There is no need to consider the problem of February in leap year and ordinary year. The test is just an ordinary simulation.
public class Guess birthday {
static int a=2012;
static int b=3;
static int c=12;
public static void main(String[] args) {
for(int i=1900;i<2000;i++){
for(int j=1;j<=30;j++){
long count=i*10000+600+j;
//At the same time, the multiple of year and month is the answer
if(count%2012==0&&count%3==0&&count%12==0){
System.out.println(count);//19550604
}
}
}
}
}🍋 3. Super large data processing
This is also a major feature of the Blue Bridge Cup. Whether it is a blank filling question or a large question, the data range is outrageous. If you fill in the blanks with int, you will explode, and if you use int for big questions, you won't get full marks. Therefore, it is a very important ability to deal with big data. We can find it by looking at the real problem
⚡ 3.1 putting wheat on the chessboard
You must have heard the story. The king admired the minister who invented chess and asked him what reward he wanted. The minister said: please put 1 grain of wheat in the first chessboard, 2 grains of wheat in the second chessboard, 4 grains of wheat in the third chessboard, and 8 grains of wheat in the fourth chessboard The number of the latter space is twice that of the previous space until all the chessboard spaces are played (there are 64 # spaces in chess).
The king thought he just wanted a bag of wheat and laughed.
It was impossible to calculate accurately under the conditions at that time, but the estimation results were surprising: even if the whole world was covered with wheat, it was not enough!
Please use the computer to calculate exactly how many grains of wheat you need.
Title Link: Wheat on a chessboard
The title says that the whole world is covered with wheat and dare not use it. Then we can imagine how big this number is! int must not work, and using long to calculate must be the same result - it will explode! At this time, it is natural to think whether it can express a greater value than long? Since the question is asked like this, there must be some, that is - big inteegr. I believe many people haven't used this class, because it's true that most of the topics long are enough. This class is troublesome because addition, subtraction, multiplication and division need to be completed through methods. Here, you can check the API document and use it. You can see how big this number is!
public class Wheat on a chessboard {
public static void main(String[] args) {
BigInteger count=new BigInteger("1");
BigInteger ans=new BigInteger("1");
BigInteger x=new BigInteger("2");
for(int i=2;i<=64;i++){
ans=ans.multiply(x);
count=count.add(ans);
}
System.out.println(count);//18446744073709551615
}
}🌀 3.2 sequence evaluation
The given sequence of numbers... 1, 1, 1, 3, 5, 9, 17,... Starts from item 4, and each item is the sum of the first item 3.
Find the last 4 # digits of item # 20190324.
Title Link: Sequence evaluation
The purpose of this question is not to let everyone deal with big data types, but to analyze the meaning of the question! This number is certainly too large to be expressed in numbers, and the title only requires our last four digits - more to explain, so there is no need to deal with big data at all! The title only cares about the last four digits, and the root of the previous digit will not affect the following digits, so when our digit is greater than four digits, we can only keep the last four digits.
public class Sequence evaluation {
public static void main(String[] args) {
int a=1;
int b=1;
int c=1;
int d =0;
for(int i=4;i<=20190324;i++){
d=a+b+c;
if(d>10000) d=check(d);
a=b;
b=c;
c=d;
}
System.out.println(d);//4659
}
static int check(int n){
return n%10000;
}
}🍏 4. Table printing simulation ability
The reason why the ability to type the table is the top priority is that mastering it can not only quickly calculate the answer, save us a lot of time, but also simplify many questions. The reason for this is that the blank filling questions of blue bridge only need answers. Even if the program you write needs to run for a few minutes to get the answers, what's the difference? As long as my answer is right, and generally playing the watch for more than ten seconds at most, do you want to enter the national competition? Can't type a watch, that won't work! It's no use talking without practicing! Go straight to the question
🌊 4.1 formula problem
Look at this formula:
☆☆☆ + ☆☆☆ = ☆☆☆
If each Pentagram represents a different number of ， 11 ~ 99 ，.
How many possible ways to fill in this formula correctly?
Title Link: Arithmetic problem
This problem is very simple. The test is full permutation. The importance of full permutation is self-evident. In algorithm real problem 1, I have worked out all kinds of detailed real problems, which must be mastered by my partners who can't yet! Firstly, the method of full arrangement of templates is given. Test method is a fixed full arrangement template method, and the logic of check is written according to the requirements of the topic.
public class Formula problem {
static int[] arr= {1,2,3,4,5,6,7,8,9};
static int ans=0;
public static void main(String[] args) {
test(0);
System.out.println(ans);//336
}
static void test(int k) {
if(k==9) {
if(check()) ans++;
return;
}
for(int i=k;i<arr.length;i++) {
exch(k,i);
test(k+1);
exch(k,i);
}
}
static boolean check() {
int a=arr[0]*100+arr[1]*10+arr[2];
int b=arr[3]*100+arr[4]*10+arr[5];
int c=arr[6]*100+arr[7]*10+arr[8];
return a+b==c;
}
static void exch(int a,int b) {
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
}
Some brothers said, what if you don't remember the whole arrangement?? There's no way. I can only type a table to simulate all three digit addition, and then judge whether nine numbers are not equal. The amount of code is still a little large, but it's the only way to do it if you can't do it in the examination room.
We simulate a from 123 to 987, because 123 is the minimum number that meets the requirements of the topic and 987 is the maximum number that meets the requirements of the topic, then B should be (123 to 987) - A. Then A+B gets a C, and then judge whether nine numbers are not equal.
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
static int check(int a, int b, int c)
{
int flag[]=new int[11];
for(int i=0;i<10;i++) flag[i]=0;
flag[0]=1;
while(a!=0)
{
if(flag[a%10]==1) return 0;
else flag[a%10]=1;
if(flag[b%10]==1) return 0;
else flag[b%10]=1 ;
if(flag[c%10]==1) return 0;
else flag[c%10]=1 ;
a=a/10;
b=b/10;
c=c/10;
}
return 1;
}
public static void main(String[] args) {
int ans=0;
for(int a=123;a<=987;a++)
for(int b=123;b<=987-a;b++)
{
int c=a+b;
if(check(a,b,c)==1)
{
ans++;
System.out.println(a+"+"+b+"="+c);
}
}
System.out.println(ans);
}
}🌊 4.2 evaluation
After learning the divisor, Xiao Ming is very curious about the divisor. He found that given a positive integer tt, you can always find an integer containing {tt} divisors. Xiao Ming is very interested in the minimum number of divisors containing ， tt ， and defines it as ， S_tSt .
For example, S1 = 1,S2 = 2,S3 = 4,S4 = 6, ··· S1 = 1,S2 = 2,S3 = 4,S4 = 6, ⋅⋅⋅.
Now Xiao Ming wants to know, when St = 100, what is St = 100? That is, what is S1 ？ 00 ？?
Title Link: evaluation
The requirement of the topic is to find a minimum number with 100 factors. We write a method to calculate the number of factors, and then traverse back from 1. Here we recommend that you do not optimize the method of calculating the number of factors to prevent problems in some details. The amount of data is small. Just traverse from 1 to n. Our goal is to get the right answer and try not to optimize the code to prevent errors when possible.
public class evaluation {
public static void main(String[] args) {
int count=1;
//I'm sure I can get the answer before I reach 1000000
for(;count<=1000000;count++) {
if(check(count)==100) break;
}
System.out.println(count);//45360
}
static int check(int n) {
int ans=0;
//Simple traversal without optimization
for(int i=1;i<=n;i++) {
if(n%i==0) ans++;
}
return ans;
}
}
🍒 5. Classic must do series
🚀 5.1k times interval
Title Link: k-fold interval
The reason why I can say this question is because it is simple among the big questions in the Blue Bridge Cup. Li Kou even has the same original problem as it (and only the difficulty of mid). It's just a little different, but it's almost the same. First of all, let's explain a theorem - congruence theorem
Identical theorem - if you want ， b - a to be a multiple of ， k ， you only need to ensure that ， b ， and ， a ， modulus ， k ， are identical
After mastering this theorem, we can analyze the problem. First of all, we should find sub arrays. We must think of using prefixes and arrays to find them (we have to reflect on what we didn't expect). When traversing the i-th prefix and array, the value of arr[i]%k is obtained. At this time, the left side of I (i.e. [0,i-1] interval) is j. if arr[j]%k==arr[i]%k, it means that the sum of [j,i] intervals is a multiple of K. Write the code according to the above
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class k Multiple interval {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int k=sc.nextInt();
//Pay attention to the long array, which has a large amount of data
long[] arr=new long[N+1];
//Long must also be used in front of the Map, because the return value of the operation involving long is also long
Map<Long,Integer> map=new HashMap<Long,Integer>();
//Get prefix and array
for(int i=0;i<N;++i) {
arr[i+1]=arr[i]+sc.nextLong();
}
long ans=0;
//Never forget to put this in
map.put(0L,1);
for(int i=1;i<=N;++i) {
ans+=map.getOrDefault(arr[i]%k, 0);
map.put(arr[i]%k, map.getOrDefault(arr[i]%k, 0)+1);
}
System.out.println(ans);
}
}Put it on the blue bridge OJ and take a run. The full score is no problem.
✈️ 5.2 substring score
Title Link: Substring score
Title Analysis: this question can be done violently, and you can get 60 points. Each time we calculate the score that can be obtained by traversing the head of S[i] as the string. For the elements that only appear once in the subarray of S[i,j], we can get them through S[i,j-1], without traversing them every time. Here, I use a Set to record the elements that appear only once, and then use a Set to record the elements that appear repeatedly (I feel that it can be optimized, but I didn't optimize it)
public class Substring score {
//After six, I got 60 points
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s=sc.next();
int count=0;
int n=s.length();
for(int i=0;i<n;++i){
int ans=1;
//Put characters that appear only once
Set<Character> set1=new HashSet<>();
//Put multiple characters
Set<Character> set2=new HashSet<>();
set1.add(s.charAt(i));
for(int j=i+1;j<n;++j) {
char c=s.charAt(j);
if(set1.contains(c)) {
set1.remove(c);
set2.add(c);
}else if(!set1.contains(c)&&!set2.contains(c)) {
set1.add(c);
}
//The length of set1 is the element that appears only once
ans+=set1.size();
}
count+=ans;
}
System.out.println(count);
}
}Full score method:
To do this, we can analyze it. When can a character contribute a score?
The title requires that in a string, only the elements that appear only once can score. So what does it mean that it can't score? Is it that when it is in an interval with the same character as the previous one or the same character as the latter one, it cannot score. Let me take abcdaefa as an example: when the middle a is not in the same substring as its previous a and the latter a, it can score. To put it another way: this a can score only if it is in the bcdaef range. Draw a sketch for everyone to understand
Through the above ideas, we can calculate the scores of all characters, which is our answer. Take a at position j in the figure as an example. The element of the former a is i (if there is no one, it is recorded as - 1), and the position of the latter a is k (if there is no one, it is recorded as n). Then the score of a in position j is (j-i) (k-j). Therefore, based on this idea, we need to use an array pre to record the position of the previous occurrence of each character, and next is the position of the next occurrence. An array where records the subscript of the last occurrence of each character. The difficulty lies in the update of three arrays. After getting three arrays, the answer will be very good.
import java.util.Arrays;
import java.util.Scanner;
public class Substring score 2 {
//Full Score answer
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length();
//Record the position of each character a in the previous occurrence. If not, it is - 1
int[] pre=new int[n];
//Record the position of each character a in the next occurrence. If not, it is n
int[] next=new int[n];
int[] where=new int[26];//Count the subscript of the last occurrence of each character
Arrays.fill(where, -1);
//In this way, the position of the last occurrence of i characters can be obtained
for(int i=0;i<n;++i) {
pre[i]=where[s.charAt(i)-'a'];
where[s.charAt(i)-'a']=i;
}
Arrays.fill(where, n);
for(int i=n-1;i>=0;i--) {
next[i]=where[s.charAt(i)-'a'];
where[s.charAt(i)-'a']=i;
}
//Statistical answer
int ans=0;
for(int j=0;j<n;++j) {
ans+=(j-pre[j])*(next[j]-j);
}
System.out.println(ans);
}
}Take it and run. Sure enough, I got full marks 😆
In the last month, I hope you can work hard and enter the national competition together (earn the ticket fee first and then ha ha ha)!
Of course, useful brothers also ask for a third company. Thank you very much!!!
