谈资

Talk

3265B BY S031402628 @ 2019-12-01 19:37:05

题目难度:
eazy:ABC
easy-medium:DE
medium:F
medium-hard:G
hard:H

A. eazy fibonacci

puts(n % 3 == 0 ? "Even"   "Odd");

B. 黑白配  

暴力枚举所有可行的状态,然后一一判定即可。

C. 快乐小马

两种走法分别是(1,2)和(2,1),我们设第一种走法走了x次,第二种走法走了y次,就是一个很简单的二元一次方程求解了。如果找不到正整数解就是无解,否则走法应该是C(x, x+y)。

D. move on circle

容易证明合并方式为某一个人的位置保持不动,两边的人向他靠拢,只要枚举不动的人,再枚举从顺时针方向与逆时针方向靠拢的分界线,分别统计两边的移动步数即可取和最小即可

E. 战术电台

题意为给定两个圆,判断圆的公共部分最远距离点对的距离是多少。

显然,当两个圆相离的时候距离为0;

那么考虑什么时候答案为2*r1(r1为小圆半径)。经过作图易得,当r1,r2和两圆心距离d成直角三角形或者钝角三角形时(r2为最长边),小圆的直径包含在大圆内,答案为2 * r1。

剩下的相交的情况,就通过三角函数计算圆公共部分弦长。大部分人写了海伦公式,也可以夹角公式(cos ∠a = (b * b + c * c - a * a )/ 2 / b /c )求解,方法还是比较多的。

F.  road on tree

dp[i][j]表示从i为根的子树中选一个点到i,用的边数为奇数(j=1)或偶数(j=0)条,所有边中最长的,路径长度是多少。
树形dp的过程中,假设搜索到了x,要给答案更新路径两点的公共祖先为x的情况。
显然只有x的子节点到x,两条偶数长度的边,或者两条奇数长度的边,才能组成偶数长度的路径,从x的儿子dp值中找最大和次大的加起来就好了。
然后同时更新x的dp值。

G. 魔法阵  

暴力枚举左上角坐标(i,j),再枚举右边界k,维护dp[j,k]表示第j列和第k列上的最大的乘积和次大乘积,最后从所有dp[j,k]中选择一个相乘最大的即为答案,时间复杂度为n * (1+m) * m/2。因为计算量不大,所以可以卡过。  

H. special MST

最小生成树的kruskal算法有一个性质,如果边权小于x的边处理完了,那么无论之前具体取了哪些边,并查集的状态都是一致的。
因此这个题存在离线做法,我们先把所有询问处理成(边的编号,询问编号)的二元组形式,按照边权从小到大排序。
由于前面的边选取不会影响到后面,所以每个权值的边对答案的影响是独立的,可以分别判断。
由于是按照权值顺序处理的,对于权值一致的边,我们预先会知道之前的并查集状态。
然后我们试图处理同一权值,同一询问下的所有边,如果在过程中没有出现集合一致的情况,就说明这些边是可以加进最小生成树里的,然后把判断过程的并查集变动撤销(标程使用了栈维护),继续进行下一组边的判断。
同一权值处理完后,我们按照kruskal算法的过程,把并查集状态更新,继续进行下一个权值的判断。
对于一个询问,只要之前的判断都通过了,他就可以是一个最小生成树边集的子集,否则就不行。
Tips:本主题暂无回复。
登录OnlineJudge账号后可以发表和回复Talk~登录OnlineJudge
请点击右方按钮跳转至OnlineJudge登录页面。