c - 算法编程 Q - 看似正确的解决方案却得到错误的答案

Question

This是问题。我想出了一个算法，但我一直处于错误答案状态。我需要知道我的方法有什么问题。

这是我的算法:

   Traverse the char array s: for i in range(0,len(s))
1. If c = '?' start from p=0 and check if p is present in left or right. If yes then increment it and repeat this step until p != left and p != right.
2. Check if p >= k. If yes then print NO and continue to the next test case.
3. Put the value of p in s[i] and continue
4. If c != '?', then check if c = its left and right digits. If it is, then print NO and continue to the next test case.

当 k=2 且 s[0] = '?' 时，我必须处理一个特殊情况(在我的算法上对输入 k = 2, s = ???0 进行试运行，输出结果将是 NO，而它应该是 < strong>1010，所以很容易弄清楚为什么这是一个特例)。对于 k=2，数字将交替。因此，如果第一个字符是 1，则可以确定整个字符串。如果 s[0] 是 '?'，那么在答案中 s[0] 可能是 0 或 1。这是我考虑过的特殊情况。

这里有一些关于为什么我的程序(根据我的说法)总是正确运行的理论。

我已经正确处理了 k = {1,2} 的情况，并且对于所有 k >= 3，答案永远不会是 NO，只要输入测试用例尚未不正确(至少有一对相同的相邻数字)。这是因为，任何数字(在圆圈中)都将恰好有 2 个邻居，并且我将至少有 3 种颜色可以放置，因此所有情况 k>=3 也被处理。现在，根据我的说法，我的逻辑在任何方面都没有错，但是当我提交时，我得到了一个错误的答案。

只是为了了解更多细节，这里是 C 代码:

#include <stdio.h>
#include <string.h>
int main()
{
    int t; scanf("%d\n",&t);
    while(t--)
    {
        int a=0,k,len; scanf("%d\n",&k);
        char s[101]; scanf("%s\n",&s);
        len = strlen(s);
        if(k==2 && s[0] == '?') // the special test case I was talking about
        {
            while(s[++a] == '?');
            if(a < len && ((a%2 == 0 && s[a] == 49) || (a%2 == 1 && s[a] == 48))) s[0] = 49;
        }
        for(a=0;a<len;a++)
        {
            int l = a==0 ? len-1 : a-1, r = a==len-1 ? 0 : a+1, p=0;
            if(s[a] == '?')
            {
                while(s[l]-48 == p || s[r]-48 == p) p++;
                if(p >= k) goto NP;
                s[a] = p+48;
            }
            else // checking the validity of input string
            {
                if(s[a] == s[l] || s[a] == s[r] || s[a] >= k+48) goto NP;
            }
        }
        printf("%s\n",s); continue;
        NP:
        printf("NO\n");
    }
}

Answer 1

来自问题陈述:

In the case N = 1 any arrangement is valid as long as the color used for the only cherry of this arrangement is less than K.

使用以下输入运行您的代码:

1
5
2

即T=1，K=5，一 block 樱桃色“2”的蛋糕

它应该做什么？