c++ - codeforces 问题名为 Strange List the "MEMORY LIMIT EXCEEDED"

Question

参考codeforces中名为“奇怪列表”的问题，下面是我的代码

但问题是所有测试用例都通过了，但最后一个测试用例显示“内存超出限制”，最后一个测试用例的值也很大，比如 n 是 100000。请指导我解决它的方法

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
int t; 
cin>>t;
while(t--)
{
    ll ele,sum=0,i,j,h,n,x;
      
    cin>>n>>x;
    vector <ll> vec;
    for(i=0;i<n;i++)
    { 
        cin>>ele;
        vec.push_back(ele);
    }
    for(i=0;i>=0;i++)
    {
         
        if(vec.at(i)%x==1)
        {
            break;
        }
        else
        {
            h=vec.at(i)/x;
            for(j=0;j<x;j++)
            {
                vec.push_back(h);
            }
            
        }
    }
    for(i=0;i<vec.size();i++)
    {
     
        sum+=vec.at(i);
    }
   cout<<sum<<"\n";
  }
 }   

标签： c++

Answer 1

你可以使用动态规划来解决这个问题
存储结果的实现可以通过使用对的向量
来完成下面是AC 代码，演示了如何在内存消耗方面有效地解决这些问题......快乐编码： )

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 

int main(){

    ll t;
    cin>>t;
    
    
    while(t--){
        ll n,x;
        cin>>n>>x;
        
        vector<pair<ll,ll>> a(n);
        for(int i=0;i<n;i++){
            cin>>a[i].first;
            a[i].second=a[i].first;  // Storing initial results in second part of pair 
        }
        
        ll s=0;
        ll d=0;
        ll r=0;
        ll k=0;

        while(++r){
            for(int i=0;i<n;i++){
                if(a[i].first%x==0){
                    s+=a[i].second;
                    a[i].first=a[i].first/x;
                    a[i].second=(a[i].first*pow(x,r));  // updating results 
                }
                else{
                    s+=a[i].second;
                    if(d==0)
                    k=i;
                    d=1;
                }
            }
            if(d)
            break;
        }
        
        for(int i=0;i<k;i++)
        s+=a[i].second;   // getting desired sum 
        
        cout<<s<<"\n";   // printing answer
    }
    
}