这就是问题。我想出了一个算法,但我一直收到错误答案状态。我需要知道我的方法有什么问题。
这是我的算法:
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");
}
}