CF1556D Take a Guess 做题记录

这是一道交互题,给定两个正整数 n,kn,k,你需要通过 2n\leq 2n 次询问猜出长度为 nn 的序列 {ai}\{a_i\} 中的第 kk 小值。

询问分为两种类型:

  1. or i j,交互器会返回 aioraja_i \operatorname{or}a_j 的值。
  2. and i j,交互器会返回 aiandaja_i\operatorname{and}a_j 的值。

其中需要满足 1i,jn1\leq i,j\leq ni=ji\not = j

最后你需要输出 finish res,其中 resres 表示你的答案。

3n104,1kn,0ai1093\leq n \leq 10^4,1\leq k\leq n,0\leq a_i\leq 10^9

阅读全文 »

CF1583D Omkar and the Meaning of Life 做题记录

这是一道交互题。

原来生命的意义是一个 nn (2n1002 \leq n \leq 100) 的排列。 创造了世上所有生命的 Omkar 知道这个排列,他允许你在有限的询问次数内查询出这个排列是什么。

每一次询问你可以给出一个序列 a1,a2,,ana_1, a_2, \ldots, a_n (1a1,a2,,ann1\le a_1,a_2,\ldots,a_n \le n) 来对 Omkar 进行询问。 $ a $ 序列不一定要是一个排列。之后 Omkar 会逐个将 aia_ipip_i 相加得到一个新的序列 ss ,即对于每个 jj (1jn1\le j \le n) ,sj=pj+ajs_j = p_j + a_j 。最后 ss 序列中可能会出现一些相同的数,你将读入 Omkar 告诉你的第一个出现相同数的位置。如果没有相同的数出现,你将读入数字 00

你最多只能进行 2n2n 次询问。

阅读全文 »

CF896B Ithea Plays With Chtholly 做题记录

桌子上面摆着 nn 张白纸,交互库会依次给你 mm[1,c][1,c] 中的数,你每次可以把所获得的数写在一张纸上或者替换掉某一张纸上写的数,在你行动结束后交互库才会给你下一个数。任何时候,如果所有纸上都写了数字并且成非降序排列,你就赢了,直接结束程序。你要想办法赢交互库。

2n,m2\le n,m1c10001\le c\le 10001nc2m10001\le n\cdot \lceil\frac{c}{2}\rceil\le m\le 1000

阅读全文 »

CF1713D Tournament Countdown 做题记录

这是一道交互题。

有一场由 2n2^n 位选手组成的锦标赛。

这个锦标赛的规则如下:第 11 位选手与第 22 位选手竞争,第 33 位选手与第 44 位选手竞争……以此类推,比赛结束时会只剩下一位参赛选手,这位参赛选手就是胜利者。

你不知道比赛的结果,但你想通过询问评审团来得知最后谁赢了。

每次询问评审团,你需要给定两个正整数 aabbaabb 分别代指两位选手的编号。

aa 选手 比 bb 选手 赢的回合更多,评委团将报出数字 11;如果 bb 选手 比 aa 选手 赢的回合更多,评审团将报出数字 22;如果这两位选手赢的回合一样多,评审团会报出数字 00

你要做的是在不超过 132n+1\lceil \frac{1}{3} \cdot 2^{n+1} \rceil 的次数内找到最后胜利的选手。此处 x\lceil x \rceil 表示四舍五入 xx 到最近的整数。

这场锦标赛已经过去很久了。所以保证有唯一解。

1n171\leq n\leq 17

阅读全文 »

CF1713E Cross Swapping 做题记录

给定一个 n×nn\times n 的矩阵。一次操作可以给定一个 kk 然后交换所有的 Ai,kA_{i,k}Ak,iA_{k,i}

如图表示 n=4,k=3n=4,k=3 的情况。

求若干次操作后字典序最小的矩阵。

1n10001 \leq n \leq 1000

阅读全文 »

CF1088D Ehab and another another xor problem 做题记录

交互题,系统有两个整数 (a,b)(a,b),你每次可以询问一组整数 (c,d)(c,d),系统会回答:

  • 11 如果 ac>bda\oplus c>b\oplus d
  • 00 如果 ac=bda\oplus c=b\oplus d
  • 1-1 如果 ac<bda\oplus c<b\oplus d

其中操作 aba\oplus b 表示 aabb 按位异或。

你需要在询问不超过 6262 次之后输出 (a,b)(a,b) 的值,保证 0a,b<2300\le a, b < 2^{30}

阅读全文 »

CF1451E1&2 Bitwise Queries (Easy&Hard Version) 做题记录

Ridbit 有一个隐藏的长度为 nn 的数组 aa,Ashish 要去猜,nn22整数次幂。Ridbit 允许 Ashish 提出三种不同类型的查询。它们分别是:

  • AND i,ji,j:求元素 aia_iaja_j 每一位的 andand1i1≤i,jnj≤n,iji≠j

  • OR i,ji,j:求元素 aia_iaja_j 每一位的 oror1i1≤i,jnj≤n,iji≠j

  • XOR i,ji,j:求元素 aia_iaja_j 每一位的 xorxor1i1≤i,jnj≤n,iji≠j

限制:

  • Ashish 最多可以询问 n+1n + 1 次(Hard Version)n+2n+2 次(Easy Version)。
  • 0ain20 \le a_i \le n - 2

1n2161\le n\le 2^{16}

阅读全文 »

CF1415D XOR-gun 做题记录

给定一个长为 nn 的不降序列,每次操作可以任选相邻的两个数,并将这两个数替换为两个数按位异或的结果,现在需要破坏序列的不降,求最少操作次数,无解输出 1-1

2n1052 \le n \le 10^51ai1091 \le a_i \le 10^9

阅读全文 »