【题解】2019西北工业大学程序设计创新实践基地春季选拔赛

A. Chino with Geometry
签到题+喜闻乐见的乱搞题。。。因为都是整点，所以答案都是整数。。。
算法一
联立直线和圆的方程，得到D,E的坐标，然后根据距离公式强算。窝也没有写过，布吉岛会不会爆精度。不过比较难写就对了。
算法二
过圆心作AH⊥BC，则答案就是(√(AB^2-AH^2 )-√(r^2-AH^2 ))×(√(AB^2-AH^2 )+√(r^2-AH^2 )).似乎精度爆炸……
算法三
化简上述式子可以得到答案等于AB^2-r^2，于是我们得到了：割线长的乘积等于切线长的平方。看似很有道理，你也恍然大悟，然而这是初中平面几何里我们都学过的“切割线定理”。

B. Chino with Repeater
签到题。。。
算法一
问题其实等价于求最少的复制粘贴数使得行数大于等于n，每次复制粘贴最多的就行了，贪心策略显然。
算法二
上述贪心策略等价于⌈〖"log" 〗_2 n⌉，有很多写法，正确的有：
cout << (int)(ceil(log2(1.0 * n)));
cout << (int)(ceil(log10(1.0 * n) / log10(2.0)));
错误的有使用了log函数，原因未知。

C. Chino with Queue
首先考虑暴力，我们可以枚举这个队列的顺序并且进行计算，时间复杂度是O(n!⋅n)的。接下来考虑用动态规划去优化这个问题（出题人太菜了没想到更好的方法），我们令f_(i,S)表示现在正在排第i个人，并且状态是S的最大舒适度，其中S是一个bitset（在这里可以看成是一个(unsigned) long long），第i-1位为1表示这个人已经在队伍中了。那么一次排队其实就转化成了一个不用回到起点的 TSP问题（一个经典的NPC难题，dp入门题了）。状态转移方程如下：
f_(i,S+{i})="max"{f_(j,S)+W_(i,j) |i∉S,j∈S}
注意到每个人排在第一个的状态是不一样的，我们需要枚举起点op，边界条件就是f_(i,0)=W_(i,op)，最终的答案就是"max"{W_(op,op)+f_(i,{0,1,…,n-1}) |i=1,2,…,n}，时间复杂度是O(n^3×2^n).可以加一个起点然后把问题变成一个O(n^2×2^n)的标准的TSP问题.

D. Chino with Equation
组合数学里“插板法”的简单运用。。。
题目可以抽象成下面两个问题：
1、把n个相同的球放进m个盒子里，不允许盒子为空，有几种方法？
2、把n个相同的球放进m个盒子里，且允许盒子为空，有几种方法？
对于第一个问题，我们可以看成在n个球中***n-1块隔板，从这n-1块隔板里取出m-1块即可，答案是((n-1)¦(m-1)).对于第二个问题，我们只需要再插入m块隔板，然后从里面选m-1块即可，答案是((n+m-1)¦(m-1)).
放到这个题里就是把n拆成n个“1”，然后把这些“1”放到变量里。考虑到数据比较大，应该求一下乘法逆元。

E. Chino with Triangle
这是我认为的中档题。。。
算法一
枚举三个点，算出距离，然后判断一下。
诶怎么求距离啊？？？我好像不知道诶？？？dfs一下？时间复杂度O(n^4).
算法二
我好想知道有一个叫做 “Least/Lowest Common Ancestor”的东西，距离公式是depth_u+depth_v-2⋅depth_(lca_(u,v) )诶！快来试一试吧！等一下，怎么求LCA？暴力一下吧！时间复杂度O(n^4).
算法三
哇我好像会倍增/树链剖分求LCA！赶紧用起来吧！时间复杂度O(n^3 "log" n).
算法四
对于一棵无权树，只要取出来的三个点不在同一条链上就是可以构成三角形的。
考虑到直接求答案比较困难，我们可以求答案的补集。每条链对答案的贡献是去掉端点以后剩下的结点数量，也就是说每个点对答案的贡献就是经过它但是不以它为端点的路径的条数。
我们考虑三个点u,v,w，假设u是v的父亲结点，那么可以分成下面两种情况：
1、w也是u的儿子结点
2、w不是u的儿子结点
具体地说，根据乘法原理和加法原理，答案分成两部分统计：
f_u=size_v×(size_u-size_v-1)/2+size_v×(n-size_u)
前一半表示第一种情况，v和每一个w计算一次之后因为计算到w的时候还会被重复计算一次，因此要除以二；后面一半表示后一种情况，不会出现重复，因此v可以直接和每个w计算一次。其中size_u表示以u为根结点的子树的大小（包括u），直接dfs即可统计。整个公式也可以在dfs的时候顺便统计出来，这个是自下而上更新的信息。
总的选法是(n¦3).

F. Chino with Expectation
签到题。。。
由于选择是完全随机的，因此每个数都会有1/n的概率被选中，考虑用长度表示概率，那么可以得到：

事件选择的数落在区间内选择的数落在区间外
概率 (r-l+1)/n 1-(r-l+1)/n
而对于第一种情况，答案就是(x_i+∑(j=l_i)^(r_i)▒a_j )/(r_i-l_i+1)，对于后一种情况，答案就是(∑(j=l_i)^(r_i)▒a_j )/(r_i-l_i+1)，根据期望的定义计算即可，考虑到范围很大，用前缀和加速一下即可。

G. Chino with Train to the Rabbit Town
题目可以抽象成是把一组数分成若干个不相交的区间使得最多的区间异或和是k，考虑动态规划。
令g_i表示划分到某个以i结尾的区间时包含的的异或和为k的区间个数最大值，f_i表示1…i的答案，那么可以得到这么一个方程：
g_i="max"{f_j+1|a_(j+1)⊕⋯⊕a_i=k}
然后f_i="max"{g_i,f_(i-1)}.其中，j以降序枚举，时间复杂度是O(n^2)的。然后我们考虑优化。首先为了快速得到一段区间的异或和，我们可以考虑异或前缀和一下，然后考虑sum_i⊕k，如果我们能在之前找到这个数，并且它在此之前最后一次出现的位置是p，那么(p,i]这一段的异或和就是k.于是我们开个桶维护一下最后一次出现的位置就可以了，用map应该也不会怎么样？？？我隐藏了k的取值范围（逃，并把它作为考点之一。事实上考虑到〖10〗^5<2^17，因此k∈[0,2^17-1].当然考虑到3×〖10〗^5>2^17-1，因此直接把桶的范围开到3×〖10〗^5也是可以的，当然题目并没有卡各位的空间复杂度。

H. Chino with Ciste
考虑到deque可以在首尾插入元素，因此我们把0边放在队首，1边放在队尾，每次出队扩展的时候进行松弛操作（也就是更新答案并且入队），对于01网格图，这种特殊的bfs顺序类似于堆的操作。可以参考 OI-Wiki - bfs的有关内容。
有关deque，可以看 C++ Reference - deque.

I. Chino with Rewrite
算法一（假）
我们每次维护一个桶记录颜色，每次从两个点逐级上提到LCA，然后统计有多少颜色即可，时间复杂度是O(60⋅qn)的。
颜色表示
首先有一个必须想到的地方就是颜色不超过60种的话我们可以用一个(unsigned) long long来保存一个集合，第i位为1就说明有这种颜色。这样两个集合之间的∪操作就是按位或。
离线做法
保存所有的操作，顺序枚举操作，利用操作一把最终的树建出来，利用并查集判断连通性给无效的操作打上标记。接下来考虑到需要在树上维护区间信息，因此树链剖分+线段树就是不二的选择，首先对这棵树进行树链剖分，线段树的每个点就是上述的一个(unsigned) long long，这样操作一相当于单点修改，操作二相当于区间查询。得到结果以后数二进制有几个1即可。
在线做法
其实出题人并没有想到在线做法，不过考虑到操作二的特殊性可以用一种被称为Link-Cut Tree的数据结构直接做掉，同样是每个点往上维护一个(unsigned) long long，然后每次询问先把x变成根，把x→y变成preferred path（即access(y)），然后把y splay到根，就可以完成信息的维护了。常数略大。

【题解】2019西北工业大学程序设计创新实践基地春季选拔赛

全站热榜