Solution to the 38th weekly match of acwing

AcWing 4299. Delete point

Topic link ：AcWing 4299. Delete point

The first question is sign in question , In fact, it is to calculate whether there is y Both sides of the shaft , Whether the number of points on one side is less than or equal to 1

The code is as follows ：

#include <iostream>

using namespace std;

const int N = 110;
int n, l, r;

int main(){
    
    cin >> n;
    for(int i = 0; i < n; i++){
    
        int x, y;
        cin >> x >> y;
        if(x > 0)r++;
        else l++;
    }
    if(l <= 1 || r <= 1)puts("Yes");
    else puts("No");
    
    return 0;
}

AcWing 4300. Two kinds of operations

Topic link ：AcWing 4300. Two kinds of operations

This problem is not difficult , As long as you find the right direction , He has only two operations , Immediate subtraction 1 And ride 2, The reverse is equivalent to m There are two operations , That is, by adding 1 And division 2 obtain n, In order to make m Faster approach n, Obviously, we need to divide first , When m Less than n when , We are adding , But in the process ,m May be odd , So we need to judge , When m When bits are odd , It needs to be added 1, To ensure that it can be divided , Finally get n.
Of course, there is another situation , Is that when n > m when , This is a n Only by subtracting 1 The way to get m, So in this case, calculate directly n - m that will do .

The code is as follows ：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, res;

int mid(){
    
    int k = 0;
    while(m > n){
    //  When m <= n Time description m It's close to n And it can be obtained by adding one n 了 
        if(m % 2){
     // Judge m Whether it's odd or not 
            m++;
            res++;//res Used to calculate midway +1 The number of operations 
        }
        m /= 2;
        k++;//k Calculate Division 2 The number of operations 
    }
    return k;
}

int main(){
    
    cin >> n >> m;
    if (n == m)cout << 0 << endl;// situation 1: n == m
    else if(n > m)               // situation 2: n > m 
        cout << n - m << endl;
    else{
                            // situation 3: n < m
        int b = m;
        int k = mid();           // Because besides 2 The process is a bit like dichotomy , So I named it mid
        if(m == n)cout << k + res << endl; //  If it is exactly equal to, there is no need to add 1 operation 
        else if(m < n)cout << (n - m) + k + res << endl; //  Otherwise, add the last 1 The operation of 
    }
    
    return 0;
}

AcWing 4301. Truncated sequence

Topic link ：AcWing 4301. Truncated sequence

Although this problem is difficult , But it's not too difficult , The direction is still very easy to think of , That is, different programming methods may encounter some troubles , For example, convert it into numbers and store it in an array , In this way, we have to deal with some special situations , In fact, there is no need to convert , Directly in the form of string , They correspond to ASCLL Code value calculation is the same .

Ideas ：

In fact, it is divided into two or more groups and the same size form , We can easily consider , First calculate the sum of them , Then group in the more summative factors , Because you can't divide it casually , The order is the same , So we traverse the string for each factor , If you can form this number , Then you can .

The code is as follows ：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, sum;
char s[N];

int main(){
    
    cin >> n >> s;
    for(int i = 0; i < n; i++){
    
        s[i] -= '0';
        sum += s[i];
    }
    
    for(int i = 2; i <= n; i++){
    
        if(sum % i == 0){
    // Judge if it's a factor 
            int k = 0;
            int p = sum / i;   
            bool f = true;
            // Traverse , See if it can be divided into equal parts 
            for(int j = 0; j < n; j++){
    
                k += s[j];
                // If k Greater than p Then it means that , immediate withdrawal , Tagged false
                if(k > p){
    
                    f = false;
                    break;
                }
                else if(k == p){
    // If equal, then return to 0, Restart the calculation 
                    k = 0;
                }
            }
            if(f){
    
                puts("YES");
                return 0;
            }
        }
    }
    puts("NO");
    return 0;
}