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

From EOJ Wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== One,Two,Three,AK ==
 
== One,Two,Three,AK ==
 +
 +
题解:https://acm.ecnu.edu.cn/blog/entry/253/
  
 
=== Problem A ===
 
=== Problem A ===
  
 
Solved by dreamcloud. 0:24:12(+)
 
Solved by dreamcloud. 0:24:12(+)
 +
 +
题意:总共有 n (奇数)个座位围成一圈,不能有相同性别的人相邻,所以肯定有位置是空着的。每次询问告诉你该位置上的性别。在一定询问次数内确定至少一个空位置。
 +
 +
题解:每次根据原来已知的位置上的性别,询问对面性别,根据奇偶性可以把区间缩小一半。
  
 
=== Problem B ===
 
=== Problem B ===
  
 
Solved by dreamcloud. 3:00:55(+3)
 
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 ===
 
=== Problem C ===
Line 33: Line 45:
 
=== Problem G ===
 
=== Problem G ===
  
Unsolved.
+
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 ===
 
=== Problem H ===
Line 61: Line 91:
 
=== Problem K ===
 
=== Problem K ===
  
Unsolved.
+
Upsolved by dreamcloud.

Latest revision as of 10:25, 31 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

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.