「CROI · R2」在相思树下 I

Luogu
IDLGP10765
Time1000ms
Memory512MB
DifficultyP2
数学贪心洛谷原创O2优化洛谷月赛
**本题采用多组数据测试。** 现在欣欣有一个从 $1$ 到 $n$ 的序列,并想对这个序列进行如下两种操作。 操作一:删去所有的奇数项。 操作二:删去所有的偶数项。 欣欣发现她在进行 $k$ 次操作后,最后只剩下一个数,但她不知道这个数是多少,于是欣欣来找你求助,她会给你她所进行的 $k$ 次操作的种类,希望你告诉她最后的那个数是多少。 ## Input 第一行一个正整数 $T$,表示数据组数。 对于每组数据: 第一行两个整数 $n$ 和 $k$,含义如题面所示。 第二行 $k$ 个整数,代表欣欣依次进行的操作种类,其中 $1$ 代表操作一,$2$ 代表操作二。 ## Output 共 $T$ 行,每行一个数代表每组数据对应的答案。 [samples] ## Background >年年桃树下 > >常看一个变成俩 > >小小心愿常比划 > >快快实现吧 > >却没看到他也在树下 > >相逢二字纵使隔天涯 > >转角总会遇上他 > >缘分缘分啊 ## Note **【样例解释】** 对于第一组数据,序列的变化如下: $\{1,2,3,4,5\} \to \{2,4\} \to \{4\}$。 **【数据范围】** 对于 $30\%$ 的数据, $n\le 5\times10^5$。 对于 $100\%$ 的数据,$1\le T \le 10$,$1\le n\le 10^{18}$。 保证对于所有的数据,操作 $k$ 次后均仅剩下一个数。
Samples
Input #1
4
5 2
1 1
8 3
2 2 2 
8 3 
1 1 1
8 3
1 2 1
Output #1
4
1
8
6
API Response (JSON)
{
  "problem": {
    "name": "「CROI · R2」在相思树下 I",
    "description": {
      "content": "**本题采用多组数据测试。** 现在欣欣有一个从 $1$ 到 $n$ 的序列,并想对这个序列进行如下两种操作。 操作一:删去所有的奇数项。 操作二:删去所有的偶数项。 欣欣发现她在进行 $k$ 次操作后,最后只剩下一个数,但她不知道这个数是多少,于是欣欣来找你求助,她会给你她所进行的 $k$ 次操作的种类,希望你告诉她最后的那个数是多少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10765"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**本题采用多组数据测试。**\n\n现在欣欣有一个从 $1$ 到 $n$ 的序列,并想对这个序列进行如下两种操作。\n\n操作一:删去所有的奇数项。\n\n操作二:删去所有的偶数项。\n\n欣欣发现她在进行 $k$ 次操作后,最后只剩下一个数,但她不知道这个数是多少,于是欣欣来找你求助,她会给你她所进行的 $k$ 次操作的种类,希望你告诉她最后的那个数是多少。\n\n## Input\n\n第一行一个正整数 $T$,表...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments