关键词:
【Summarize】
1.求满足条件的情况下最大化中位数可以枚举中位数再验证条件
2.对于种类并查集,可以利用拆点的方式,用x-A表示x属于A类,将种类归属关系作为节点进行运算
POJ 3614:Sunscreen
/* 每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值 防晒霜的作用是让阳光照在身上的阳光强度固定为某个值 每瓶防晒霜给出固定的阳光量和防晒霜数量 每头奶牛只能用一瓶防晒霜 问最多能晒太阳的奶牛数量 */ #include <cstdio> #include <queue> #include <algorithm> const int N=3000; using namespace std; int n,m; typedef pair<int,int> P; priority_queue<int,vector<int>,greater<int> > q; P cow[N],bottle[N]; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d%d",&cow[i].first,&cow[i].second); for(int i=0;i<m;i++)scanf("%d%d",&bottle[i].first,&bottle[i].second); sort(cow,cow+n);sort(bottle,bottle+m); int j=0,ans=0; for(int i=0;i<m;i++){ while(j<n&&cow[j].first<=bottle[i].first)q.push(cow[j++].second); while(!q.empty()&&bottle[i].second){ int x=q.top(); q.pop(); if(x<bottle[i].first)continue; ans++; bottle[i].second--; } }printf("%d ",ans); return 0; }
POJ 2010:Moo University - Financial Aid
/* 每个物品有两个属性值s和f,从m个物品中选取n个物品 求f的和小于等于F的情况下s的中位数最大值。 按照s排序,枚举每个s作为中位数的情况 那么只要知道前面n/2最小值的和和后面n/2最小值的和就好 这个可以利用优先队列预处理出来 */ #include <cstdio> #include <algorithm> #include <queue> using namespace std; priority_queue<int> q; const int N=100010; int n,m,F,pre[N],nxt[N],sum; struct data{int s,f;}p[N]; bool cmp(data a,data b){return a.s>b.s;} int main(){ scanf("%d%d%d",&n,&m,&F); for(int i=1;i<=m;i++)scanf("%d%d",&p[i].s,&p[i].f); sort(p+1,p+m+1,cmp); int base=n/2; for(int i=1;i<=base;i++)q.push(p[i].f),sum+=p[i].f; for(int i=base+1;i<=m-base;i++){ pre[i]=sum; if(q.top()>p[i].f){ sum-=q.top(); q.pop(); sum+=p[i].f; q.push(p[i].f); } }while(!q.empty())q.pop();sum=0; for(int i=m;i>m-base;i--)q.push(p[i].f),sum+=p[i].f; for(int i=m-base;i>=base+1;i--){ nxt[i]=sum; if(q.top()>p[i].f){ sum-=q.top(); q.pop(); sum+=p[i].f; q.push(p[i].f); } }int ans=-1; for(int i=base+1;i<=m-base;i++){ if(p[i].f+pre[i]+nxt[i]<=F){ ans=p[i].s; break; } }printf("%d ",ans); return 0; }
POJ 2236:Wireless Network
/* 每台电脑可以连接到距离不超过d的正常电脑,连接具有传递性 现在因为地震,所有的电脑被损坏了,现在进行维修电脑的行动 O x表示维修好了编号为x的电脑,S x y表示查询x和y是否能连接 */ #include <cstdio> const int N=1010; struct data{int x,y;}p[N]; int f[N],x,y,n,d,a[N]; char op[10]; int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);} int sqr(int x){return x*x;} bool link(int a,int b){return sqr(p[a].x-p[b].x)+sqr(p[a].y-p[b].y)<=d*d;} int main(){ scanf("%d%d",&n,&d); for(int i=1;i<=n;i++)f[i]=i,a[i]=0,scanf("%d%d",&p[i].x,&p[i].y); while(~scanf(" %s",op)){ if(op[0]==‘O‘){ scanf("%d",&x); for(int i=1;i<=n;i++)if(a[i]&&link(x,i)){ if(sf(x)==sf(i))continue; f[sf(x)]=sf(i); }a[x]=1; }else{ scanf("%d%d",&x,&y); if(sf(x)==sf(y))puts("SUCCESS"); else puts("FAIL"); } }return 0; }
POJ 1703:Find them, Catch them
/* 有两个物种,每个生物都属于两种物种之一, 现在有两个操作,表示两个生物属于不同物种或者查询两个物种的关系 */ #include <cstdio> const int N=100010<<1; int T,f[N],n,m,x,y; char op[2]; void init(int n){for(int i=0;i<=n;i++)f[i]=i;} int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);} bool Same(int x,int y){return sf(x)==sf(y);} bool Union(int x,int y){f[sf(x)]=sf(y);} int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); init(2*n); for(int i=1;i<=m;i++){ scanf(" %s%d%d",&op,&x,&y); x--;y--; if(op[0]==‘D‘){Union(x,y+n);Union(x+n,y);} else{ if(Same(x,y)||Same(x+n,y+n))puts("In the same gang."); else if(Same(x,y+n)||Same(x+n,y))puts("In different gangs."); else puts("Not sure yet."); } } }return 0; }
AOJ 2170:Marked Ancestor
/* 给出一棵树,一开始根节点是上色的, 现在有两个操作:给某个节点上色,或者查询一个节点最近的上色的祖先节点 */ #include <cstdio> const int N=100010; int f[N],n,m,x; char op[2]; int sf(int x){return f[x]==x?x:sf(f[x]);} int main(){ while(scanf("%d%d",&n,&m),n+m){ for(int i=2;i<=n;i++)scanf("%d",&f[i]); long long ans=0; f[1]=1; while(m--){ scanf(" %s%d",op,&x); if(op[0]==‘M‘)f[x]=x; else ans+=sf(x); }printf("%lld ",ans); }return 0; }
挑战程序设计竞赛(算法和数据结构)——4.4链表习题的java实现(代码片段)
链表有初始化、插入元素、删除元素、查找元素等方法。在创建链表的过程中,最关键的是搞清楚链表的几个关键数据构成:链表由一个个节点互相串联构成,节点作为一个基础的对象,可由类Node(随便取个... 查看详情
挑战程序设计竞赛2.4习题:moouniversity-financialaidpoj-2010
Bessienotedthatalthoughhumanshavemanyuniversitiestheycanattend,cowshavenone.Toremedythisproblem,sheandherfellowcowsformedanewuniversitycalledTheUniversityofWisconsin-Farmside,"MooU"forshort.Notwishingtoadmitdumber-than-averagecows,thefounderscreatedanincrediblypreciseadmissionexamcalledtheCowScholas... 查看详情
挑战程序设计竞赛(算法和数据结构)——4.5java中对应c++stl的数据结构类
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——4.3队列习题的java实现(代码片段)
题目:基本思路:将任务定义为一个包含名称和时间的Task类,定义一个Task类型的队列,并循环下列算法:用时间sum_time来记录处理情况,只要队列不为空,就不断执行当处理一个队头任务时,首先... 查看详情
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现(代码片段)
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——7.7最小成本排序的java实现(代码片段)
题目&思路:代码:importjava.util.*;publicclassMinimumCostSortpublicstaticfinalintMAX=1000;publicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();in 查看详情
加工并存储数据的数据结构(代码片段)
堆一些注意点:左儿子的编号是自己的编号*2+1右儿子的编号是自己的编号*2+2父亲节点的编号是(自己的编号-1)/2 手动实现的堆,贴一段书上的代码:1#include<iostream>23usingnamespacestd;45intconstMAX_N=233333;6intheap[MAX_N];7intsz... 查看详情
挑战程序设计竞赛(算法和数据结构)——4.6数据结构的应用——计算面积java代码实现(代码片段)
题目:代码及实现思路如下:importjava.io.BufferedInputStream;importjava.util.Scanner;importjava.util.Stack;importjava.util.Vector;publicclass_4_6publicstaticvoidmain(String[]args)/*设计两个栈,S1和S 查看详情
挑战程序设计竞赛(算法和数据结构)——17.4最大正方形的java实现(代码片段)
题目&思路:代码:importjava.util.Scanner;publicclassLargestSquarepublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intH=cin.nextInt();intW=cin.nextInt();intmap[] 查看详情
挑战程序设计竞赛(算法和数据结构)——5.5迭代器和二分查找的java实现(代码片段)
迭代器代码:importjava.util.Arrays;importjava.util.Iterator;publicclassIteratorDemopublicstaticvoidmain(String[]args)int[]arr=newint[]1,2,3,4,5,6,7,8,9,8,2,6,5,7,1,3,4,5,6;Iterator<Integer 查看详情
挑战程序设计竞赛(算法和数据结构)——5.4散列法习题java代码实现(代码片段)
题目:散列法相关的代码可以参考之前一篇博文https://blog.csdn.net/weixin_42887138/article/details/121254659importjava.lang.ref.PhantomReference;importjava.util.Scanner;publicclass_5_4publicstaticvoidmain(String[]arg 查看详情
挑战程序设计竞赛(算法和数据结构)——14.1互质的集合(并查集)的java实现(代码片段)
题目与思路:代码:importjava.util.Scanner;importjava.util.Vector;publicclassDisjointSetpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();intq=cin.nextInt();//首先定义并查集(用Vector),初始化为nUnionFin... 查看详情
挑战程序设计竞赛(算法和数据结构)——13.3单源最短路径(dijkstra算法)的java实现(代码片段)
题目:代码:importjava.io.BufferedInputStream;importjava.io.BufferedReader;importjava.util.Scanner;publicclassSingleSourceShortestPathpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();//初始化邻接矩阵MintM[][]... 查看详情
挑战程序设计竞赛(算法和数据结构)——分割(下)&快速排序的java实现(代码片段)
在《挑战程序设计竞赛(算法和数据结构)——7.2分割(上)JAVA实现》中实现了将任一数组的元素以最后一个元素为界,小的排在前,大的排在后的功能,参照以下链接:https://blog.csdn.net/weixin_42887... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.2图的表示java实现(代码片段)
题目:importjava.util.Scanner;publicclassGraphImplementpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();//建立图的邻接矩阵intM[][]=newint[n][n];for(inti=0;i<n;i++)intid=cin.nextInt();intdegree=cin.nextInt();for(i... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.5连通分量的java实现(代码片段)
题目:讲解:注意:定义了一个Vector类型的数组,不仅需要初始化Vector类型的数组,还需初始化每一个Vector类型的容器。否则会出现以下异常:Exceptioninthread“main”java.lang.NullPointerException:Cannotinvoke“java.uti... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.1几何对象的基本元素与表现的java实现(代码片段)
importjava.awt.*;importjava.util.Vector;publicclassGraghBasic//表示点的类publicstaticclassPointdoublex,y;Point(doublex,doubley)this.x=x;this.y=y;//表示向量的类publicstaticclassMyVectordoublex,y;MyVector(doublex,doubley)this.x=x;this.y=y;//表示线段的类publicstaticclas... 查看详情