Codeforces Round #425 (Div.2)

A、Sasha and Sticks

　　题意：有两个人，每次轮流从n个棒子中抽出k个，直到剩余不足k个棒子。Sasha先抽。如果Sasha抽取的多，则输出YES，否则输出NO。

　　思路：n/k为奇数时，Sasha获胜。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 LL n, k;
 6 int main()
 7 {
 8     while (~scanf("%I64d%I64d", &n, &k))
 9     {
10         LL ans = n/k;
11         if (ans % 2 == 1) printf("YES
");
12         else printf("NO
");
13     }
14     return 0;
15 }

View Code

B、Petya and Exam

　　题意：先给出若干个good字符，其他剩下的小写英文字符都是bad字符，再给出一个需要匹配的字符串p(有若干个小写字母、若干个‘？’，最多一个‘*’)，接下来给出n个字符串，你可以每次把‘？’改成一个good字符，把‘*’改为一个空字符串或者由bad字符组成的字符串，如果能够使其和给出的字符串相同，则输出‘YES’，否则输出NO。

　　思路：模拟即可。

 1 #include<iostream>
 2 #include<memory.h>
 3 #include<string.h>
 4 using namespace std;
 5 bool good[26];
 6 char gd[30];
 7 char p[100010];
 8 char s[100010];
 9 int main()
10 {
11     while (~scanf("%s", gd))
12     {
13         memset(good, 0, sizeof(good));
14         for (int i = 0; gd[i] != ''; i++) good[gd[i] - 'a'] = true;
15         scanf("%s", p);
16         int lenp = strlen(p);
17         int q;
18         scanf("%d", &q);
19         for (int i = 0; i < q; i++)
20         {
21             scanf("%s", s);
22             int len = strlen(s);
23             int d = len - lenp;
24             if (d < 0)
25             {
26                 if (d<-1) printf("NO
");
27                 else
28                 {
29                     bool flag = true;
30                     for (int i = 0,j=0; i < lenp; j++,i++)
31                     {
32                         if (p[i] == '*') j--;
33                         else
34                         {
35                             if (p[i] == s[j]) continue;
36                             else
37                             {
38                                 if (p[i] == '?'&&good[s[j] - 'a']) continue;
39                                 else
40                                 {
41                                     flag = false;
42                                     break;
43                                 }
44                             }
45                         }
46                     }
47                     if (flag) printf("YES
");
48                     else printf("NO
");
49                 }
50             }
51             else
52             {
53                 d = d + 1;
54                 bool flag = true;
55                 int j,i;
56                 for (i = 0,j=0; i < lenp; i++,j++)
57                 {
58                     if (p[i] == s[j]) continue;
59                     else if (p[i] == '?')
60                     {
61                         if (!good[s[j] - 'a'])
62                         {
63                             flag = false;
64                             break;
65                         }
66                     }
67                     else if(p[i]=='*')
68                     {
69                         for (int k = 0; k < d; k++)
70                         {
71                             if (good[s[j + k]-'a'])
72                             {
73                                 flag = false;
74                                 break;
75                             }
76                         }
77                         if (!flag) break;
78                         j += d-1;
79                     }
80                     else
81                     {
82                         flag = false;
83                         break;
84                     }
85                 }
86                 if (j < len) flag = false;
87                 if (flag) printf("YES
");
88                 else printf("NO
");
89             }
90         }
91     }
92     return 0;
93 }

View Code