sicily题目分类.docx

Sicily题目分类 【数据结构/图论】1310 Right-Heavy Tree 笛卡尔树相关，复杂度O(N)或O(NlogN)。 1426 Phone List 电话号码前缀检索，trie树相关。 1443 Printer Queue 基本队列操作。 1149 等价表达式 判断表达式是否等价（递归求解） 1136 山海经 n长序列里求m次区间询问的最大连续子区间和。线段树/RMQ 1252 Defining Moment 字符串划分前后缀 1194 Message Flood 单词查找。排序后二分查找 1201 01000001 大整数二进制加法 1381 a * b 高精度乘法 1424 奖金 拓扑排序 1350 Piggy banks 给出每个点出度为1的有向图，求环的个数。（简单） 1423 魔王bug的2色定理 构图求网络的最小割。 1173 Reliable Nets 无向图求最小的二连通子图。（数据小可以搜索） 1192 Guardian of Decency 求最大独立集，比较特殊可以转二分匹配做。 1031 Campus 单源最短路，dijkstra。 1090 Highways 最小生成树。 1034 Forest 森林的定义，求最大宽度与深度。（深度优先遍历） 1114 Food Cubes 广度优先遍历给3维空间图染色。（dfs容易栈溢出） 1132 ROUTES 用括号序列表示树，求两节点最近公共祖先。 1155 Can I Post the letter 判断两点是否可达。（图的遍历） 1141 猴子的争斗 完全图最小生成树的方法数，节点全排列: n!*(n(n-2) 1170 Countdown 建树，统计 1196 Conflict 关系闭包的转换 1210 二叉树 知道前序后序求可能的方法数 1402 Panic Room 构图求网络最大流 1303 Job Assignment 二分图的最大权匹配 1308 Dependencies among Jobs 图的遍历。 【几何】 1175 Swamp Things 平面上N个点，求一条经过最多点的直线。 1234 Playground 半圆圈能否构成封闭圈。平面图，转为判断多边形能否构成 1179 Extrusion 多边形求面积 1045 Space Management 求平面上矩形叠加的总面积，矩形切割或者离散化. 1092 Stars in Your Window 线段树. 1145 校门外的树 离散化或O(n)的扫描 1223 防御力场 求一条过目标点的直线，使得直线一边的点最少 1216 野外行军 光程最短路 1118 War on Weather 球外一点与球切线直接判断范围。 【搜索】 1444 Prime Path 广度优先搜索 1317 Sudoku 数独求解的个数。 1171 The Game of Efil 216 dfs枚举棋盘后检测 1219 新红黑树 砍树博弈，min-max搜索或记忆化搜索 1215 脱离地牢 有限制的迷宫求两人相遇的最小步骤。（广度优先搜索） 1180 Pasting Strings 给10个字符串，求一个排列使得某种权和最大，全排列搜索。 1024 Magic Island 无向图的最长路。（深度优先搜索） 1048 Inverso 广度优先搜索，二进制表示状态判重。 1050 Numbers & Letters 深度优先搜索 1135 飞越原野 最短时间过地图，广度优先搜索. 1107 Simple Puzzle 按题意搜索，有可能有前置零，输出排序. 1150 简单魔板 广度优先搜索，全排列的hash函数设计 1151 魔板 同上。 1152 简单的马周游问题 迷宫问题的可行性剪枝. 1153 马周游问题 同上，扩展状态节点的时候按目标函数值排序。 1378 八数码问题 启发式搜索。 【动态规划/递推/组合计数】 1342 开心的金明 背包dp 1264 Atomic Car Race dp基本题. 1146 采药 01背包 剩余类dp 1355 The Bus 二维的最长上升子序列 1169 ACM(ACronymMaker) 给一些短语求按题意要求构成指定缩写的方法数. 1163 Tour 欧几里德旅行商问题（吴文虎那本书p314） 1233 Necklace Decomposition 按题意分割字母. 1222 单词选择 在给定文章里选出连续的一段包含最多的word且长度最短. 1211 商人的宣传 求两点间L步到达的方法数. 1197 Hotel 字符串含通用符的匹配,记忆化搜索. 1120 Walk Through the Forest 简单无向图,求节点1到节点2的按题意走法的方法数. 1091 Maximum Sum 求分两个部分后的和最大. 1098 Marching in the Corp 给出部分偏序关系,求可能的排名方法数. 1049 Mondriaan 2*1跟1*1的砖铺成2*n的走道的方法数%10. 1121 Tri Tiling 2*1的转铺成3*n的走道的方法数。 1019 Apple Tree 树型dp,边dfs边更新最优值。 1138 寻宝之旅 同上。 1225 电子眼 树+一边的图上求最小边覆盖，树型dp. 1327 Pinary 递推求第k个pinary数。 1404 Hie with the Pie 状态压缩dp 1233 Necklace Decomposition 按题意分割字母. 1221 数字游戏 n个数序列每个数每次会减少bi。取出m个数,求最大值. 1103 The Top-Code 字符串划分dp,要求字典序输出方案时的状态表示方法。 1139 电路稳定性 递归处理括号对序列算电路不通概率. 1108 Online Selection 问答游戏，n层k个回答拿了m分，求最大的回答0的个数. 1123 The Longest Walk 有向图求任意起终点的无重复点的最长路，状态压缩dp 1033 City Road 求0,0走到n+1,m+1的最短路方法数，中间有一些障碍. 1176 Two Ends 二人从两头取数，对方贪心取大的，你尽量使得两者的差大. 1413 Whac-a-Mole 打地鼠游戏，求一定时间内能打到最多地鼠的方案。 1415 Honeycomb Walk 蜜蜂窝走N步回到出发地的方法数。 【二分法】 1137 河床 求一个最长的连续区间满足其中的最小数和最大数之差不大于k。 1411 Pie 二分 【贪心】 1198 Substring 8个串排出最小字典序。（用abf1f3.）统计极点个数 1344 数列 某种规则的数列生成 1433 Optimal Parking 直接算 1259 Sum of Consecutive Prime Numbers 连续素数和 1240 Faulty Odometer 十进制数少了4的计数 1242 Suit Distribution 无聊计数 1239 Smallest Differencev 一些数码，组成差最小的两个数 1231 The Embarrassed Cryptographer 两个素数积，枚举因子 1174 Square Count 数方块数，容斥原理。 1214 信号分析 数列找规律求an=n的个数. 二进制表示时是回文。 1218 纪念邮票 同1209 1209 Sequence Sum Possibilities 求m分解成不同的连续整数和的方法数 1206 Stacking Cylinders 堆圆筒，解方程. 1203 The Cubic End 给一个1,3,7,9结尾的数求一个数的立方的尾部是原数 1199 GCD 求小于N且与N的GCD大于M的数个数. 1190 Reduced ID Number 找最小的数使得给出的所有数mod它的结果不同 1099 Packing Passengers 线性模方程 1119 Factstone Benchmark 求n!=2k的最大n. 两边取对数. 1412 Tour Guide n个物体向各个方向做匀速运动。 1305 Whos Winner 博弈题，找规律。 【模拟/其他】 1323 Switch text 字符串处理。 1122 Prerequisites 模拟统计学生选课。 1046 Plane Spotting 排序。 1097 LED Modding 排序。 1093 Air Express 枚举。 1237 Paint Mix 黑白染料混合出指定灰度的染料。 1202 The Bank of Kalii 日期比较 1187 Laserbox 机器人运动模拟，dfs遍历。 1177 Take Your Vitamins 按要求做一些基本的数据统计。 1182 Context-Free Clock 钟表时间和时针分针之间夹角的关系。 1100 Tennis Anyone 网球排名统计。 1110 ioi photos 模拟.统计 1128 DICE 判断骰子是左手型还是右手型，模拟