I
P1059 [NOIP2006 popularity group] clear random number
Title Description
Mingming wants to invite some students to do a questionnaire survey in the school. For the objectivity of the experiment, he first uses the computer to generate N random integers between 1 and 1000 (n ≤ 100). For the repeated numbers, only one is retained, and the other same numbers are removed. Different numbers correspond to different student numbers. Then sort these numbers from small to large, and go to the students to make a survey according to the arranged order. Please help Mingming to complete the work of "de duplication" and "sorting".
Input format
The input has two lines. The first line is a positive integer, which represents the number N of generated random numbers
Line 2 has N positive integers separated by spaces, which are the generated random numbers.
Output format
The output is also two lines. The first line is a positive integer MM, which represents the number of different random numbers.
The second line is M positive integers separated by spaces, which are different random numbers in good order from small to large.
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[1001]={0};
int i,t,cent=0;
for(i=0;i<n;i++)
{
scanf("%d",&t);
a[t]++;
}
for(i=0;i<1001;i++)
{
if(a[i]!=0)
{
cent++;
}
}
printf("%d\n",cent);
for(i=0;i<1001;i++)
{
if(a[i]!=0)
{
printf("%d ",i);
}
}
return 0;
}For a basic problem, bucket sorting is used to solve the problem of de duplication and sorting, but at the beginning of the final output, a[i] is output, that is, the number of occurrences is output. Here it should be changed to I, so that the random number can be output. This small problem is reflected in many problems in this problem. In the future, more attention should be paid to similar situations
II
P1152 happy jump
Title Description
An integer array of n elements. If the absolute value of the difference between two consecutive elements of the array includes all integers between [1,n-1], it is called "happy jump". For example, the number group 1423 is consistent with "happy jump", because the absolute values of the difference are: 3, 2 and 1 respectively.
Given an array, your task is to determine whether the array meets the "happy jump".
Input format
The first row of each group of test data starts with an integer n(1 ≤ n ≤ 1000), followed by an integer between [- 10 ^ 8,10 ^ 8] separated by N spaces.
Output format
For each group of test data, output a row. If the array meets the "happy jump", output "Jolly". Otherwise, output "Not jolly".
#include <stdio.h>
#include <math.h>
int main()
{
int n;
scanf("%d",&n);
int i,j,s,flag=0;
long long a[100000];
int b[100000];
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
for(i=1;i<=n-1;i++)
{
b[i]=0;
}
for(i=0;i<n-1;i++)
{
j=i+1;
s=a[i]-a[j];
s=abs(s);
b[s]=1;
}
for(i=1;i<n-1;i++)
{
if(b[i]==0)
{
flag=1;
break;
}
}
if(flag==0)
printf("Jolly");
if(flag==1)
printf("Not jolly");
return 0;
}We haven't found the problem of WA before, because we only noticed the condition in the topic (1 ≤ n ≤ 1000) and didn't notice the condition of "integer separated by N spaces between [- 10 ^ 8,10 ^ 8]. Therefore, we didn't create b array according to the value range, resulting in the array being too small. We can pass it after adjusting the size of the array
III
P5143 climber
Topic background
After HKE finished GDOI, he went mountain climbing with his God friends.
Title Description
He marked N points on the topographic map, and each point Pi has a coordinate (xi, yi, zi). In all point pairs, the height value z will not be equal. HKE is ready to climb from the lowest point to the highest point. His climbing meets the following conditions:
(1) Through every point he marked;
(2) Starting from the second point, the height z of each point he passes is higher than the previous point;
(3) HKE can fly. The distance he climbs from one point Pi to Pj is the Euclidean distance of two points. That is, sqrt{(Xi XJ) ^ 2 + (Yi YJ) ^ 2 + (Zi ZJ) ^ 2}
Now, HKE wants you to find out the total distance he climbs.
Input format
In the first line, an integer N represents the number of points on the map.
Next, in line N, three integers xi, yi, zi ， represent the coordinates of the ith point.
Output format
A real number indicating the total distance HKE needs to climb (three decimal places)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
struct dis
{
double x;
double y;
double z;
};
struct dis a[50002],temp;
void quicksort(int left,int right)
{
double t=a[left].z;
int i=left;
int j=right;
if(left>right)
return ;
while(i!=j)
{
while (a[j].z>=t&&j>i)
j--;
while(a[i].z<=t&&i<j)
i++;
if(i!=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i];
a[i]=a[left];
a[left]=temp;
quicksort(left,i-1);
quicksort(i+1,right);
}
int main()
{
int n;
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
scanf("%lf %lf %lf",&a[i].x,&a[i].y,&a[i].z);
}
quicksort(0,n-1);
double d;
d=0;
for(i=0;i<n-1;i++)
{
d+=sqrt((a[i+1].x-a[i].x)*(a[i+1].x-a[i].x)+(a[i+1].y-a[i].y)*(a[i+1].y-a[i].y)+(a[i+1].z-a[i].z)*(a[i+1].z-a[i].z));
}
printf("%.3lf",d);
return 0;
}There are three points to pay attention to in this topic
1 understanding of the topic, "starting from the second point, the height z of each point he passes through is higher than the previous point", which shows that no matter how input, the order of the real points should be in the order of z from small to large
2. Bubble is used in the first sorting, but when judging J and j+1, the range of J is j < n-i, and j+1 is equal to n-i, resulting in an error
3 again, it was found that bubble sorting could not meet the time requirements of the question. After many attempts, I chose quick sorting, and finally met the time requirements of the question. Pass
There are few questions for learning new knowledge points this week, but the summary is also the typical or common mistakes made this week. I hope that if similar mistakes occur again in the future, we can quickly find the specific points of the mistakes and corresponding solutions