April 12, 2020 individual competition

A - Balloons

Meaning: the meaning of this question is relatively simple. In short, it is to divide the numbers so that the sum of the numbers obtained by A is greater than the sum of the numbers obtained by B, and then output the subscript of the numbers distributed to A.

Question solution: pay attention to the special judgment of n==1 and n==2, which belongs to the sign in question.

Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int main() {
    int n;
    cin>>n;
    int num[20]= {0};
    int sum=0;
    for(int i=1; i<=n; i++) {
        cin>>num[i];
        sum=sum+num[i];//Total
    }
    if(n==1) {
        cout<<-1<<endl;
    } else if(n==2) {
        if(num[1]==num[2]) {
            cout<<-1<<endl;
        } else {
            cout<<1<<endl;
            cout<<1<<endl;
        }
    } else { //Greater than or equal to 3
        int su=0;
        int i;
        int f=0;
        for(i=1; i<=n; i++) {
            su=su+num[i];
            sum=sum-num[i];
            if(su!=sum&&sum!=0&&su!=0) {
                f=1;
                break;
            }
        }
        if(f==1) {
            cout<<i<<endl;
            for(int j=1; j<=i; j++) {
                cout<<j;
                if(j<i) {
                    cout<<" ";
                }
            }
            cout<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}

B - Cutting

Meaning: this question is also relatively simple. The question gives you an array of length n. you can "cut off" between two numbers at the cost of the absolute value of the difference between the two numbers.

Problem solving: there are several solutions to this problem. Here I write it with a backpack (0-1). The key is to judge that a knife can be cut between those two numbers. The cost is used as consumption, and the profit gained is regarded as "1". In this way, it is a naked problem of "0-1 backpack".

Code:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int n,B;
    cin>>n>>B/*This is equivalent to a total volume*/;
    int num[250]={0};
    int jnum=0,onum=0;
    for(int i=0;i<n;i++){
        cin>>num[i];
        if(num[i]%2==0){
            onum++;
        }else{
            jnum++;
        } 
    }//After data input, start to process data
    int t=0;//Number of records
    int V[200]={0},W[200]={0};
    int tj=0,to=0;//Decibels represent the number of odd and even numbers ahead 
     for(int i=0;i<n;i++){//Gap 
        if(i+1<n){
            if(num[i]%2==0){
                to++;
            }else{
                tj++;
            }
            if((tj==to)&&((jnum-tj)==(onum-to))){
                W[t]=1;
                V[t++]=abs(num[i]-num[i+1]);
                tj=0;
                to=0;
            }
        }
    }        
    int dp[500]={0};
    for(int i=0;i<t;i++){
        for(int j=B;j>=V[i];j--){
            dp[j]=max(dp[j],dp[j-V[i]]+1);
        }
    }
    cout<<dp[B]<<endl;
    return 0;
}

D - Sonya and Hotels

Question meaning: this question roughly means, give you a string of numbers, insert a number between numbers, ask the absolute value of the difference between this number and its adjacent number = d, and ask how many insertion points there are.

Solution: this problem is relatively simple. Here we find the difference between two adjacent numbers. If the difference is more than 2*d, we can insert two numbers. The difference = 2*d, we can insert one. Pay attention to the last two endpoints.

Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int main() {
    ll n,d;
    cin>>n>>d;
    int temp,p;
    cin>>temp;
    ll ans=0;
    for(int i=1;i<n;i++){
        cin>>p;
        if(p-temp-2*d>0){
            ans++;
            ans++;
        }else if(p-temp-2*d==0){
            ans++;
        }
        temp=p;
    }
    cout<<ans+2;

    return 0;
}

 E - Sonya and Exhibition

Question meaning: this question is more interesting. Roughly speaking, there are n flowers, which can be lilies or roses. There are m people. Give their observation range, find the sum of their beauty value (equal to the number of roses * the number of lilies), and find the maximum value of this beauty value.

Solution: the key to this problem is to know that in order to maximize a single beauty value, it is necessary to make the number of two kinds of flowers in the interval equal. There is also a pit where he gives m people. If there is only one person, this is a good discovery. Here, we just need to make two kinds of flowers alternate. (like a brain teaser)

Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
int main() {
    ll n,m;
    cin>>n>>m;
    ll li,ri;
    char ptr[10000];
    for(int i=0;i<m;i++){
        cin>>li>>ri;
    }
    for(int i=0;i<n;i++){
        if(i%2==0){
            cout<<1;
        }else{
            cout<<0;
        }
    }

    return 0;
}

F - Sonya and Robots

The basic requirement is to give you a string of int arrays with n elements, from which you need to find two numbers, assign the two numbers to two cars respectively, and make them move in opposite direction. In the array, when encountering the same number words as the car, the car will stop moving. When the final relative position of the two cars changes, the car will be damaged Yes, ask the logarithm of the number taken from this array, how many can make the car undamaged.

Problem solving: this problem is also a simple problem in essence, but I didn't read it during the competition, and I probably can't write it after reading it. What the online problem solving gives is to record how many kinds of cars there are on the left side of each car, and then add them up. Unfortunately, my idea is just the opposite. What I think of is to record the number of kinds of cars on the right side, but I haven't written it out yet. It's a thought Lesson from.

Code:

#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
#define ll long long
const int N=100005;
using namespace std;
int arr[N],vis[N];
set<int> st;
int main(){
    int n,t;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t;
        vis[t]=st.size();
        st.insert(t);
    }
    ll sum=0;
    for(int i=0;i<=100000;i++){
        sum=sum+vis[i];
    }
    cout<<sum<<endl;
    return 0;
}

Keywords: C++

Added by optimus on Sat, 18 Apr 2020 15:57:21 +0300