Personal Competition, April 19, 2020

A - Buggy Sorting

Title: This title is to give you an incorrect sorting method, which requires you to determine if there is a correct running result.If the correct result exists, then output-1, otherwise output an example illustration is wrong.The input to the title is the number n of elements.

Question: This is an interesting question and it is easy to tell that the results are correct only when n=1 or n=2, and the rest are wrong.So we can construct a sequence.

Code:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<=2){
        cout<<-1;
    }else{
        for(int i=n;i>=1;i--){
            cout<<i;
            if(i!=1){
                cout<<" "; 
            }
        }
    }
    return 0;
} 

B - Increase and Decrease

Title: The general meaning of this question is to give you an int sequence of length n.You can choose any two of these numbers to do a + 1 and - 1 operation on them, and ask how many identical numbers can exist at most after several times.

Solution: It is easy to think of the + 1 and - 1 operations on two elements in the same array that its elements are always certain, which is a breakthrough point.Here we determine if an element's sum can be divided by n. If it can, the maximum number is n (which means there must be some way to make all elements the same). If not, there must be a remainder. In this case, we can discard this element and operate on other elements.Then the number of elements is n-1.

Code:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    int num[100005]={0};
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>num[i];
        sum=sum+num[i];
    }
    if(sum%n==0){
        cout<<n<<endl;
    }else{
        cout<<n-1<<endl;
    }
    return 0;
} 

E - Dividing Orange

Title: The general meaning of this question is that K people have an average score of n*k oranges, especially each person has an orange they must need, the others have no requirements.

Question: This is also a simple question (regret it).

Code: Here we just need to use a vis array to record which orange was divided, and then output the number of oranges in turn (with special attention to the number of oranges this person needs in particular).

Code:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    ll n,k;
    cin>>n>>k;
    int num[1000]={0};
    int vis[1000]={0}; 
    int t;
    for(int i=0;i<k;i++){ 
        cin>>vis[i];
        num[vis[i]]=1;
    }
    int len=0;
    for(int i=0;i<k;i++){
        len=0;
        cout<<vis[i]<<" ";
        len++;
        for(int j=1;j<=n*k;j++){
            if(len<n&&num[j]==0){
                cout<<j;
                num[j]=1;
                len++;
                if(len<=n-1){
                    cout<<" ";
                }
            }
        } 
        cout<<endl;
    } 
    return 0;
} 

F - Undoubtedly Lucky Numbers

Title: The general meaning of this question is that it defines a special number which contains no more than two categories of single numbers. Now you need to find out how many such numbers exist in [1,n].

Question: We didn't see this is a dfs after half a day of thinking about the game. Here we can think about it. We traverse all two combinations of numbers in [0,9], then arrange and combine them, put less than n into the set (can be weighted), and the final output is OK.

Knowledge Point: dfs Arrangement and Combination

Code:

#include<iostream>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
set<ll> st;
ll n;
void dfs(int a,int b,ll num){
    st.insert(num);
    ll ta=num*10+a;
    ll tb=num*10+b;
    if(ta&&ta<=n){
        dfs(a,b,ta);
    }
    if(tb&&tb<=n){
        dfs(a,b,tb);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            dfs(i,j,0);/*Each number starts with zero*/
        }
    }
    cout<<st.size()-1;
    return 0;
}

Tags: C++ REST less

Posted on Thu, 23 Apr 2020 09:34:04 -0700 by nepeaNMedia