Mashup Trainings Day 3: F0RE1GNERS' Contest

One,Two,Three,AK

题解：https://acm.ecnu.edu.cn/blog/entry/253/

Problem A

Solved by dreamcloud. 0:24:12(+)

题意：总共有 n （奇数）个座位围成一圈，不能有相同性别的人相邻，所以肯定有位置是空着的。每次询问告诉你该位置上的性别。在一定询问次数内确定至少一个空位置。

题解：每次根据原来已知的位置上的性别，询问对面性别，根据奇偶性可以把区间缩小一半。

Problem B

Solved by dreamcloud. 3:00:55(+3)

题意：给你一堆数，$a_1,a_2,……,a_n$,让你在相邻数之间插入$+,-,*$, 总共$3^{n-1}$种填法，问你它们计算出结果之后的累和。每次询问会修改一个数。

题解：由于有加号和减号都存在，它们会互相抵消，对一个数来说只有满足它前面的运算符都是乘法，他才会对答案有贡献。 实际上最后剩下的只有$a_1 \times (3^{n-1}-3^{n-2}), a_1 \times a_2 \times (3^{n-2}-3^{n-3}),……，a_1 \times a_2 … \times a_n$求和, 修改一个数，只要对所有包含这个数的，都乘上原来数的逆和现在这个数。 0是个需要特别注意判的

Problem C

Solved by dreamcloud && Xiejiadong. 3:45:29(+2)

题意：交互题，两个人抢巧克力，你最后要获得$\ge 0.55$的巧克力。

题解：第一次只取$1/3$，留下$2/3$在第一堆，然后每次都在除第$0$堆以外的最大堆里取$2/3$，最后一次，在从第$0$堆取出$2/3$。

需要注意只有一轮的情况。

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Upsolved by Xiejiadong.

题意：求$m$条，长度在$l$到$r$范围内的自底向上的链的最大和。

题解：这题的简化版本：https://www.lydsy.com/JudgeOnline/problem.php?id=2006

我们可以从最大的开始枚举$k$个可行区间。

我们用五个信息来维护区间$(x,l,r,q,v)$，$x$表示区间右端点，$l$表示区间最左边可以到的位置，$r$表示区间最右边可以到的位置，$q$表示最大区间和在的左边界坐标，$v$表示这个可行范围内的最大区间和。

我们先枚举所有的右边界，直接扔到优先队列里维护$v$即可。

对于当前取出的区间，我们可以把它分裂成两个区间$(x,l,q-1,q_1,v_1)$，$(x,q+1,r,q_2,v_2)$，即区间位置$q$以后的区间，$q_1,1_2,v_1,v_2$需要重新计算。

作为上边的加强版，我们只要从叶子结点开始统计$min$信息和$fa$信息，然后把所有结点作为最底层结点，向上维护，类似于链的形式，维护一个五元的组合。

noi的钢琴那题，贪图方便，上面代码时间复杂度是$O(n\times log^2_2m)$，然后这题就被卡了。

在维护st表的时候，新开一个数组$ANS$表示当前位置向上对应的长度，然后不再用二分去探查位置，直接可以得到。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Xiejiadong && oxx1108. 4:59:24(+32)

题意：交互题。猜一个$0/1$串，只有猜对$n/2$或者$n$的时候才会返回值，否则范围$0$。

题解：好像可以先随便猜一个$n/2$位相同的串出来..期望次数大约是$40$..不会证明。

现在我们想知道每一位具体的值。 似乎将每一位单独取反之后.. 答案要么$+1$要么$-1$.. 返回值都是$0$，这样就没有办法判断了。

把每位与第一位同时取反,然后做一次询问，这样就能得到每一位和第一位之间的关系了,这一步要进行$n-1$次询问

然后枚举第一位是$0$还是$1$.. 根据之前得到的每位与第一位之间的关系，就能得出每一位的值。

对这两种情况分别做一次询问就好了。

Problem K

Upsolved by dreamcloud.