Difference between revisions of "Mashup Trainings Day 3: F0RE1GNERS' Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 18: Line 18:
  
 
题解:由于有加号和减号都存在,它们会互相抵消,对一个数来说只有满足它前面的运算符都是乘法,他才会对答案有贡献。
 
题解:由于有加号和减号都存在,它们会互相抵消,对一个数来说只有满足它前面的运算符都是乘法,他才会对答案有贡献。
实际上最后剩下的只有$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$求和,
+
实际上最后剩下的只有$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是个需要特别注意判的
 
修改一个数,只要对所有包含这个数的,都乘上原来数的逆和现在这个数。 0是个需要特别注意判的
  

Revision as of 04:31, 8 October 2018

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

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.