Typical Topic Sets (CSP-S ~ Provincial Team Selection)
Some topics / knowledge that are too basic will not be added
This problem set has some good problems corresponding to the knowledge, and you can add a sentence on this topic to give a brief description of the practice as appropriate. Since I haven't solved all the problems, if someone can provide it, please contact gsczl71 on Codeforces
If you want to add some better problems for some knowledge, you can contact me and add them. A '*' will be added in front of the problem number.
Improvement
2.3.1.4 Priority queues
- P6033 [NOIP2004 Improvement Group] Merging Fruit Enhancement
- P2827 [NOIP2016 Improvement Group] Earthworms
P3045 [USACO12FEB] Cow Coupons G
2.3.1.5 Sparse Table
- P2048 [NOI2010] Super Piano
- P8818 [CSP-S 2022] Strategy Game
P2880 [USACO07JAN] Balanced Lineup G
2.3.2.1 Disjoint Set Union
- P5937 [CEOI1999] Parity Game
- P2024 [NOI2001] Food Chain
- P1196 [NOI2002] Legend of the Galactic Heroes
- P1525 [NOIP2010 Improvement Group] Locking Up Criminals
- P1955 [NOI2015] Automated Program Analysis
- P4185 [USACO18JAN] MooTube G
P2661 [NOIP2015 Improvement Group] Messaging
2.3.3.2 Fenwick Tree
- P1966 [NOIP2013 Raising Group] Match Queuing
- P3960 [NOIP2017 raise group] Queue
- P1712 [NOI2016] Districts
- P2880 [USACO07JAN] Balanced Lineup G
P3605 [USACO17JAN] Promotion Counting P
2.3.3.3 Segment Tree
- P4560 [IOI2014] Wall Brick Wall
- P5874 [IOI2015] horses
- P3960 [NOIP2017 Raise Group] Queue
- P8868 [NOIP2022] Competition
- P2894 [USACO08FEB] Hotel G
P8518 [IOI2021] Splitting Candy
2.3.3.4 Trie
- P4683 [IOI2008] Type Printer
- P2922 [USACO08DEC] Secret Message G
2.3.3.6 Balanced Trees (AVL Treap Splay)
- P4008 [NOI2003] Text Editor
- P1486 [NOI2004] Depressed Cashier
- P2042 [NOI2005] Maintaining the array
- P3960 [NOIP2017 Improvement Group] Queuing
2.3.5.2 String hash function construction
P3823 [NOI2017] Earthworm queue
2.4.5 Strings (kmp)
- P2375 [NOI2014] Zoo
- P4156 [WC2016] Argumentative Bundle of Bamboo Poles
- P3426 [POI2005] SZA-Template
- P3435 [POI2006] OKR-Periods of Words
- P4391 [BOI2009] Radio Transmission Wireless Transmission
P3121 [USACO15FEB] Censoring G
2.4.6 Search Algorithms (Pruning Notation Search A* Bidirectional BFS IDA*)
- P1731 [NOI1999] Birthday Cake
- P1535 [USACO08MAR] Cow Travelling S
- P5195 [USACO05DEC] Knights of Ni S
- P3067 [USACO12OPEN] Balanced Cow Subsets G
P4799 [CEOI2015 Day2] World Ice Hockey Championship
2.4.7.1 Minimal Spanning Trees
- P1967 [NOIP2013 Improvement Group] Truck Transportation
- P2872 [USACO07DEC] Building Roads S
- P4768 [NOI2018] Homestretching
P4899 [IOI2018] werewolf werewolf
2.4.7.3 Single Source Shortest Path
- P1073 [NOIP2009 Improvement Group] Optimal Trade
- P2296 [NOIP2014 Raise Group] Finding the Road
- P3953 [NOIP2017 Improvement Group] Strolling in the Park
- P1948 [USACO08JAN] Telephone Lines S
P3008 [USACO11JAN] Roads and Planes G
2.4.7.5 Floyd
- P2047 [NOI2007] Social Networking
- P1522 [USACO2.4] Cow Tours
P2886 [USACO07NOV] Cow Relays G
2.4.7.6 Directed graph topology
- P1038 [NOIP2003 Improvement Group] Neural Networks
- P1983 [NOIP2013 Popularization Group] Station Classification
- P7113 [NOIP2020] Drainage
2.4.7.7 Euler Paths & Euler Circuits
- P6066 [USACO05JAN] Watchcow S
2.4.7.8 Bipartite graph determination
- P1155 [NOIP2008 Improvement Group] Dual Stack Sorting
P1525 [NOIP2010 Improvement Group] Locking Up Criminals
2.4.7.9 Strongly connected components
- P1073 [NOIP2009 Improvement Group] Optimal Trade
- P2661 [NOIP2015 Improvement Group] Messaging
- P2863 [USACO06JAN] The Cow Prom S
P2921 [USACO08DEC] Trick or Treat on the Farm G
2.4.7.10 Cut Vertices & Bridges
- P3469 [POI2008] BLO-Blockade
P2860 [USACO06JAN] Redundant Paths G
2.4.7.11 Centroid, Diameter, DFS Sequence, Eulerian Sequence of Tree
- P4408 [NOI2003] Truant Kids
- P1099 [NOIP2007 Improvement Group] Kernel of a Tree Network
- P3629 [APIO2010] Patrol
- P1232 [NOI2013] Tree Counting
P5666 [CSP-S2019] Center of Gravity of Tree
Tree differencing, subtree sums, multiplication
- P2680 [NOIP2015 Improvement Group] Transportation Plan
- P1600 [NOIP2016 Improvement Group] Everyday Running
- P4775 [NOI2018] Intelligence Center
- P8820 [CSP-S 2022] Data Transfer
- P2052 [NOI2011] Road Construction
- P1084 [NOIP2012 Improvement Group] Outbreak Control
P5024 [NOIP2018 Raising Group] Defending the Kingdom
2.4.7.13 Lowest Common Ancestors
- P1600 [NOIP2016 Improvement Group] Everyday Running
2.4.8.1 Tree DPs
- P2014 [CTSC1997] Course Selection
- P1040 [NOIP2003 Improvement Group] Additive Binary Trees
- P5658 [CSP-S2019] Bracketed Trees
- P8867 [NOIP2022] Building Barracks
- P4395 [BOI2003] Gem Hovercraft
- P3354 [IOI2005] Riv River
- P3047 [USACO12FEB] Nearby Cows G
- P3554 [POI2013] LUK-Triumphal arch
- P3647 [APIO2014] Lian-Chu line
2.4.8.2 Bitmasks DP
- P2704 [NOI2001] artillery position
- P2831 [NOIP2016 Improvement Group] Angry Birds
- P3959 [NOIP2017 Raise Group] Treasure
- P2150 [NOI2015] Sushi Dinner
- P1879 [USACO06NOV] Corn Fields G
P3092 [USACO13NOV] No Change G
2.4.8.3 (Rolling Arrays, Monotonic Queues) Optimizing DPs
- P1081 [NOIP2012 Improvement Group] Drive-Thru
- P1973 [NOI2011] NOI Carnival
- P1398 [NOI2013] Calligraphy
- P3957 [NOIP2017 POP] Hopscotch
- P5017 [NOIP2018 POPULAR] The Ferry
- P5664 [CSP-S2019] Emiya's Family Meal Today
- P5665 [CSP-S2019] Zoning
- P4954 [USACO09OPEN] Tower of Hay G
- P4544 [USACO10NOV] Buying Feed G
- P3089 [USACO13NOV] Pogo-Cow S
- P3522 [POI2011] TEM-Temperature
- P3572 [POI2014] PTA-Little Bird
P6764 [APIO2020] Paint the Walls
2.5.2.7 Exgcd
- P3951 [NOIP2017 Improvement Group] Kai's Doubt / [Blue Bridge Cup 2013 Province] The Number You Can't Buy
- P1082 [NOIP2012提高组] Congregate equations
P4774 [NOI2018] Dragon Slayers
2.5.3.8 Admissibility
2.5.3.9 Cartesian numbers
P1044 [NOIP2003 Universal Group] Stack
2.5.4.4 Matrix operations
- P2020 [NOI2011] Rabbit Farmer
- P2044 [NOI2012] Random Number Generator
- P1224 [NOI2013] Vector inner product
- P1397 [NOI2013] Matrix Games
NOI Part
3.2.1 Linear Structures (Block List)
3.2.3.1 HLD
- P2146 [NOI2015] Package Manager
P7735 [NOI2021] Light and light edges
3.2.3.2 Link Cut Tree
- P4172 [WC2006] Chief Plumber
- P2387 [NOI2014] Enchanted Forest
P7735 [NOI2021] Light and Light Sides
3.2.3.3 2D Segment Tree
P2086 [NOI2012] Magic Chessboard
3.2.3.4 Tree in tree
3.2.3.5 K-D Tree
3.2.3.6 Virtual trees
3.2.4.1 Leftist Tree
- P4331 [BalticOI 2004] Sequence Digital Sequence
3.2.5.1 Persistent Segment Tree
3.3.1.1 Decomposition
3.3.1.2 Offline Algorithms
3.3.1.3 Complex Divide Algorithms
- AT_joisc2014_i かかし
- P4390 [BalkanOI2007] Mokia Mokia
- P4292 [WC2010] Rebuild Program
- P4149 [IOI2011] Race
- P5306 [COCI2018-2019#5] Transport
- P4183 [USACO18JAN] Cow at Large P
3.3.1.5 Constructive Algorithms
- P7115 [NOIP2020] Ball shifting game
- P8866 [NOIP2022] Meow Meow Meow
- P5884 [IOI2014] game game
- p6169 [ioi2016] molecules
- P3839 [IOI2017] The Big Prize
- P5811 [IOI2019] Dividing Attractions
P6830 [IOI2020] Connecting the Optimist Tree
3.3.2.2 ExKMP
P7114 [NOIP2020] String Matching
3.3.2.4 AC Automaton
- P2444 [POI2000] Virus
- P2414 [NOI2011] Beaver's Typewriter
- P3121 [USACO15FEB] Censoring G
P3041 [USACO12JAN] Video Game G
3.3.2.5 Suffix arrays
- P2178 [NOI2015] Wine Tasting Conference
- P1117 [NOI2016] Excellent split
- P4770 [NOI2018] Your Name
P2852 [USACO06DEC] Milk Patterns G
3.3.2.6 Suffix Trees
P2178 [NOI2015] Wine Tasting Conference
3.3.2.7 Suffix Automaton
- P3649 [APIO2014] Palindrome String
3.3.3.1 Pseudo Tree
- P4381 [IOI2008] Island
- P2081 [NOI2012] Lost Amusement Park
- P1399 [NOI2013] Fast Food Restaurant
P3533 [POI2012] RAN-Rendezvous
3.3.3.3 2-SAT
- P3825 [NOI2017] Games
P3513 [POI2011] KON-Conspiracy
3.3.3.4 Flows
- P2754 [CTSC1999] Homestead / Star Shift Issues
- P3980 [NOI2008] Volunteer Recruitment
- P2805 [NOI2009] Zombies
3.3.3.6 Hungarian algorithm
- P1963 [NOI2009] Sequence of Transformations
- P1971 [NOI2011] Rabbit and Egg Game
- P6062 [USACO05JAN] Muddy Fields G
- P7368 [USACO05NOV] Asteroids G
- P2857 [USACO06FEB] Steady Cow Assignment G
- P3033 [USACO11NOV] Cow Steeplechase G
P4617 [COCI2017-2018#5] Planinarenje
3.3.3.8 General graph matching
P4258 [WC2016] Challenging NPCs
3.3.4 Construction/optimization of complex dynamic programming models
- P1933 [NOI2010] Traveling Routes
- P5024 [NOIP2018 Improvement Group] Defending the Kingdom
- P6775 [NOI2020] Making Dishes
- P8497 [NOI2022] Removing Stones
- P7302 [NOI1998] Free Pie
- P4767 [IOI2000] Post Office
- P6246 [IOI2000] Post Office Enhanced
- P4027 [NOI2007] Currency Exchange
- P1912 [NOI2009] Poet Little G
- P2305 [NOI2014] Ticket Purchase
- P1721 [NOI2016] The King Drinks
- P5468 [NOI2019] Route Home
- P6302 [NOI2019] Route Home Enhanced Edition
- P6773 [NOI2020] Destiny
- P3628 [APIO2010] Special Ops
- P3642 [APIO2016] Fireworks Display
- P5892 [IOI2014] holiday Vacation
3.4.2.4 Möbius Inversion
- P1447 [NOI2010] energy harvesting
3.4.5.2 Expectation and Variance of Random Variables
- P4206 [NOI2005] Satoshi and Coco
- P2081 [NOI2012] Lost Amusement Park
- P1850 [NOIP2016 Improvement Group] Changing Classrooms
3.4.7 Optimization
P3980 [NOI2008] Volunteer Recruitment
3.4.8 Computational Geometry
- P7529 [USACO21OPEN] Permutation G
- P3827 [NOI2017] Splitting
- P4293 [WC2010] Energy Field
- P5403 [CTS2019] Field
- P1452 [Template] Spinning Jam | [USACO03FALL] Beauty Contest G
- P8101 [USACO22JAN] Multiple Choice Test P
P5696 [CTSC1998] Surveillance Camera
3.4.10.3 Concept of Communication Complexity
- P8491 [IOI2022] Prisoner Challenge
- P8494 [IOI2022] The Rarest Insect
thanks!
bro this is codeforces. Why are you providing problem links to luogu? Maybe you can post this on luogu blog rather than cf.
is it : luogu blog only usable for china nor worldwise
The bill of lading I put together comes from questions in a book called the NOI Dictionary, which is a compilation of past tournament questions from NOI , IOI, USACO and others. The questions are not available on CF, so I quoted the luogu link and put it on CF in order for more people to see it.
Thanks!
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
Do you (or anyone else) have a top 5 favorites from NOI? Particularly what are the "must do" or most historically significant if you've done many questions from other olympiad but minimal NOI.
I think you'd better improve your English before posting this article, because you called a segment tree "line tree".
Pseudo Tree -> Based Ring Tree
Flow -> Streaming
Catalan numbers -> Cartesian numbers
Lowest Common Ancestor -> Recent Public Ancestors
English is not my mother tongue, and I can't imagine how difficult it'll be for people from other countries to understand your article.
Thanks, I'll go make some changes now
There are still many issues.
The ones on the left are incorrect, and the ones on the right are correct.
The feeling of reading these stiff words is very terrible. I hope I can also help more people.
And I suggest you standardize the use of capitalization when writing titles / names of tasks.
My English isn't good either, but I think since you want to help others, try to do it as seriously as possible.
Update:
Typical Topic Sets (CSP-S ~ Provincial Team Selection)
Some topics / knowledge that are too basic will not be added.
This problem set has some good problems corresponding to the knowledge, and you can add a sentence on this topic to give a brief description of the practice as appropriate. Since I haven't solved all the problems, if someone can provide it, please contact gsczl71 on Codeforces.
If you want to add some better problems for some knowledge, you can contact me and add them. A '*' will be added in front of the problem number.
thanks
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
This is AMAZING! Thank you!
Errr.. What are Complex Divide Algorithms? I guess they're Divide&Conquer?
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
1
Auto comment: topic has been updated by gsczl71 (previous revision, new revision, compare).
Thank you for this useful list.
Does Luogu have problems in English? Even after using a translator, some problem statements are very hard to understand.
may be in the future，Luogu will have English.But these problems are Chinese contest problem，so there always don not have English.But some problem like IOI，you can find the English problem on the internet.Iknow a translator call deepL，it is very good.
Why did you delete the blog about Chunking and Mo's Algorithm and the one about Flows? They are very helpful.