Difference between revisions of "ITMO Chinese Winter Camp -Day4"

From EOJ Wiki
Jump to navigation Jump to search
(Blanked the page)
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
= ITMO Chinese Winter Camp Day4 =
 
  
[http://neerc.ifmo.ru/pcms2client/party/links/peking/2019/20190124.pdf Statements]
 
 
[http://neerc.ifmo.ru/pcms2client/party/links/peking/2019/solutions-20190124.zip Solutions]
 
 
[http://neerc.ifmo.ru/pcms2client/party/links/peking/2019/tutorial-20190124.pdf Slides of tutorial]
 
 
== Problem A ==
 
 
Solved by Xiejiadong. 00:19:49(+)
 
 
题意:求$B_1$进制下位数为$D_1$和$B_2$进制下位数为$D_2$的数一共有几个。
 
 
题解:求两个进制下位数为$D$的范围,取个交就好了。但要注意可能会爆long long,用除法来比较就不会出问题了。
 
 
== Problem B ==
 
 
Solved by Kilo. 00:12:01(+1)
 
 
题意:给定两个$n$维的球的球心坐标和半径,求两球交点个数,交点无穷多则输出-1。
 
 
题解:先考虑同心的情况,半径相同则有无穷多的交点,否则没有交点。
 
 
在两个球不同心的情况下,设圆心距离为$dis$,则:
 
 
$dis<abs(r1-r2)$或$dis>r1+r2$:包含或相离,没有交点。
 
 
$dis=abs(r1-r2)$或$dis=r1+r2$:相切,有一个交点。
 
 
$abs(r1-r2<dis<r1+r2$:相交,如果$n=2$则有两个交点,否则有无穷多个交点。
 
 
== Problem C ==
 
 
Solved by Weaver_zhu. 00:10:53(+)
 
 
== Problem D ==
 
 
Solved by Kilo. 00:43:10(+1)
 
 
== Problem E ==
 
 
Solved by Kilo && Weaver_zhu. 04:10:23(+)
 
 
== Problem F ==
 
 
Solved by Xiejiadong. 02:42:20(+3)
 
 
题意:每个物品只有一件,求放到背包里再也装不下东西的方案有多少。
 
 
题解:枚举正好塞不下的物品是哪一件,即剩下不拿的物品里面最小的物品是哪一件。
 
 
这样的话,比这个物品小的,肯定全部要塞下去,剩下比他大的物品,再背一遍0/1背包。
 
 
有个坑点就是,所有的物品都放下了,背包还是没有溢出,按照题意,这算是一种方案。
 
 
== Problem G ==
 
 
Unsolved.
 
 
== Problem H ==
 
 
Upsolved by Xiejiadong. (-8)
 
 
题意:求$i_1,i_2\cdots i_k$满足$1\le i_1<i_2<\cdots <i_k\le n$,且使得$max\{(w_{i_1}+w_{i_2}),(w_{i_2}+w_{i_3}),\cdots ,(w_{i_k}+w_{i_1})\}$最小。
 
 
题解:首先考虑二分答案。
 
 
验证的时候,我们肯定按照原来的位置,从小到大插入,满足现有的相邻和$\le mid$的插入,否则,直接扔掉。
 
 
扔掉的数,我们可以保证插入他是不优的,因为插入他,就相当于用一个比较大的数替换了一个小的数,显然不可行。
 
 
这样的时间复杂度是$O(nlog^2n)$,TLE了。
 
 
我们观察二分答案,其实我们就是在查找插入的时候,两面出现相邻和的max的第$k$大。
 
 
于是,我们直接动态维护插入即可。
 
 
不过动态维护似乎有点难写,在观察一下就能发现,其实就是查询每一个数的两边小于他的数里面离他最近的数是多少,直接RMQ维护就行了。
 
 
对于相等的数,我们可以采用左边可以取到相等的,右边必须严格小于的来区分。
 
 
这样RMQ问题用ST表解决,时间复杂度就就降到了$O(nlogn)$。
 
 
== Problem I ==
 
 
Solved by Kilo. 01:50:23(+2)
 
 
== Problem J ==
 
 
Unsolved.
 
 
== Problem K ==
 
 
Unsolved.
 

Latest revision as of 02:19, 30 January 2019