[数据结构与算法]Acwing第57场周赛

4486. 数字操作

题意：
给定一个整数 $n$，你可以对该数进行任意次（可以是 $0$ 次）变换操作。

每次操作为以下两种之一：

• 将整数 $n$ 乘以任意一个正整数 $x$。
• 将整数 $n$ 替换为 $\sqrt{n}$（执行此操作的前提是 $\sqrt{n}$ 为整数）。

请你计算，通过上述操作，$n$ 能达到的最小可能值，以及达到最小可能值所需要的最少操作次数。

输入格式

一个整数 $1\le n\le 10^6$ 。

输出格式

一行，两个整数，分别为 $n$ 能达到的最小可能值，以及达到最小可能值所需要的最少操作次数。

copilot 强大能力惊讶到我了

// 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
// 使用递归判断n是不是x的整数次幂
bool is_power(int n,int X){
    if(n==1)return true;
    if(n%X==0)return is_power(n/X,X);的整数次幂
    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;
}

// 找到一个数字cnt，使得(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;
}

我的直觉是dfs，时间复杂度比较模糊，自己没写出来，递归判断边界不太会，因为要乘一个数，会变得非常大，不知道怎么处理。

法一：
Q1： A，B两个操作是轮流进行的，还是A->B，B->A进行的 ？
?Q2: 需要用到什么知识？ dp，二分答案，数学？

Q1：直觉是先乘一个数，然后一直开方，数字变小的速度最快。

证明：（方法临项交换）

$$\begin{gathered} n?>\sqrt{n}?>\sqrt{n}?x \\ n?>n{x}^2?>\sqrt{n}x \end{gathered}$$

发现，方法1一定可以变成方法2，而且总次数不变，那么可以把所有的乘法操作提前，合并成一个乘法操作。

Q2：因数，开方，用到因子 ，联想到质因数分解。

$5184=2^6?3^4$

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

直觉是：先乘一个数，让最高次幂变成2的倍数，然后一直开方。

特殊情况？

? 可以直接开方 $A=2^4?4^4?8^4$

用得到的最高次幂 $x^{\prime }$ 和之前每个质因子的幂次比较，如果全都相等，那么表示可以直接开方。

注意到，如果是一个质数 $A=3$ , 那么最高次幂是0，刚好就是不用整除，直接就是0次。

注意到，$A=1$, 没有质因数分解，特判，cnt=0。

能够变成的最小的数，就是所有质因数的乘积。

/*
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;

// 找到一个数字cnt，使得(2^cnt)>=res
int find_cnt(int res) {
    int cnt = 0;
    while (1) {
        if ((1 << cnt) >= res) {
            return cnt;
        }
        cnt++;
    }
}

void solve(){
    cin>>n;
    // 对n分解质因数,将质因数和次数存入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});
    // 对a按照次数从大到小排序
    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){ // 可以直接被整除，或者n=1
        ;   
    }
    else{
        cnt++;
    }
    cout<<mul<<" "<<cnt;
}

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

4487. 最长连续子序列

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots ,a_n$。

现在，请你找到一个序列 $a$ 的连续子序列 $a_l,a_{l+1},\dots ,a_r$。

要求：

• ${\sum }_{i=l}^r{a}_i>100\times (r?l+1)$。
• 连续子序列的长度（即 $r?l+1$）尽可能大。

请你输出满足条件的连续子序列的最大可能长度。

所有测试点满足 $1\le n\le 10^6,0\le a_i\le 5000$。

自己写的代码8/11个点，不知道哪里不能AC。

直觉：dp，贪心，二分答案。二分答案思维难度最低，考虑二分答案。

阅读题解发现，有一个在平均数相关 的TRICK总是忘记。

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

等价于

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

即

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

问题抽象，在 a 数组中找到一个最长的子数组，该数组的平均值大于 k ，

经过上述转化变成，在 s 数组中找到两个下标 l,r。 s[l] < s[r], r-l 最大。其中l在数轴上其实是l+1，

l 取值范围[0,i-1] 。

只能过8个的二分答案。

不能过的原因：二分数组中是否存在长度等于len的子串，满足条件。

分析：二分的内容具有两端性吗？如果一个长度等于len的子串满足，就去长度更长的串去找。

也就是认为长的满足，短的也满足。（认为短长度是满足是存在长长度满足的必要条件）

100 -150 100 ， len=2不满足，len=3满足。长的满足，短的不一定满足。

/*
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

// 判断数组a中是否存在长度为len的子串，子串的平均值>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;
}

二分内容有问题

短的满足，长的满足。二分数组中是否存在长度大于等于len的子串，满足条件。

感觉这个二分和平时二分的思路是拧巴的。如果check成立了，短的满足了，长的肯定可以满足，就取短了，形成了两段性。

mrk的代码非常的妙了

// 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];

// 判断大于等于长度x，是否存在解
bool inline chk(int x) {
    LL mn = 9e18;// 在i左侧，与i距离大于等于x的所有元素的最小值。
    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总的单调栈二分，感觉熟练打出来是基本功

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