CF2276F.Permutation Coloring Game

提高+/省选-

通过率:0%

时间限制:3.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Alice and Bob are playing a game. They have a permutation pp of length nn — an array of nn elements in which every integer from 11 to nn occurs exactly once. Initially, every element of the permutation is colored white.

The players take turns; Alice goes first. On each turn, the current player chooses between 11 and kk white elements and colors all of them either red or blue. All elements chosen on the same turn must receive the same color.

The game ends when there are no white elements left. If the resulting permutation can be sorted in increasing order by swapping elements of the same color, Alice wins. Otherwise, Bob wins. Any two elements may be swapped as long as they have the same color.

Determine who wins if both players play optimally.

爱丽丝和鲍勃正在玩一个游戏。他们有一个长度为 nn 的排列 pp —— 即一个由 nn 个元素组成的数组,其中 11 到 nn 的每个整数恰好出现一次。初始时,排列中的每个元素均为白色。

双方轮流行动,爱丽丝先手。在每一轮中,当前玩家需从所有白色元素中选择 11 至 kk 个,并将它们全部染成红色或全部染成蓝色;同一轮中所选的所有元素必须染成同一种颜色。

当不再有白色元素时,游戏结束。若最终的排列可以通过仅交换同色元素(即任意两个同色元素均可交换)的方式升序排序,则爱丽丝获胜;否则鲍勃获胜。

假设双方均以最优策略进行游戏,请判断谁将获胜。

输入格式

The first line contains one integer tt (1≤t≤1041 \le t \le 10^4) — the number of test cases.

Each test case consists of two lines:

  • the first line contains two integers nn and kk (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5; 1≤k≤min⁡(20,n)1 \le k \le \min(20, n)) — the length of the permutation and the maximum number of elements that can be colored in one turn;
  • the second line contains nn pairwise distinct integers p1,p2,…,pnp_1, p_2, \ldots, p_n (1≤pi≤n1 \le p_i \le n).

Additional constraints on the input:

  • the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)—— 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含两个整数 nn 和 kk(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5;1≤k≤min⁡(20,n)1 \le k \le \min(20, n))—— 排列的长度,以及每次操作最多可染色的元素个数;
  • 第二行包含 nn 个互不相同的整数 p1,p2,…,pnp_1, p_2, \ldots, p_n(1≤pi≤n1 \le p_i \le n)。

输入的额外约束条件:

  • 所有测试用例的 nn 值之和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, print Alice on a separate line if Alice wins, or Bob if Bob wins.

对于每个测试用例,如果 Alice 获胜,则单独输出一行 Alice;如果 Bob 获胜,则单独输出一行 Bob。

输入输出样例

  • 输入#1

    10
    2 1
    1 2
    2 1
    2 1
    2 2
    2 1
    3 2
    2 3 1
    4 2
    2 3 1 4
    8 3
    2 3 1 5 6 4 8 7
    10 3
    2 3 1 5 6 4 8 7 10 9
    6 2
    1 2 3 5 6 4
    7 1
    4 5 6 1 2 3 7
    8 1
    4 5 6 1 2 3 7 8

    输出#1

    Alice
    Bob
    Alice
    Bob
    Alice
    Alice
    Bob
    Bob
    Alice
    Bob

说明/提示

null

输入解题思路,AI测评打分。不知道怎么写?

首页