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 * (3^{n-1}-3^{n-2}), a_1 * a_2 * (3^{n-2}-3^{n-3}),……，a_1*a_2*……*a_n$,

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

Unsolved.

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

Unsolved.