这是P1018的代码,一开始用c++14和c++11编译错误,c++98可以,但是在本地上c++14貌似是可行的,能否帮忙看看哪些地方会CE
代码(码风不好不喜勿喷)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PII pair<int,int>
#define ft first
#define sd second
#define PII pair<int,int>
const int INF=0x3f3f3f3f,MOD=1e9+7;
const int M=10001,N=45;
int n,K;
struct HP
{
bool flag = true; // true表示当前高精度正数为正
int len = 1; // 有效数位,不包含前导0
int num[M] = {0}; // 存储数位,num[0]存储数字的个位
bool equal_zero() { return ((len == 1 && num[0] == 0) || (len <= 0)); }
void get(const string& s) // 从s中获取高精度整数
{
if(s[0] == '-') // 从s中获取负整数
{
len = s.length(); // 获取数位
for(int i = 0; i < len - 1; ++ i)
num[i] = s[len - i - 1] - '0';
len --;
flag = false;
}
else // 从s中获取正整数
{
len = s.length(); // 获取数位
for(int i = 0; i < len; ++ i)
num[i] = s[len - i - 1] - '0';
}
}
void print() // 输出当前存储的高精度整数
{
if(equal_zero()) { cout << "0"; return; }
if(! flag) cout << "-";
for(int i = len - 1; i >= 0; -- i)
cout << num[i];
}
int compare(const HP& y) // 1表示当前数更大,0表示相等,-1表示y更大
{
if((this->flag && y.flag) || (! this->flag && ! y.flag)) // 都是正数或者都是负数
{
int d = flag ? 1 : -1;
if(len > y.len) return 1 * d;
else if(len < y.len) return -1 * d;
else // 位数相等逐位比较
for(int i = len - 1; i >= 0; -- i)
if(num[i] > y.num[i]) return 1 * d;
else if(num[i] < y.num[i]) return -1 * d;
return 0;
}
else
return this->flag ? 1 : -1;
}
void lmove() // 左移
{
for(int i = len; i > 0; -- i) num[i] = num[i - 1];
num[0] = 0, len ++;
}
void rmove() // 右移
{
for(int i = 0; i < len - 1; ++ i) num[i] = num[i + 1];
num[--len] = 0;
}
HP plus(const HP& y) // 返回一个高精度整数表示当前结点和另一个高精度整数y相加的结果
{
HP z; // 保存计算结果
z.len = max(len, y.len); // 暂时以高位作为结果的位数
for(int i = 0; i < z.len; ++ i) // 从个位向高位处理
{
z.num[i] += num[i] + y.num[i];
if(z.num[i] >= 10) z.num[i + 1] ++, z.num[i] -= 10; // 处理进位
}
if(z.num[z.len] > 0) z.len ++; // 处理最高位进位
return z;
}
HP subtract(HP y) // 返回一个高精度整数表示当前结点和另一个高精度正整数y相减的结果
{
HP z; // 保存计算结果
if(this->compare(y) == 0) // 相等时返回0
{
z.len = 1, z.flag = true, z.num[0] = 0;
return z;
}
else if(this->compare(y) < 0) // 被减数小于减数
{
swap(*this, y);
z.flag = false; // 差小于0;
}
z.len = max(this->len, y.len); // 设置差的位数
for(int i = 0; i < z.len; ++ i) // 从个位向高位处理
{
z.num[i] += (this->num[i] - y.num[i]);
if(z.num[i] < 0) z.num[i + 1] --, z.num[i] += 10; // 处理借位
}
while(z.num[z.len - 1] == 0) z.len --; // 处理前导0
return z;
}
HP multi(int y) // 高精度整数乘int类型
{
HP z; // 保存结果
if((this->flag && y < 0) || (!this->flag && y > 0)) z.flag = false; // 两数异号
else z.flag = true; // 两数同号
z.len = this->len, y = abs(y);
unsigned long long res = 0;
for(int i = 0; i < len; ++ i)
{
res += (num[i] * y); // 计算当前数位的乘积
z.num[i] = res % 10; // 个位部分留在这里
res /= 10; // 剩余部分进到下一位
}
while(res) z.num[z.len ++] = res % 10, res /= 10; // 处理最高位进位
while(z.num[z.len - 1] == 0) z.len --; // 处理前导0
return z;
}
HP multi(HP y) // 高精度乘高精度
{
HP z; // 保存结果
if(! (this->flag ^ y.flag)) z.flag = true; // 两数同号
else z.flag = false; // 异号
z.len = this->len + y.len; // 设置答案的位数
for(int j = 0; j < y.len; ++ j) // 从低到高枚举第二个乘数
for(int i = 0; i < this->len; ++ i) // 从低到高枚举第一个乘数
z.num[i + j] += (this->num[i] * y.num[j]);
for(int i = 0; i < z.len; ++ i) // 处理进位
z.num[i + 1] += (z.num[i] / 10), z.num[i] %= 10;
while(z.num[z.len - 1] == 0) // 处理前导零
z.len --;
return z;
}
HP divide(HP y) // 高精除高精
{
HP x = *this, z; // 记录被除数和商
// HP z; // 保存结果
if(! (x.flag ^ y.flag)) z.flag = true; // 两数同号
else z.flag = false; // 异号
if(x.compare(y) < 0) return z; // 被除数小于除数
if(y.equal_zero()) return z; // 除0错误
HP d = y; d.flag = true; // 创造一个被适当扩大的除数
int cnt = 0; // 记录左移的位数
while(x.compare(d) >= 0) // 在除数小于被除数时一直扩大
d.lmove(), ++ cnt;
d.rmove(), -- cnt; // 获得一个小于等于被除数的最大除数
z.len = max(z.len, cnt + 1); // 记录商的位数
// 被除数大于除数,现在的除数不能小于原始的除数
while(x.compare(d) >= 0 && d.compare(y) >= 0)
{
while(x.compare(d) >= 0) // 在被除数一直比除数大的前提下
x = x - d, z.num[cnt] ++; // 对应位置的商增加
while(x.compare(d) < 0) // 适当减小除数
d.rmove(), -- cnt; // 得到一个不大于目前被除数的最大除数
}
return z;
}
HP operator +(HP y)
{
// ① 正数 + 正数 => a.正数 + 正数
if(this->flag && y.flag) { return this->plus(y); }
// ② 负数 + 负数 => a.正数 + 正数
// -A + -B => -(A + B)
else if(! this->flag && ! y.flag) { this->flag = y.flag = true; HP z = this->plus(y); z.flag = false; return z; }
// ③ 正数 + 负数 => b.正数 - 正数
else if(this->flag && ! y.flag) { y.flag = true; return this->subtract(y); }
// 负数 + 正数
else if(! this->flag && y.flag) { this->flag = true; return y.subtract(*this); }
}
HP operator -(HP y)
{
// ④ 正数 - 正数 => b.正数 - 正数
if(this->flag && y.flag) { return this->subtract(y); }
// ⑤ 正数 - 负数 => a.正数 + 正数
else if(this->flag && ! y.flag) { y.flag = true; return this->plus(y); }
// ⑥ 负数 - 正数 => ② 负数 + 负数
// -A - B => -(A + B)
else if(! this->flag && y.flag) { this->flag = true; HP z = this->plus(y); z.flag = false; return z; }
// ⑦ 负数 - 负数 => 负数 + 正数 => b.正数 - 正数
// (-A) - (-B) => -A + B => B - A
else if(! this->flag && ! y.flag) { this->flag = y.flag = true; return y.subtract(*this); }
}
HP operator *(int y) { return this->multi(y); } // 高精乘低精
HP operator *(HP y) { return this->multi(y); } // 高精乘高精
HP operator /(HP y) { return this->divide(y); } // 高精除以高精
bool operator >(HP y) {return this->compare(y)==1;}//大于
bool operator <(HP y) {return this->compare(y)==-1;}//小于
bool operator ==(HP y) {return this->compare(y)==0;}//等于
bool operator !=(HP y) {return this->compare(y)!=0;}//不等于
bool operator <=(HP y) {bool t=this->compare(y);return t==1||t==0;}//小于等于
bool operator >=(HP y) {bool t=this->compare(y);return t==-1||t==0;}//大于等于
};
HP max(HP x,HP y)
{
if(x.compare(y)==1)
return x;
else
return y;
}
HP min(HP x,HP y)
{
if(x.compare(y)==-1)
return x;
else
return y;
}
HP f[10][N];
signed main()
{
fst;
cin>>n>>K;
string s;
cin>>s;
for(int i=1;i<=n;i++)
{
HP x;
x.get(s.substr(0,i));
f[0][i]=x;
}
for(int i=1;i<=K;i++)
{
for(int j=i+1;j<=n;j++)
{
for(int k=1;k<j;k++)
{
HP x;
string t=s.substr(k,(j-k));
// cout<<k<<" "<<j<<" "<<t<<endl;
x.get(t);
f[i][j]=max(f[i][j],f[i-1][k]*x);
}
}
}
// for(int i=0;i<=K;i++)
// {
// for(int j=1;j<=n;j++)
// {
// f[i][j].print();
// cout<<" ";
// }
// cout<<endl;
// }
HP ans;
for(int i=1;i<=n;i++)
{
ans=max(ans,f[K][i]);
}
// cout<<114514<<endl;
ans.print();
return 0;
}