PKU ACM 1852、3684解题报告 | Jorbe's Blog



之所以把这两道题放到一起,是因为这两道题是同一种题型,我把它们叫做"穿越题"。解这种题型的题目,关键是要用穿越的思想。一般这种题目,如果不能想进去的话,会感觉无从下手,可一旦想进去,就会发现题目太简单了。

解1852时,关键是要看出,就算两只蚂蚁相遇各自会朝相反方向移动,但如果我们假设相遇的蚂蚁依然能按照原来的方向移动,即它们穿越了对方的身体,这样问题就简单多了,而且,这样的假设,对最后的答案并没有影响。

同样地,在题3684中,我们也可以假设,两个球相互碰撞时,它们也穿越了对方的球体,依然朝着原来的方向运动,这时,我们就可以忽略其他球,把每个球当做一个个独立的球体,它们之间的运动不受其他球的影响,这样问题也就变得很简单了,而且,这样做并不影响最后的结果,不过最后得再对这些球的位置进行一次排序,因为这些球的相对位置关系是固定的。


Read full article from PKU ACM 1852、3684解题报告 | Jorbe's Blog


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts