ITMO Chinese Winter Camp -Day4
ITMO Chinese Winter Camp Day4
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)
题意：给定$n$，求一个$n$位二进制序列的排列，使相邻两项及首尾的二进制序列有至少$\lfloor \frac{n}{2} \rfloor$位不同。
题解：如果设定第$2k+1$项是第$2k+2$项的反码，题目就变成了求一个$n-1$位二进制序列的排列，使得相邻两项及首尾的二进制序列有至少$\lfloor \frac{n}{2} \rfloor-1$位相同。
把二进制序列分为左右两块，枚举左序列，对于每一种左序列，枚举右序列。在上下两个序列的左序列相同时，至少有$\lfloor \frac{n-1}{2} \rfloor$位相同，因此只要满足上下左序列不同时，右序列相同就可以了。
因此，按字典序升序枚举左序列，对于每个左序列，如果最后一位为$1$，右序列按字典序降序枚举，否则按升序枚举。再将每个枚举出的序列的反码紧接着加到序列后，就能满足条件。
Problem E
Solved by Kilo && Weaver_zhu. 04:10:23(+)
题意：一个圆上有n个点，每个点连着2条边，改变点在圆上的位置，求最小的步数使得图形成一个n边形
思路：只有图不连通时无解，考虑将图的结构转化为一个n排列环，则问题转化为移动最少的元素使得将排列环排好序。每次移动元素必定能使得该元素放到自己合适的相对位置（考虑反悔机制），那么剩下的就是求已经在相对合适位置上的元素，求最长上升链和最长下降链。注意要求$2n$次，因为要将环转化为序列
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)
题意：给定排列$\{ p_n \}$，$\{ q_n \}$，构造两个长度为n，取值在$[-n,n]$的整数序列$\{ a_n\} ,\{ b_n\}$，使$a_{p_1} \le a_{p_2} \le \dots \le a_{p_n}, b_{q_1} \le b_{q_2} \le \dots \le b_{q_n}$，且对于所有的$i<j$，满足$a_i+b_j<0$的数对数量为$k$。
题解：令$b_{q_i}=i-1$，剩余未匹配数对为$k$，对于每一个$a_{p_i}$，设为-n可以最多贡献$n-p_i$组数对，设为n可以一组都不贡献，因此在$k>=n-p_i$和$k=0$时都可以$O(1)$得出答案，因此只考虑$0<k<n-p_i$的情况。
在这种情况下，$a_{p_i}$可以和所有$\{ b_n \}$中所有下标大于$p_i$的数产生数对，由于$\{ b_n \}$中的数是各不相同的，因此只要对$\{ b_n \}$中下标大于$p_i$的数排序，取出第$k$个，取反后$-1$就能贡献$k$对数对。
Problem J
Unsolved.
Problem K
Unsolved.