Educational Codeforces Round 68 (Rated for Div. 2)

Remove a Progression

找到规律，隔一个删一个

Yet Another Crosses Problem

这个气死了，存的时候从index[1]开始的，访问从index[0]，一直re

检测每一行和每一列‘*’数量，最大的行列数量，cntn，cntm以及取到最大值的所有行列

记录最多的数量，如果N - cntn + M - cntm == 1 || 0的话就直接输出

如果不是的话就需要判断一下缺的‘*’是不是在交汇点，是的话ans–

From S To T

  1. s中的字符t都有
  2. s中的字符在t中对应顺序相同
  3. s+p中的字符数量够组成t

1-2-K Game

终于找到规律了，收到之前取石头的启发，寻找必胜的策略

然后下面是打表代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*-------------------------------------------------------------------------------------------*/
struct Pos
{
    int x,y,z;
}a[MAX];
int flag[MAX];
/* ------------------------------------------------------------------------------------------*/

void myanscout(bool flag)
{
    if(!flag) cout << "Alice" <<endl;
    else cout << "Bob"<<endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* --------------------------------------------------------------------------------------*/
    cin >> T;
    int k;
    while(T--)
    {
        cin >> N >> k;
        flag[0] = 1;
        flag[1] = flag[2] = 0;//0代表走到这一步就会输
        for(int i = 3;i <= N;i++)
        {
            a[i].x = i-1;
            a[i].y = i-2;
            if(i >= k) a[i].z = i-k;
            else a[i].z = -1;
            if(!flag[a[i].x] && !flag[a[i].y] && !flag[a[i].z])
            {
                flag[i] = 1;//1代表走到这一步就会赢
            }
            else flag[i] = 0;
        }
        for(int i = 0;i <= N;i++)
        {
            cout << setw(3) <<i;
        }
        cout << endl;
        for(int i = 0;i <= N;i++)
        {
            cout << setw(3) <<a[i].x;
        }
        cout << endl;
        for(int i = 0;i <= N;i++)
        {
            cout << setw(3) <<a[i].y ;
        }
        cout << endl;
        for(int i = 0;i <= N;i++)
        {
            cout <<setw(3) << a[i].z ;
        }
        cout << endl;
        for(int i = 0;i <= N;i++)
        {
            cout << setw(3) <<flag[i] ;
        }
        cout << endl;
        myanscout(flag[N]);
    }
    return 0;
}

定义的x,y,z为这一步可以走到的下一步

flag的值代表走到这一步必输还是必赢（0，1）

轻松的可以知道，如果走到n，而n可以到达的下一步都是必输，你走到的n就会必赢，因为对手只能走到必输的一步

通过打表可以找到到规律

如果k不是三的倍数，那么flag一定是100循环

如果k是三的倍数，则是0-K的循环，其实就是k位的 flag1->0,循环

/img/post_blog/ECF-68-2-1.jpg

再仔细想一下，其实前三位一定是100，当k不是三的倍数的时候前四位也是确定的1001，那么5，6位也会确定是00，

第七位因为k不是3的倍数所以肯定是不会走到flag = 1的值上，所以答案确定

当k是3的倍数时候再走到k之前，flag是不变的，k位的flag就会 flag1->0

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
36
37
LL T,N,M;
/*-------------------------------------------------------------------------------------------*/
 
/* ------------------------------------------------------------------------------------------*/
 
void myanscout(bool flag)
{
    if(!flag) cout << "Alice" <<endl;
    else cout << "Bob"<<endl;
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* --------------------------------------------------------------------------------------*/
    cin >> T;
    int k;
    while(T--)
    {
        cin >> N >> k;
        if(k % 3 == 0)
        {
            N = N%(k+1);
            if(N == k) myanscout(0);
            else myanscout(!(N % 3));
        }
        else
        {
            myanscout(!(N % 3));
        }
    }
    return 0;
}