[Div1][Div2]「CodePlus 2018 4 月赛」白金元首与七彩魔法

[Div1][Div2]「CodePlus 2018 4 月赛」白金元首与七彩魔法
给定HSV色盘上的两个点,求联结它们的直线段上亮度最大的颜色,精确到四位小数。
按照给出的公式,RGB值和极坐标的两个分量呈分段线性关系,亮度和RGB值呈线性关系。
将两点的极坐标转为直角坐标,等距离采样,按照公式计算,取最小值即可。
由于色盘上临近颜色的亮度值相近,精度不难得到保证。
关于采样数目的选择,比赛期间当然只要糊一个 10^5 就能过啦,不过这里随意证明一个极其松的上界聊博一笑吧
考虑一个与原点 O 距离为 r 的点 P,以其为端点任作一条不跨越 60\degree 分界线、长度为 d 的线段 PQ。此处 d 很小。
\theta 为线段 OP 与线段 OQ 张成的角,由于 \sin \theta \sim \theta,有 \theta \leq \frac d r
s = \lvert OQ \rvert,显然 \lvert r - s \rvert \leq d
由题目中给出的公式,有
 ......  查看更多

[Div1]「CodePlus 2018 4 月赛」最短路

[Div1]「CodePlus 2018 4 月赛」最短路
n \leq 100000,m \leq 500000的有向图,
两点之间还可以以a xor b的代价从ab,问st的最短路。
先两个点之间不走给定的边,最短路一定是直接ss到tt,
因为一个二进制的差异至少要被算一次。观察st的过程,
可以把这个过程完全等价地变成:一次只改一个二进制位,代价完全不变。
因此xor的边只用连nlog2(n)条,然后就无脑最短路了。 ......  查看更多

[Div2]「CodePlus 2018 4 月赛」喵呜

[Div2]「CodePlus 2018 4 月赛」喵呜
a=b=1
因为每次移动时,小猫的两个坐标奇偶性同时改变,所以不难发现此时小猫能从(x,y)到达(p,q)的条件是|x-p||y-q|的奇偶性相同,只要发现了这个性质,也容易推导出小
猫从(x,y)到达(p,q)的最少步数为min(|x-p|,|y-q|)。这部分数据主要给正解写挂选
b=1
容易知道小猫能够到达的树的编号一定能写作x+ka的形式,所以我们把符合这种形式
的编号的树单独拿出来,就把问题完全转化为了 的情形,用上面相同的方法即可通
过这部分数据。 ......  查看更多

[Div2]「CodePlus 2018 4 月赛」组合数游戏

[Div2]「CodePlus 2018 4 月赛」组合数游戏
看到这个题目x比较大,k比较小直接搞搞就好了呀不是吗
通过对比可以知道

C(x,0)=0 因为任何数选0个只有一种方法

C(x,1)=x x个数选1个有x种方法

利用这个把前面的k-1个都弄成C(x,0),最后一个弄成C(k-x+1,1)就好,这题就水了,然而我OnlineJudge上的Spj好像挂掉了,没办法评测,所以转载Loj评测。 ......  查看更多

「CodePlus 2018 4 月赛」解题报告

比赛题目

[Div2]「CodePlus 2018 4 月赛」组合数游戏 [Div2]「CodePlus 2018 4 月赛」喵呜 [Div1][Div2]「CodePlus 2018 4 月赛」白金元首与七彩魔法 [Div1][Div2]「CodePlus 2018 4 月赛」组合数问题 2 [Div1]「CodePlus 2018 4 月赛」最短路 [Div1]「CodePlus 2018 4 月赛」Tommy 的结合

解题概况

这次我第一次参加Code++的比赛,然后自己傻傻的参加了Div1难度的,平时Codeforces比赛Div1难度没有这么高,所以这次有点蒙吧,这次比赛我做了不是很久,但是我还是想好好的做一下这套题目,一题一题做,好好写题解什么的,毒瘤题就跳过吧。 ......  查看更多