1. Question report:
(The following are the scores after supplementary questions)
(1) Score:
T1: [Late]: 100
T2: [Climb the ladder]: 100
T3: [Hamster Queue]: 100
T4: [square matrix]: 100
Total score: 400/400
(2) Question analysis:
1.No.1
Late:
Title description
The entire map can be viewed as a one-dimensional number axis. The coordinates of Xiaoke’s home are x, and the coordinates of the school are y. Xiaoke now has two modes of transportation:
1. Walk. To walk a distance of unit length 11, the time consumed is a
2. Ride a shared bicycle. Riding a shared bicycle over a distance of unit length 11 consumes time b, but borrowing and returning the bicycle requires c time.
If Xiaoke chooses to walk, he can walk directly to school. But if you choose to ride a shared bicycle, you still need to go to coordinate z, then borrow the bicycle, ride it, arrive at the school, and then return the bicycle.
May I ask Xiaoke how to get to school the fastest? .
Enter description
Multiple inputs. A positive integer T in the first line represents the number of input groups.
For each set of input, there is a row of six integers x, y, z, a, b, c, with the meanings as shown in the title.
Output description
For each set of data, if the walking time does not exceed the riding time, output Walk, otherwise output Ride.
Sample input
56 6 5 6 9 58 3 9 6 7 103 6 2 9 1 58 6 5 5 10 510 1 1 7 9 8
Sample output
WalkWalkRideWalkWalk
Data range
For 100% of the data, no data entered is greater than 1000.
Idea:
(My idea): Define a walk (representing the time of walking) and define a ride (representing the time of riding)
Walking time: |x-y|a (|| is an absolute value such as: |1|=1, |-1|=1)
Cycling time: |x-z|a (|| Same as above) The total time for borrowing and returning the car is 2c, and the cycling time is |z-y|b.
Note:
No.
Code:
#include<iostream>
using namespace std;
int main(){
// freopen("late.in","r",stdin);
// freopen("late.out","w",stdout);
int n;
cin>>n;
int x,y,z,a,b,c;
for(int w=1;w<=n;w + + ){
cin>>x>>y>>z>>a>>b>>c;
int walk=0,ride=2*c;
int len=max(x,y);
int le=min(x,y);
for(int i=le;i<len;i + + ){
walk + =a;
}
len=max(x,z);
le=min(x,z);
for(int i=le;i<len;i + + ){
ride + =a;
}
len=max(z,y);
le=min(z,y);
for(int i=le;i<len;i + + ){
ride + =b;
}
if(walk<=ride){
cout<<"Walk"<<endl;
}
else{
cout<<"Ride"<<endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
2.No.2
Climb the ladder
Title description
There is a poker game called “Climb the Ladder”, also known as “Train Line”.
The rules of the game are: Divide all playing cards (except the king and king) into two parts, one for each person. Next, take turns to play out the cards and line up the played cards in a row. If the same card appears (ignoring the suit), you can take away all the cards between the two identical cards.
NOTE: Cards taken away are set aside for final scoring instead of being added to the hand.
Now Xiaoke and Dada have determined the order of playing cards. Obviously the winner of the game has been decided by this time, so they have no interest in playing anymore. But they want to know the outcome of the game. So they find you and want you to figure out who wins.
Enter description
Poker card 10 is represented by 0, and other characters are represented by corresponding characters.
The first line of 26 characters represents Xiao Ke’s hand.
The second line of 26 characters represents Dada’s hand.
Output description
The first line is a string. If Xiao can win, it will output xk, if Dada wins, it will output dd, and if it is a tie, it will output Equal;
The two numbers in the second line represent the final number of cards for Xiao Ke and Dada respectively.
Sample input
A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 J J Q Q K K A A 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 J J Q Q K K
Sample output
dd
0 52
Data range
Ensure that the input is a deck of playing cards.
Ideas:
Just use array/string/stack to simulate.
Note:
Remember to change subscripts when simulating.
Code:
#include<iostream>
using namespace std;
int main(){
char a[30],b[30],ans[60];
for(int i=1;i<=26;i + + ){
cin>>a[i];
}
for(int i=1;i<=26;i + + ){
cin>>b[i];
}
int sum=0,t=0,anns=0;
for(int i=1;i<=26;i + + ){
ans[ + + t]=a[i];
for(int j=1;j<=t-1;j + + ){
if(ans[j]==a[i]){
sum + =t-j + 1;
t=j-1;
}
}
ans[ + + t]=b[i];
for(int j=1;j<=t-1;j + + ){
if(ans[j]==b[i]){
anns + =t-j + 1;
t=j-1;
}
}
}
if(sum==anns){
cout<<"Equal";
}
if(sum>anns){
cout<<"xk";
}
if(sum<anns){
cout<<"dd";
}
cout<<endl<<sum<<" "<<anns;
return 0;
}
3.No.3
Hamsters line up
Title description
Xiao Ke raises n hamsters, and each hamster has a fixed amount of food a?i.
Now Xiaoke wants to line up these n hamsters in a row. For the first (i≥2) hamsters, if the gcd of their food amount is greater than i, then they will fight.
Xiao Ke wanted to know if there was an arrangement that would prevent all hamsters from fighting.
Enter description
Multiple inputs. The first line is a positive integer t, representing the number of groups of input groups.
For each set of input, the first line contains a positive integer n, representing the number of hamsters.
The second line contains n positive integers, representing the amount of food for each hamster.
Output description
For each set of inputs, if there is an arrangement that prevents the hamsters from fighting, then output Peace, otherwise output Fight
Sample input
3
2
1 2
5
3 4 5 4 2
3
3 6 9
Sample output
Peace
Peace
Fight
Sample explanation
For the first set of inputs, it can be arranged as 1,2
For the second set of inputs, it can be arranged as 2,4,5,4,3
In the third set of inputs, we can find that no matter how they are arranged, the hamsters will definitely fight.
Of course, the arrangement may not be unique, we just need to determine whether it can prevent the hamsters from fighting.
Data range
For 20% of the data, a?i is completely random in the range [1,10 to the 9th power]
For the other 20% of the data, a?i is a prime number
For the other 20% of the data, n≤10
For 100% of the data, 2≤n<=100, 1≤t<=100, 1≤ai<=10 to the 9th power
Ideas:
There is a conclusion: for a set, if we add numbers to the set, the value of the entire set will not increase. Either remain unchanged or decrease.
So as long as there is an arrangement scheme that satisfies the gcd of the first two numbers to be less than or equal to 2, then the following numbers will not be greater than 2 no matter how they are arranged. So in this case, hamsters will definitely not fight.
Then the problem becomes to find whether there are two numbers whose gcd is less than or equal to 2, just enumerate directly.
Note:
The data range of this question is small, and you can directly use three-level nested loops to traverse the enumeration.
Code:
#include<iostream>
using namespace std;
int gcd(int a,int b){
int r;
while(a%b!=0){
r=a%b;
a=b;
b=r;
}
return b;
}
int main(){
int t;
cin>>t;
int n,a[105];
for(int w=1;w<=t;w + + ){
cin>>n;
for(int i=1;i<=n;i + + ){
cin>>a[i];
}
int f=0;
for(int i=1;i<=n;i + + ){
for(int j=1;j<=n;j + + ){
if(gcd(a[i],a[j])<=2){
cout<<"Peace\
";
f=1;
break;
}
}
if(f==1){
break;
}
}
if(f==0){
cout<<"Fight\
";
}
}
return 0;
}
4.No.4
phalanx
Title description
There are n people in Xiaoke’s class, and everyone belongs to a group. Groups are numbered from 1 to m (there may not necessarily be people in each group).
Everyone has an execution ability. This execution power may be a positive integer or a negative number. The higher the execution ability, the faster and better everything will be done when this person is present.
Now the class has to select several groups to go out and form a square formation. Select a number of people from each selected group. But make sure that in each selected group, the same number of people are selected.
Please tell me, what is the highest total execution ability of all selected people?
Enter description
The two positive integers n and m in the first line represent the number of people in the class and the number of groups;
The next n lines have two numbers in each line, indicating which group the person belongs to and what the person’s execution ability is.
Output description
If asked, output the answer.
Sample input
5 3
1 8
2 8
2 5
3 -5
1 0
Sample output
21
Data range
For 30% of the data, it is guaranteed that everyone’s execution power is a positive integer.
For 60% of the data, n≤1000
For 100% of the data, n≤10 to the 5th power, 1≤m≤n, ensure that the final result is within the range of long long.
Ideas:
1. Greedy
No matter how many people are selected, we will definitely give priority to those with the greatest execution ability.
So when we select i people in the th group, we must choose the largest k people. So we have to sort the people in each group from largest to smallest. Prefixes and optimizations can be used at the same time.
We can use vector arrays for grouping operations, then sort each group from large to small, and then find the prefix sum within each group.
We know the previous greedy strategy, so for each group, when we find the prefix sum, we can determine whether we should choose person i when we choose it. Put the selected situation into the ans array and find the maximum value.
Note:
The idea of this question is not easy to think about. The main idea is to use vector. The reason why this question is implemented using vector is because it is impossible to determine the specific number of people in each group, so we can only declare a two-dimensional array or structure according to the maximum upper limit, resulting in memory overrun. Therefore, consider using dynamic vector to implement it.