ACM题目分类参考模板.docx
《ACM题目分类参考模板.docx》由会员分享，可在线阅读，更多相关《ACM题目分类参考模板.docx（18页珍藏版）》请在冰点文库上搜索。
ACM题目分类参考模板
-----------------------------最优化问题-------------------------------------
----------------------常规动态规划
SOJ1162I-Keyboard
SOJ1685Chopsticks
SOJ1679Gangsters
SOJ2096MaximumSubmatrix
SOJ2111littlekenbg
SOJ2142CowExhibition
SOJ2505TheCountyFair
SOJ2818QQ音速
SOJ2469ExploringPyramids
SOJ1833BaseNumbers
SOJ2009ZerosandOnes
SOJ2032TheLostHouse
SOJ2113数字游戏
SOJ2289Adecorativefence
SOJ2494Appleland
SOJ2440Thedaysinfzk
SOJ2494Appleland
SOJ2515SkiLift
SOJ2718Bookshelf
SOJ2722TreatsfortheCows
SOJ2726DeckofCards
SOJ2729SpaceElevator
SOJ2730LazyCows
SOJ2713CuttheSequence
SOJ2768Bomb
SOJ2779Findthemax（I）（最大M子段和问题）
SOJ2796LetterDeletion
SOJ2800三角形
SOJ2804LongestOrderedSubsequence（II）
SOJ2848RiverHopscotch（二分）
SOJ2849CowRollerCoaster
SOJ2886CowWalk
SOJ2896Alphacode
SOJ2939bailey'strouble
SOJ2994RSI
SOJ3037Paintingtheballs
SOJ3072Computers
SOJ3078windy's"K-Monotonic"
SOJ3084windy'scakeIV
SOJ3104Game（注意大数运算，高精度）
SOJ3110kCoverofLine
SOJ3111kMedianofLine
SOJ3123TelephoneWire
SOJ3142UnfriendlyMultiPermutation
SOJ3213Pebbles
SOJ3219CoverUp
SOJ3263Function
SOJ3264EvilGame
SOJ3339graze2
SOJ3341Ski
SOJ3352TheBaricBovine
SOJ3503BananaBoxes
SOJ3633Matches'sGame
SOJ3636理想的正方形
SOJ3711MountainRoad
SOJ3723RoboticInvasion
nankai1134RelationOrdering
srm150--div1--500
----------------背包问题
SOJ2222HealthPower
SOJ2749TheFewestCoins
SOJ2785BinaryPartitions
SOJ2930积木城堡
SOJ3172Fisherman
SOJ3300StockholmCoins
SOJ3360BuyingHay
SOJ3531NumberPyramids
----------------状态DP
SOJ2089lykoo
SOJ2768Bomb
SOJ2819Ader
SOJ2842TheTSPproblem
SOJ3025Artillery（状态DP）
SOJ3088windy'scakeVIII
SOJ3183Fgjlwj'sboxes
SOJ3259Countingnumbers
SOJ3262SquareFields（二分+状态DP）
SOJ3371MixedUpCows
SOJ3631ShoppingOffers
----------------树状DP
SOJ1870RebuildingRoads
SOJ2136Apple（树形依赖背包n*C算法）
SOJ2514MilkTeamSelect
SOJ2199AppleTree
SOJ3295TreelandExhibition
SOJ3635WorldCup2010
hdoj1561Themore,TheBetter
PKU1655BalancingAct
PKU3107Godfather
PKU3345BribingFIPA
PKU2378TreeCutting
PKU3140ContestantsDivision
PKU3659CellPhoneNetwork
---------------配合数据结构的优化DP
SOJ2702Alanna
SOJ2978Tasks
SOJ3234FindingSeats
SOJ3540股票交易
--------------斜率优化
SOJ3710特别行动队
SOJ3734搬家
SOJ3736LawrenceofArabia
---------------四边形不等式
SOJ1702CuttingSticks
SOJ2775BreakingStrings
---------------最优化之排序
（思考两个元素之间的先后关系，以此得出一个二元比较关系，并验证此关系可传递,反对称，进而排序）
SOJ2509TheMilkQueue
SOJ2547cards
SOJ2850ProtectingtheFlowers
SOJ2957SettingProblems
SOJ3167Computer
SOJ3331Cards（2547加强版）
SOJ3327Dahema'sComputer（通过此题学会排序）
-----------------最优化之必要条件枚举
（思考最优解所具有的性质，得出最优解的一个强必要条件，在此基础上枚举）
SOJ3317FGJ'sPlane
SOJ3429Foodportionsizes
--------------------------------贪心---------------------------------------
SOJ1078BlueEyes'Schedule
SOJ1203Pass-Muraille
SOJ1673GoneFishing
SOJ2574pie
SOJ2645BuyOneGetOneFree
SOJ2701InaCycle
SOJ2876Antimonotonicity（经典模型O（n）算法）
SOJ3343Tower
--------------------------------搜索---------------------------------------
SOJ1106DWeep
SOJ1626square
SOJ20618puzzle
SOJ2485Sudoku
SOJ1045Sticks
SOJ2736Fliptile
SOJ2771CollectingStones
SOJ2715MazeBreak
SOJ2518MagicCowShoes
SOJ2829binarystrings（双向BFS）
SOJ3005Droppingthestones
SOJ3136scu07t01的迷宫（BFS预处理然后枚举交汇点）
SOJ3330Windy'sMatrix（BFS）
--------------------------------DFA----------------------------------------
---------------状态矩阵
SOJ1826NumberSequence
SOJ1936Firepersons
SOJ2552NumberofTilings
SOJ2919MatrixPowerSeries（学习矩阵的快速乘法从此开始）
SOJ2920MagicBean
SOJ3021QuadTiling
SOJ3046OddLovingBakers
SOJ3176E-string
SOJ3246TilingaGridWithDominoes
SOJ3323K-SatisfiedNumbers
SOJ3337Wqb'sWord
----------------DFA+DP
SOJ1112RepeatlessNumbers（DFA+二分）
SOJ2913NumberSubstring
SOJ2826ApocalypseSomeday
SOJ3128windy和水星--水星数学家1
SOJ3182Windynumbers
---------------------------------图论---------------------------------------
--------------------最短路
SOJ1697CashierEmployment
SOJ2325WordTransformation
SOJ2427Daizi'spathsystem
SOJ2468Catcus
SOJ2751Wormholes（SPFA判断负圈回路的存在性）
SOJ2932道路
SOJ3160ClearAndPresentDanger
SOJ3335Windy'sRoute（最短路径的分层图思想）
SOJ3346BestSpot（N^3放心的写）
SOJ3423RevampingTrails
---------------------查分约束
SOJ1687Intervals
---------------------最小生成树
SOJ1169Networking
SOJ2198Highways
SOJ3366WateringHole
SOJ3427Darkroads
---------------------强连通分支
SOJ2832Marscity
---------------------2-SAT
SOJ3535ColorfulDecoration
HDU3062Party
---------------------拓扑排序
SOJ1075BlueEyesandApples（II）
---------------------无向连通图上的割点和割边问题
SOJ1935Electricity
WHU145Railway
---------------------二分图的匹配
------------------最大匹配
SOJ1183GirlsandBoys
SOJ1186Courses
SOJ2035TheTilingProblem
SOJ2077MachineSchedule
SOJ2160OptimalMilking
SOJ2342Rectangles（BelovedSons模型）
SOJ2472GuardianofDecency
SOJ2681平方数2
SOJ2737Asteroids
SOJ2764Link-upGame
SOJ2806LEDDisplay
SOJ2958WeirdFence
SOJ3043MinimumCost
SOJ3038BelovedSons（简单贪心一下）
SOJ3453StockCharts
ZOJ3265StrangeGame
---------------最佳匹配
SOJ1981GoingHome
WHU1451SpecialFish
---------------------最近公共祖先问题
SOJ1187ClosestCommonAncestors
SOJ1677Howfaraway
SOJ3023Network
SOJ3098Bond
---------------------其他
SOJ3013tree
SOJ3056Averagedistance（树上的DFS）
---------------------------------网络流-------------------------------------
---------------------最大流
POJ1273DrainageDitches
POJ1274ThePerfectStall（二分图匹配）
POJ1698Alice'sChance
POJ1459PowerNetwork
POJ2112OptimalMilking（二分）
POJ2455SecretMilkingMachine（二分）
POJ3189SteadyCowAssignment（枚举）
POJ1637Sightseeingtour（混合图欧拉回路）
POJ3498MarchofthePenguins（枚举汇点）
POJ1087APlugforUNIX
POJ1149Pigs（构图题）
ZOJ2760HowManyShortestPath（边不相交最短路的条数）
POJ2391OmbrophobicBovines（必须拆点，否则有BUG）
WHU1124FootballCoach（构图题）
SGU326Perspective（构图题，类似于WHU1124）
UVa563Crimewave
UVa820InternetBandwidth
POJ3281Dining（构图题）
POJ3436ACMComputerFactory
POJ2289Jamie'sContactGroups（二分）
SGU438TheGloriousKarlutkaRiver=）（按时间拆点）
SGU242Student'sMorning（输出一组解）
SGU185Twoshortest（Dijkstra预处理，两次增广，必须用邻接阵实现，否则MLE）
HOJ2816PowerLine
POJ2699TheMaximumNumberofStrongKings（枚举+构图）
ZOJ2332Gems
JOJ2453Candy（构图题）
SOJ2414Leapin'Lizards
SOJ2835PickUpPoints
SOJ3312StockholmKnights
SOJ3353TotalFlow
--------------------最小割
SOJ2662Playground
SOJ3106DualCoreCPU
SOJ3109Spaceflight
SOJ3107Select
SOJ3185Blackandwhite
SOJ3254RainandFgj
SOJ3134windy和水星--水星交通
HOJ2634Howtoearnmore
ZOJ2071TechnologyTrader（找割边）
HNU10940Coconuts
ZOJ2532Internship（找关键割边）
POJ1815Friendship（字典序最小的点割集）
POJ3204Ikki'sStoryI-RoadReconstruction（找关键割边）
POJ3308Paratroopers
POJ3084PanicRoom
POJ3469DualCoreCPU
ZOJ2587UniqueAttack（最小割的唯一性判定）
POJ2125DestroyingTheGraph（找割边）
ZOJ2539EnergyMinimization
ZOJ2930TheWorstSchedule
TJU2944MussyPaper（最大权闭合子图）
POJ1966CableTVNetwork（无向图点连通度）
HDU1565方格取数
（1）（最大点权独立集）
HDU1569方格取数
（2）（最大点权独立集）
HDU3046Pleasantsheepandbigbigwolf
POJ2987Firing（最大权闭合子图）
SPOJ839OptimalMarks（将异或操作转化为对每一位求最小割）
HOJ2811EarthquakeDamage（最小点割集）
2008BeijingRegionalContestProblemADestroyingthebusstations（BFS预处理）（http:
//acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?
p=4322）
ZOJ2676NetworkWars（参数搜索）
POJ3155HardLife（参数搜索）
ZOJ3241BeingaHero
-----------------有上下界
ZOJ2314ReactorCooling（无源汇可行流）
POJ2396Budget（有源汇可行流）
SGU176FlowConstruction（有源汇最小流）
ZOJ3229ShoottheBullet（有源汇最大流）
HDU3157CrazyCircuits（有源汇最小流）
-----------------最小费用流
HOJ2715Matrix3
HOJ2739TheChinesePostmanProblem
POJ2175EvacuationPlan（消一次负圈）
POJ3422Kaka'sMatrixTravels（与Matrix3类似）
POJ2516MinimumCost（按物品种类多次建图）
POJ2195GoingHome
POJ3762TheBonusSalary!
BUAA1032DestroyingaPainting
POJ2400Supervisor,Supervisee（输出所有最小权匹配）
POJ3680Intervals
HOJ2543StoneIV
POJ2135FarmTour
SOJ3186Segments
SOJ2927终极情报网
SOJ3634星际竞速
HDU3376MatrixAgain
-----------------------------------数据结构---------------------------------
-----------------------------------基础数据结构
----------------------栈
SOJ2511Moooo
SOJ3085windy'scakeV（经典栈与单调性的结合）
SOJ3279hm与zx的故事系列2
SOJ3329MaximumSubmatrixII（转化为上面两题的模型）
---------------------双端队列
SOJ2978Tasks
SOJ3139SlidingWindow（双端队列最经典的应用）
SOJ3636理想的正方形
----------------------------------高级数据结构
---------------------线段树
SOJ1862ChoicePears
SOJ2057Themanager'sworry
SOJ2249Mayor'sposters
SOJ2309IntheArmyNow
SOJ2436Picturepuzzlegame
SOJ2556FindthePermutation
SOJ2562TheEndofCorruption
SOJ2719CorraltheCows（线段树+二分）
SOJ2740BalancedLineup
SOJ2745零序列
SOJ2776MatrixSearching
SOJ2808ThermalDeathoftheUniverse
SOJ2822BuyTickets
SOJ2937Tetris
SOJ2938AppleTree（先DFS获得欧拉序列）
SOJ2965capitallyplayers
SOJ2968Matrix（二维线段树）
SOJ3019CountColor
SOJ3022DifferenceIsBeautiful（RMQ+二分经典模型）
SOJ3086windy'scakeVI（二维线段树）
SOJ3099ASimpleProblemwithIntegers
SOJ3248Mousetrap
SOJ3321Windy'sSequenceII
SOJ3370LightSwitching
SOJ3640SpecialSubsequence
---------------------树状数组
SOJ2309IntheArmyNow
---------------------归并排序思想
SOJ2906Ultra-QuickSort
SOJ2431Cowsdistributefood（利用归并排序求逆序数：
nlogn）
SOJ2497Numbersequence
SOJ2559WhatistheRank?
SOJ2728MooFest
SOJ3009StonesforAmy
SOJ3010K-thNumber
SOJ3147K-thnumber
---------------------并查集
SOJ1824TheSuspects
SOJ1953key
SOJ2245UbiquitousReligions
SOJ2389JourneytoTibet
SOJ2438Pet
SOJ2490Mathteacher'stest
POJ2832Howmanypairs?
POJ2821Auto-CalculationMachine
S
升级会员 