51Nod-1523-非回文

描述

题解

MDZL，这么简单一道题，三个小时还没AC……一直有三组数据过不去，第18、24、25组数据（代码One），经过测试发现一个十分邪性的问题，有的测试数据尾有\r\n，而有的却没有，这是神马情况啊~~~

这是我的Xcode的工具FileMerge的对比结果（左边是51给的测试数据文件，右边是本地测试文件）：

这简直是给我开国际玩笑啊！！！真是搞不懂为啥会有10个人AC……我的算法没错啊，除了文件尾的这个莫名其妙的字符问题，其他都是正确的，这就很尴尬了，Mark一下，以后再说吧，真是恶心透了，炸了炸了，碎觉！！！

次日更新：
我已经开始怀疑人生了，各种试验，均失败，然后将最外层的while循环去掉了试一下，结果WA了六组，可是理论上，去最外层的这个while循环不会产生负面影响的啊，夹克老师说，51比较注重思维，输出格式上相对较为宽松，那么，问题就死这里了~~~究竟是啥引起的啊？

算了，算法思路可以肯定没有问题，找了别人的代码（代码Two），发现思路是一样的，只是实现方法略微不同，暂且就这样吧，恶心透了。这道题我已经各种bug排查，各种单步调试，各种数据测试，均无问题，不存在其他问题。

10.25 更新：
谢谢评论区的大神给我指出了问题所在，虽然有些懵逼，以前没有遇见过这样的bug啊，为什么只WA了三组呢？一直以来都记得后边系统会自动默认为'\0'的啊~~~有些吃惊了！！！以后一定要注意这个问题，防止再被这种bug毁人生了。

代码

One：

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1010;

char s[MAXN];

int main(int argc, const char * argv[])
{
    // freopen("/Users/zyj/Desktop/51nod_Problem_1523_Test_18_In.txt", "r", stdin);
    // freopen("/Users/zyj/Desktop/output.txt", "w", stdout);

    int n, p;
    while (cin >> n >> p)
    {
        char ss[MAXN];

        scanf("%s", s);
        int len = (int)strlen(s);
        for (int i = 0; i < len && i < n; i++)
        {
            ss[i] = s[i];
        }
        int flag = 0;
        for (int i = len; i < n; i++)
        {
            flag = 1;
            for (int j = 0; j < p; j++)
            {
                if ('a' + j != ss[i - 1] && 'a' + j != ss[i - 2])
                {
                    ss[i] = 'a' + j;
                    flag = 0;
                    break;
                }
            }
            if (flag)
            {
                puts("NO");
                break;
            }
        }
        if (flag)
        {
            continue;
        }
        if (len < n)
        {
            ss[n] = '\0';    // 添加
            puts(ss);
        }
        else
        {
            // flag = 0;
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = ss[i] + 1; j < 'a' + p; j++)
                {
                    if (i > 0 && j == ss[i - 1])
                    {
                        continue;
                    }
                    else if (i > 1 && j == ss[i - 2])
                    {
                        continue;
                    }
                    else
                    {
                        ss[i] = j;
                        flag = 1;
                        break;
                    }
                }
                if (flag)
                {
                    for (int j = i + 1; j < n; j++)
                    {
                        for (int k = 0; k < p; k++)
                        {
                            if (j > 1)
                            {
                                if ('a' + k != ss[j - 1] && 'a' + k != ss[j - 2])
                                {
                                    ss[j] = 'a' + k;
                                    break;
                                }
                            }
                            else if (j > 0)
                            {
                                if ('a' + k != ss[j - 1])
                                {
                                    ss[j] = 'a' + k;
                                    break;
                                }
                            }
                        }
                    }
                    ss[n] = '\0';    // 添加
                    puts(ss);
                    break;
                }
            }
            if (!flag)
            {
                puts("NO");
            }
        }
    }

    return 0;
}

Two：

#include <cstdio>

using namespace std;

const int MAXN = 1005;

int N, P;
char s[MAXN];

bool check(int v)
{
    if (v > 0 && s[v] == s[v - 1])
    {
        return false;
    }
    if (v > 1 && s[v] == s[v - 2])
    {
        return false;
    }
    return true;
}

bool solve(int v)
{
    while (true)
    {
        if (v >= N)
        {
            return true;
        }

        if (v < 0)
        {
            return false;
        }

        if (s[v] - 'a' == P - 1)
        {
            s[v] = 'a' - 1;
            v--;
        }
        else
        {
            int k = (s[v] - 'a' + 1) % P;
            if (k < 0)
            {
                k = 0;
            }
            s[v] = 'a' + k;

            if (check(v))
            {
                v++;
            }
        }
    }
    return false;
}

int main ()
{
    scanf("%d%d%s", &N, &P, s);

    if (solve(N - 1))
    {
        s[N] = '\0';
        printf("%s\n", s);
    }
    else
    {
        printf("NO\n");
    }

    return 0;
}