下载文档原格式
交集差集并集补集效率
交集、差集、并集和补集的计算效率取决于使用的算法和数据结构。
交集的计算效率通常是最高的，可以使用哈希表或排序算法来实现。
对于两个集合的交集，可以将其中一个集合存储到哈希表中，然后遍历另一个集合，在哈希表中进行查找，时间复杂度为O(n)，其中n为集合的大小。
差集的计算效率也可以通过哈希表或排序算法来实现。
对于A 和B两个集合的差集A-B，可以将A存储到哈希表中，然后
遍历B，在哈希表中删除与B中元素相同的元素，得到差集。
时间复杂度为O(n+m)，其中n为集合A的大小，m为集合B
的大小。
并集的计算效率也可以通过哈希表或排序算法来实现。
对于A 和B两个集合的并集A∪B，可以将A和B存储到哈希表中，然后将哈希表中的元素输出即可。
时间复杂度为O(n+m)，其
中n为集合A的大小，m为集合B的大小。
补集的计算效率也可以通过哈希表或排序算法来实现。
对于A 集合的补集A^c，可以将A和全集U存储到哈希表中，然后
遍历哈希表，将不在A中的元素输出即可。
时间复杂度为
O(n)，其中n为集合A的大小。
总的来说，交集、差集、并集和补集的计算效率取决于集合的
大小和使用的算法和数据结构。
通常情况下，使用哈希表来实现这些操作的效率会比较高。
洛⾕专题-并查集P1196 [NOI2002]银河英雄传说(带权并查集)题意：有n艘舰依次排序，每次将i及其⾝后的舰艇合并⾄j及其所有舰艇之后，每次询问i到j舰艇之间的距离，如果不在⼀列输出-1思路：单纯的合并与查询是否在⼀列操作⽐较简单，难的在于查询距离⾸先我们需要三个数组fa[i],sum[i],dis[i]分别为i的⽗亲，i列所有的舰艇数，与其到其⽗亲的距离可能有⼈会想i到其⽗亲的距离不都是1嘛，其实在路径压缩过程中，⽗亲会与实际的情况不符，虽然直接相连但是可能距离并不为1现在考虑合并(i,j)操作，每次合并操作只要对第⼀艘舰艇进⾏修改就好了，分别修改dis数组的修改直接等于sum[j]，之后将sum[j]+=sum[i]，并将sum[i]=0在每次查询时都会进⾏路径压缩，因此dis[k](k为排在i之后的舰艇)虽然在合并时没有修改，但是会在路径压缩(查询⽗亲)时修改成到该列第⼀艘舰艇的距离之后在利⽤前缀后的思想，(dis[i]-dis[j])-1即为连个舰艇之间的舰艇数了#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const int maxn=3e4+10;int fa[maxn],sum[maxn],dis[maxn];int find(int x){if(fa[x]==x) return x;int f1=fa[x],f2=find(fa[x]);dis[x]+=dis[f1];fa[x]=f2;return f2;}void uni(int x,int y){int f1=find(x),f2=find(y);fa[f2]=f1;dis[f2]=sum[f1];sum[f1]+=sum[f2];sum[f2]=0;}int main(){int t,i,j;char op;scanf("%d",&t);for(int i=1;i<=maxn;i++){fa[i]=i;sum[i]=1;}while(t--){cin>>op>>i>>j;if(op=='M') uni(j,i);else{if(find(i)!=find(j)) cout<<-1<<endl;else{cout<<abs(dis[j]-dis[i])-1<<endl;}}}return0;}View CodeP2024 [NOI2001]⾷物链(种类并查集)题意：现在有三种⽣物，ABC，A吃B，B吃C，C吃A，现在依次告诉你⼀些关系，请说出这些关系中假话的个数(假话的定义为与之前的话⽭盾或不符合事实例如A吃A)思路：对于⼀对关系，⽐较难处理的是虽然你知道X吃Y，但是你不知道X跟Y究竟属于什么物种那么我们可以建⽴3*N⼤⼩的并查集，分为A,B,C三个部分，代表着A中的⽣物吃B中的⽣物等等类推对于⼀个关系⽐如X跟Y⼀类，我们在三个集合中分别将⼆者相连对于关系X吃Y，我们就将A中的X与B中的Y相连，还有两个集合中操作类似对于每个关系，我们就可以通过判断在⼀个集合内是否相连，或者在另⼀个集合内相连来判断正误了#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;const int maxn=2e5+10;int fa[maxn];int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}int main(){int n,k,ans=0,op,x,y;scanf("%d%d",&n,&k);for(int i=1;i<=3*n;i++) fa[i]=i;for(int i=1;i<=k;i++){scanf("%d%d%d",&op,&x,&y);if(x>n||y>n){ans++;continue;}if(op==1){if(find(x)==find(y+n)||find(y)==find(x+n)) ans++;else{fa[find(x)]=find(y);fa[find(x+n)]=find(y+n);fa[find(x+2*n)]=find(y+2*n);}}else{if(x==y){ans++;continue;}if(find(x)==find(y)||find(x)==find(y+2*n)) ans++;else{fa[find(x)]=find(y+n);fa[find(x+n)]=find(y+2*n);fa[find(x+2*n)]=find(y);}}}cout<<ans<<endl;return0;}View CodeP1197 [JSOI2008]星球⼤战（逆向思维，并查集）题意:给你⼀个⽆向图，每次从图中删去⼀个点，询问每次删点过后图中连通块的数量思路：本题可以离线，因此我们采⽤离线的逆向做法怎么个逆向呢？我们假设⼀开始只有所有删点操作之后的点，并算出连通块个数之后每次向图中加⼊被删除的点，并统计连通块个数如果重新对所有点跑⼀遍的话时间复杂度上⼀定会炸，对于新加⼊的点，我们先对当前连通块个数加1，如果遍历该点连接的所有点，如果能够合并，那么就将连通块个数减1最后把答案倒序输出就好了#include<cstdio>#include<iostream>#include<algorithm>#include<vector>#include<stack>#include<cstring>using namespace std;const int maxn=4e5+1000;int flag[maxn],fa[maxn];vector<int>a[maxn];stack<int> s,q;int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}int main(){int n,m,k,u,v;memset(flag,1,sizeof(flag));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);a[u].push_back(v);a[v].push_back(u);}scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d",&u);s.push(u);flag[u]=0;}int cnt=n-k;for(int i=0;i<n;i++) fa[i]=i;for(int i=0;i<n;i++){if(!flag[i]) continue;else{for(int j=0;j<a[i].size();j++){if(flag[a[i][j]]){int f1=find(a[i][j]),f2=find(i);if(f1!=f2) fa[f1]=find(fa[f2]),cnt--;}}}}q.push(cnt);for(int i=1;i<=k;i++){cnt++;int x=s.top();s.pop();for(int j=0;j<a[x].size();j++){if(flag[a[x][j]]){int f1=find(a[x][j]),f2=find(x);if(f1!=f2) fa[f1]=find(fa[f2]),cnt--;}}flag[x]=1;q.push(cnt);}while(!q.empty()){cout<<q.top()<<endl;q.pop();}return0;}View CodeP1111 修复公路(并查集)题意：给你n个点，m条⽆向边，每条边建好都有⼀个时间，问什么时候各个点能互相可达思路：将每条边按时间排序，每次加⼊⼀条边，看边连接的两点是否在⼀个连通块内，不在的话合并连通块，看是否总连通块个数为1即可#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;const int maxn1=1e5+10;const int maxn2=1e3+10;int fa[maxn2],siz[maxn2],n,m;struct node{int u,v,t;}edge[maxn1];int cmp(node a,node b){return a.t<b.t;}int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].t); sort(edge,edge+m,cmp);for(int i=1;i<=n;i++) fa[i]=i;memset(siz,0,sizeof(siz));int cnt=n;for(int i=0;i<m;i++){int u=edge[i].u,v=edge[i].v,t=edge[i].t;int f1=find(u),f2=find(v);if(f1!=f2) fa[f1]=f2,cnt--;if(cnt==1){cout<<t<<endl;return0;}}cout<<-1<<endl;return0;}View Code。
1000 A+B Problem 送分题1001 Exponentiation 高精度1003 Hangover 送分题1004 Financial Management 送分题1005 I Think I Need a Houseboat 几何1006 Biorhythms 送分题1007 DNA Sorting 送分题1008 Maya Calendar 日期处理1010 STAMPS 搜索＋DP1011 Sticks 搜索1012 Joseph 模拟/数学方法1014 Dividing 数论/DP?/组合数学->母函数?1015 Jury Compromise DP1016 Numbers That Count 送分题1017 Packets 贪心1018 Communication System 贪心1019 Number Sequence 送分题1020 Anniversary Cake 搜索1023 The Fun Number System 数论1025 Department 模拟1026 Cipher 组合数学1027 The Same Game 模拟1028 Web Navigation 送分题1031 Fence 计算几何1034 The dog task 计算几何1037 A decorative fence DP/组合数学1039 Pipe 几何1042 Gone Fishing 贪心/DP1045 Bode Plot 送分题(用物理知识)1046 Color Me Less 送分题1047 Round and Round We Go 高精度1048 Follow My Logic 模拟1049 Microprocessor Simulation 模拟1050 To the Max DP1053 Set Me 送分题1054 The Troublesome Frog 搜索1060 Modular multiplication of polynomials 高精度1061 青蛙的约会数论1062 昂贵的聘礼DP1064 Cable master DP/二分查找1065 Wooden Sticks DP1067 取石子游戏博弈论1068 Parencodings 送分题1069 The Bermuda Triangle 搜索1070 Deformed Wheel 几何1071 Illusive Chase 送分题1072 Puzzle Out 搜索1073 The Willy Memorial Program 模拟1074 Parallel Expectations DP1075 University Entrance Examination 模拟1080 Human Gene Functions DP->LCS变形1082 Calendar Game 博弈论1084 Square Destroyer 搜索？1085 Triangle War 博弈论1086 Unscrambling Images 模拟?1087 A Plug for UNIX 图论->最大流1088 滑雪DFS/DP1090 Chain ->格雷码和二进制码的转换1091 跳蚤数论1092 Farmland 几何1093 Formatting Text DP1094 Sorting It All Out 图论->拓扑排序1095 Trees Made to Order 组合数学1096 Space Station Shielding 送分题1097 Roads Scholar 图论1098 Robots 模拟1099 Square Ice 送分题1100 Dreisam Equations 搜索1101 The Game 搜索->BFS1102 LC-Display 送分题1103 Maze 模拟1104 Robbery 递推1106 Transmitters 几何1107 W's Cipher 送分题1110 Double Vision 搜索1111 Image Perimeters 搜索1112 Team Them Up! DP1113 Wall 计算几何->convex hull1119 Start Up the Startup 送分题1120 A New Growth Industry 模拟1122 FDNY to the Rescue! 图论->Dijkstra 1125 Stockbroker Grapevine 图论->Dijkstra 1128 Frame Stacking 搜索1129 Channel Allocation 搜索（图的最大独立集）1131 Octal Fractions 高精度1135 Domino Effect 图论->Dijkstra1137 The New Villa 搜索->BFS1141 Brackets Sequence DP1142 Smith Numbers 搜索1143 Number Game 博弈论1147 Binary codes 构造1148 Utopia Divided 构造1149 PIGS 图论->网络流1151 Atlantis 计算几何->同等安置矩形的并的面积->离散化1152 An Easy Problem! 数论1157 LITTLE SHOP OF FLOWERS DP1158 TRAFFIC LIGHTS 图论->Dijkstra变形1159 Palindrome DP->LCS1160 Post Office DP1161 Walls 图论1162 Building with Blocks 搜索1163 The Triangle DP1170 Shopping Offers DP1177 Picture 计算几何->同等安置矩形的并的周长->线段树1179 Polygon DP1180 Batch Scheduling DP1182 食物链数据结构->并查集1183 反正切函数的应用搜索1184 聪明的打字员搜索1185 炮兵阵地DP->数据压缩1187 陨石的秘密DP（BalkanOI99 Par的拓展）1189 钉子和小球递推?1190 生日蛋糕搜索/DP1191 棋盘分割DP1192 最优连通子集图论->无负权回路的有向图的最长路->BellmanFord 1193 内存分配模拟1194 HIDDEN CODES 搜索+DP1197 Depot 数据结构->Young T ableau1201 Intervals 贪心/图论->最长路->差分约束系统1202 Family 高精度1209 Calendar 日期处理1217 FOUR QUARTERS 递推1218 THE DRUNK JAILER 送分题1233 Street Crossing 搜索->BFS1245 Programmer, Rank Thyself 送分题1247 Magnificent Meatballs 送分题1248 Safecracker 搜索1250 T anning Salon 送分题1251 Jungle Roads 图论->最小生成树1271 Nice Milk 计算几何1273 Drainage Ditches 图论->最大流1274 The Perfect Stall 图论->二分图的最大匹配1275 Cashier Employment 图论->差分约束系统->无负权回路的有向图的最长路->Bellman-Ford1280 Game 递推1281 MANAGER 模拟1286 Necklace of Beads 组合数学->Polya定理1288 Sly Number 数论->解模线性方程组1293 Duty Free Shop DP1298 The Hardest Problem Ever 送分题1316 Self Numbers 递推同Humble Number一样1322 Chocolate 递推/组合数学1323 Game Prediction 贪心1324 Holedox Moving BFS+压缩储存1325 Machine Schedule 图论->二分图的最大匹配1326 Mileage Bank 送分题1327 Moving Object Recognition 模拟?1328 Radar Installation 贪心（差分约束系统的特例）1338 Ugly Numbers 递推(有O(n)算法)1364 King 图论->无负权回路的有向图的最长路->BellmanFord1370 Gossiping (数论->模线性方程有无解的判断)+(图论->DFS)2184 Cow Exhibition DP2190 ISBN 送分题2191 Mersenne Composite Numbers 数论2192 Zipper DP->LCS变形2193 Lenny's Lucky Lotto Lists DP2194 Stacking Cylinders 几何2195 Going Home 图论->二分图的最大权匹配2196 Specialized Four-Digit Numbers 送分题2197 Jill's Tour Paths 图论->2199 Rate of Return 高精度2200 A Card Trick 模拟2210 Metric Time 日期处理2239 Selecting Courses 图论->二分图的最大匹配2243 Knight Moves 搜索->BFS2247 Humble Numbers 递推(最优O(n)算法)2253 Frogger 图论->Dijkstra变形(和1295是一样的)2254 Globetrotter 几何2261 France '98 递推2275 Flipping Pancake 构造2284 That Nice Euler Circuit 计算几何2289 Jamie's Contact Groups 图论->网络流?2291 Rotten Ropes 送分题2292 Optimal Keypad DP2299 Ultra-QuickSort 排序->归并排序2304 Combination Lock 送分题2309 BST 送分题2311 Cutting Game 博弈论2312 Battle City 搜索->BFS2314 POJ language 模拟2315 Football Game 几何2346 Lucky tickets 组合数学2351 Time Zones 时间处理2379 ACM Rank T able 模拟+排序2381 Random Gap 数论2385 Apple Catching DP(像NOI98“免费馅饼”)2388 Who's in the Middle 送分题(排序)2390 Bank Interest 送分题2395 Out of Hay 图论->Dijkstra变形2400 Supervisor, Supervisee 图论->二分图的最大权匹配?2403 Hay Points 送分题2409 Let it Bead 组合数学->Polya定理2416 Return of the Jedi 图论->2417 Discrete Logging 数论2418 Hardwood Species 二分查找2419 Forests 枚举2421 Constructing Roads 图论->最小生成树2423 The Parallel Challenge Ballgame 几何2424 Flo's Restaurant 数据结构->堆2425 A Chess Game 博弈论2426 Remainder BFS2430 Lazy Cows DP->数据压缩1375 Intervals 几何1379 Run Away 计算几何->1380 Equipment Box 几何1383 Labyrinth 图论->树的最长路1394 Railroad 图论->Dijkstra1395 Cog-Wheels 数学->解正系数的线性方程组1408 Fishnet 几何1411 Calling Extraterrestrial Intelligence Again 送分题1430 Binary Stirling Numbers 日期处理1431 Calendar of Maya 模拟1432 Decoding Morse Sequences DP1434 Fill the Cisterns! 计算几何->离散化/1445 Random number 数据结构->碓1447 Ambiguous Dates 日期处理1450 Gridland 图论(本来TSP问题是NP难的，但这个图比较特殊，由现成的构造方法)1458 Common Subsequence DP->LCS1459 Power Network 图论->最大流1462 Random Walk 模拟+解线性方程组1463 Strategic game 贪心1466 Girls and Boys 图论->n/a1469 COURSES 贪心1475 Pushing Boxes DP1476 Always On the Run 搜索->BFS1480 Optimal Programs 搜索->BFS1481 The Die Is Cast 送分题1482 It's not a Bug, It's a Feature! 搜索->BFS1483 Going in Circles on Alpha Centauri 模拟1484 Blowing Fuses 送分题1485 Fast Food DP(似乎就是ioi2000的postoffice)1486 Sorting Slides 图论->拓扑排序1505 Copying Books DP+二分查找1510 Hares and Foxes 数论1512 Keeps Going and Going and ... 模拟1513 Scheduling Lectures DP1514 Metal Cutting 几何1515 Street Directions 图论->把一个无向连通图改造成为有向强连通图1517 u Calculate e 送分题1518 Problem Bee 几何1519 Digital Roots 送分题(位数可能很大)1520 Scramble Sort 排序1547 Clay Bully 送分题1555 Polynomial Showdown 送分题(非常阴险)1563 The Snail 送分题1601 Pizza Anyone? 搜索1604 Just the Facts 送分题1605 Horse Shoe Scoring 几何1606 Jugs 数论/搜索1631 Bridging signals DP+二分查找1632 Vase collection 图论->最大完全图1633 Gladiators DP1634 Who's the boss? 排序1635 Subway tree systems 图论->不同表示法的二叉树判同1637 Sightseeing tour 图论->欧拉回路1638 A number game 博弈论1639 Picnic Planning 图论->1641 Rational Approximation 数论1646 Double Trouble 高精度1654 Area 几何1657 Distance on Chessboard 送分题1658 Eva's Problem 送分题1660 Princess FroG 构造1661 Help Jimmy DP1663 Number Steps 送分题1664 放苹果组合数学->递推1677 Girls' Day 送分题1688 Dolphin Pool 计算几何1690 (Your)((Term)((Project))) 送分题1691 Painting A Board 搜索/DP1692 Crossed Matchings DP1693 Counting Rectangles 几何1694 An Old Stone Game 博弈论?1695 Magazine Delivery 图论->1712 Flying Stars DP1713 Divide et unita 搜索1714 The Cave 搜索/DP1717 Dominoes DP1718 River Crossing DP1719 Shooting Contest 贪心1729 Jack and Jill 图论->1730 Perfect Pth Powers 数论1732 Phone numbers DP1734 Sightseeing trip 图论->Euler回路1738 An old Stone Game 博弈论?1741 Tree 博弈论?1745 Divisibility DP1751 Highways 图论->1752 Advertisement 贪心/图论->差分约束系统1753 Flip Game 搜索->BFS1755 Triathlon 计算几何?1770 Special Experiment 树形DP1771 Elevator Stopping Plan DP1772 New Go Game 构造?1773 Outernet 模拟1774 Fold Paper Strips 几何1775 Sum of Factorials 送分题1776 T ask Sequences DP1777 Vivian's Problem 数论1870 Bee Breeding 送分题1871 Bullet Hole 几何1872 A Dicey Problem BFS1873 The Fortified Forest 几何+回溯1874 Trade on Verweggistan DP1875 Robot 几何1876 The Letter Carrier's Rounds 模拟1877 Flooded! 数据结构->堆1879 Tempus et mobilius Time and motion 模拟+组合数学->Polya定理1882 Stamps 搜索+DP1883 Theseus and the Minotaur 模拟1887 Testing the CATCHER DP1889 Package Pricing DP1893 Monitoring Wheelchair Patients 模拟+几何1915 Knight Moves 搜索->BFS1916 Rat Attack 数据结构->?1936 All in All DP?1946 Cow Cycling DP1947 Rebuilding Roads 二分1985 Cow Marathon 图论->有向无环图的最长路1995 Raising Modulo Numbers 数论->大数的幂求余2049 Finding Nemo 图论->最短路2050 Searching the Web 模拟(需要高效实现)2051 Argus 送分题(最好用堆，不用也可以过)2054 Color a Tree 贪心2061 Pseudo-random Numbers 数论2080 Calendar 日期处理2082 Terrible Sets 分治/2083 Fractal 递归2084 Game of Connections 递推(不必高精度)2105 IP Address 送分题2115 C Looooops 数论->解模线性方程2136 Vertical Histogram 送分题2165 Gunman 计算几何2179 Inlay Cutters 枚举2181 Jumping Cows 递推2182 Lost Cows ->线段树/＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝1370 Gossiping (数论->模线性方程有无解的判断)+(图论->DFS)1090 Chain ->格雷码和二进制码的转换2182 Lost Cows ->线段树/2426 Remainder BFS1872 A Dicey Problem BFS1324 Holedox Moving BFS+压缩储存1088 滑雪DFS/DP1015 Jury Compromise DP1050 To the Max DP1062 昂贵的聘礼DP1065 Wooden Sticks DP1074 Parallel Expectations DP1093 Formatting Text DP1112 Team Them Up! DP1141 Brackets Sequence DP1157 LITTLE SHOP OF FLOWERS DP1160 Post Office DP1163 The Triangle DP1170 Shopping Offers DP1179 Polygon DP1180 Batch Scheduling DP1191 棋盘分割DP1293 Duty Free Shop DP2184 Cow Exhibition DP2193 Lenny's Lucky Lotto Lists DP2292 Optimal Keypad DP1432 Decoding Morse Sequences DP1475 Pushing Boxes DP1513 Scheduling Lectures DP1633 Gladiators DP1661 Help Jimmy DP1692 Crossed Matchings DP1712 Flying Stars DP1717 Dominoes DP1718 River Crossing DP1732 Phone numbers DP1745 Divisibility DP1771 Elevator Stopping Plan DP1776 T ask Sequences DP1874 Trade on Verweggistan DP1887 Testing the CATCHER DP1889 Package Pricing DP1946 Cow Cycling DP1187 陨石的秘密DP（BalkanOI99 Par的拓展）1485 Fast Food DP(似乎就是ioi2000的postoffice) 2385 Apple Catching DP(像NOI98“免费馅饼”) 1064 Cable master DP/二分查找1037 A decorative fence DP/组合数学1936 All in All DP?1505 Copying Books DP+二分查找1631 Bridging signals DP+二分查找1159 Palindrome DP->LCS1458 Common Subsequence DP->LCS1080 Human Gene Functions DP->LCS变形2192 Zipper DP->LCS变形1185 炮兵阵地DP->数据压缩2430 Lazy Cows DP->数据压缩1067 取石子游戏博弈论1082 Calendar Game 博弈论1085 Triangle War 博弈论1143 Number Game 博弈论2311 Cutting Game 博弈论2425 A Chess Game 博弈论1638 A number game 博弈论1694 An Old Stone Game 博弈论?1738 An old Stone Game 博弈论?1741 Tree 博弈论?2083 Fractal 递归1104 Robbery 递推1217 FOUR QUARTERS 递推1280 Game 递推2261 France '98 递推2181 Jumping Cows 递推1316 Self Numbers 递推同Humble Number一样2084 Game of Connections 递推(不必高精度) 1338 Ugly Numbers 递推(有O(n)算法)2247 Humble Numbers 递推(最优O(n)算法)1322 Chocolate 递推/组合数学1189 钉子和小球递推?1947 Rebuilding Roads 二分2418 Hardwood Species 二分查找2082 Terrible Sets 分治/1001 Exponentiation 高精度1047 Round and Round We Go 高精度1060 Modular multiplication of polynomials 高精度1131 Octal Fractions 高精度1202 Family 高精度2199 Rate of Return 高精度1646 Double Trouble 高精度1147 Binary codes 构造1148 Utopia Divided 构造2275 Flipping Pancake 构造1660 Princess FroG 构造1772 New Go Game 构造?1005 I Think I Need a Houseboat 几何1039 Pipe 几何1070 Deformed Wheel 几何1092 Farmland 几何1106 Transmitters 几何2194 Stacking Cylinders 几何2254 Globetrotter 几何2315 Football Game 几何2423 The Parallel Challenge Ballgame 几何1375 Intervals 几何1380 Equipment Box 几何1408 Fishnet 几何1514 Metal Cutting 几何1518 Problem Bee 几何1605 Horse Shoe Scoring 几何1654 Area 几何1693 Counting Rectangles 几何1774 Fold Paper Strips 几何1871 Bullet Hole 几何1875 Robot 几何1873 The Fortified Forest 几何+回溯1031 Fence 计算几何1034 The dog task 计算几何1271 Nice Milk 计算几何2284 That Nice Euler Circuit 计算几何1688 Dolphin Pool 计算几何2165 Gunman 计算几何1755 Triathlon 计算几何?1379 Run Away 计算几何->1113 Wall 计算几何->convex hull1434 Fill the Cisterns! 计算几何->离散化/1151 Atlantis 计算几何->同等安置矩形的并的面积->离散化1177 Picture 计算几何->同等安置矩形的并的周长->线段树2419 Forests 枚举2179 Inlay Cutters 枚举1025 Department 模拟1027 The Same Game 模拟1048 Follow My Logic 模拟1049 Microprocessor Simulation 模拟1073 The Willy Memorial Program 模拟1075 University Entrance Examination 模拟1098 Robots 模拟1103 Maze 模拟1120 A New Growth Industry 模拟1193 内存分配模拟1281 MANAGER 模拟2200 A Card Trick 模拟2314 POJ language 模拟1431 Calendar of Maya 模拟1483 Going in Circles on Alpha Centauri 模拟1512 Keeps Going and Going and ... 模拟1773 Outernet 模拟1876 The Letter Carrier's Rounds 模拟1883 Theseus and the Minotaur 模拟2050 Searching the Web 模拟(需要高效实现)1012 Joseph 模拟/数学方法1086 Unscrambling Images 模拟?1327 Moving Object Recognition 模拟?1893 Monitoring Wheelchair Patients 模拟+几何1462 Random Walk 模拟+解线性方程组2379 ACM Rank T able 模拟+排序1879 Tempus et mobilius Time and motion 模拟+组合数学->Polya定理1520 Scramble Sort 排序1634 Who's the boss? 排序2299 Ultra-QuickSort 排序->归并排序1008 Maya Calendar 日期处理1209 Calendar 日期处理2210 Metric Time 日期处理1430 Binary Stirling Numbers 日期处理1447 Ambiguous Dates 日期处理2080 Calendar 日期处理2351 Time Zones 时间处理1770 Special Experiment 树形DP1916 Rat Attack 数据结构->?1197 Depot 数据结构->Young T ableau1182 食物链数据结构->并查集2424 Flo's Restaurant 数据结构->堆1877 Flooded! 数据结构->堆1445 Random number 数据结构->碓1023 The Fun Number System 数论1061 青蛙的约会数论1091 跳蚤数论1152 An Easy Problem! 数论2191 Mersenne Composite Numbers 数论2381 Random Gap 数论2417 Discrete Logging 数论1510 Hares and Foxes 数论1641 Rational Approximation 数论1730 Perfect Pth Powers 数论1777 Vivian's Problem 数论2061 Pseudo-random Numbers 数论1014 Dividing 数论/DP?/组合数学->母函数?1606 Jugs 数论/搜索1995 Raising Modulo Numbers 数论->大数的幂求余2115 C Looooops 数论->解模线性方程1288 Sly Number 数论->解模线性方程组1395 Cog-Wheels 数学->解正系数的线性方程组1000 A+B Problem 送分题1003 Hangover 送分题1004 Financial Management 送分题1006 Biorhythms 送分题1007 DNA Sorting 送分题1016 Numbers That Count 送分题1019 Number Sequence 送分题1028 Web Navigation 送分题1046 Color Me Less 送分题1053 Set Me 送分题1068 Parencodings 送分题1071 Illusive Chase 送分题1096 Space Station Shielding 送分题1099 Square Ice 送分题1102 LC-Display 送分题1107 W's Cipher 送分题1119 Start Up the Startup 送分题1218 THE DRUNK JAILER 送分题1245 Programmer, Rank Thyself 送分题1247 Magnificent Meatballs 送分题1250 T anning Salon 送分题1298 The Hardest Problem Ever 送分题1326 Mileage Bank 送分题2190 ISBN 送分题2196 Specialized Four-Digit Numbers 送分题2291 Rotten Ropes 送分题2304 Combination Lock 送分题2309 BST 送分题2390 Bank Interest 送分题2403 Hay Points 送分题1411 Calling Extraterrestrial Intelligence Again 送分题1481 The Die Is Cast 送分题1484 Blowing Fuses 送分题1517 u Calculate e 送分题1547 Clay Bully 送分题1563 The Snail 送分题1604 Just the Facts 送分题1657 Distance on Chessboard 送分题1658 Eva's Problem 送分题1663 Number Steps 送分题1677 Girls' Day 送分题1690 (Your)((Term)((Project))) 送分题1775 Sum of Factorials 送分题1870 Bee Breeding 送分题2105 IP Address 送分题2136 Vertical Histogram 送分题1555 Polynomial Showdown 送分题(非常阴险) 2388 Who's in the Middle 送分题(排序)1519 Digital Roots 送分题(位数可能很大)1045 Bode Plot 送分题(用物理知识)2051 Argus 送分题(最好用堆，不用也可以过) 1011 Sticks 搜索1020 Anniversary Cake 搜索1054 The Troublesome Frog 搜索1069 The Bermuda Triangle 搜索1072 Puzzle Out 搜索1100 Dreisam Equations 搜索1110 Double Vision 搜索1111 Image Perimeters 搜索1128 Frame Stacking 搜索1142 Smith Numbers 搜索1162 Building with Blocks 搜索1183 反正切函数的应用搜索1184 聪明的打字员搜索1248 Safecracker 搜索1601 Pizza Anyone? 搜索1713 Divide et unita 搜索1129 Channel Allocation 搜索（图的最大独立集）1190 生日蛋糕搜索/DP1691 Painting A Board 搜索/DP1714 The Cave 搜索/DP1084 Square Destroyer 搜索？1010 STAMPS 搜索＋DP1194 HIDDEN CODES 搜索+DP1882 Stamps 搜索+DP1101 The Game 搜索->BFS1137 The New Villa 搜索->BFS1233 Street Crossing 搜索->BFS2243 Knight Moves 搜索->BFS2312 Battle City 搜索->BFS1476 Always On the Run 搜索->BFS1480 Optimal Programs 搜索->BFS1482 It's not a Bug, It's a Feature! 搜索->BFS 1753 Flip Game 搜索->BFS1915 Knight Moves 搜索->BFS1017 Packets 贪心1018 Communication System 贪心1323 Game Prediction 贪心1463 Strategic game 贪心1469 COURSES 贪心1719 Shooting Contest 贪心2054 Color a Tree 贪心1328 Radar Installation 贪心（差分约束系统的特例）1042 Gone Fishing 贪心/DP1752 Advertisement 贪心/图论->差分约束系统1201 Intervals 贪心/图论->最长路->差分约束系统1097 Roads Scholar 图论1161 Walls 图论1450 Gridland 图论(本来TSP问题是NP难的，但这个图比较特殊，由现成的构造方法)2197 Jill's Tour Paths 图论->2416 Return of the Jedi 图论->1639 Picnic Planning 图论->1695 Magazine Delivery 图论->1729 Jack and Jill 图论->1751 Highways 图论->1122 FDNY to the Rescue! 图论->Dijkstra1125 Stockbroker Grapevine 图论->Dijkstra1135 Domino Effect 图论->Dijkstra1394 Railroad 图论->Dijkstra1158 TRAFFIC LIGHTS 图论->Dijkstra变形2395 Out of Hay 图论->Dijkstra变形2253 Frogger 图论->Dijkstra变形(和1295是一样的)1734 Sightseeing trip 图论->Euler回路1466 Girls and Boys 图论->n/a1515 Street Directions 图论->把一个无向连通图改造成为有向强连通图1635 Subway tree systems 图论->不同表示法的二叉树判同1275 Cashier Employment 图论->差分约束系统->无负权回路的有向图的最长路->Bellman-Ford1274 The Perfect Stall 图论->二分图的最大匹配1325 Machine Schedule 图论->二分图的最大匹配2239 Selecting Courses 图论->二分图的最大匹配2195 Going Home 图论->二分图的最大权匹配2400 Supervisor, Supervisee 图论->二分图的最大权匹配?1637 Sightseeing tour 图论->欧拉回路1383 Labyrinth 图论->树的最长路1094 Sorting It All Out 图论->拓扑排序1486 Sorting Slides 图论->拓扑排序1149 PIGS 图论->网络流2289 Jamie's Contact Groups 图论->网络流?1192 最优连通子集图论->无负权回路的有向图的最长路->BellmanFord 1364 King 图论->无负权回路的有向图的最长路->BellmanFord1985 Cow Marathon 图论->有向无环图的最长路1087 A Plug for UNIX 图论->最大流1273 Drainage Ditches 图论->最大流1459 Power Network 图论->最大流1632 Vase collection 图论->最大完全图2049 Finding Nemo 图论->最短路1251 Jungle Roads 图论->最小生成树2421 Constructing Roads 图论->最小生成树1026 Cipher 组合数学1095 Trees Made to Order 组合数学2346 Lucky tickets 组合数学1286 Necklace of Beads 组合数学->Polya定理2409 Let it Bead 组合数学->Polya定理1664 放苹果组合数学->递推。
POJ上一些题目在http://162.105.81.202/course/problemSolving/可以找到解题报告。
《算法艺术与信息学竞赛》的习题提示在网上可搜到一.动态规划参考资料：刘汝佳《算法艺术与信息学竞赛》《算法导论》推荐题目：/JudgeOnline/problem?id=1141简单/JudgeOnline/problem?id=2288中等，经典TSP问题/JudgeOnline/problem?id=2411中等，状态压缩DP/JudgeOnline/problem?id=1112中等/JudgeOnline/problem?id=1848中等，树形DP。
可参考《算法艺术与信息学竞赛》动态规划一节的树状模型/show_problem.php?pid=1234中等，《算法艺术与信息学竞赛》中的习题/JudgeOnline/problem?id=1947中等，《算法艺术与信息学竞赛》中的习题/JudgeOnline/problem?id=1946中等，《算法艺术与信息学竞赛》中的习题/JudgeOnline/problem?id=1737中等，递推/JudgeOnline/problem?id=1821中等，需要减少冗余计算/show_problem.php?pid=2561中等，四边形不等式的简单应用/JudgeOnline/problem?id=1038较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答/JudgeOnline/problem?id=1390较难，《算法艺术与信息学竞赛》中有解答/JudgeOnline/problem?id=3017较难，需要配合数据结构优化（我的题目^_^）/JudgeOnline/problem?id=1682较难，写起来比较麻烦/JudgeOnline/problem?id=2047较难/JudgeOnline/problem?id=2152难，树形DP/JudgeOnline/problem?id=3028难，状态压缩DP，题目很有意思/JudgeOnline/problem?id=3124难/JudgeOnline/problem?id=2915非常难二.搜索参考资料：刘汝佳《算法艺术与信息学竞赛》推荐题目：/JudgeOnline/problem?id=1011简单，深搜入门题/JudgeOnline/problem?id=1324中等，广搜/JudgeOnline/problem?id=2044中等，广搜/JudgeOnline/problem?id=2286较难，广搜/JudgeOnline/problem?id=1945难，IDA*，迭代加深搜索，需要较好的启发函数/JudgeOnline/problem?id=2449难，可重复K最短路，A*。
专题1 ⼦集、交集、并集、补集之间的关系式⼆级结论1：⼦集的个数问题【结论阐述】若⼀个集合含有（）个元素，则集合有个⼦集，有个真⼦集，有个⾮空⼦集，有个⾮空真⼦集.理解：的⼦集有个，从每个元素的取舍来理解，例如每个元素都有两种选择，则个元素共有种选择，该结论需要掌握并会灵活应⽤.对解决有关集合的个数问题，可以直接利⽤这些公式进⾏计算.计算时要分清这个集合的元素是从哪⾥来的，有哪些，即若可供选择的元素有个，就转化为求这个元素集合的⼦集问题.另外要注意⼦集､真⼦集､⼦集､⾮空真⼦集之间的联系有区别.【典例指引1】（2023·安徽·合肥市第⼋中学模拟预测）【典例指引2】【针对训练】（2023·河南·开封市东信学校模拟预测）（2022·⿊⻰江⻬⻬哈尔·⼆模）A n n ∈N ∗A 2n (−1)2n (−1)2n (−2)2n A 2n n 2n 已知集合，，则满⾜条件的集合的个数为（ ）A ．3B ．4C ．7D ．8已知集合，则集合的真⼦集的个数为（ ）A ．B ．C ．D ．集合的⾮空真⼦集的个数为（ ）A ．5B ．6C ．7D ．8设集合，则集合M 的真⼦集个数为（ ）已知集合，，若，则实数的取值范围是（）A．B．C．D．【典例指引2】已知集合，或.（1）若，求的取值范围；（2）若，求的取值范围.【针对训练】已知集合，，若，则实数的取值集合为（）A．B．C．D．（2023·湖北·⻩⽯市有⾊第⼀中学模拟预测）已知，且，则满⾜条件的x有（）A．1个B．2个C．3个D．4个（2021·辽宁沈阳·三模）已知集合，若，则实数（）A．B．1C．D．或（2023·重庆⼋中模拟预测）已知集合，，且，则a的取值范围可以是（）A．B．C．D．（2023·辽宁·⾼三⽉考）（2023·浙江绍兴·模拟预测）（2023·天津·南开中学模拟预测）A ．B ．C ．D ．若全集，则集合等于（ ）A ．B ．C ．D ．已知集合，，则（ ）A ．B ．C ．D ．设全集，集合，，则（ ）A ．B ．C ．D ．已知全集为，集合，则___________，___________.。
二分答案例1：二分查找的基本思想:首先将结点按关键字排序,其次将查找值与中间位置的值比较,相等,查找成功;不等,则中间数据大于或小于查找值,无论怎样查找将在一半的数据中查找。
参考程序1：#include <iostream>using namespace std;int a[1000],i,x;int main(){int n,m;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);int l, r;int mid;l = 1;r = n;x=0;while(l<=r){mid=(l+r)/2;if(a[mid]==m){x=mid;break;}else if(m<a[mid]) r=mid-1;else l=mid+1;}printf("%d",x);return 0;}练习：一元三次方程求解（codevs1038）题目描述 Description有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。
给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。
输入描述 Input Description一个三次方程的各项系数输出描述 Output Description三个解样例输入 Sample Input1 -5 -4 20样例输出 Sample Output-2.00 2.00 5.00#include <iostream>#include <cstdio>using namespace std;double a,b,c,d;double f(double x){return a*x*x*x+b*x*x+c*x+d;}void finder(double L,double R){if(L>=R-0.0001)return;double mid=(L+R)/2;double midy=f(mid);if(midy>-0.005&&midy<0.005){printf("%.2f ",mid);return;}finder(L,mid-0.0001);finder(mid+0.0001,R);}int main(){cin >> a>>b>>c>>d;finder(-100,100);return 0;}练习：木材加工(codevs3297)题目描述Description木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。
