【题目链接】:http://codeforces.com/contest/791/problem/C

【题意】



给你n-k+1个限制

要求

a[i]..a[i]+k-1里面有相同的元素,或全都不同;

让你输出可能的一个序列

【题解】



先找到YES的一段

(找不到就全都输出一样的);

然后以这段YES作为种子

假设YES的段为pos..pos+k-1

往左往右构造

如果往左构造的话

就是for (int i = pos-1;i>=1;i–)

接下来要给第i个位置确定数字;

则如果i..i+k-1为YES的话

就取[i..i+k-1]中最小的未出现的那个数字;

如果i..i+k-1为NO的话

就取ans[i]=ans[i+k-1];

这样

ans[i..i+k]全都是不一样的;

就不会对再往左的答案造成影响.

往右的话

YES的情况相同

NO的情况变成ans[i]取ans[i-k+1]了.



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 50 + 20;

int n, k, cnt1, po;

int ok[N], ans[N];

int bo[N];

char s[6];

string tar[N];

void in()

{

    rei(n), rei(k);

    rep1(i, 1, n - k + 1)

    {

        scanf("%s", s);

        if (s[0] == 'N')

            ok[i] = 0;

        else

        {

            ok[i] = 1;

            cnt1++;

            po = i;

        }

    }

}

void zhitrue(int pos, int l, int r)

{

    rep1(i, 0, n)

        bo[i] = 0;

    rep1(i, l, r)

        bo[ans[i]]++;

    int x = 0;

    while (bo[x]) x++;

    ans[pos] = x;

}

void zhifalse(int pos, int l, int r,int p)

{

    if (p == 1)

    {

        ans[pos] = ans[r];

    }

    else

    {

        ans[pos] = ans[l];

    }

}

void ga()

{

    if (cnt1 == 0)

    {

        rep1(i, 1, n)

            ans[i] = 1;

    }

    else

    {

        rep1(i, po, po + k - 1)

            zhitrue(i, po, po + k - 1);

        rep2(i, po - 1, 1)

        {

            if (ok[i])

                zhitrue(i, i, i + k - 1);

            else

                zhifalse(i, i, i + k - 1,1);

        }

        rep1(i, po + k, n)

        {

            if (ok[i])

                zhitrue(i, i - k + 1, i);

            else

                zhifalse(i, i - k + 1, i,0);

        }

    }

}

void init()

{

    rep1(i, 1, 26)

    {

        char t = i + 'A' - 1;

        tar[i] = "";

        tar[i] += t;

        tar[i] = t;

    }

    rep1(i, 1, 24)

    {

        char t1 = i + 'A' - 1, t2 = i + 'a' - 1;

        tar[i + 26] = "";

        tar[i + 26] += t1;

        tar[i + 26] += t2;

    }

}

void o()

{

    rep1(i, 1, n)

    {

        cout << tar[ans[i]];

        if (i == n)

            puts("");

        else

            putchar(' ');

    }

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    init();

    in();

    ga();

    o();

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}