关于F题的一个奇怪到极点的问题
我的F题是动态规划写法然后类似树结构进行回溯方案。
这是我普通数组的实现方式，连交都不让我交，直接显示error，超过内存限制
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
using namespace std;
int f[51][51][2501];
struct fib{
int i;
int o;
int g;
}fu[51][51][2501];
int gc[110][110];
void solve()
{
int n,m,x;
cin>>n>>m>>x;
for(int i=1;i<=m;i++) f[1][i][i]=1;
for(int t=2;t<=n;t++)//第t项
{
for(int i=1;i<=m;i++)//第t项取i时
{
for(int o=1;o<=m;o++)//第t-1项前缀gcd为o时
{
for(int g=1;g<=n*m;g++)//第t-1项前缀gcd为o时其贡献可以为g时
{
if(f[t-1][o][g]==0) continue;
int zhi=g+gc[i][o];
f[t][gc[i][o]][zhi]=1;
fu[t][gc[i][o]][zhi]={t-1,o,g};
}
}
}
}
fib fg={-1,-1,-1};
vector<int> v;
for(int i=1;i<=m;i++)
if(f[n][i][x]==1)
{
fg=fu[n][i][x];
v.clear();
v.push_back(i);
}
if(fg.i==-1) cout<<"-1"<<endl;
else
{
int i=0;
while(1)
{
v.push_back(fg.o);
fib nx=fu[fg.i][fg.o][fg.g];
fg=nx;
if(i>100) break;
if(fg.g==0) break;
}
reverse(v.begin(),v.end());
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
cout<<endl;
}
for(int t=1;t<=n;t++)
{
for(int i=1;i<=m;i++)
{
for(int g=1;g<=n*m;g++)
{
f[t][i][g]=0;
fu[t][i][g]={0,0,0};
}
}
}
}
signed main()
{
IOS;
int T=1;
for(int i=1;i<=100;i++)
for(int o=1;o<=100;o++) gc[i][o]=__gcd(i,o);
cin>>T;
while(T--) solve();
return 0;
}
然后我交了个用vector代替普通数组的实现方式，为什么这次就不提示而且能正常通过，如下
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
using namespace std;
struct fib{
int i;
int o;
int g;
};
int gc[110][110];
void solve()
{
int n,m,x;
cin>>n>>m>>x;
vector<vector<vector<int>>> f(n+1,vector<vector<int>>(m+1,vector<int>(n*m+1,0)));
vector<vector<vector<fib>>> fu(n+1,vector<vector<fib>>(m+1,vector<fib>(n*m+1,{0,0,0})));
for(int i=1;i<=m;i++) f[1][i][i]=1;
for(int t=2;t<=n;t++)//第t项
{
for(int i=1;i<=m;i++)//第t项取i时
{
for(int o=1;o<=m;o++)//第t-1项前缀gcd为o时
{
for(int g=1;g<=n*m;g++)//第t-1项前缀gcd为o时其贡献可以为g时
{
if(f[t-1][o][g]==0) continue;
int zhi=g+gc[i][o];
f[t][gc[i][o]][zhi]=1;
fu[t][gc[i][o]][zhi]={t-1,o,g};
}
}
}
}
fib fg={-1,-1,-1};
vector<int> v;
for(int i=1;i<=m;i++)
if(f[n][i][x]==1)
{
fg=fu[n][i][x];
v.clear();
v.push_back(i);
}
if(fg.i==-1) cout<<"-1"<<endl;
else
{
int i=0;
while(1)
{
v.push_back(fg.o);
fib nx=fu[fg.i][fg.o][fg.g];
fg=nx;
if(i>100) break;
if(fg.g==0) break;
}
reverse(v.begin(),v.end());
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
cout<<endl;
}
}
signed main()
{
IOS;
int T=1;
for(int i=1;i<=100;i++)
for(int o=1;o<=100;o++) gc[i][o]=__gcd(i,o);
cin>>T;
while(T--) solve();
return 0;
}
这是我那个普通数组哪里有可能爆的地方，还是平台的编译检测出了什么毛病，或者说是测试用例不够强啊，
但是最大情况就是下50*50*2500=6,250,000,大概是6e6的长度，乘上结构体的，也就是一共乘上4是2e7多，我交过比这更大的数组，为什么提交的编译都过不了呢 ? 我刚刚扒了一下后台的数据，还是有极限数据的：n=50,m=50,x=2500，我那个用vector实现的就没被卡住，很奇怪
