【题解】PATB-1069 微博转发抽奖

发表于 分类于 ， ， 本文字数： 322 阅读时长 ≈ 1 分钟
PATB-1069 微博转发抽奖 类型 水题

微博转发抽奖 (PATB-1069)

题面

小明 PAT 考了满分，高兴之余决定发起微博转发抽奖活动，从转发的网友中按顺序每隔 N 个人就发出一个红包。请你编写程序帮助他确定中奖名单。

输入

输入第一行给出三个正整数 M（≤ 1000）、N 和 S，分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号（编号从 1 开始）。随后 M 行，顺序给出转发微博的网友的昵称（不超过 20 个字符、不包含空格回车的非空字符串）。

注意：可能有人转发多次，但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖，则跳过他顺次取下一位。

输出

按照输入的顺序输出中奖名单，每个昵称占一行。如果没有人中奖，则输出 Keep going...。

样例输入1

1
2
3
4
5
6
7
8
9
10
9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

样例输出1

1
2
3
PickMe
Imgonnawin!
TryAgainAgain

样例输入2

1
2
3
2 3 5
Imgonnawin!
PickMe

样例输出2

1
Keep going...

提示

无

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ULL bkdr(char* s)
{
 ULL seed = 131, h = 0;
 while (*s)
  h = h * seed + (*s++);
 return h;
}

int main()
{
    int m, n, s;
    scanf("%d %d %d", &m, &n, &s);

    map<ULL, int> mmp;
    int now=0, num=0; char t[25];

    for(int i=1; i<=m; i++)
    {
        scanf("%s", t); now++;
        if(now>=s && (now-s)%n==0)
        {
            int x = bkdr(t);
            if(mmp.count(x) == 0)
            {
                printf("%s\n", t);
                num++, mmp[x]++;
            }
            else
                now--;
        }
    }
    if(num == 0) printf("Keep going...\n");

    return 0;
}