Anya loves to watch horror movies. In the best traditions of horror, she will be visited bym ghosts tonight. Anya has lots of candles prepared for the visits, each candle can produce light for exactlyt seconds. It takes the girl one second to light one candle. More formally, Anya can spend one second to light one candle, then this candle burns for exactlyt seconds and then goes out and can no longer be used.

For each of the m ghosts Anya knows the time at which it comes: thei-th visit will happenw_i seconds after midnight, allw_i‘s are distinct. Each visit lasts exactly one second.

What is the minimum number of candles Anya should use so that during each visit, at leastr candles are burning? Anya can start to light a candle at any time that is integer number of seconds from midnight, possibly, at the time before midnight.That means, she can start to light a candle integer number of seconds before midnight or integer number of seconds after a midnight, or in other words in any integer moment of time.

The first line contains three integers m, t, r (1?≤?m,?t,?r?≤?300), representing the number of ghosts to visit Anya, the duration of a candle‘s burning and the minimum number of candles that should burn during each visit.

The next line contains m space-separated numbersw_i (1?≤?i?≤?m,1?≤?w_i?≤?300), thei-th of them repesents at what second after the midnight thei-th ghost will come. Allw_i‘s are distinct, they follow in the strictly increasing order.

If it is possible to make at least r candles burn during each visit, then print the minimum number of candles that Anya needs to light for that.

If that is impossible, print ?-?1.

Anya can start lighting a candle in the same second with ghost visit. But this candle isn‘t counted as burning at this visit.

It takes exactly one second to light up a candle and only after that second this candle is considered burning; it means that if Anya starts lighting candle at moment x, candle is buring from second x + 1 to second x + t inclusively.

In the first sample test three candles are enough. For example, Anya can start lighting them at the3-rd,5-th and7-th seconds after the midnight.

In the second sample test one candle is enough. For example, Anya can start lighting it one second before the midnight.

In the third sample test the answer is ?-?1, since during each second at most one candle can burn but Anya needs three candles to light up the room at the moment when the ghost comes.

题目大意：一个人要遇到m只鬼，遇到每只鬼要的时间为w[i]，他的蜡烛能亮t秒，遇到一只鬼要至少有r支蜡烛亮着，他点燃蜡烛要1s，点燃的时间不算燃烧的时间，求他最少要带多少根蜡烛，要不存在解输出－1

题目分析：按区间模拟，首先要判断的是当t小于r时无解，因为点燃也要1s，因此不可能存在一个时刻让r支蜡烛都亮着，接着我们先找遇到第一个鬼的前1秒点一支蜡烛，假设此时为时刻t0则其后t0 + 1 + t的时间这根蜡烛都亮着，则这段区间标记一下，若此时不足以过第一个鬼则再遇到其前的第2秒再点一根，依次前推，注意当t0 + 1 + i小于0时，时间为负，不计积累量

#include <cstdio> 
#include <cstring> 
int const MAX = 1e4 + 5;
int w[MAX], vis[MAX];

int main()
{
    int m, t, r, ans = 0;
    scanf("%d %d %d", &m, &t, &r);
    if(t < r)
    {
        printf("-1\n");
        return 0;
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < m; i++)
        scanf("%d", &w[i]);
    for(int i = 0; i < m; i++)
    {
        for(int j = w[i] - 1; vis[w[i]] < r; j--)
        {
            for(int k = j + 1; k <= j + t; k++)
                if(k >= 0) 
                    vis[k]++;           
            ans++;
        }
    }
    printf("%d\n", ans);
}

5
aca
aba
aba
cab
bac

YES
abacaba

4
abc
bCb
cb1
b13

NO

7
aaa
aaa
aaa
aaa
aaa
aaa
aaa

YES
aaaaaaaaa

题目大意：给一个n，输入n个长度为3的字符串，字符包含英文的大小写和数字，判断是否存在一个长度为n+2的字符串包含全部n个子串

题目分析：可以把问题转化为判断是否存在欧拉通路，那如何构图？因为题目说了每个字符串的长度为3，因此我们把它的前两个字符当做一个结点，后两个字符当作一个结点，然后构建一个有向图，只需要判断这张图是否存在欧拉通路即可，欧拉通路是一条经过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路。这题和poj2377有点类似，但是这题有两点比那题棘手，1是结点的存储问题，那题是尾首字符相同便可链接，而这题需要将结点散列，因为一共就10+26+26=62个字符，我们先将62个字符从1到61编号再把结点设置为62x+y的整型变量，则可以将所有结点表示出来。还有个麻烦的地方在于数据量，本题的n即边数达到20w，如果已经判断存在欧拉通路，按照点dfs来找的话，平行边和自环一多很有可能超时甚至爆栈，因此我们可以用边来找，用边找的好处是找的过程中可以把自环和平行的都去掉，下面就是如何判断是否存在欧拉通路的问题，这里简单说，(我有详细介绍此类问题的博文)

1.并查集判连通

2.出入度都相等则为欧拉回路，dfs起点任意，若出入度相差1的点的个数不大于2则把出度大的做为起点，若个数大于2或者出入度相差超多1则不存在欧拉通路

#include <cstdio>
#include <cstring>
int const MAX = 200005;
int const MAX2 = 4000;
bool has[MAX2];
int fa[MAX2], out[MAX2], in[MAX2], path[MAX], e[MAX2][MAX2];
int n, len, st;
struct node
{
    int u, v;
    char name[3];
}r[MAX];

int abs(int x)
{
    return x > 0 ? x : -x;
}

void UF_set()
{
    for(int i = 0; i < MAX2; i++)
        fa[i] = i;
}

int Find(int x)
{
    return x == fa[x] ? x : fa[x] = Find(fa[x]); 
}

void Union(int a, int b)
{
    int r1 = Find(a);
    int r2 = Find(b);
    if(r1 != r2)
        fa[r1] = r2;
}

int ctoi(char ch)
{ 
    if(ch >= 'A' && ch <= 'Z') return ch - 'A' + 10;  
    if(ch >= 'a' && ch <= 'z') return ch - 'a' + 36;  
    return ch - '0';  
}

char itoc(int a)
{
    if(a >= 0 && a <= 9) return '0' + a;
    if(a >= 10 && a <= 35) return 'A' + a - 10;
    return 'a' + a - 36;
}

bool Exist()
{
    int t = -1;
    for(int i = 0; i < MAX2; i++)
    {
        if(has[i])
        {
            if(t == -1)
                t = Find(i);
            else if(Find(i) != t)
                return false;
        }
    }
    int sum = 0, tmp;
    for(int i = 0; i < MAX2; i++)
    {
        if(has[i])
        {
            tmp = i;
            if(in[i] != out[i])
            {
                sum++;
                if(abs(in[i] - out[i]) > 1)
                    return false;
                if(out[i] > in[i])
                    st = i;
            }
        }
    }
    if(sum > 2)
        return false;
    if(sum == 0)
        st = tmp;
    return true;
}

void DFS(int now)
{
    for(int i = 0; i < MAX2; i++)
    {
        while(e[now][i])
        {
            e[now][i]--;
            DFS(i);
            path[len++] = i;
        }
    }
}

int main()
{
    scanf("%d", &n);
    UF_set();
    memset(e, 0, sizeof(e));
    for(int i = 0; i < n; i++)
    {
        scanf("%s", r[i].name);
        r[i].u = ctoi(r[i].name[0]) * 62 + ctoi(r[i].name[1]);
        r[i].v = ctoi(r[i].name[1]) * 62 + ctoi(r[i].name[2]);
        has[r[i].u] = true;
        has[r[i].v] = true;
        Union(r[i].u, r[i].v);
        out[r[i].u]++;
        in[r[i].v]++;
        e[r[i].u][r[i].v]++;
    }
    if(!Exist())
        printf("NO\n");
    else
    {   
        len = 0;
        DFS(st);
        path[len++] = st;
        printf("YES\n");
        printf("%c%c", itoc(path[len - 1] / 62), itoc(path[len - 1] % 62));
        for(int i = len - 2; i >= 0; i--)
            printf("%c", itoc(path[i] % 62));
        printf("\n");
   }
}