【Acwing】第57场周赛 题解

 

---

AcWing 4485. 比大小

 

输入样例1：

5
1 2 3 4 5
2 1 4 3 5

输出样例1：

Yes

输入样例2：

5
1 1 1 1 1
1 0 1 0 1

输出样例2：

Yes

输入样例3：

3
2 3 9
1 7 9

输出样例3：

No

---

AC代码 

#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. 数字操作 

输入样例1：

20

输出样例1：

10 2

输入样例2：

5184

输出样例2：

6 4

---

解题思路 

由算术分解定理可知： 

由题意可知，最后操作完最后最小的结果就是 

我们需要找到一个  满足  ，然后通过一次操作使得所有的质因子的次数都为 

如果所有质因子的次数恰好都为  ，则不需要这一步操作

剩下的就是把  开根号至  即可 。

---

AC代码

#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. 最长连续子序列

输入样例1：

5
100 200 1 1 1

输出样例1：

3

输入样例2：

5
1 2 3 4 5

输出样例2：

0

输入样例3：

2
101 99

输出样例3：

1

---

 解题思路

题目所给的条件上本质上是求在这段区间上的平均数。

通过前缀和的思想，即满足下列公式 

令  问题等价于，一段区间和(bi)满足大于0

AC代码

#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;
}