[acwing] explanation of the 57th weekly competition

 

---

AcWing 4485. Than the size

 

sample input 1：

5
1 2 3 4 5
2 1 4 3 5

sample output 1：

Yes

sample input 2：

5
1 1 1 1 1
1 0 1 0 1

sample output 2：

Yes

sample input 3：

3
2 3 9
1 7 9

sample output 3：

No

---

AC Code  

#include <iostream>
using namespace std;
typedef long long LL;
int main()
{
    LL res1 = 0, res2 = 0;
    int n; cin >> n;
    for(int i = 0; i < n; i ++ ) 
    {
        int num1; cin >> num1; 
        res1 += num1;
    }
    for(int i = 0; i < n; i ++ ) 
    {
        int num1; cin >> num1; 
        res2 += num1;
    }
    if(res1 >= res2) puts("Yes");
    else puts("No");
    return 0;
}

---

AcWing 4486. Digital operation  

sample input 1：

20

sample output 1：

10 2

sample input 2：

5184

sample output 2：

6 4

---

Their thinking  

from Arithmetic decomposition theorem You know ： 

It can be seen from the meaning of the question , Finally, the operation is finished The smallest result Namely  

We need to find one    Satisfy   , Then through one operation, make The number of all prime factors All for  

If all The number of qualitative factors Exactly  , This step is not required

All that's left is a    Open the root sign to    that will do  .

---

AC Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int n; cin >> n;
    
    int res = 1, m = 0;
    vector<int> a;
    for(int i = 2; i * i <= n; i ++ )
        if(n % i == 0)
        {
            int c = 0;
            while(n % i == 0) n /= i, c ++ ;
            res *= i;
            a.push_back(c);
            while(1 << m < c) m ++ ;
        }
    if(n > 1) 
    {
        res *= n;
        a.push_back(1);
        while(1 << m < 1) m ++ ;
    }
    
    for(auto x : a)
        if(x < 1 << m)
        {
            m ++ ;
            break;
        }
    
    cout << res << ' ' << m << endl;
    
    return 0;
}

---

AcWing 4487. The longest continuous subsequence

sample input 1：

5
100 200 1 1 1

sample output 1：

3

sample input 2：

5
1 2 3 4 5

sample output 2：

0

sample input 3：

2
101 99

sample output 3：

1

---

  Their thinking

On the condition given by the title In essence, it is to find the average over this interval .

adopt The prefix and Thought , The following formula is satisfied  

Make    The problem is equivalent to , a section Interval and (bi) Satisfaction is greater than 0

AC Code

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
LL s[N];
int stk[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        int x; scanf("%d", &x);
        s[i] = s[i - 1] + x - 100;
    }
    
    int top = 0, res = 0;
    stk[++ top] = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(s[stk[top]] > s[i]) stk[++ top] = i;
        else if(s[stk[top]] < s[i])
        {
            int l = 1, r = top;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(s[stk[mid]] < s[i]) r = mid;
                else l = mid + 1;
            }
            res = max(res, i - stk[r]);
        }
    }
    cout << res << endl;
    
    return 0;
}