Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"YueGuan1234","updateTime":1712143942000,"title":"UIC 4月杂题汇总","dislikeCnt":0,"content":"# 二分查找\u0026二分答案\n\n- [River Hopscotch](https://vjudge.net/problem/OpenJ_NOI-CH0111-10)\n\n来源:OpenJ_NOI - CH0111-10\n\n原因:简单二分,基础题。\n\n- [COCI \u002711 Contest 5 #2 Eko](https://vjudge.net/problem/DMOJ-coci11c5p2)\n\n来源:USACO\n\n原因:简单二分,基础题。\n\n- [K-divisible Sum](https://codeforces.com/problemset/problem/1476/A)\n\n来源:Educational Codeforces Round 103 (Rated for Div. 2)\n\n原因:一道有点经典的题,思想有拓展性。\n\n- [Max Median](https://codeforces.com/problemset/problem/1486/D)\n\n来源:Codeforces Round 703 (Div. 2)\n\n原因:一道略难的题,供大家挑战。与 DP 结合的二分。\n\n- [Game with Multiset](https://codeforces.com/problemset/problem/1913/C)\n\n来源:Educational Codeforces Round 160 (Rated for Div. 2)\n\n原因:一道与贪心结合的二分。难度适中。\n\n- [Wooden Toy Festival](https://codeforces.com/problemset/problem/1840/D)\n\n来源:Codeforces Round 878 (Div. 3)\n\n原因:一道与贪心结合的二分。难度适中。\n\n- [Fear of the Dark ](https://vjudge.net/problem/CodeForces-1886B)\n\n来源:Educational Codeforces Round 156 (Rated for Div. 2)\n\n原因:与几何知识相关的二分题,有创新点。难度适中。\n\n- [To Become Max](https://codeforces.com/problemset/problem/1856/C)\n\n来源:Codeforces Round 890 (Div. 2) supported by Constructor Institute\n\n原因:与数据结构、DP结合的二分题,难度适中。\n\n- [River Hopscotch](https://vjudge.net/problem/POJ-3258#author\u003dGPT_zh)\n\n来源:USACO 2006 December Silver\n\n原因:经典题。还是推荐做。\n\n- [Drying](https://vjudge.net/problem/POJ-3104#author\u003dGPT_zh)\n\n来源:Northeastern Europe 2005, Northern Subregion\n\n原因:经典题。还是推荐做。\n\n- [Garland](https://vjudge.net/problem/POJ-1759)\n\n来源:Northeastern Europe 2000\n\n原因:与数学结合的二分题。难度适中,经典。\n\n- [Cable master](https://vjudge.net/problem/POJ-1064#author\u003dGPT_zh)\n\n来源:Northeastern Europe 2001\n\n原因:经典题。还是推荐做。\n\n- [Blog Photo](https://codeforces.com/problemset/problem/53/B)\n\n来源:Codeforces Beta Round 49 (Div. 2)\n\n原因:难度略高,结合了模拟和二分,有一定思维。\n\n- [Perfect Number](https://codeforces.com/problemset/problem/919/B)\n\n来源:Codeforces Round 460 (Div. 2)\n\n原因:简单的二分;可以 DP\n\n- [Frodo and pillows ](https://codeforces.com/problemset/problem/760/B)\n\n来源:Codeforces Round 393 (Div. 2) (8VC Venture Cup 2017 - Final Round Div. 2 Edition)\n\n原因:结合了贪心的二分。\n\n# 贪心\n\n- [Chip and Ribbon](https://codeforces.com/problemset/problem/1901/B)\n\n来源:Educational Codeforces Round 158 (Rated for Div. 2)\n\n原因:难度略低。一道结合了贪心和数学知识的题目,有创新点。\n\n- [Helmets in Night Light ](https://codeforces.com/problemset/problem/1876/A)\n\n来源:Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)\n\n原因:简单贪心。\n\n- [Tenzing and Books](https://codeforces.com/problemset/problem/1842/B)\n\n来源:CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)\n\n原因:结合了二进制,有创新点。\n\n- [Strong Password](https://codeforces.com/problemset/problem/1845/C)\n\n来源:Educational Codeforces Round 151 (Rated for Div. 2)\n\n原因:考点丰富,做法多样。难度适中。\n\n- [Target Practice](https://codeforces.com/problemset/problem/1873/C)\n\n来源:Codeforces Round 898 (Div. 4)\n\n原因:一道简单题,考察基础。\n\n- [Best Cow Line](https://vjudge.net/problem/POJ-3617#author\u003dGPT_zh)\n\n来源:USACO 2007 November Silver\n\n原因:一道经典题,难度适中。\n\n- [Saruman\u0027s Army](https://vjudge.net/problem/POJ-3069#author\u003dGPT_zh)\n\n来源:Stanford Local 2006\n\n原因:一道经典题,难度适中。\n\n- [Fence Repair](https://vjudge.net/problem/POJ-3253#author\u003dGPT_zh)\n\n来源:USACO 2006 November Gold\n\n原因:一道经典题,难度适中。\n\n- [Even More Odd Photos](https://vjudge.net/problem/USACO-1084#author\u003dGPT_zh)\n\n来源:USACO 2021 January Contest, Bronze\n\n原因:奇偶性也是经常出现的性质。这题与奇偶性结合,考察了一个贪心思想。\n\n- [Hero](https://vjudge.net/problem/HDU-4310#author\u003dGPT_zh)\n\n来源:2012 Multi-University Training Contest 2\n\n原因:这种样式的题目还是不少,来一个简单的。\n\n- [Before an Exam](https://codeforces.com/problemset/problem/4/B)\n\n来源:Codeforces Beta Round 4 (Div. 2 Only)\n\n原因:有一点思维含量,简单题。\n\n- [Lorry](https://codeforces.com/problemset/problem/3/B)\n\n来源:Codeforces Beta Round 3\n\n原因:难一点的排序\n\n- [Dense Subsequence](https://codeforces.com/problemset/problem/724/D)\n\n来源:Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)\n\n原因:与数据结构结合。较难。\n\n- [Dishonest Sellers](https://codeforces.com/problemset/problem/779/C)\n\n来源:Codeforces Round 402 (Div. 2)\n\n原因:与图论算法结合的贪心\n\n- [Tea Party](https://codeforces.com/problemset/problem/808/C)\n\n来源:Educational Codeforces Round 21\n\n原因:与图论算法结合的贪心\n\n# 枚举 \u0026 模拟\n\n- [ISBN Conversion](https://codeforces.com/gym/104757/problem/I)\n\n来源:2023-2024 ICPC East North America Regional Contest (ECNA 2023)\n\n原因:字符串模拟题,出现过在 NOIp 真题中\n\n- [Place for a Selfie](https://codeforces.com/problemset/problem/1805/C)\n\n来源:Codeforces Round 862 (Div.2)\n\n原因:与数学知识结合的模拟题,考察基础数学知识和枚举、模拟能力\n\n- [Mike and Cellphone](https://codeforces.com/problemset/problem/689/A)\n\n来源:Codeforces Round 361 (Div.2)\n\n原因:简单枚举\n\n- [Ski Course Design](https://vjudge.net/problem/Baekjoon-9881#author\u003dGPT_zh)\n\n来源:USACO Jan. 2014 Bronze\n\n原因:模拟,考察一定思维\n\n- [Flip Game](https://vjudge.net/problem/POJ-1753)\n\n来源:Northeastern Europe 2000\n\n原因:枚举经典题,考察一定思维\n\n- [The Pilots Brothers\u0027 refrigerator](https://vjudge.net/problem/POJ-2965#author\u003dGPT_zh)\n\n来源:Northeastern Europe 2004, Western Subregion\n\n原因:枚举经典题,考察一定思维\n\n- [Parencodings](https://vjudge.net/problem/POJ-1068#author\u003dGPT_zh)\n\n来源:Tehran 2001\n\n原因:括号序列相关的模拟,对考察的经典套路有引入作用\n\n- [Crashing Robots](https://vjudge.net/problem/POJ-2632#author\u003dGPT_zh)\n\n来源:Nordic 2005\n\n原因:在棋盘上的模拟,对考察的经典套路有引入作用\n\n- [Robot Motion](https://vjudge.net/problem/POJ-1573#author\u003dnEo2)\n\n来源:Mid-Central USA 1999\n\n原因:在棋盘上的模拟,对考察的经典套路有引入作用\n\n- [Help Me with the Game](https://vjudge.net/problem/POJ-2996#author\u003dGPT_zh)\n\n来源:Mid-Central USA 1999\n\n原因:纯粹的模拟,还带字符串;最近几年热门的模拟都与字符串相关。\n\n- [Cola](https://codeforces.com/problemset/problem/44/B)\n\n来源:School Team Contest 2 (Winter Computer School 2010/11)\n\n原因:有思维的模拟题。难度适中\n\n- [Irrational problem](https://codeforces.com/problemset/problem/68/A)\n\n来源:Codeforces Beta Round 62\n\n原因:简单题,枚举即可。\n\n- [Hidden Word](https://codeforces.com/problemset/problem/725/C)\n\n来源:Canada Cup 2016\n\n原因:结合了构造的枚举,有较高的思维含量。\n\n- [Cubes for Masha](https://codeforces.com/problemset/problem/887/B)\n\n来源:Codeforces Round 444 (Div. 2)\n\n原因:爆搜,但是是枚举的思想。\n\n- [Pizza Separation](https://codeforces.com/problemset/problem/895/A)\n\n来源:Codeforces Round 448 (Div. 2)\n\n原因:有思维含量的枚举\n\n- [[NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)\n - Source: NOI1995\n - 原因: 有一定难度的 dp,需要更多的思维\n - Note: why not greedy?\n\n- [Grouping Increases](https://codeforces.com/problemset/problem/1919/C)\n - 来源: Codeforces\n - 原因: 通过将元素分组以形成递增序列,使用动态规划方法来找出最优的分组策略。\n\n- [[SHOI2002] 滑雪](https://www.luogu.com.cn/problem/P1434)\n - Source: SHOI2002\n - 原因: 基础的二维 dp\n\n- [数字转换 ](https://vjudge.net/problem/LibreOJ-10155)\n 原因:树形dp\n\n- [The Walkway](https://codeforces.com/problemset/problem/1858/B)\n - 来源: Codeforces\n - 原因: 使用动态规划解决行走路径问题,考虑不同路径的成本和限制。\n\n- [Cow Frisbee Team S](https://www.luogu.com.cn/problem/P2946)\n\n - 来源:USACO 2009 March\n - 原因:背包问题\n \n\n- [The more, The Better](https://vjudge.net/problem/HDU-1561)\n - Source: HDU 2006-12 Programming Contest\n - 原因: 树上背包\n\n- [Binary Path](https://codeforces.com/problemset/problem/1937/B)\n - 来源: Codeforces\n - 原因: 通过动态规划处理二进制路径问题,关键在于状态的定义和转移。\n\n- [Shuffling Songs](https://codeforces.com/contest/1950/problem/G)\n - 来源:Codeforces Round 937 (Div. 4) \n - 原因:状压dp \n\n- [Hamiltonian Wall](https://codeforces.com/problemset/problem/1766/C)\n - 来源: Codeforces\n - 原因: 采用动态规划方法解决汉密尔顿墙问题,着重于路径的选择和优化。\n\n \n- [[NOIP2006 提高组] 能量项链](https://www.luogu.com.cn/problem/P1063)\n - Source: NOIP 2006 提高组 第一题\n - 原因: 经典题,对区间的处理有启发性\n\n- [P8703 [蓝桥杯 2019 国 B] 最优包含](https://www.luogu.com.cn/problem/P8703)\n - 来源:蓝桥杯 2019 年国赛 B 组 F 题\n - 原因:字符串相关的dp\n\n- [Journey Planning](https://codeforces.com/problemset/problem/1320/A)\n - 来源: Codeforces\n - 原因: 通过dp优化旅程规划问题,关注于最大化利益和路径选择。\n\n- [P1782 旅行商的背包](https://www.luogu.com.cn/problem/P1782)\n - 原因:考察了背包dp的优化,有难度。\n\n# DP 基础 2\n\n\u003e Notice:\n\u003e\n\u003e 为了锻炼自己(和题目进行拳击),请尽量使用非搜索方法实现的 dp 完成本题单中的题目\n\n- [[NOIP2007 普及组] 守望者的逃离](https://www.luogu.com.cn/problem/P1095)\n - Source: NOIP2007 普及组 T3\n - 原因: 简单的线性 dp,经典\n- [[TJOI2007] 线段](https://www.luogu.com.cn/problem/P3842)\n - Source: TJOI2007\n - 原因: 经典的 dp,分类讨论\n- [[NOIP2006 普及组] 开心的金明](https://www.luogu.com.cn/problem/P1060)\n - Source: NOIP 2006 普及组 第二题\n - 原因: 经典的 01 背包\n\n- [Party at Hali-Bula](https://vjudge.net/problem/UVA-1220#author\u003d0)\n - Source: UVA\n - 原因: 简单的树形DP\n\n- [樱花](https://www.luogu.com.cn/problem/P1833)\n - 原因: 经典的多重背包\n \n- [疯狂的采药](https://www.luogu.com.cn/problem/P1616)\n - 原因: 经典的完全背包\n\n- [Seraphim the Owl](https://codeforces.com/problemset/problem/1945/D)\n - 来源: Codeforces\n - 原因: 使用动态规划解决与移动和收集有关的优化问题,涉及空间和策略考量。\n\n- [[USACO03FALL] Cow Exhibition G](https://www.luogu.com.cn/problem/P2340)\n - Source: USACO03FALL\n - 原因: 经典的 01 背包,一点小细节\n\n- [[NOIP2010 提高组] 乌龟棋](https://www.luogu.com.cn/problem/P1541)\n - Source: NOIP2010 提高组 T2\n - 原因: 基础 dp,主要考察状态设计\n\n- [Did We Get Everything Covered?](https://codeforces.com/problemset/problem/1924/A)\n - 来源: Codeforces\n - 原因: 通过分析集合的覆盖情况,使用基础动态规划技巧来优化决策过程。\n\n- [Block Sequence](https://codeforces.com/problemset/problem/1881/E)\n - 来源: Codeforces\n - 原因: 利用动态规划处理序列分块问题,以最大化特定条件下的序列值。\n\n- [[NOIP2008 提高组] 传纸条](https://www.luogu.com.cn/problem/P1006)\n - Source: NOIP 2008 提高组第三题\n - 原因: 有一定难度的 dp,很好的锻炼思维\n- [Hie with the Pie](https://vjudge.net/problem/POJ-3311#author\u003dGPT_zh)\n\n - 来源:East Central North America 2006\n - 原因: 状压DP\n\n- [Maximum Sum of Products](https://mirror.codeforces.com/problemset/problem/1519/D)\n - Source: Educational Codeforces Round 108 (Rated for Div. 2)\n - 原因: 有启发性\n \n- [Reverse String](https://codeforces.com/problemset/problem/1553/B)\n - 来源: Codeforces\n - 原因: 使用动态规划技术处理字符串反转问题,涉及字符操作和序列分析。\n\n# 图论\n\n- [P2661 信息传递](https://www.luogu.com.cn/problem/P2661)\n - 来源: 洛谷\n - 原因: 通过图的遍历和动态规划技巧寻找最小环,是图论和动态规划结合的经典问题。\n\n- [畅通工程再续](https://vjudge.net/problem/HDU-1875)\n - 来源: 2008浙大研究生复试热身赛(2)——全真模拟\n - 原因: 最小生成树基础\n\n- [P1522 Cow Tours](https://www.luogu.com.cn/problem/P1522)\n - 来源: 洛谷\n - 原因: 结合图的最短路径和动态规划的典型。\n\n- [Rank of Tetris](https://vjudge.net/problem/HDU-1811)\n - 来源: HDOJ 2007 Summer Exercise(2)\n - 原因: 并查集和拓扑排序的结合。略难。\n\n- [一个人的旅行](hhttps://vjudge.net/problem/HDU-2066)\n - 来源: RPG专场练习赛\n - 原因: 基础最短路(多源多汇,可以建立超级源点和终点)\n\n- [P4568 飞行路线](https://www.luogu.com.cn/problem/P4568)\n - 来源: 洛谷\n - 原因: 考虑成本和路径。\n\n- [六度分离](https://vjudge.net/problem/HDU-1869)\n - 来源: 2008杭电集训队选拔赛——热身赛\n - 原因: 传递闭包经典题目。\n\n- [P4047 部落划分](https://www.luogu.com.cn/problem/P4047)\n - 来源: 洛谷\n - 原因: 难一点的最小生成树。\n\n- [Trucking](https://vjudge.net/problem/HDU-2962)\n - 来源: 2008 Rocky Mountain Regional\n - 原因: 二分+最短路(带限制最短路)\n\n- [P4281 紧急集合 / 聚会](https://www.luogu.com.cn/problem/P4281)\n - 来源: 洛谷\n - 原因: 略难,但经典问题。可以选做。\n\n- [P2872 Building Roads](https://www.luogu.com.cn/problem/P2872)\n - 来源: 洛谷\n - 原因: 图的连通性\n\n- [P1991 无线通讯网](https://www.luogu.com.cn/problem/P1991)\n - 来源: 洛谷\n - 原因: 最优化问题。\n\n- [迷宫城堡](https://vjudge.net/problem/HDU-1269)\n - 来源: HDU 2006-4 Programming Contest\n - 原因: 判断是否是一个强连通\n\n- [P2648 赚钱](https://www.luogu.com.cn/problem/P2648)\n - 来源: 洛谷\n - 原因: 虚点建图,建图技巧。\n\n\n- [P1983 车站分级](https://www.luogu.com.cn/problem/P1983)\n - 来源: 洛谷\n - 原因: 动态规划方法解决车站分级问题,涉及到站点之间的相互影响和最优配置。\n\n- [P1038 神经网络](https://www.luogu.com.cn/problem/P1038)\n - 来源: 洛谷\n - 原因: 拓扑排序。题面很高级。\n\n# 搜索1\n\n\n- [滑雪](https://www.luogu.com.cn/problem/P1434)\n\n来源:[SHOI2002]\n\n原因:要一点思考的记搜\n\n- [求细胞数量](https://www.luogu.com.cn/problem/P1451)\n\n来源:[洛谷]\n\n原因:打标记的简单搜索\n\n- [Catch That Cow S](https://www.luogu.com.cn/problem/P1588)\n\n来源:[USACO07OPEN]\n\n原因:简单广搜\n\n\n- [好奇怪的游戏](https://www.luogu.com.cn/problem/P1747)\n\n来源:[洛谷]\n\n原因:简单二维广搜\n\n- [Binary Land](https://www.luogu.com.cn/problem/P3855)\n\n来源:[TJOI2008]\n\n原因:很酷的两个角色的广搜\n\n- [八数码难题](https://www.luogu.com.cn/problem/P1379)\n\n来源:[洛谷]\n\n原因:考验数据存储的广搜,会用stl后难度大幅下降\n\n- [寻找道路](https://www.luogu.com.cn/problem/P2296)\n\n来源:[NOIP2014 提高组]\n\n原因:要思维的搜索题,也可以用最短路算法来做\n\n- [铁盘整理](https://www.luogu.com.cn/problem/P2534)\n\n来源:[AHOI2012]\n\n原因:A*板子题\n\n- [乌龟棋](https://www.luogu.com.cn/problem/P1541)\n\n来源:[NOIP2010 提高组]\n\n原因:好想的记搜题\n\n- [选课](https://www.luogu.com.cn/problem/P2014)\n\n来源:[CTSC1997]\n\n原因:树上跑深搜\n\n- [K皇后](https://www.luogu.com.cn/problem/P2105)\n\n来源:[洛谷]\n\n原因:dfs+剪枝\n\n- [最大食物链计数](https://www.luogu.com.cn/problem/P4017)\n\n来源:[洛谷]\n\n原因:记搜跑DAG或者用拓扑\n\n- [挖地雷](https://www.luogu.com.cn/problem/P2196)\n\n来源:[NOIP1996提高组]\n\n原因:简单搜索\n\n- [小Z的传感器](https://www.luogu.com.cn/problem/P2189)\n\n来源:[洛谷]\n\n原因:并查集+建图+搜索,很酷的一道题\n\n- [普通平衡树](https://www.luogu.com.cn/problem/P3369)\n\n来源:[洛谷]\n\n原因:在权值线段树上跑二分查找也可以算是一种搜索\n\n# 搜索2\n\n- [Two Buttons](https://codeforces.com/problemset/problem/520/B)\n\n- [P1030 求先序排列](https://www.luogu.com.cn/problem/P1030)\n\n- [P1025 数的划分](https://www.luogu.com.cn/problem/P1025)\n\n- [P1037 产生数](https://www.luogu.com.cn/problem/P1037)\n\n- [P2733 家的范围](https://www.luogu.com.cn/problem/P2733)\n\n- [P8673 迷宫与陷阱](https://www.luogu.com.cn/problem/P8673)\n\n- [P3956 棋盘](https://www.luogu.com.cn/problem/P3956)\n\n- [P1632 点的移动](https://www.luogu.com.cn/problem/P1632)\n\n- [P2386 放苹果](https://www.luogu.com.cn/problem/P2386)\n\n- [P3848 跳棋](https://www.luogu.com.cn/problem/P3848)\n\n- [Code For 1](https://codeforces.com/problemset/problem/768/B)\n\n- [P2383 狗哥玩木棒](https://www.luogu.com.cn/problem/P2383)\n\n- [P1021 邮票面值设计](https://www.luogu.com.cn/problem/P1021)\n\n- [P1902 刺杀大使](https://www.luogu.com.cn/problem/P1902)\n\n- [P1126 机器人搬重物](https://www.luogu.com.cn/problem/P1126)","threadId":188498,"likeCnt":0,"createTime":1711979778000,"isWorkbook":false,"viewCnt":102,"openness":2,"fav":false,"id":4801,"trustable":false}