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の場合、入力テストケースがまだ正しくない（少なくとも1組の同じ隣接する数字がある）場合、答えが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、そして1つの桜の色「2」のケーキ1枚です。

代わりに何をすることになっていますか？

于 2012-06-02T18:51:39.017 に答える
1

ええと、101はk = 2、s = ?? 1の場合には正しくないようです。問題の説明によれば、それはNOであるはずです。

于 2012-06-03T06:47:59.743 に答える