Educational Codeforces Round 68 Editorial

The example contains all the pictures from above in the same order.

The first 5 pictures already contain a cross, thus you don‘t have to paint anything.

You can paint (1,3)(1,3), (3,1)(3,1), (5,3)(5,3) and (3,5)(3,5) on the 66-th picture to get a cross in (3,3)(3,3). That‘ll take you 44 minutes.

You can paint (1,2)(1,2) on the 77-th picture to get a cross in (4,2)(4,2).

You can paint (2,2)(2,2) on the 88-th picture to get a cross in (2,2)(2,2). You can, for example, paint (1,3)(1,3), (3,1)(3,1) and (3,3)(3,3) to get a cross in (3,3)(3,3) but that will take you 33 minutes instead of 11.

There are 9 possible crosses you can get in minimum time on the 99-th picture. One of them is in (1,1)(1,1): paint (1,2)(1,2) and (2,1)(2,1).

题解：题目说在一个 n 行 m 列区域内，看有没一个黑色通道通往这个区域的行与列，有输出0，没有计算需要改变白色区域的最少次数。暴力解法开两个数组记录每行和每列缺少黑色的个数，最后遍历一遍，注意每次遍历的时候都要看一下当前字母是黑色还是白色，因为每行和每列都有个重复的字母，所以要特别判断一下。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int MAXX = 0x7fffffff;
 7 int main()
 8 {
 9     ios::sync_with_stdio(false);
10     cin.tie(0); cout.tie(0);
11     int q;
12     cin>>q;
13     while(q--)
14     {
15         int m,n;
16         cin>>n>>m;
17         char a[n + 10][m + 10];
18         int x[n + 10] , y[m + 10];
19         memset(x,0,sizeof(x));
20         memset(y,0,sizeof(y));
21         for(int i = 0; i < n; i++)
22             for(int j = 0; j < m; j++)
23                 cin>>a[i][j];
24  
25         for(int i = 0; i < n; i++)
26         {
27             int flag = 0;
28             for(int j =0; j < m; j++)
29                 if(a[i][j] == ‘.‘)
30                     flag++;
31             x[i] = flag;
32         }
33  
34         for(int i = 0; i < m; i++)
35         {
36             int flag = 0;
37             for(int j = 0; j < n; j++)
38                 if(a[j][i] == ‘.‘)
39                     flag++;
40             y[i] = flag;
41         }
42         int ans = MAXX;
43         for(int i = 0; i < n; i++)
44         {
45             for(int j = 0; j < m; j++)
46             {
47                 if(a[i][j] == ‘.‘)
48                     ans = min(ans,x[i] + y[j] - 1);
49                 else
50                     ans = min(ans,x[i] + y[j]);
51             }
52         }
53         cout<<ans<<endl;
54     }
55     return 0;
56 }

View Code

                                                                                                 C. From S To T

                                                                                                      time limit per test：1 second

                                                                                                memory limit per test：256 megabytes

                                                                                                             input：standard input

                                                                                                            output：standard output

4
ab
acxb
cax
a
aaaa
aaabbcc
a
aaaa
aabbcc
ab
baaa
aaaaa

YES
YES
NO
NO

Note

In the first test case there is the following sequence of operation:

1. s=s= ab, t=t= acxb, p=p= cax;
2. s=s= acb, t=t= acxb, p=p= ax;
3. s=s= acxb, t=t= acxb, p=p= a.

In the second test case there is the following sequence of operation:

1. s=s= a, t=t= aaaa, p=p= aaabbcc;
2. s=s= aa, t=t= aaaa, p=p= aabbcc;
3. s=s= aaa, t=t= aaaa, p=p= abbcc;
4. s=s= aaaa, t=t= aaaa, p=p= bbcc.

题解：题目说给你三个字符串 s , t , p, 然后从 字符串p 拿任意字符插入 字符串s 任何位置， 最后匹配一下 字符串s 是否等价于 字符串t, 若匹配输出 "YES", 反之输出 "NO"。

思路： 模拟一下是否为子序列，然后记下数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int q;
 6     int a[30],b[30];
 7     cin>>q;
 8     while(q--)
 9     {
10         string s,t,p;
11         memset(a,0,sizeof(a));
12         memset(b,0,sizeof(b));
13         cin>>s>>t>>p;
14         int k = 0;
15         bool flag = true;
16         for(int i = 0; i < s.size(); i++)
17         {
18             int j;
19             a[s[i] - ‘a‘]++;
20             for(j = k; j < t.size(); j++)
21             {
22                 if(s[i] == t[j])
23                 {
24                     k = j + 1;
25                     break;
26                 }
27             }
28             if(j >= t.size())
29                     flag = false;
30         }
31         if(!flag)
32         {
33             cout<<"NO"<<endl;
34             continue;
35         }
36         for(int i = 0; i < p.size(); i++)
37             a[p[i] -‘a‘]++;
38         for(int i = 0; i < t.size(); i++)
39             b[t[i] - ‘a‘]++;
40         for(int i = 0; i <= 26; i++)
41         {
42             if(a[i] < b[i])
43             {
44                 flag = false;
45                 break;
46             }
47         }
48         if(flag)
49             cout<<"YES"<<endl;
50         else
51             cout<<"NO"<<endl;
52     }
53     return 0;
54 }

View Code

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 
 6 int number(string a, char b)
 7 {
 8     int cnt = 0;
 9     for (int i = 0; i < a.size(); i++)
10         if (a[i] == b)
11             cnt++;
12     return cnt;
13 }
14 
15 int main()
16 {
17     int q;
18     cin >> q;
19     string s, t, p;
20     while (q--)
21     {
22         cin >> s >> t >> p;
23         int k = 0;
24         bool is_continue = false;
25         for (int i = 0; i < s.size(); i++)
26         {
27             if (t.find(s[i], k) != t.npos)
28             {
29                 k = t.find(s[i], k)+1;
30             }
31             else
32             {
33                 cout << "NO" << endl;
34                 is_continue = true;
35                 break;
36             }
37         }
38         if (is_continue == true)
39             continue;
40         bool is_real = false;
41         for (int i = 0; i < t.size(); i++)
42         {
43             if ((number(s, t[i]) + number(p, t[i])) < number(t, t[i]))
44             {
45                 cout << "NO" << endl;
46                 is_real = true;
47                 break;
48             }
49         }
50         if (is_real == false)
51             cout << "YES" << endl;
52     }
53     return 0;
54 }

View Code

                                                                                                                   D. 1-2-K Game

                                                                                                                       time limit per test:2 seconds

                                                                                                                       memory limit per test:256 megabytes

                                                                                                                                     input:standard input

                                                                                                                                     output:standard output

Alice and Bob play a game. There is a paper strip which is divided into n + 1 cells numbered from left to right starting from 0. There is a chip placed in the n-th cell (the last one).

Players take turns, Alice is first. Each player during his or her turn has to move the chip 1, 2 or k cells to the left (so, if the chip is currently in the cell i, the player can move it into cell i - 1, i - 2 or i - k). The chip should not leave the borders of the paper strip: it is impossible, for example, to move it k cells to the left if the current cell has number i < k. The player who can‘t make a move loses the game.

Who wins if both participants play optimally?

Alice and Bob would like to play several games, so you should determine the winner in each game.

Input

The first line contains the single integer T (1 ≤ T ≤ 100) — the number of games. Next T lines contain one game per line. All games are independent.

Each of the next T lines contains two integers n and k (0 ≤ n ≤ 109, 3 ≤ k ≤ 109) — the length of the strip and the constant denoting the third move, respectively.

Output

For each game, print Alice if Alice wins this game and Bob otherwise.

Example

input

Copy

4
0 3
3 3
3 4
4 4

output

Copy

Bob
Alice
Bob
Alice
题解：博弈问题两人每人能取 1 , 2 , k 个东西，谁先不能移动谁先输，我们来看看当不取K个时的SG函数:
        G(s0)=0,G(s1)=1,G(s2)=2,G(s3)=0,G(S4)=1,G(S5)=2，G(s6)=1......
        G(s) = 0是一个 P 态，反之是一个N态。即n≡0mod3时是必败态，否则是必胜态。

• 根据以下原则打表：
• 当前状态指向的所有后继状态都是必胜态，那么当前状态是必败态
• 当前状态能够指向某一个必败态，那么当前状态是必胜态

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main() {
 5     int t;
 6     cin >> t;
 7     while(t--) {
 8         int n, k;
 9         cin >> n >> k;
10         if(k % 3 != 0)
11             cout << (n % 3 == 0 ? "Bob\n" : "Alice\n");
12         else {
13             n %= (k + 1);
14             if(n % 3 == 0 && n < k)
15                 cout << "Bob\n";
16             else
17                 cout << "Alice\n";
18         }
19     }
20 }

View Code