天天看點
傳回

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發展趨勢預測
下一篇: 第十屆藍橋杯算法競賽

繼續閱讀