首页
D
1027964
当前主题:自动模式
查看保存队列
搜索
社区讨论
不被卡精度的方法
z
zhenzitou
2024/12/26 14:04
P2252
【模板】威佐夫博弈 / [SHOI2002] 取石子游戏
参与者 3
已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
当前回复
2 条
当前快照
1 份
快照标识符
@m54x61zr
此快照首次捕获于
2024/12/26 14:04
去年
此快照最后确认于
2025/11/04 12:20
4 个月前
查看原帖
时光机
更新帖子
复制链接
复制快照链接
复制零楼 Markdown
题目可转化为判断
⌊
(
y
−
x
)
5
+
1
2
⌋
=
x
(
x
≤
y
)
\lfloor(y−x)\frac{\sqrt5+1}2\rfloor=x\ (x\leq y)
⌊(
y
−
x
)
2
5
+
1
⌋
=
x
(
x
≤
y
)
是否成立。(见题解)
然而题解都用的是浮点数,我这么做被卡精度了。此处提供一种可以不被卡精度的方法。
⇔
x
≤
(
y
−
x
)
5
+
1
2
<
x
+
1
\Leftrightarrow x\leq(y−x)\frac{\sqrt5+1}2<x+1
⇔
x
≤
(
y
−
x
)
2
5
+
1
<
x
+
1
令
y
−
x
=
z
≥
0
y-x=z\geq0
y
−
x
=
z
≥
0
⇔
x
≤
z
5
+
1
2
<
x
+
1
\Leftrightarrow x\leq z\frac{\sqrt5+1}2<x+1
⇔
x
≤
z
2
5
+
1
<
x
+
1
⇔
2
x
≤
5
z
+
z
<
2
x
+
2
\Leftrightarrow 2x\leq \sqrt5z+z<2x+2
⇔
2
x
≤
5
z
+
z
<
2
x
+
2
⇔
2
x
−
z
≤
5
z
<
2
x
−
z
+
2
\Leftrightarrow 2x-z\leq \sqrt5z<2x-z+2
⇔
2
x
−
z
≤
5
z
<
2
x
−
z
+
2
若
2
x
−
z
+
2
≤
0
2x-z+2\leq0
2
x
−
z
+
2
≤
0
,显然不成立
否则若
2
x
−
z
<
0
2x-z<0
2
x
−
z
<
0
,
⇔
5
z
2
<
(
2
x
−
z
+
2
)
2
\Leftrightarrow 5z^2<(2x-z+2)^2
⇔
5
z
2
<
(
2
x
−
z
+
2
)
2
否则
⇔
(
2
x
−
z
)
2
≤
5
z
2
<
(
2
x
−
z
+
2
)
2
\Leftrightarrow (2x-z)^2\leq5z^2<(2x-z+2)^2
⇔
(
2
x
−
z
)
2
≤
5
z
2
<
(
2
x
−
z
+
2
)
2
然后就转化为整数运算,不会被卡精度了。
回复
共 2 条回复,欢迎继续交流。
最新优先
最早优先
搜索
正在加载回复...
相关推荐