ITMO Chinese Winter Camp -Day4

ITMO Chinese Winter Camp Day4

Statements

Solutions

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.