Problem A: Bichrome Cells
topic description
We have an N×N square grid.
We will paint each square in the grid either black or white.
If we paint exactly A squares white, how many squares will be painted black?
Translation: We have an N×N square grid. We paint each square in the grid either black or white. If we paint square A white, how many squares will be painted black?
Constraints
1≤N≤100
0≤A≤N2
enter
Input is given from Standard Input in the following format:
N
A
output
Print the number of squares that will be painted black.
sample input
3 4
sample output
5
hint
There are nine squares in a 3×3 square grid. Four of them will be painted white, so the remaining five squares will be painted black.
Ideas:
Because n is a number less than or equal to 100, the result will not explode int, just output n*n-a directly
AC Code:
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,a;
cin >> n >> a;
cout << max(n*n-a,0);
return 0;
}Problem B: Maximum Partial Sum
topic description
There are n integers (1≤n≤100), arranged in a row, for example n=7
-2 13 12 9 14 -10 2 (7 integers)
Its largest partial sum is 48 (ie 13+12+9+14)
enter
The first line is an integer n
There is a space between n integers (-100≤xi≤100) in the second line; where xi has a positive number
output
an integer (i.e. the largest consecutive partial sum)
sample input
7
-2 13 12 9 14 -10 2
sample output
48
Problem-solving idea 1: violence method:
In this question, n∈[1,100], so we can violently enumerate all continuous sums and take the maximum value. Time complexity: O(n^2)
AC code 1:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N];//Storing data
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,sum,ans = 0;
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i <= n;i++)//i is used to enumerate the position of the first number
{
sum = 0;
for (int j = i;j <= n;j++)//Starting from the i-th position, the enumeration length
{
sum += a[j];
ans = max(ans,sum);
}
}
cout << ans;
return 0;
}Problem-solving idea 2: Dynamic programming:
Let dp[i] denote the largest consecutive partial sum ending with the number in the i-th position. It is not difficult to find that dp[1] = -2, dp[2] = 11, dp[3] = 25... ...the state transition equation is:
dp[i] = max(a[i],dp[i - 1] + a[i]);
AC code 2:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N];//Storing data
int dp[N];//dp[i] represents the largest continuous sum ending with the number at the i-th position
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i];
dp[1] = a[1];
int ans = -1;
for (int i = 2;i <= n;i++)
{
//Two cases of dp[i]: 1. Choose a[i]:dp[i - 1] + a[i] 2. Don't choose dp[i - 1] to get a[i], take the larger value
dp[i] = max(a[i],dp[i - 1] + a[i]);
ans = max(ans,dp[i]);
}
cout << ans;
return 0;
}Problem C: Even and Odd Numbers
topic description
Small W defines a parity exchange rule. When a number x is even, it becomes x/2. When x is odd, it becomes x-1 until x becomes 1.
Using this rule, we can write path(x) to represent a sequence that starts from x and changes according to the above rules. For example, path(1)=[1],path(15)=[15,14,7,6,3,2,1],path(32)=[32,16,8,4,2,1] .
Now what we require is a maximum y, so that y appears in at least k path(x), where 1≤x≤n.
For example, when n=11 and k=3, the answer is 5, because 5 appears in path(5), path(10), and path(11). Specifically, let’s look at these: path(5)= [5,4,2,1],path(10)=[10,5,4,2,1],path(11)=[11,10,5,4,2,1], no bigger The number of occurrences is at least 3 times.
For another example, when n=11, k=6, the answer is 4, because 4 is in path(4),path(5),path(8),path(9),path(10),path(11) All have appeared, and no larger number has appeared at least 6 times.
enter
Enter a line with only two positive integers n and k.
output
Output the largest integer y that satisfies the condition.
sample input
[Example 1] 11 3 [Example 2] 11 6 [Example 3] 20 20 [Example 4] 1000000 100
sample output
[Example 1] 5 [Example 2] 4 [Example 3] 1 [Example 4] 31248
hint
For 100% of the data, 1≤k≤n≤10^18;
train of thought
The construction law of each digital answer can be deduced through simulation. When the integer x is an even number, the number of x in the path is x,x+1,2x,2x+1,2x+2,2x+3..., when the integer x is The odd number is the number x,2x,2x+1,2x+2,2x+3..., so for the odd number and the even number, they have continuity respectively, which can be solved (two points)
AC Code:
#include<iostream>
using namespace std;
#define int long long
int n,k;
bool judge(int x)
{
int left=x,right=x+1;
if(x&1)
right--;
int ret=0;
while(left<=n)
{
ret+=min(n,right)-left+1;
left<<=1;
right=(right<<1)+1;
}
return ret>=k;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> k;
int l=1,r=n+1,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
int tot=mid<<1;
if(judge(tot))
{
ans=max(ans,tot);
l=mid+1;
}
else if(judge(tot-1))
{
l=mid+1;
ans=max(ans,tot-1);
}
else
r=mid-1;
}
cout << ans;
return 0;
}Problem I: Weird License Plate Numbers
topic description
The license plate number of a car is an 8-digit number, and the highest digit can be 0, so the license plate number ranges from 00000000 to 99999999.
A car had an accident and the driver fled. Three witnesses tipped off the police.
A: The first 4 digits of the license plate number are increasing natural numbers, such as 0 1 2 3 , or 1 2 3 4 ,... at most 6 7 8 9
B: The last 4 digits of the license plate number are also increasing natural numbers
C: The sum of the numbers of the license plate number is the square of an integer
For example: 0 1 2 3 1 2 3 4 is to meet the above three conditions
0 1 2 3 and 1 2 3 4 are both increasing natural numbers, and their sum 16 is the square of 4.
Of course, there are still many license plate numbers that meet the above three conditions. Your task is to find the number of all license plate numbers that meet the conditions.
enter
none
output
An integer, that is, the number of license plate numbers that meet the condition.
Ideas:
Simulate according to the requirements of the topic
AC Code:
#include<iostream>
#include<cmath>
using namespace std;
int cnt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for(int a=0,b=1,c=2,d=3;a<=6;a++,b++,c++,d++)
{
for(int aa=0,bb=1,cc=2,dd=3;aa<=6;aa++,bb++,cc++,dd++)
{
int sum=a+b+c+d+aa+bb+cc+dd;
if((int)sqrt(sum)*(int)sqrt(sum)==sum)
{
cnt++;
}
}
}
cout << cnt;
return 0;
}Problem J: Faceted Dice
topic description
Luo Luo now has three multi-sided dice in his hand. Multi-sided dice are not the usual six-sided dice, but 33-sided dice, 100-sided dice... Generally speaking, the points on each side of i-sided dice are 1, 2, 3 ,...i.
The three dice in Luo Luo's hand may have different sides. He wants to know when the sum of the points of the three dice appears the most times in all the situations in which the three dice are thrown.
If there are multiple points with the same number of occurrences, the sum of points will be output in ascending order.
enter
The first line inputs three integers n1, n2, n3, which respectively represent the number of sides of the three dice.
output
Output a line containing any number of integers, respectively representing the sum of the points with the largest number of times, separated by spaces.
sample input
Sample input 1 1 2 3 Sample input 2 2 3 4
sample output
Sample output 1 4 5 Sample output 2 6
hint
[Example Explanation]
Example 1, the dice are cast in the following six situations:
1+1+1=3 1+1+2=4 1+1+3=5
1+2+1=4 1+2+2=5 1+2+3=6
It can be seen that 4 and 5 have the most occurrences and both are 2 times.
For 50% of the data, it is guaranteed that 1 ≤ n1, n2, n3 ≤ 5;
For 80% of the data, it is guaranteed that 1 ≤ n1, n2, n3 ≤ 10.
For 100% of the data, it is guaranteed that 1 ≤ n1, n2, n3 ≤ 100.
Ideas:
Just simulate the example given in the title
AC Code:
#include<iostream>
using namespace std;
int c[330];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n1,n2,n3,maxx=0;
cin >> n1 >> n2 >> n3;
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
for(int k=1;k<=n3;k++)
{
if(i+j+k>maxx)
{
maxx=i+j+k;
}
c[i+j+k]++;
}
}
}
int x=3;
for(int i=4;i<=maxx;i++)
if(c[i]>c[x])
x=i;
for(int i=3;i<=maxx;i++)
if(c[i]==c[x])
cout << i <<" ";
return 0;
}Problem K: Queuing
topic description
When Lolo travels, he finds that there are more and more civilized phenomena in the society. People will spontaneously wait in line when buying tickets.
It is a pity that the heights of the people in the queue are uneven, and sometimes the height difference between the two people before and after is too large, which lacks some aesthetic feeling.
If the height difference between the front and back two people (the difference is a positive number) is expressed as the degree of violation when the two are adjacent to each other, the sum of the degree of violation of a continuous group of people because of the difference in height between the two people before and after can be calculated. called the violation value. Lolo wants to know which part of the team he is in, and the team is composed of m consecutive individuals, and the violation value is the smallest.
enter
The first line inputs two positive integers n, m, n represents the total number of teams, and m represents the number of people in a certain segment.
Enter n integers in the second line, indicating the height of n people in the team (unit: cm).
output
The output contains an integer, the minimum violation value.
sample input
Sample input 1 4 3 1 2 4 7 Sample input 2 4 3 10 7 5 4
sample output
Sample output 1 3 Sample output 2 3
hint
Example 2 description: m=3, there are two ways to select 3 consecutive people:
10 7 5: The sum of violation degrees=3+2=5
7 5 4: The sum of violation degrees=2+1=3
So the answer is 3.
For 50% of the data guarantee 2 ≤ n ≤ 10;
For 80% of the data guarantee 2 ≤ n ≤ 1000;
For 100% data guarantee 2 ≤ n ≤ 100000, 1 ≤ m < n, each person's height does not exceed 300 cm.
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,k;
cin >> n >> k;
int minn=0,l=0;
int a[n],s[n]={0};
for(int i=1; i<=n; i++)
{
cin>>a[i];
if(i>0)
{
s[i-1]=abs(a[i]-a[i-1]);
}
}
for(int i=1; i<k; i++)
{
l+=s[i];
}
minn=l;
for(int i=2;i<=n-k+1;i++)
{
l=l-s[i-1]+s[i+k-2];
if(l<minn)
{
minn=l;
}
}
cout << minn;
return 0;
}Question L: Summer camp flag bearer
topic description
In 2014, the "Information and the Future" elementary school summer camp in Jiangsu Province was held at the Hexi Branch of Jinling Middle School. The organizing committee decided to recommend a small flag bearer from the students of the Hexi Branch and output the corresponding number.
Every student in the Hexi branch has a name in Chinese pinyin. The characters in the name are all uppercase English letters without spaces, for example:
Name: Wang Xiaoming, pinyin WANGXIAOMING
Each uppercase letter corresponds to an ASCII number, as shown in the following table:
character encoding (decimal number)
'A' 65
'B' 66
... ...
'Z' 90
The sum of the ASCII codes of the characters in the name is the student's number, for example:
Name: ABCD Number: 266 (ie 65+66+67+68)
Your task is to output the corresponding number based on the given student's name.
enter
A string of uppercase letters with a length not exceeding 20
output
Corresponding student number
sample input
ABCD
sample output
266
Ideas:
Add the ASCII code of each character in the string
AC Code:
#include<iostream>
#include<string>
using namespace std;
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> s;
int ans=0;
for(int i=0;i<s.size();i++)
ans+=(int)(s[i]);
cout << ans;
return 0;
}Problem M: Flower beds
topic description
When Luo Luo was taking a walk, he saw many unknown flowers blooming in the square flower beds in the park. After careful observation, he found that the planting positions of these flowers were regular.
Luo Luo found that the flowers on the outermost layer of the square flower bed, that is, the first layer, are all the same color; and on the second layer of the flower bed, the flowers are all the same color... A square flower bed is composed of several layers of flowers, and the flowers on the same layer The flowers on the top are all the same color, and the colors of the flowers between different layers are not necessarily the same. As shown in the picture below, it is a square flower bed with three layers of flowers:
After returning home, Luo Luo still remembered how many layers of flowers surrounded the flower bed, and the color of each layer of flowers. The colors of flowers were represented by upper and lower case letters. But Luo Luo forgot the image of the entire flower bed, and Luo Luo hopes that you can express the image of the entire flower bed in the form of computer-printed characters according to his description.
enter
Input an integer n in the first line, indicating that there are n layers of flowers in a square flower bed.
Enter n characters in the second line, and the i-th character represents the color of the flower on the i-th floor. The first layer is the outermost layer of the flower bed. The nth layer is the innermost layer of the flower bed, with only one flower.
output
Output 2*n-1 lines, an image of a flower bed consisting of (2*n-1)*(2*n-1) characters.
sample input
Sample input 1 3 abC Sample input 2 4 abac
sample output
Sample output 1 aaaaa abbba abCba abbba aaaaa Sample output 2 aaaaaaa abbbbba abaaaba abacaba abaaaba abbbbba aaaaaaa
hint
Example Explanation]
Example 1, as shown above, has only three layers of flowers:
The first layer is the flower whose color is character a, in the outermost layer;
The second layer is a flower whose color is character b, on the second layer.
The third layer is the flower whose color is the character c, and there is only one flower, which is in the innermost layer.
For 20% of the data, it is guaranteed that there is only one flower, and the color is character a;
For 50% of the data, it is guaranteed that 1 ≤ n ≤ 10, the color is only represented by lowercase letters,
For 80% of the data, 1 ≤ n ≤ 100 is guaranteed.
For 100% of the data, it is guaranteed that 1 ≤ n ≤ 1000, and the colors are represented by lowercase letters and uppercase letters.
Note: For flowers in different layers, there may be cases where the color is the same.
AC Code:
#include<iostream>
#include<string>
using namespace std;
int n,l=0,k;
string s;
char a[2005][2005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> s;
k = 2 * n - 1;
for(int j = 0 ; j < n ; j ++ )
{
for(int i = j ; i < k ; i ++ )
a[j][i] = a[i][k-1] = a[k-1][i] = a[i][j] = s[j];
k--;
}
for(int i = 0 ; i < 2 * n - 1 ; i ++)
{
for(int j = 0 ; j < 2 * n - 1 ; j ++ )
cout<<a[i][j];
cout<<"\n";
}
return 0;
}Problem N: Sum of Odd and Even Numbers
topic description
Given a positive integer n (1≤n≤1000), find the sum of all odd numbers and the sum of all even numbers in 1, 2, ... n.
For example: n=9
Odd sum 1+3+5+7+9=25
Even sum 2+4+6+8=20
sample input
9
sample output
25\20
Ideas:
n is less than or equal to 1000, the result will definitely not explode int, just define two variables to record the sum of odd numbers and the sum of even numbers respectively
AC Code:
#include<iostream>
using namespace std;
int n,odd,even;
//odd records the sum of odd numbers between 1 and n
//even records the sum of even numbers between 1 and n
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++)
{
if(i&1)
odd+=i;
else
even+=i;
}
cout << odd << "\\" << even;
return 0;
}Problem P: Listening to songs and recognizing them
topic description
Luo Luo has a private playlist, which is full of his favorite songs, such as Xia Lian, Yu Dao, Caiyue, Huan Zhou... there are hundreds of them. Luo Luo listens to his playlist every day, so that he can know what song is playing at what time.
After Lolo recommended his playlist to you, he decided to test you. From the start of his playlist, which song is being played at the t second.
enter
The first line inputs two integers n and t, which respectively represent the total number of songs in the playlist and which song is played at the tth second.
The second line has n integers, A1, A2,..., An, respectively indicating how long the i-th song in the playlist will be played.
output
Output an integer, indicating which song is played at the t-th second after the playlist is played in order.
sample input
Sample input 1 3 5 5 5 5 Sample input 2 3 5 1 4 5 Sample input 3 3 5 1 3 5
sample output
Sample output 1 1 Sample output 2 2 Sample output 3 3
hint
[Example 3 Explanation]
There are three songs in total:
The first song is played for 1 second, accounting for the first 1 second;
The second song plays for 3 seconds, accounting for 2-4 seconds;
The third song plays for 5 seconds, accounting for 5-9 seconds.
So the third song is played in the 5th second.
For 30% of the data, it is guaranteed that 1≤n≤3;
For 60% of the data, it is guaranteed that 1≤n≤2000, 1≤Ai≤500;
For 100% of the data, it is guaranteed that 1≤n≤100000, 1≤Ai≤1000, 1≤t≤A1+A2+....+An.
Ideas:
This is a practice problem of prefix sum, traverse the prefix and array from front to back, find a certain sum[i]>=t, output the current i, and then end the program
AC Code:
#include<iostream>
using namespace std;
int n,T,t[100001];
int sum[100001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> T;
for(int i=1;i<=n;i++)
cin >> t[i];
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+t[i];
for(int i=1;i<=n;i++)
{
if(sum[i]>=T)
{
cout << i;
return 0;
}
}
return 0;
}Problem S: Maximum length of consecutive non-prime numbers
topic description
Given a positive integer n (2≤n≤1000000), for example n=30, in 1, 2, 3, ... 30, the continuous non-prime numbers have
4 with a length of 1
6 length is 1
8 9 10 has a length of 3
12 length is 1
14 15 16 length is 3
18 length is 1
20 21 22 has a length of 3
24 25 26 27 28 length is 5
30 length is 1
Among them, the maximum length is 5, that is, there are 5 consecutive non-prime numbers.
enter
an integer n
output
An integer, i.e. the maximum length of consecutive non-prime numbers
sample input
12
sample output
3
Ideas:
Just enumerate it directly
AC Code:
#include<iostream>
using namespace std;
bool isprime(int n)
{
if(n==0||n==1)
return 0;
if(n==2||n==3||n==5)
return 1;
if(n%2==0||n%3==0)
return 0;
for(int i=5;i*i<=n;i+=6)
{
if(n%i==0||n%(i+2)==0)
return 0;
}
return 1;
}
//Determine whether n is a prime number, if it is a prime number, return 1, otherwise return 0
int n,maxx,s=0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++) {
if(!isprime(i))
{
s++;
maxx=max(s,maxx);
}
else
s=0;
}
cout << maxx;
return 0;
}