Acwing game 57 (AK)

2022-07-19 06:05:00 【lovesickman】

4486. Digital operation

The question ：
Given an integer $n$ , You can do this number any number of times （ It can be $0$ Time ） Change operation .

Each operation is one of the following two ：

The integer $n$ Multiply by any positive integer $x$ .
The integer $n$ Replace with $\sqrt n$ （ The precondition for this operation is $\sqrt n$ Integers ）.

Please calculate , By doing this , $n$ The lowest possible value that can be reached , And the minimum number of operations required to reach the minimum possible value .

Input format

An integer $1\leq n \leq10^6$ .

Output format

a line , Two integers , Respectively $n$ The lowest possible value that can be reached , And the minimum number of operations required to reach the minimum possible value .

~~copilot I was surprised by my powerful ability~~

// Judge whether n is a power of x
bool is_power(int x,int n){
    
    int t=n;
    while(t%x==0){
    
        t/=x;
    }
    return t==1;
}

//Use recursion judge whether n is a power of X
//  Use recursion to judge n Is it right? x Omega to an integer power 
bool is_power(int n,int X){
    
    if(n==1)return true;
    if(n%X==0)return is_power(n/X,X); Omega to an integer power 
    return false;
}

//Use bit operation judge whether n is a power of 2
bool is_power_of_2(int n) {
    
    return (n&(n-1)) == 0;
}

//  Find a number cnt, bring (2^cnt)>=res
int find_cnt(int res) {
    
    int cnt = 0;
    while (1) {
    
        if ((1 << cnt) >= res) {
    
            return cnt;
        }
        cnt++;
    }
}

//Use binary_search to find a number cnt, so that (2^cnt) >=res
int binary_serarch(int res){
    
    int l=0,r=31;
    while(l<r){
    
        int mid=(l+r)>>1;
        if(1<<mid>=res)r=mid;
        else l=mid+1;
    }
    return l;
}

My intuition is dfs, The time complexity is vague , I didn't write it out , Recursively judging boundaries is not very good , Because you have to multiply by a number , It's going to get very big , I don't know how to deal with .

Law 1 ：
Q1： A,B The two operations are carried out in turn , still A->B,B->A On going ？
Q2: What knowledge is needed ？ dp, Two points answer , mathematics ？

Q1： Intuition is to multiply by a number first , And then keep prescribing , The number gets smaller the fastest .

prove ：（ Method temporary Exchange ）

$\sqrt n \ -> \sqrt n *x \\ n-> n x^2 \ -> \sqrt n x$

Find out , Method 1 It must become a method 2, And the total number of times remains the same , Then you can advance all multiplication operations , Merge into a multiplication operation .

Q2： Factor , prescribing , Use factors , Associate with prime factor decomposition .

$5184 = 2^6 * 3^4$

$5184 * x = 2^8 *3^8 = 6^8$

Intuition is ： Multiply by a number first , Let the highest power become 2 Multiple , And then keep prescribing .

A special case ？

You can directly prescribe $A = 2^4 * 4 ^4 * 8^4$

Use the highest power obtained $x^{'}$ Compare with the power of each prime factor before , If they are all equal , Then it means that the square can be directly drawn .

be aware , If it is a prime number $A = 3$ , Then the highest power is 0, It just doesn't need division , Is directly 0 Time .

be aware , $A = 1$ , There is no prime factorization , Special judgement ,cnt=0.

The smallest number that can become , Is the product of all prime factors .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
ll n;
// 2022-6-30 20:27:14

vector<pair<int,int>>a;

//  Find a number cnt, bring (2^cnt)>=res
int find_cnt(int res) {
    
    int cnt = 0;
    while (1) {
    
        if ((1 << cnt) >= res) {
    
            return cnt;
        }
        cnt++;
    }
}

void solve(){
    
    cin>>n;
    //  Yes n Decomposing prime factor , Save the prime factor and number into a
    for(int i=2;i*i<=n;i++){
    
        int cnt=0;
        while(n%i==0){
    
            n/=i;
            cnt++;
        }
        if(cnt)a.pb({
    i,cnt});
    }
    if(n>1)a.pb({
    n,1});
    //  Yes a Sort according to the number from large to small 
    sort(all(a),[](const pair<int,int>&a,const pair<int,int>&b){
    return a.second>b.second;});
    ll mul=1,cnt=0;
    if(a.size())cnt=find_cnt(a[0].second);
    ll sum=0;
    for(auto c:a){
    
        mul*=c.first;
        sum+=(1<<cnt) - c.second;
    }
    if(sum==0 || a.size()==0){
     //  It can be divided directly , perhaps n=1
        ;   
    }
    else{
    
        cnt++;
    }
    cout<<mul<<" "<<cnt;
}

int main(){
    
    solve();
	return 0;
}

4487. The longest continuous subsequence

Given a length of $n$ Integer sequence of $a_1,a_2,…,a_n$ .

Now? , Please find a sequence $a$ Of Continuous subsequences $a_l,a_{l+1},…,a_r$ .

requirement ：

$∑^{r}_{i=l}a_i >100×(r−l+1)$ .
The length of a continuous subsequence （ namely $r - l + 1$ ） As big as possible .

Please output the maximum possible length of the continuous subsequence that meets the conditions .

All test points meet $1≤n≤10^6,0≤a_i\leq5000$ .

Write your own code 8/11 A little bit , I don't know where I can't AC.

intuition ：dp, greedy , Two points answer . Two point answers have the lowest difficulty in thinking , Think about the dichotomy .

Read the solution and find , There is one in Mean correlation Of TRICK Always forget .

$a [l] + a [l + 1] +,,, + a [r] > k * (r - l + 1)$

Equivalent to

$(a [l] - k) + (a [l + 1] - k) + . . . + (a [r] - k) > 0$

namely

$s [r] - s [l - 1] > 0$

The problem is abstract , stay a The longest subarray was found in the array , The average value of this array is greater than k ,

After the above transformation, it becomes , stay s Two subscripts were found in the array l,r. s[l] < s[r], r-l Maximum . among l In fact, it is l+1,

l Value range [0,i-1] .

Can only pass 8 A binary answer .

The reason why I can't pass ： Whether there is a binary array with a length equal to len The string of , Meet the conditions .

analysis ： Does the content of dichotomy have two ends ？ If a length equals len The substring of satisfies , Go to the longer string to find .

That is to say, long-term satisfaction , Short is also satisfied .（ It is considered that short length is a necessary condition for the existence of long length satisfaction ）

100 -150 100 , len=2 dissatisfaction ,len=3 Satisfy . Long satisfaction , Short is not necessarily satisfied .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+10,M=1e9+7;
ll n,a[N],sum[N];
// 2022-7-1 15:59:11

//  Judge array a Whether there is a with a length of len The string of , Average value of substring >100
bool check(int len)
{
    
    int l=1,r=l+len-1;
    ll Sum = sum[r] - sum[l-1];
    if(Sum*1.0/len>100)return true;
    for(;l<=n-len;l++){
    
        Sum+=a[l+len]-a[l];
        if(Sum*1.0/len>100)return true;
    }
    return false;
}

void solve(){
    
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
    ll l=0,r=n;
    while(l<r){
    
        ll mid=l+r+1>>1;
        if(check(mid)){
    
            l=mid;
        }
        else{
    
            r=mid-1;
        }
    }
    cout<<l;
}
int main(){
    
    solve();
	return 0;
}

There is a problem with the content of the dichotomy

Short satisfaction , Long satisfaction . Whether there is a length in the binary array Greater than or equal to len The string of , Meet the conditions .

I feel that this dichotomy is different from the usual dichotomy . If check Set up the , Short satisfaction , Long can definitely meet , It's short , Formed two stages .

mrk The code of is very wonderful

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) {
     return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) {
     return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') {
     if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e6 + 5;

int n, a[N], q[N];

LL s[N];

//  Judge whether the length is greater than or equal to x, Is there a solution 
bool inline chk(int x) {
    
    LL mn = 9e18;//  stay i left , And i The distance is greater than or equal to x The minimum value of all elements of .
    for (int i = 1; i <= n; i++) {
    
        if (i - x >= 0) chkMin(mn, s[i - x]);
        if (s[i] - mn > 0) return 1;
    }
    return 0;
}

int main() {
    
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]), a[i] -= 100, s[i] = s[i - 1] + a[i];
    int l = 0, r = n;
    while (l < r) {
    
        int mid = (l + r + 1) >> 1;
        if (chk(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r;
    return 0;
}

y Total monotony stack dichotomy , I feel that playing skillfully is the basic skill

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

using namespace std;

typedef long long LL;

const int N = 1000010;

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

int main()
{
    
    scanf("%d", &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 = 0, 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]);
        }
    }

    printf("%d\n", res);
    return 0;
}