sfiction/2016-P01

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||sfiction||I||AC||0||3||C++ 5.3.0||2323||2016-08-01 22:42:13||
||sfiction||I||WA|| ||  ||C++ 5.3.0||2311||2016-08-01 22:36:32||
||sfiction||I||WA|| ||  ||C++ 5.3.0||2311||2016-08-01 22:23:55||
||sfiction||I||WA|| ||  ||C++ 5.3.0||2311||2016-08-01 22:22:00||
||sfiction||I||WA|| ||  ||C++ 5.3.0||2244||2016-08-01 22:08:26||
||sfiction||I||RE|| ||  ||C++ 5.3.0||2243||2016-08-01 22:07:02||
||sfiction||H||AC||0||23||C++ 5.3.0||1435||2016-08-01 21:40:31||
||sfiction||G||AC||0||3||C++ 5.3.0||425||2016-08-01 21:07:07||
||sfiction||G||WA|| ||  ||C++ 5.3.0||416||2016-08-01 21:01:42||
||sfiction||E||AC||0||3||C++ 5.3.0||388||2016-08-01 20:52:59||
||sfiction||C||AC||0||3||C++ 5.3.0||593||2016-08-01 20:47:46||
||sfiction||B||AC||0||3||C++ 5.3.0||533||2016-08-01 20:42:16||
||sfiction||B||WA|| ||  ||C++ 5.3.0||483||2016-08-01 20:37:58||
||sfiction||B||RE|| ||  ||PYTH3 3.5.1||280||2016-08-01 20:32:34||
||sfiction||B||RE|| ||  ||PYTH3 3.5.1||275||2016-08-01 20:28:08||
||sfiction||D||AC||0||6||C++ 5.3.0||399||2016-08-01 20:07:14||
||sfiction||A||AC||0||9||C++ 5.3.0||258||2016-08-01 19:58:39||

[http://acm.hust.edu.cn/vjudge/contest/125600 比赛链接]

== solution ==

ACGI略去不表。

=== B. Running Steps ===

简单组合数计算。

最大值与C(S/3,S/6)同级别，不会爆longlong。

=== D. Farey Sequence Length ===

法雷序列，易见均为互质对。

=== E. A Rational Sequence ===

pq大小关系决定其位于左子树还是右子树，递归处理比较方便。

=== F. Robots ===

容易证明有解的充分必要条件为任意点对均可合并，可以得到基于BFS的O(n!^3)解法。

=== H. Brocard Point of a Triangle ===

若夹角从小到大变化，先绘出其中两角AB的射线交点Q，再检查ACQ的大小，猜测ACQ大小与BAQ成正比，因此可以二分。

== 补题 ==

 * Unaccepted: F
UserProblemResultMemoryTimeLanguageLengthSubmit Time
sfictionIAC03C++ 5.3.023232016-08-01 22:42:13
sfictionIWA C++ 5.3.023112016-08-01 22:36:32
sfictionIWA C++ 5.3.023112016-08-01 22:23:55
sfictionIWA C++ 5.3.023112016-08-01 22:22:00
sfictionIWA C++ 5.3.022442016-08-01 22:08:26
sfictionIRE C++ 5.3.022432016-08-01 22:07:02
sfictionHAC023C++ 5.3.014352016-08-01 21:40:31
sfictionGAC03C++ 5.3.04252016-08-01 21:07:07
sfictionGWA C++ 5.3.04162016-08-01 21:01:42
sfictionEAC03C++ 5.3.03882016-08-01 20:52:59
sfictionCAC03C++ 5.3.05932016-08-01 20:47:46
sfictionBAC03C++ 5.3.05332016-08-01 20:42:16
sfictionBWA C++ 5.3.04832016-08-01 20:37:58
sfictionBRE PYTH3 3.5.12802016-08-01 20:32:34
sfictionBRE PYTH3 3.5.12752016-08-01 20:28:08
sfictionDAC06C++ 5.3.03992016-08-01 20:07:14
sfictionAAC09C++ 5.3.02582016-08-01 19:58:39

比赛链接

solution

ACGI略去不表。

B. Running Steps

简单组合数计算。

最大值与C(S/3,S/6)同级别，不会爆longlong。

D. Farey Sequence Length

法雷序列，易见均为互质对。

E. A Rational Sequence

pq大小关系决定其位于左子树还是右子树，递归处理比较方便。

F. Robots

容易证明有解的充分必要条件为任意点对均可合并，可以得到基于BFS的O(n!^3)解法。

H. Brocard Point of a Triangle

若夹角从小到大变化，先绘出其中两角AB的射线交点Q，再检查ACQ的大小，猜测ACQ大小与BAQ成正比，因此可以二分。

补题

  • Unaccepted: F