catalogue
7-6 weights of complete binary tree
7-1 contraction summation
-The 9th Lanqiao provincial competition - group C
Before the popularization of electronic computers, people often used a rough method to check whether the four operations were correct.
For example: 248 × 15=3720
Sum the multiplier and the multiplicand bit by bit respectively. If it is a multi digit number, sum it bit by bit until it is 1 digit, and then get
2 + 4 + 8 = 14 ==> 1 + 4 = 5;
1 + 5 = 6
5 * 6
The bitwise sum of the results is 3
The result of 5 * 6 is consistent with 3, indicating that it is very likely to be correct!! (errors cannot be excluded)
Please write a computer program to sum the given string bit by bit.
Input format:
A string of numbers representing n digits. 1≤n≤1000
Output format:
Single digit, indicating the result of repeated bit by bit summation.
Input sample:
35379
Output example:
9
The code is as follows:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string n;
int sum, res;
int main()
{
cin >> n ;
for(int i=0; i<n.size(); i++ ) sum += n[i] - '0';
while(sum>=10)
{
res = 0;
while(sum)
{
res += sum%10;
sum /= 10;
}
sum = res;
}
cout << sum ;
return 0;
}
7-2 isosceles triangle
-The 9th Lanqiao provincial competition - group C
This topic requires you to output an isosceles triangle composed of numbers.
The specific steps are:
First use the natural numbers of 1, 2, 3,... To spell a long enough string. Fill the three sides of the triangle with this string. Start at the top vertex and fill counterclockwise. For example, when the triangle height is 8:
Input format:
A positive integer n that represents the height of the triangle. 3<n<300
Output format:
Output, isosceles triangle filled with numbers.
In order to facilitate the evaluation, we require all spaces to be used Replace.
For details, please refer to the example.
Input sample:
A set of inputs is given here. For example:
5
Output example:
The corresponding output is given here. For example:
....1 ...2.1 ..3...2 .4.....1 567891011
The code is as follows:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2010;
int n;
char s[4], num[N];
char g[N][N];
int t, k=1;
void init()
{
for(int i=1; i<=600; i++)
{
t=i;
if(t<10)
num[k++] = t + '0';
else
{
int a=0;
while(t) s[a++] = t%10 + '0', t /= 10;
for(int i=a-1; i>=0; i--) num[k++] = s[i];
}
}
}
int main()
{
cin >> n;
init();
memset(g, '.', sizeof g);
k = 1;
int x = 4*(n-1) ;
for(int i=1; i<=n; i++)
{
if(i<n)
{
g[i][n-i+1] = num[k++];
}
else
{
int z=2*n-1, t=1;
while(z--) g[n][t++] = num[k++];
}
if(i>1) g[i][n+i-1] = num[x--];
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n+i-1; j++)
printf("%c",g[i][j]);
if(i<n) printf("\n");
}
return 0;
}
7-3 settlement issues
-The 9th Lanqiao provincial competition - group A
It is common for several people to go out to dinner together. But when checking out, there are often some disputes. Now there are n people going out to eat. They spent S yuan in total. Among them, the i-th person brought ai yuan. Fortunately, the total amount of money everyone brings is enough to pay the bill, but now the question comes: how much does each person pay?
For the sake of fairness, we hope that under the premise that the total payment is just S, the standard deviation of each person'S payment will be the smallest. Here we agree that the amount of money paid by each person can be any non negative real number, that is, it can not be an integral multiple of a penny. What is the minimum standard deviation you need to output.
Introduction to standard deviation: standard deviation is the square average of the difference between multiple numbers and their average. It is generally used to describe the "how big the deviation is" between these numbers. Formally speaking, let the i-th person pay bi Yuan, then the standard deviation is:
Input format:
The first line contains two integers n, S; The second line contains n non negative integers a1, , an.
For 10% of the data, all ai are equal;
For 30% of the data, all non-zero ai are equal;
For 60% data, n ≤ 1000;
For 80% data, n ≤ 10 ^ 5;
For all data, n ≤ 5 × 10^5, 0 ≤ ai ≤ 10^9，0 ≤S ≤ 10^18
Output format:
Output to standard output.
Output the minimum standard deviation, round to 4 decimal places. Ensure that the correct answer will not change the result of rounding after adding or subtracting 10 ^ − 9.
Input sample:
A set of inputs is given here. For example:
10 30 2 1 4 7 4 8 3 6 4 7
Output example:
The corresponding output is given here. For example:
0.7928
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 502000;
int n;
long long s;
long double sum;
int a[N];
int main()
{
cin >> n >> s ;
for(int i=0; i<n; i++ ) scanf("%d",&a[i]);
sort(a, a+n);
long double p = s*1.0/n, p1 = p;
for(int i=0; i<n; i++ )
{
if(a[i] <= p1)
{
s -= a[i];
sum += (a[i]-p)*(a[i]-p);
p1 = s*1.0/(n-i-1);
}
else sum += (p1-p)*(p1-p);
}
printf("%.4Lf", sqrt(sum/n));
return 0;
}
7-4 flight time
-The 9th Lanqiao provincial competition - group A (100 points)
Xiao h went to the United States to participate in the blue bridge cup international competition.
Little h's girlfriend found that little h left at 10 a.m. and arrived in the United States at 12 a.m., so she sighed, "now the plane flies so fast that it can reach the United States in two hours.".
Little h was terrified of supersonic flight.
After careful observation, it is found that the take-off and landing time of the aircraft is local time.
Due to the 12 hour time difference between Beijing and the eastern United States, the plane needs a total of 14 hours of flight time.
Soon after, little h's girlfriend went to the Middle East to exchange.
Xiao h doesn't know the time difference between the Middle East and Beijing.
But little h got the take-off and landing time of his girlfriend's round-trip flight.
Little h wants to know the flight time of his girlfriend's flight.
For a flight that may cross time zones, the take-off and landing time of the return trip is given.
Assuming that the round-trip flight time of the aircraft is the same, calculate the flight time of the aircraft.
Input format:
One input contains multiple sets of data.
The first input line is a positive integer T, indicating the number of input data groups.
Each group of data contains two lines, the first line is the take-off and landing time of the departure journey, and the second line is the take-off and landing time of the return journey.
The format of takeoff and landing time is as follows:
h1:m1:s1 h2:m2:s2
h1:m1:s1 h3:m3:s3 (+1)
h1:m1:s1 h4:m4:s4 (+2)
The first format indicates that the flight takes off at h1:m1:s1 local time and lands at h2:m2:s2 local time.
The second format indicates that the flight takes off at h1:m1:s1 local time and lands at h2:m2:s2 local time the next day.
The third format indicates that the flight takes off at h1:m1:s1 local time and lands at h2:m2:s2 on the third day local time.
Ensure that the input time is legal (0 ≤ h ≤ 23,0 ≤ m,s ≤ 59) and the flight time does not exceed 24 hours.
Output format:
For each group of data, one line of time hh:mm:ss is output, indicating that the flight time is HHH mm min ss.
Note that when the time is a single digit, the leading zero should be filled in. For example, three hours, four minutes and five seconds should be written as 03:04:05.
Input sample:
3 17:48:19 21:57:24 11:05:18 15:14:23 17:21:07 00:31:46 (+1) 23:02:41 16:13:20 (+1) 10:19:19 20:41:24 22:19:04 16:41:09 (+1)
Output example:
04:09:05 12:10:39 14:22:05
The code is as follows:
#include <iostream>
#include <cstdio>
using namespace std;
int get_time()
{
int h1, m1, s1, h2, m2, s2, d=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&h1, &m1, &s1, &h2, &m2, &s2, &d);
int t = (h2+d*24)*3600 + m2*60 + s2 - h1*3600 - m1*60 - s1;
return t;
}
int main()
{
int n;
cin >> n;
while(n -- )
{
int time1 = get_time();
int time2 = get_time();
int time = (time1+time2)/2;
int h = time/3600, m = time/60%60, s = time%60;
printf("%02d:%02d:%02d\n",h, m, s);
}
return 0;
}
7-5 global warming
-The 9th Lanqiao provincial competition - group AB (100 points)
Do you have a Zhang × N-pixel photo, "." Indicates ocean, "#" indicates land, as follows:
.......
.##....
.##....
....##.
..####.
...###.
.......
Among them, a piece of land connected in the four directions of "up, down, left and right" forms an island. For example, there are two islands in the above figure.
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 coming 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 format:
The first line contains an integer n. 1≤N≤1000.
The following n rows and N columns contain a combination of the characters "#" and "." Constituent n × N character matrix, representing a picture of sea area, "#" represents land, "." Indicates the ocean.
The picture ensures that the pixels in row 1, column 1, row N and column n are oceans.
Output format:
An integer represents the answer.
Input sample:
7 ....... .##.... .##.... ....##. ..####. ...###. .......
Output example:
1
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
int n;
char g[N][N];
int res, f;
bool st[N][N];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int i, int j)
{
st[i][j] = true;
if(g[i][j+1]=='#' && g[i][j-1]=='#' && g[i+1][j]=='#' && g[i-1][j]=='#')
f = 1;
for(int k=0; k<4; k++)
{
int x=i+dx[k], y=j+dy[k];
if(g[x][y]=='#' && !st[x][y])
dfs(x,y);
}
}
int main()
{
cin >> n ;
for(int i=0; i<n; i++ )
{
scanf("%s",g[i]);
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(g[i][j]=='#' && st[i][j]==false)
{
f = 0;
dfs(i,j);
if(!f) res++;
}
}
}
cout << res <<endl;
return 0;
}
7-6 weights of complete binary tree
-The 10th Lanqiao provincial competition - group B (100 points)
Given a complete binary tree with N nodes, each node in the tree has a weight, which is A1,A2 and ⋅⋅⋅ AN from top to bottom and from left to right, as shown in the following figure:
Now Xiao Ming wants to add up the weights of nodes with the same depth. He wants to know which depth has the largest sum of nodes' weights?
If the weight sum of multiple depths is the largest, please output the smallest depth.
Note: the depth of the root is 1.
Input format:
The first line contains an integer N.
The second line contains N integers A1,A2, ⋅⋅⋅ AN.
1≤N≤10^5 , −10^5≤Ai≤10^5
Output format:
Output an integer representing the answer.
Input sample:
A set of inputs is given here. For example:
7 1 6 5 4 3 2 1
Output example:
The corresponding output is given here. For example:
2
The code is as follows:
#include <iostream>
#include <climits>
#include <cstdio>
using namespace std;
const int N = 500010;
int n;
int a[N];
int max1 = INT_MIN;
int res;
int main()
{
cin >> n ;
for(int i=1; i<=n; i++ ) scanf("%d",&a[i]);
for(int i=1, d=1; i<=n; i*=2, d++ )
{
long long sum=0;
for(int j=i; j<=i*2-1 && j<=n; j++ )
{
sum += a[j];
}
if(sum > max1)
{
max1 = sum;
res = d;
}
}
cout << res << endl;
return 0;
}
7-7 children's worship circle
-The 9th Lanqiao provincial competition - group C (100 points)
There are N children in the class, and everyone has a child they admire most (or themselves).
In a game, children need to sit in a circle. Each child has his favorite child on his right hand.
How many people in the circle who meet the conditions?
The children are numbered 1, 2, 3,... N.
Input format:
First line, an integer n. 3<N<10^5
The next line contains N integers separated by spaces.
Output format:
Output an integer representing the maximum number of circles that meet the conditions.
Input sample:
A set of inputs is given here. For example:
9 3 4 2 5 3 8 4 6 9
Output example:
The corresponding output is given here. For example:
4
The code is as follows:
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 500010;
int n;
int a[N];
int res;
int cnt;
bool st[N];//Record status
void dfs(int x, int m, int cnt)
{
if(x==m)
{
res = max(res,cnt);
return;
}
if(st[x]) return;
st[x] = true;
dfs(a[x], m, cnt+1);
st[x] = false;//Restore the site
}
int main()
{
cin >> n ;
for(int i=1; i<=n; i++ ) scanf("%d",&a[i]);
for(int i=1; i<=n; i++ )
{
dfs(a[i], i, 1);
}
cout << res << endl;
return 0;
}
*7-8 multiple problem
-The 9th Lanqiao provincial competition - group A (100 points)
As we all know, Xiao Cong is good at calculation, especially at calculating whether one number is a multiple of another number.
But shallot is only good at two numbers. When there are many numbers, it will be more distressed.
Now XiaoCong gives you n numbers. I hope you can find three numbers from these n numbers, so that the sum of these three numbers is a multiple of K, and this sum is the largest.
The data guarantee must have a solution.
Input format:
The first line includes two positive integers n, K.
The second line contains n positive integers, representing the given n numbers.
1 ≤ n ≤ 10 ^ 5, 1 ≤ K ≤ 10 ^ 3, the number of given n shall not exceed 10 ^ 8
Output format:
The output line is an integer representing the sum.
Input sample:
4 3 1 2 3 4
Output example:
9
7-9 incrementing triples
-The 9th Lanqiao provincial competition - group B (100 points)
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 format:
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.
1≤N≤10^5 , 0≤Ai,Bi,Ci≤10^5
Output format:
An integer represents the answer.
Input sample:
3 1 1 1 2 2 2 3 3 3
Output example:
27
The code is as follows:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500010;
int n;
int a[N], b[N], c[N];
long long sum;
int main()
{
cin >> n ;
for(int i=1; i<=n; i++ ) scanf("%d",&a[i]);
for(int i=1; i<=n; i++ ) scanf("%d",&b[i]);
for(int i=1; i<=n; i++ ) scanf("%d",&c[i]);
sort(a+1, a+n+1);
sort(b+1, b+n+1);
sort(c+1, c+n+1);
for(int i=1; i<=n; i++ )
{
int x, y;
x = lower_bound(a+1,a+n+1,b[i])-a -1;
y = n -( upper_bound(c+1,c+n+1,b[i])-c ) +1;
sum += (long long)x*y;
}
cout << sum << endl;
return 0;
}*7-10 spiral polyline
-The 9th Lanqiao provincial competition - group B (100 points)
As shown in the figure below, the spiral polyline 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 format:
Contains two integers x, y. −10^9≤X,Y≤10^9
Output format:
Output an integer representing dis(X,Y).
Input sample:
0 1
Output example:
3
The code is as follows:
*7-11 log statistics
-The 9th Lanqiao provincial competition - group B (100 points)
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 with a length of D, Xiaoming thinks that the post was once a "hot post".
Specifically, if there is a certain 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 the number of all the posts that were once "hot posts".
Input format:
The first line contains three integers N,D,K.
Each of the following N lines contains two integers ts and id.
1≤K≤N≤10^5, 0≤ts,id≤10^5, 1≤D≤10000
Output format:
Output the hot post id from small to large.
Each id occupies one line.
Input sample:
A set of inputs is given here. For example:
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
Output example:
The corresponding output is given here. For example:
1 3
*Maximum product of 7-12
-The 9th Lanqiao provincial competition - group B (100 points)
Give N integers A1,A2,... AN.
Please choose K numbers from them to maximize their product.
Please find the maximum product. Since the product may exceed the integer range, you only need to output the remainder of the product divided by 100000009.
Note that if x < 0, we define that the remainder of X divided by 100000009 is the remainder of negative (− X) divided by 100000009, that is: 0 − ((0 − X)% 100000009)
Input format:
The first line contains two integers N and K.
The following N lines each contain an integer AI. 1 ≤ K ≤ N ≤ 10^5, −10^5 ≤ Ai ≤ 10^5
Output format:
Output an integer representing the answer.
Input sample:
5 3 -100000 -10000 2 100000 10000
Output example:
The corresponding output is given here. For example:
999100009
*7-13 fall resistance index
-The 9th Lanqiao provincial competition - group C (100 points)
The residents of Planet x have a bad temper, but fortunately, when they are angry, the only unusual behavior is to drop their mobile phones.
Major manufacturers have also 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 evaluate a fall resistance index before they are 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, three mobile phones were sampled from each manufacturer to participate in the test.
If the height of the test tower is known and the best strategy is adopted, how many tests are required to determine the fall resistance index of the mobile phone under the worst luck? An integer n representing the height of the test tower.
For example, if the input n is 3, 2 is output. Because the test process is as follows: mobile phone a is thrown from the second floor. If it breaks down, throw mobile phone b from the first floor; Otherwise, a mobile phone will continue to be dropped on the third floor.
If input n is 7, output 3. The test process is as follows: if the mobile phone a is thrown from the fourth floor and broken, there are three floors below. Two mobile phones B and C can measure the index twice; If it is not broken and the mobile phone is sufficient, it is easy to detect the upper 5, 6 and 7 layers twice.
Input format:
An integer n representing the height of the test tower. 3≤n≤10000
Output format:
An integer indicating the maximum number of tests.
Input sample:
A set of inputs is given here. For example:
3
Output example:
The corresponding output is given here. For example:
2
*7-14 three body attack
-The 9th Lanqiao provincial competition - group A (100 points)
In the input example below, because after the second round of attack, the warship (1,1,1) received a total of 2 points of damage, exceeding its defense and causing an explosion. So output 2.
Input sample:
2 2 2 3 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 2
Output example:
The corresponding output is given here. For example:
2