CSP first week of question brushing

csp Brush problem

The first question is （ Array derivation ）

202109-1	Array derivation
http://118.190.20.162/view.page?gpid=T129

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
	long long n;
	long long sum_min=0,sum_max=0;

	cin>>n;
	long long B[n];
	for(long long i=0;i<n;i++){
        cin>>B[i];

        sum_max+=B[i];
	}
	for(long long i=1;i<n;i++){
        if(B[i]>B[i-1]){
            sum_min+=B[i];
        }

	}
	cout<<sum_max<<endl;
	cout<<sum_min+B[0]<<endl;
	return 0;
}

The second question is （ Gray histogram ）

202104-1	Gray histogram
http://118.190.20.162/view.page?gpid=T128

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,m,L;
    cin>>n>>m>>L;
    int num=n*m;
    vector<int> res(L);
    for(int i=0;i<num;i++){
        int data;
        cin>>data;
        res[data]++;
    }
    for(int i=0;i<L-1;i++){
        cout<<res[i]<<" ";
    }
    cout<<res[L-1]<<endl;
	return 0;
}

* Third question （ Neighborhood mean ）

202104-2	Neighborhood mean
	http://118.190.20.162/view.page?gpid=T127

Reference blog ：

https://blog.csdn.net/weixin_47946614/article/details/117392544?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164465892116781685343265%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=164465892116781685343265&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allbaidu_landing_v2~default-1-117392544.first_rank_v2_pc_rank_v29&utm_term=%E9%82%BB%E5%9F%9F%E5%9D%87%E5%80%BCC%2B%2B&spm=1018.2226.3001.4187

#include<bits/stdc++.h>
using namespace std;
int n,l,r,t,A[601][601],s[601][601];
void solve(){
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){// Transform the neighborhood into the form of matrix  (i_min,j_min) (i_max,j_max) For this position, the boundary of the neighborhood matrix 
            double cal=0;
            int i_max=min(n,i+r);
            int i_min=max(1,i-r)-1;
            int j_max=min(n,j+r);
            int j_min=max(1,j-r)-1;
            double sum=s[i_max][j_max]-s[i_max][j_min]-s[i_min][j_max]+s[i_min][j_min];
            int num=(i_max-i_min)*(j_max-j_min);// The number of elements in the matrix 
            cal=(double)sum/(double)num;// The average must be kept in decimal places 
            if(cal<=t) ans++;
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>l>>r>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>A[i][j];
        }
    }
    for(int i=1;i<=n;i++){// Construct prefixes and arrays 
        for(int j=1;j<=n;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+A[i][j];
        }
    }
    solve();
    system("pause");
    return 0;
}

Fourth question （ It's called checkpoint query ）

202009-1	It's called checkpoint query
	http://118.190.20.162/view.page?gpid=T113

Ideas ：

1. Define a structure , Storage number and distance
2. By rewriting the sorting method , If the distance is the same , Small numbers are preferred , Otherwise, short distance is preferred
3. adopt sort Function pair vector Sort , Then output the numbers of the first three elements

#include<bits/stdc++.h>
using namespace std;
struct point{
int id;
double sum;
};
bool cmp(point a,point b){
	if(a.sum==b.sum){
    	return a.id<b.id;
	}else{
		return a.sum<b.sum;
}
}
int main()
{
   int n,X,Y;
   cin>>n>>X>>Y;
   vector<point> res(n);
    // Input 
  for(int i=0;i<n;i++){
    int x,y;
    cin>>x>>y;
    res[i].id=i+1;
    res[i].sum=pow(x-X,2)+pow(y-Y,2);
   }
    // Sort 
   sort(res.begin(),res.end(),cmp);
    // Output 
   for(int i=0;i<3;i++){
    cout<<res[i].id<<endl;
   }

    return 0;
}

Fifth question （ Divide the cake ）

201703-1	Divide the cake
	http://118.190.20.162/view.page?gpid=T57

Ideas ：

1、 Count how many people got the cake , That is, maintain a variable weight,weight Indicates the weight of the cake in the hands of the friend who is being assigned the cake .
2、 Add the input data to weight On , When weight >= k when , Show friends A Your cake has been distributed , At this time, the number of people assigned to the cake increases 1, Then for the next friend B Distribute the cake , At this time, friends B No cake yet , So will weight Set as 0, Then start with the smallest number of the remaining cakes for friends B Divide the cake .
3、 If the cake has been distributed , But this time weight Not for 0, It means there is a friend C At the end, I got the cake , But he's a little dark , The weight of the cake is less than k, But he still got the cake , So the final number has to be increased 1.
4、 Output number .

/*
20190817
ccf test questions 1： Divide the cake  
*/
#include <iostream>
using namespace std;

int main(){
	// Receive input data  
	int n, k;
	cin >>n;
	cin >>k;
	int arr[n];
	for(int i=0; i<n; i++){
		cin >>arr[i];
	} 
	
	// Count the number of people 
	int index = 0;
	int weight = 0;
	for(int i=0; i<n; i++){
		weight += arr[i];
		if(weight >= k){
			index++;
			weight = 0;
		}
	} 
	if(weight != 0){
		index += 1;
	}
	 
	// Output results  
	cout <<index<<endl;
	return 0;
} 

Sixth question （ Small, medium and large ）

201703-1	Divide the cake
http://118.190.20.162/view.page?gpid=T89

80 Decomposition ：

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n;
    vector<int> res(n);
    for(int i=0;i<n;i++){
        cin>>res[i];
    }
    sort(res.begin(),res.end());
    int mid=0;
    if(n%2==0){
        mid = (res[n/2]+res[n/2-1])/2;
    }else{
    mid = res[n/2];
    }
    cout<<res[n-1]<<" "<<mid<<" "<<res[0];

    return 0;
}

100 Decomposition ：

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  float mid;
  int mid1,mid2,max,min;
  int temp;
  cin>>n;
  cin>>temp;
  mid1=mid2=max=min=temp;
  // find   The possible value of the median    if n It's odd   mid1 and mid2  Pointing to the same location ,  If even , Then point to the two in the middle 
  for(int i=2;i<=n;i++){
    cin>>temp;
    if(i == ((n+1)/2)){
        mid1=temp;
    }
    if(i == (n/2)+1){
        mid2=temp;
    }
    if(temp>max)
			max = temp;
    if(temp<min)
			min = temp;
  }
//  cout<<"mid1:"<<mid1<<"mid2:"<<mid2<<endl;
  // In the real sense mid
mid = (mid1 + mid2)/2.0;
temp = mid;
// cout<<"mid:"<<mid<<"temp:"<<temp<<endl;
  if(temp !=mid){ // Floating point conversion to integer represents the need to round 
     temp = (mid + 0.05)*10;
		mid = temp/10.0;
        cout<<max<<' '<<mid<<' '<<min<<' ';
  }else{
     	cout<<max<<' '<<temp<<' '<<min<<' ';
  }

    return 0;
}

Question seven （ The middle number ）

201612-1	The middle number
	http://118.190.20.162/view.page?gpid=T52

Ideas

• Sort the array first
• that , After sorting, the array must be in order , Then it must be from the middle. It is possible that the number on the left is equal to the number on the right

For example, the following two sorting cases

2 3 4 5 6

2 3 4 5

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> res(n);
    for(int i=0;i<n;i++){
        cin>>res[i];
    }
    sort(res.begin(),res.end());
    int temp = n/2;
    int countleft=0,countright=0;
   for(int i=0;i<n;i++){
    if(res[i]<res[temp]){
        countleft++;
    }
    if(res[i]>res[temp]){
        countright++;
    }
   }
   if(countleft==countright){
    cout<< res[temp];
   }else{
       cout<<-1;
   }

    //2 3 5 5 6 6
    return 0;
}

The eighth question （ The sum of numbers ）

201512-1	The sum of numbers
http://118.190.20.162/view.page?gpid=T37

Ideas ：

Use string Type to store

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    int sum=0;
    for(int i=0;i<str.size();i++){
        sum+=str[i]-'0';
    }
    cout<<sum;
    return 0;
}

Question 9 （ Image rotation ）

201503-1	Image rotation
http://118.190.20.162/view.page?gpid=T27

Ideas

1 5 3

3 2 4

Turn into ：

3 4
5 2
1 3

But in fact , Is to put the third column Change to the first line , The second column becomes the second line , The first column becomes the third row

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n,m;
   cin>>n>>m;
   int arr[n][m]={0};
   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        cin>>arr[i][j];
    }
   }
 for(int j=m-1;j>=0;j--)
    {
        for(int i=0;i<n;i++)
            cout<<arr[i][j]<<" ";
        cout<<endl;
    }



    return 0;
}

Question 10

201912-1	Number off
	http://118.190.20.162/submitlist.page?gpid=T100

Ideas ：

Define an array , Used to store the number of messages, including 7 Or divisible

adopt for Loop to report

adopt COUNT Used to record whether the reported number is reached n

Be careful ： Last i%4 Used to represent which subscript is methylethylpropionate （ Because it's divided by 4, If i%4==0, It stands for Ding , So the final output needs to be processed ）

#include<bits/stdc++.h>
using namespace std;
bool isContainSeven(int x){

if(x%7==0){return true;}
else {
 int remain = 0, b = 0;
    while (x)
    {
        remain = x % 10;

        if (remain == 7)
        {
            return true;
        }
        x = x / 10;
    }
}
    return false;
}
int main()
{
   int n,m;
   cin>>n;
  int COUNT=0;
  int arr[4]={0};
  for(int i=1;;i++){
    if(COUNT==n){break;}
    if(isContainSeven(i)){
        arr[i%4]++;
    }else{
         COUNT++;
    }
   // cout<<i<<" --"<<COUNT<<endl;


  }
  for(int i=1;i<4;i++){
    cout<<arr[i]<<endl;
  }
  cout<<arr[0]<<endl;


    return 0;
}