ACM國際大學生程序設計競賽

內容概要

　　ACM國際大學生程序設計競賽（ACM-ICPC）是國際上公認的水平最高、規(guī)模最大、影響最深的計算機專業(yè)競賽，目前全球參與人數達20多萬。《ACM國際大學生程序設計競賽（ACM-ICPC）系列叢書：題目與解讀》作者將16年的教練經驗與積累撰寫成本系列叢書，全面、深入而系統(tǒng)地將ACM-ICPC展現給讀者、本系列叢書包括《ACM國際大學生程序設計競賽：知識與入門》、《ACM國際大學生程序設計競賽：算法與實現》、《ACM國際大學生程序設計競賽：題目與解讀》、《ACM國際大學生程序設計競賽：比賽與思考》等4冊，其中《ACM國際大學生程序設計競賽：知識與入門》介紹了ACM-ICPC的知識及其分類、進階與角色、在線評測系統(tǒng)；《ACM國際大學生程序設計競賽：算法與實現》介紹了ACM-ICPC算法分類、實現及索引；《ACM國際大學生程序設計競賽：題目與解讀》為各類算法配備經典例題及題庫，并提供解題思路；《ACM國際大學生程序設計競賽：比賽與思考》介紹了上海交通大學ACM-ICPC的訓練及比賽，包括訓練札記、賽場風云、賽季縱橫、冠軍之路、崢嶸歲月。
　　《ACM國際大學生程序設計競賽（ACM-ICPC）系列叢書：題目與解讀》適用于參加ACM國際大學生程序設計競賽的本科生和研究生，對參加青少年信息學奧林匹克競賽的中學生也很有指導價值。同時，作為程序設計、數據結構、算法等相關課程的拓展與提升，本叢書也是難得的教學輔助讀物。

作者簡介

　　俞勇，1961年生于上海，現為上海交通大學教授、博士生導師。1986年畢業(yè)于華東師范大學計算機科學系，獲碩士學位。畢業(yè)后在上海交通大學任教至今，，1996年至今擔任上海交通大學ACM國際大學生程序設計競賽領隊、主教練，3次率隊奪得ACM國際大學生程序設計競賽世界冠軍，上海交通大學成為該賽事亞洲第一個獲得冠軍、全球第三個“三冠王”的大學，2002、2012年相繼獲得“杰出教練獎”、“功勛教練獎”。
　　俞勇教授曾主編教材或著作4本、譯著3本，先后主持教育部教育教學改革項目2項，獲得國家級和上海市教學成果獎7項，上海市優(yōu)秀教材獎2項，并為國家精品課程“數據結構”、上海市“程序設計類基礎課程教學團隊”主持人、、從事Web搜索與挖掘研究，先后主持國家自然科學基金、863計劃等十余項，發(fā)表重要國際會議和期刊學術論文百余篇，
　　俞勇教授曾獲得國務院特殊津貼、“全國師德標兵”、“寶鋼優(yōu)秀教師特等獎”、“上海市教學名師”、“上海市五一勞動獎章”、“上海市模范教師”、“上海交通大學校長獎”、“上海交通大學最受學生歡迎教師”、“上海交通大學最受研究生歡迎導師”等榮譽。曾被中央電視臺新聞聯播、上海教育臺、光明日報、文匯報等十多家媒體報道。

書籍目錄

第一部分 例題精講
第1章 數學
1.1 概率
Coupons
Generator
1.2 代數
1.2.1 Polya
Arifin Dhaka （First Love Part2）
1.2.2 矩陣
Tower
XX Language
1.2.3 線性方程組
Ars Longa
1.2.4 線性規(guī)劃
Expensive Drink
1.3 組合
1.3.1 基本排列組合
The Unreal Tournament
1.3.2 容斥原理
Jackpot
The Almost Lucky Numbers
1.3.3 生成函數
Vasva's Dad
1.3.4 生成樹計數
Organising the Organisation
1.3.5 綜合
Hero of Our Time
Permutation
1.4博弈
Battle for the Ring
Fool's Game
Points Game
1.5 數論
1.5.1 模線性方程
Integer Sequences
1.5.2 歐幾里得
Wizards
1.5.3 歐拉定理
Strange Limit
1.5.4 歐拉函數
GCD Determinant
1.5.5 平方剩余
Square Root
1.5.6 原根
Fermat's Last Theorem
1.5.7 整除與剩余
Brute-Force Algorithm
Integral Roots
VMan's Problem
1.5.8 中國剩余定理
Voyager 1
1.6 分析
Bridge
第2章 數據結構
2.1 優(yōu)先隊列
The Lazy Programmer
2.2 線性表
Book Pile
2.3 散列表
Censored!
6.1.5 Rabin-Karp
Square Palindrome
6.2 最近公共祖先
The Merchant
Transportation Network
Design the city
6.3 2-SAT
Game with cards
Cipher
6.4 快速傅立葉變換
K-neighbor substrings
第二部分 題庫
4 Values Whose Sum is 0
8G Island
A Binary Apple Tree
A Dinner with
Schwarzenegger! ! !
A Foldy but a Goody
A Game with Colored Balls
A Line Painting
A Secret Book
A Simple Pendulum
Abelian Groups
Aerodynamic
Again Palindrome
Aaainst Mammoths
Air Conditioning
Machinery
All Your Bases Belong to Us
Alphabet
Alternating Sum of Digits
Always an Integer
Ampluplulic Carbon
Molecules
Anansi's Cobweb
Anaent decoration
Angry Teacher
Anniversary Party
Another Chocolate Maniac
Another Minimum
Spamung Tree
Antsll
Ants
Apple or Doughnut
Archipelago
Area 51
Arrays
Art ofWar
Asteroids
Astronomy
Autocompletion
Automaton
B-Station
Balance
Barisal Stadium
Battle
Battle of the Triangle
Battle
Be a Smart Raftsman
Be Wary of Roses
Beloved Sons
Best Cow Line, Gold
Bigger is Better
Binary Lexicographic
Sequence
Bingo
Bishops
Bit Compressor
Bitmap
Black & White
……

章節(jié)摘錄

版權頁：   插圖：   【題意概述】 有N個守衛(wèi)站成一個圈，每個守衛(wèi)需要ai種獎品，兩個相鄰的守衛(wèi)不能有一個獎品相同。求最少需要多少種獎品。 數據范圍：N≤105。 【算法分析】 首先，如果N是偶數的話，顯然答案就是任意兩個相鄰的人ai的和的最大值。 如果N是奇數，我們先二分一個答案M，表示有M種獎品，下面考慮M種獎品是否可行。先把獎品標號為1..M，一個比較顯然的貪心思路： 第一個人首先選取1..A1，剩余的守衛(wèi)按編號從小到大依次取，編號為偶數的守衛(wèi)盡量取不與前一個人造成矛盾的前提下編號小的獎品，編號為奇數的守衛(wèi)盡量選不與前一個人造成矛盾的前提下編號大的獎品。如果當N個人都成功取完，并且第N個人和第1個人的獎品沒沖突，則是一種可行方案。 因此判斷可行性可以做O（N），最后還要乘上二分的復雜度。 【知識點】 二分，貪心 Body Check 賽區(qū)／題庫：ZOJ 3334 難度：★★★☆☆ 【題意概述】 由于流感爆發(fā)，所以醫(yī)院有很多人排隊體檢。醫(yī)院中有m（m≤1000）個醫(yī)生。醫(yī)生只能同時工作，因為如果有人在休息那么工作的醫(yī)生就會覺得不公平。但也可以讓一個醫(yī)生工作，別的醫(yī)生都在監(jiān)視他所以他也不敢偷懶。 現在有n（n≤1000）個病人在排隊體檢，每個人需要不同的時間Ti（Ti≤106）來完成體檢。一個醫(yī)生可以只檢查病人的一部分，然后留給下一個醫(yī)生繼續(xù)。也就是說，一個人可以在任意時間找任意醫(yī)生完成任意部分的檢查，只要滿足：一個人不能同時被兩個醫(yī)生檢查，一個醫(yī)生也不能同時檢查兩個人。 給出醫(yī)生以及病人的人數以及每個病人所需的時間，求完成所有任務的最短時間。 【算法分析】 由于一個人可以在任意時間找任意醫(yī)生完成任意部分的檢查，所以可以將每個人需要的檢查時間均分給每個醫(yī)生。 但是答案并非每個人的時間求和除以醫(yī)生數，因為一個人不能同時被兩個醫(yī)生檢查，所以當有某個病人的時間超過時間求和除以醫(yī)生數時就不能按這樣分配，該病人必然是前一部分時間被均分，后一部分時間讓一個醫(yī)生單獨工作完成檢查。

編輯推薦

《ACM國際大學生程序設計競賽:題目與解讀》適用于參加ACM國際大學生程序設計競賽的本科生和研究生，對參加青少年信息學奧林匹克競賽的中學生也很有指導價值。同時，作為程序設計、數據結構、算法等相關課程的拓展與提升，本叢書也是難得的教學輔助讀物。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    ACM國際大學生程序設計競賽 PDF格式下載

---