-3

我试图解决这个问题，但我无法接受它，它的输入很大，所以我想用字符串来处理它，但我仍然得到错误的答案。问题陈述在这里BISHOPS

这是我的代码：

#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>

using namespace std;

int main()
{
    string s;
    int z;
    cin>>s;
    z = s.length();
    int i;
    vector<int>v;
    int arr[z];
    for(i=0;i<z;i++)
    {
        arr[i] = (s[i]-'0');
    }

    if ((arr[0] == 0 || arr[0] ==  1) && z == 1)
    {
        printf("%d",arr[0]);
    }
    else
    { 
        int carry = 0;
        for(i=z-1;i>=0;i--)
        {
            int x = (carry + 2*arr[i])%10;
            v.push_back(x);
            carry = ( 2*arr[i] )/10;
        }
        if(carry > 0)
        {
            v.push_back(carry);
        }

        int t = v.size();
        int g=0;
        if(v[g] >=2)
        {
            v[g] = v[g]-2;
        }
        else
        {
            v[g] = 8;
            g++;
            while(v[g] == 0)
            {
                v[g] = 9;
                g++;
            }
            v[g] = v[g] -1;
        } 


        if(v[t-1] == 0)
        {
            for(i=t-2;i>=0;i--)
                {
                    printf("%d",v[i]);
                }
        }
        else
        {
            for(i=t-1;i>=0;i--)
            {
                printf("%d",v[i]);
            }
        }
    }

        return 0;
}

问题是在 nxn 棋盘的问题中找到最大不可攻击的主教，我认为我做对了，因为除了每个其他棋盘的 1x1 之外，最大不可攻击的主教将是 2*n-2。但仍然 spoj 给出了错误的答案

4

1 回答 1

2

所有大于 的输入都有整数溢出INT_MAX：

int y=0,i,z;
z = s.length();
for(i=0;i<z;i++)
{
    y = y*10 + (s[i]-'0');
}

您正在尝试将输入转换为int，它通常是带符号的 32 位类型，INT_MAX等于 2147483647 = 2 31 -1。每当输入大于该值时，在第十位您就会溢出（顺便说一句，这是未定义的行为）。

您需要一种方法来表示/处理大于 10 100的数字。C 或 C++ 中没有标准整数类型足以处理这个问题。您必须滚动自己的大整数类型（因为 SPOJ 可能不会将代码与 GMP 链接）。对于这个问题，一些非常简单的事情就足够了。

于 2012-06-03T14:21:01.693 回答