Acwing game 57

AcWing 4485. Than the size

Ideas ：
Enumeration is enough , Grammar questions

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n; 
void solve()
{
    
    cin>>n;
    int s1=0,s2=0;
    for(int i=0;i<n;i++)
    {
    
        int x;
        cin>>x;
        s1+=x;
    }
    for(int i=0;i<n;i++)
    {
    
        int x;
        cin>>x;
        s2+=x;
    }
    if(s1>=s2)puts("Yes");
    else puts("No");
}
signed main()
{
    
    io;
    //cin>>_; 
 // while(_--)
    solve();
    return 0;
}

 author ：Leimz
 link ：https://www.acwing.com/activity/content/code/content/3669431/
 source ：AcWing
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

AcWing 4486. Digital operation

Ideas ：
Think greedily ： Multiply only once and divide smoothly is the least operand , So we need to find the number that multiplies .
Yes $n$ Do factorization ,$5184=2^6\ast 3^4$
take $6,4$ Make up the smallest one bigger than them $2$ To the power of, that is $8$
So here you are $5184\ast 2^2\ast 3^4$, Why 8？ Because every time I find the arithmetic square root , amount to $fingerCount/2$ So I'm looking for 2 To the power of

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n; 
vector<PII>v;
int maxv;
void get_fact()
{
    
    for(int i=2;i<=n/i;i++)
    {
    
        if(n%i==0)
        {
    
            int s=0;
            while(n%i==0)
            {
    
                n/=i;
                s++;
            }
            maxv=max(maxv,s);
            v.pb({
    i,s});
        }
    }
    if(n>1)v.pb({
    n,1});
}
void solve()
{
    
    cin>>n;
    get_fact();
    int s=1;
    while(s<maxv)s<<=1;
    bool f=false;
    for(int i=0;i<v.size();i++)
    {
    
        if(v[i].y<s)
        {
    
            f=true;
            break;
        }
    }
    int res=f;
    int m=s;
    while(m)
    {
    
        res++;
        m>>=1;
    }
    res--;
    int ans=1;
    for(int i=0;i<v.size();i++)
    {
    
        ans*=v[i].x;
    }
    cout<<ans<<' '<<res<<endl;
}
signed main()
{
    
    io;
 // cin>>_; 
 // while(_--)
    solve();
    return 0;
}

 author ：Leimz
 link ：https://www.acwing.com/activity/content/code/content/3669771/
 source ：AcWing
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

AcWing 4487. The longest continuous subsequence

Ideas ：
First, analyze the formula

It is equivalent to finding the average of the longest interval and dividing by 100 Greater than zero
Prefixes and denote $S[r]-S[l-1]>100\ast (len)$
namely ： Preprocessing $S[r]-100\ast r$
Enumerate left endpoints , Find the largest right endpoint , If $r<l$ Do not conform to the , Find the longest $len$
there $mx$ Array is the key to binary , Because prefixes and arrays do not necessarily satisfy monotonicity ,$mx$ Arrays are based on the idea of dynamic programming , take $r$ The subsequent maximum value is copied to $r$
The same problem can be done with a monotone stack .

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}// Its lowest 1 And behind it 0 The value of composition 
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n; 
const int N=1e6+10;
int a[N];
int s[N],mx[N];
void solve()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(int i=0;i<=n;i++)s[i]-=100*i;
    mx[n+1]=-ll_INF;
    for(int i=n;i>=0;i--)mx[i]=max(mx[i+1],s[i]);
    int res=0;
    for(int i=0;i<n;i++)
    {
    
        int l=i+1,r=n;
        while(l<r)
        {
    
            int mid=l+r+1>>1;
            if(mx[mid]>s[i])l=mid;
            else r=mid-1;
        }
        if(mx[l]<=s[i])continue;
        res=max(res,l-i);
    }
    cout<<res<<endl;

}
signed main()
{
    
    io;
 // cin>>_; 
 // while(_--)
    solve();
    return 0;
}

 author ：Leimz
 link ：https://www.acwing.com/activity/content/code/content/3670626/
 source ：AcWing
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .