天天看点
返回

Acwing第57场周赛(AK)

4486. 数字操作

题意：

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

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

  • 将整数 n n n 乘以任意一个正整数 x x x。

  • 将整数 n n n 替换为 n \sqrt n n

    ​（执行此操作的前提是 n \sqrt n n

    ​ 为整数）。

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

输入格式

一个整数 1 ≤ n ≤ 1 0 6 1\leq n \leq10^6 1≤n≤106 。

输出格式

一行，两个整数，分别为 n n 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：直觉是先乘一个数，然后一直开方，数字变小的速度最快。

证明：（方法临项交换）

n − > n   − > n ∗ x n − > n x 2   − > n x n -> \sqrt n \ -> \sqrt n *x \\ n-> n x^2 \ -> \sqrt n x n−>n

​ −>n

​∗xn−>nx2 −>n

​x

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

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

5184 = 2 6 ∗ 3 4 5184 = 2^6 * 3^4 5184=26∗34

5184 ∗ x = 2 8 ∗ 3 8 = 6 8 5184 * x = 2^8 *3^8 = 6^8 5184∗x=28∗38=68

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

特殊情况？

​ 可以直接开方 A = 2 4 ∗ 4 4 ∗ 8 4 A = 2^4 * 4 ^4 * 8^4 A=24∗44∗84

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

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

注意到， A = 1 A = 1 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 n n 的整数序列 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1​,a2​,…,an​。

现在，请你找到一个序列 a a a 的连续子序列 a l , a l + 1 , … , a r a_l,a_{l+1},…,a_r al​,al+1​,…,ar​。

要求：

  • ∑ i = l r a i > 100 × ( r − l + 1 ) ∑^{r}_{i=l}a_i >100×(r−l+1) ∑i=lr​ai​>100×(r−l+1)。
  • 连续子序列的长度（即 r − l + 1 r−l+1 r−l+1）尽可能大。

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

所有测试点满足 1 ≤ n ≤ 1 0 6 , 0 ≤ a i ≤ 5000 1≤n≤10^6,0≤a_i\leq5000 1≤n≤106,0≤ai​≤5000。

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

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

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

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

等价于

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

即

s [ r ] − s [ l − 1 ] > 0 s[r] - s[l - 1] > 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;
}
Acwing 周赛 算法
上一篇: 2023年CRM发展趋势预测
下一篇: 第十届蓝桥杯算法竞赛

继续阅读