Kingdom of Black and White

Time Limit: 2000/1000
MS (Java/Others)

Memory Limit: 65536/65536
K (Java/Others)

Total Submission(s): 1201 Accepted Submission(s): 374

-> Link
<-

看到这提交记录了吧，我活生生的拉低了通过率，都不造自己怎么想的，整整两天没A其他的题，就是死咬这道题，思路很早就有了，死活WA，终于在第三天中午浪费了一个午休搞出来了，不过参考了一下网上的博客，思路都差不多，还是有值得借鉴的地方，然后发现了一个坑点（就是跪在这两天），也发现了HDU上测试数据的问题；发了这么多时间还是有收获的；

题意：开始看了好久还看不懂，也不造求啥，后来分析样例明白了，就是给定的一个01串，求连续相同的字符的长度的平方和就是答案，然后现在可以改变一个字符，问这个值最大是？看样例，4个0，2个1，值就是4*4+2*2=20，改变一个字符很明显将与0相隔的那个1改成0，这样就是5个0，1个1，值为5*5+1*1=26；明白了吧；

思路：一开始以为是个区间dp问题，后来问学长，其实就是把字符串压缩，只留下数量，比如上面的4 2，5 1这样的，然后改变一个使得平方和最大，我们来看，如果有长度有1,则可以合并左右，否则，从当前子串的左边或者右边改变一个，这样，当前的子串长度就加1，再与最大值进行比较；

来看AC代码：

#include<bits/stdc++.h>

using namespace std;

const int N=100000+10;

char s[N];

long long a[N],b[N];注意这里数据范围，就是跪在这里了；

int main()

{

    int t,i,x;

    scanf("%d",&t);

    int t1=t;

    while(t--)

    {

        scanf("%s",s);

        x=strlen(s);

        printf("Case #%d: ",t1-t);

        if(x<4)

        {

            printf("%d\n",x*x);

            continue;

        }

        memset(a,0,sizeof(a));

        memset(b,0,sizeof(b));

        int j=1,k=0;

        for(i=1; i<=x; i++)

        {

            if(s[i]==s[i-1])

                j++;

            else

            {

                a[k++]=j;//压缩；

                j=1;

            }

        }

        long long maxx=0;

        for(i=0; i<k; i++)

            b[i]=b[i-1]+a[i]*a[i];//累加起来，当改变某一小片段时左边和右边平方和是不变的；

        long long max1=b[k-1];

        for(i=0; i<k; i++)

            if(a[i]==1)//当其为1时左右可以一起合并（恰好改变本身）

            {

                maxx=(a[i]+a[i-1]+a[i+1])*(a[i]+a[i-1]+a[i+1])+b[i-2];

                if(i<k-1)//注意边界问题；

                    maxx+=b[k-1]-b[i+1];

                max1=max(max1,maxx);

            }

        maxx=0;

        for(i=0; i<k-1; i++)//往左合并一个；

        {

            maxx=(a[i]+1)*(a[i]+1)+(a[i+1]-1)*(a[i+1]-1)+b[i-1]+(b[k-1]-b[i+1]);

            max1=max(max1,maxx);

        }

        for(i=1; i<k; i++)//往右合并一个；

        {

            maxx=(a[i]+1)*(a[i]+1)+(a[i-1]-1)*(a[i-1]-1)+b[i-2]+(b[k-1]-b[i]);

            max1=max(max1,maxx);

        }

        printf("%I64d\n",max1);

    }

    return 0;

}

网上看的一个更简洁一点的思路（有所补充）：AC

#include<bits/stdc++.h>

using namespace std;

const int N=100000+10;

char s[N];

long long a[N];

int main()

{

    int t,x,i;

    scanf("%d",&t);

    int t1=t;

    while(t--)

    {

        scanf("%s",s);

        x=strlen(s);

        i=0;

        int j=0,k=0;

        while(i<=j&&j<x)//压缩这里优化了一下；

        {

            while(j<x&&s[i]==s[j]) j++;

            a[k++]=j-i;

            i=j;

        }

        long long sum=0,maxx=0;

        for(i=0;i<k;i++)

            sum+=a[i]*a[i];//直接将未改变的值算出来，然后改变的话只需看增大了多少，加上即可；

        for(i=1;i<k-1;i++)

            if(a[i]==1)

        {

            long long neW=(a[i-1]+a[i+1]+1)*(a[i-1]+a[i+1]+1);//改变本身；

            long long old=(a[i-1]*a[i-1])+a[i+1]*a[i+1]+1;//未改变的；

            if(neW>old)

                maxx=max(maxx,neW-old);

        }

        for(i=0;i<k-1;i++)//往左合并一个，如000011-->000001；

        {

            long long neW=(a[i]+1)*(a[i]+1)+(a[i+1]-1)*(a[i+1]-1);

            long long old=a[i]*a[i]+a[i+1]*a[i+1];

            if(neW>old)

                maxx=max(maxx,neW-old);

        }

        for(i=1;i<k;i++)//往右合并一个(原代码没有这一块，但实际会出错，如1110000011，最大应输出46，而未考虑这种情况则输出44，但HDU上竟然过了，可见其测试数据之水)

        {

            long long neW=(a[i]+1)*(a[i]+1)+(a[i-1]-1)*(a[i-1]-1);

            long long old=a[i]*a[i]+a[i-1]*a[i-1];

            if(neW>old)

                maxx=max(maxx,neW-old);

        }

        printf("Case #%d: ",t1-t);

        printf("%I64d\n",sum+maxx);

    }

    return 0;

}

实力还是不行，学长秒有思路，然而我却以为是区间DP，思路就错了好久，然而思路正确却还是卡了两天，实在太弱！

巴特西

HDU-5583-Kingdom of Black and White（2015ACM/ICPC亚洲区上海站-重现赛）

Kingdom of Black and White

最新文章

热门文章