0

就是问题。我想出了一个算法,但我一直收到错误答案状态。我需要知道我的方法有什么问题。

这是我的算法:

   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,而它应该是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");
    }
}
4

2 回答 2

3

从问题陈述:

在 N = 1 的情况下,只要用于该排列的唯一樱桃的颜色小于 K,任何排列都是有效的。

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

1
5
2

也就是T=1,K=5,一饼一樱桃色“2”

它应该做什么?

于 2012-06-02T18:51:39.017 回答
1

好吧,对于 k=2 , s=??1 情况,101 似乎不正确。根据问题陈述,它应该是 NO。

于 2012-06-03T06:47:59.743 回答