洛谷P1080 国王游戏 wa一个点

Question

/#include<bits/stdc++.h>
using namespace std;
const int maxn=8010;
int n;
int x,y,maxt;
int sum[8010];
void tms(int x)
{
    for(int i=1;i<=maxn-10;i++)
        sum[i]*=x;
    for(int i=1;i<=maxn-10;i++)
        {
            int a=sum[i]/10;
            sum[i+1]+=a;
            sum[i]%=10;
        }
    return ;
}
void div(int x)
{
    for(int i=maxn-10;i>=1;i--)
        {
            int a=sum[i]%x;
            sum[i-1]+=10*a;
            sum[i]/=x;
        }
    return ;
}
int main()
{
    cin>>n;
    cin>>x>>y;
    sum[1]=1;
    tms(x);
    for(int i=2;i<=n+1;i++)
        {
            cin>>x>>y;
            maxt=max(maxt,x*y);
            tms(x);
        }
    div(maxt);
    int i=maxn-10;
    while(sum[i]==0&&i>1)
        i--;
    for(int j=i;j>=1;j--)
        cout<<sum[j];
    return 0;
}

实在是不知道哪里出了问题

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题出在函数tms()和div()中的一些逻辑错误，导致对数组sum[]的操作并不是完全正确的乘法和除法操作。具体来说，函数tms()中对数组sum[]的操作应该是将每一位乘以x，并且需要考虑进位；而函数div()中对数组sum[]的操作应该是对每一位取模x并且考虑借位。 这里给出修复后的代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 8010;
int n;
int x, y, maxt;
int sum[maxn];
void tms(int x) {
    int carry = 0;
    for(int i = 1; i <= maxn - 10; i++) {
        sum[i] = sum[i] * x + carry;
        carry = sum[i] / 10;
        sum[i] %= 10;
    }
}
void div(int x) {
    int borrow = 0;
    for(int i = maxn - 10; i >= 1; i--) {
        int remain = (sum[i] + borrow * 10) % x;
        borrow = (sum[i] + borrow * 10) / x;
        sum[i] = remain;
    }
}
int main() {
    cin >> n;
    cin >> x >> y;
    fill(sum, sum + maxn, 0);
    sum[1] = 1;
    
    tms(x);
    
    for(int i = 2; i <= n+1; i++) {
        cin >> x >> y;
        maxt = max(maxt, x*y);
        tms(x);
    }
    
    div(maxt);
    
    int i = maxn - 10;
    while(sum[i] == 0 && i > 1)
        i--;
    
    for(int j = i; j >= 1; j--) {
        cout << sum[j];
    }
    
    return 0;
}

在修复后的代码中，tms()和div()函数对数组sum[]的操作符合乘法和除法的逻辑，可以正确计算乘法和除法结果。