CF1521C Nastia and a Hidden Permutation 做题记录

这是一道交互题

有一个长为 nn 的排列 pp,你需要在 3n2+30\lfloor\frac{3n}{2}\rfloor + 30 次询问内找出排列 pp 每一位所对应的数。

有两种操作

  • t=1:max(min(x,pi),min(x+1,pj))t = 1 : max(min(x, p_i), min(x + 1, p_j))
  • t=2:min(max(x,pi),max(x+1,pj))t = 2 : min(max(x, p_i), max(x +1, p_j))

1t2,1i,jn(ij),1xn11 \le t \le 2,1 \le i,j \le n(i \ne j),1 \le x \le n - 1

1T104,3n104,n2×1041 \le T \le 10^4,3 \le n \le 10^{4}, \sum n \le 2\times 10^4

阅读全文 »

POJ21677 / QOJ141 染色 做题记录

通信题,Alice 和 Bob 会收到同一个 nn 个点 mm 条边的无向图,Alice 会额外收到这个图的一个合法 88 染色。Alice 要向 Bob 发一个长度小于等于 2.5×1052.5\times 10^50101 串,Bob 需要根据这个 0101 串还原出任意一个合法的 88 染色方案。

1n2×1051\le n\le 2\times 10^51m5×1051\le m\le 5\times 10^5

阅读全文 »

【World tour final 2019 C1】Triangular Lamps Easy 做题记录

有一个无限大的平面,每个点上都有一盏灯。

刚开始只有位于 (X,0)(X,0) 的灯是亮起的,之后 Alice 会进行若干次操作,每次操作她会选择一个位置 (x,y)(x,y),并同时改变 (x,y)(x,y)(x,y1)(x,y-1)(x1,y1)(x-1,y-1) 这些灯的状态。

最终一共有 nn 盏灯亮起了,给定这些灯的位置 (xi,yi)(x_i,y_i),请你求出 XX

1n1051\le n\le 10^50xi,yi10170\le |x_i|,|y_i|\le 10^{17}

保证有解且 0X10170\le |X| \le 10^{17}

阅读全文 »

ABC163E Active Infants 做题记录

给定 nn 个数 a[1,n]a_{[1,n]},现在要将其重排。

如果 aia_i 于重排前在第 ii 个位置,现在移动到了第 jj 个位置,那么对答案的贡献就是 ji×ai|j-i|\times a_i

输出所有重排方案中最大的答案。

  • 2N20002 \leq N \leq 2000
  • 1Ai1091 \leq A_i \leq 10^9
阅读全文 »

CF1558C Bottom-Tier Reversals 做题记录

给定一个长度为奇数的排列 a1,a2,,ana_1, a_2, \dots, a_n,你需要构造一组长度不超过的 52n\frac 52 n 的操作序列 s1,s2,,sks_1, s_2, \dots, s_k,使得:

  • 1sin1 \le s_i \le nsis_i 为奇数;
  • 按从前往后的顺序,对于每个 sis_i,反转排列的前 sis_i 项,最后得到的排列中 ai=ia_i = i

1n20211\le n\le 20211ain1\le a_i\le n

阅读全文 »