POJ经典算法题.docx
- 文档编号:10375836
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:90
- 大小:145.66KB
POJ经典算法题.docx
《POJ经典算法题.docx》由会员分享,可在线阅读,更多相关《POJ经典算法题.docx(90页珍藏版)》请在冰点文库上搜索。
POJ经典算法题
最优连通子集
Description(poj1192)
众所周知,我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x,y)来唯一表示,如果x,y都是整数,我们就把点P称为整点,否则点P称为非整点。
我们把平面上所有整点构成的集合记为W。
定义1两个整点P1(x1,y1),P2(x2,y2),若|x1-x2|+|y1-y2|=1,则称P1,P2相邻,记作P1~P2,否则称P1,P2不相邻。
定义2设点集S是W的一个有限子集,即S={P1,P2,...,Pn}(n>=1),其中Pi(1<=i<=n)属于W,我们把S称为整点集。
定义3设S是一个整点集,若点R,T属于S,且存在一个有限的点序列Q1,Q2,?
Qk满足:
1.Qi属于S(1<=i<=k);
2.Q1=R,Qk=T;
3.Qi~Qi+1(1<=i<=k-1),即Qi与Qi+1相邻;
4.对于任何1<=i 我们则称点R与点T在整点集S上连通,把点序列Q1,Q2,...,Qk称为整点集S中连接点R与点T的一条道路。 定义4若整点集V满足: 对于V中的任何两个整点,V中有且仅有一条连接这两点的道路,则V称为单整点集。 定义5对于平面上的每一个整点,我们可以赋予它一个整数,作为该点的权,于是我们把一个整点集中所有点的权的总和称为该整点集的权和。 我们希望对于给定的一个单整点集V,求出一个V的最优连通子集B,满足: 1.B是V的子集 2.对于B中的任何两个整点,在B中连通; 3.B是满足条件 (1)和 (2)的所有整点集中权和最大的。 Input 第1行是一个整数N(2<=N<=1000),表示单整点集V中点的个数; 以下N行中,第i行(1<=i<=N)有三个整数,Xi,Yi,Ci依次表示第i个点的横坐标,纵坐标和权。 同一行相邻两数之间用一个空格分隔。 -10^6<=Xi,Yi<=10^6;-100<=Ci<=100。 Output 仅一个整数,表示所求最优连通集的权和。 SampleInput 5 00-2 011 101 0-11 -101 SampleOutput 2 importjava.util.Scanner; publicclassMain{ staticintn; staticintx[]; staticinty[]; staticintc[]; staticintans=0; staticintsearch(inti,intparent) { intret=0,t; for(intj=0;j { if(parent! =j&&Math.abs(x[i]-x[j])+Math.abs(y[i]-y[j])==1) { t=search(j,i); if(t>0)ret+=t; } } if(ret+c[i]>ans)ans=ret+c[i]; returnret+c[i]; } publicstaticvoidmain(String[]args){ Scannersc=newScanner(System.in); n=sc.nextInt(); x=newint[n]; y=newint[n]; c=newint[n]; for(inti=0;i x[i]=sc.nextInt(); y[i]=sc.nextInt(); c[i]=sc.nextInt(); } search(0,-1); System.out.println(ans); } } 陨石的秘密 Description(poj1187) 公元11380年,一颗巨大的陨石坠落在南极。 于是,灾难降临了,地球上出现了一系列反常的现象。 当人们焦急万分的时候,一支中国科学家组成的南极考察队赶到了出事地点。 经过一番侦察,科学家们发现陨石上刻有若干行密文,每一行都包含5个整数: 11116 006357 801132845 著名的科学家SS发现,这些密文实际上是一种复杂运算的结果。 为了便于大家理解这种运算,他定义了一种SS表达式: 1.SS表达式是仅由'{','}','[',']','(',')'组成的字符串。 2.一个空串是SS表达式。 3.如果A是SS表达式,且A中不含字符'{','}','[',']',则(A)是SS表达式。 4.如果A是SS表达式,且A中不含字符'{','}',则[A]是SS表达式。 5.如果A是SS表达式,则{A}是SS表达式。 6.如果A和B都是SS表达式,则AB也是SS表达式。 例如 ()(())[] {()[()]} {{[[(())]]}} 都是SS表达式。 而 ()([])() [() 不是SS表达式。 一个SS表达式E的深度D(E)定义如下: 例如(){()}[]的深度为2。 密文中的复杂运算是这样进行的: 设密文中每行前4个数依次为L1,L2,L3,D,求出所有深度为D,含有L1对{},L2对[],L3对()的SS串的个数,并用这个数对当前的年份11380求余数,这个余数就是密文中每行的第5个数,我们称之为? 神秘数? 。 密文中某些行的第五个数已经模糊不清,而这些数字正是揭开陨石秘密的钥匙。 现在科学家们聘请你来计算这个神秘数。 Input 共一行,4个整数L1,L2,L3,D。 相邻两个数之间用一个空格分隔。 (0<=L1<=10,0<=L2<=10,0<=L3<=10,0<=D<=30) Output 共一行,包含一个整数,即神秘数。 SampleInput 1112 SampleOutput 8 importjava.util.*; publicclassMain{ staticints[][][][]=newint[31][11][11][11]; staticintget(intd,intl1,intl2,intl3) { intt,j,k,i,h; if(l1==0&&l2==0&&l3==0&&d>=0) return1; if(d<=0) return0; if((t=s[d][l1][l2][l3])>=0) returnt; t=0; if(d==1) { if(l1! =0)t+=get(d,l1-1,l2,l3); if(l2! =0)t+=get(d,l1,l2-1,l3); if(l3! =0)t+=get(d,l1,l2,l3-1); t%=11380; s[d][l1][l2][l3]=t; returnt; } for(i=0;i<=l1-1;i++) for(j=0;j<=l2;j++) for(k=0;k<=l3;k++) { t+=(get(d-1,i,j,k)*get(d,l1-1-i,l2-j,l3-k)); if(t>(1<<30))t%=11380; } for(j=0;j<=l2-1;j++) for(k=0;k<=l3;k++) { t+=(get(d-1,0,j,k)*get(d,l1,l2-1-j,l3-k)); if(t>(1<<30))t%=11380; } for(k=0;k<=l3-1;k++) { t+=(get(d-1,0,0,k)*get(d,l1,l2,l3-1-k)); if(t>(1<<30))t%=11380; } t%=11380; s[d][l1][l2][l3]=t; returnt; } publicstaticvoidmain(String[]args){ Scannerin=newScanner(System.in); intd,l1,l2,l3,i,j,k,l; l1=in.nextInt(); l2=in.nextInt(); l3=in.nextInt(); d=in.nextInt(); for(l=0;l<=d;l++) for(i=0;i<=l1;i++) for(j=0;j<=l2;j++) for(k=0;k<=l3;k++) s[l][i][j][k]=-1; System.out.printf("%d\n",(get(d,l1,l2,l3)-get(d-1,l1,l2,l3)+11380)%11380); } } 炮兵阵地 Description(poj1185) 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。 一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H"表示),也可能是平原(用"P"表示),如下图。 在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域: 沿横向左右各两格,沿纵向上下各两格。 图上其它白色网格均攻击不到。 从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 Input 第一行包含两个由空格分割开的正整数,分别表示N和M; 接下来的N行,每一行含有连续的M个字符('P'或者'H'),中间没有空格。 按顺序表示地图中每一行的数据。 N<=100;M<=10。 Output 仅一行,包含一个整数K,表示最多能摆放的炮兵部队的数量。 SampleInput 54 PHPP PPHH PPPP PHPP PHHP SampleOutput 6 /*题目描述: 在一张n*m的方格中放置炮兵,要求相邻2格没有炮兵,求最多能放多少 *开始因为没有想到好的方法,于是搜了一次.tle... *知道有关于状态压缩的算法,可不太清楚,一直放着没做,今天看了一个状态压缩DP算法 *,于是写了下来...终于Ac.. *状态压缩: 用位来表示状态,利用位运算节省时间(不是很能体会) *枚举状态,进行状态转移从而得到最优解,称为状态压缩DP... */ importjava.io.BufferedReader; importjava.io.IOException; importjava.io.InputStreamReader; importjava.util.StringTokenizer; classcin { staticBufferedReaderin=newBufferedReader(newInputStreamReader(System.in)); staticStringTokenizerst; staticintleave=0; staticintnextInt()throwsIOException { returnInteger.parseInt(next()); } staticStringnext()throwsIOException { while(leave==0) { st=newStringTokenizer(in.readLine()); leave=st.countTokens(); } leave--; returnst.nextToken(); } staticbooleanhasNext()throwsIOException { while(leave==0) { Stringtemp=in.readLine(); if(temp==null)returnfalse; st=newStringTokenizer(temp); leave=st.countTokens(); } returntrue; } } classDp { ints[],r[][],c[][],f[][][],n,m; intx[],top=0; Stringboard[]; staticintv[]={1,2,4,8,16,32,64,128,256,512}; Dp(Stringb[],intn,intm) { board=b; this.n=n; this.m=m; s=newint[61]; x=newint[m]; } voiddfs(intt)//计算s[] { inti; if(t>=m) { s[top]=0; for(i=0;i { s[top]+=v[i]*x[i]; } top++; } else { if(place(t)) { x[t]=1; dfs(t+1); } x[t]=0; dfs(t+1); } } booleanplace(intt) { if(t-2>=0&&x[t-2]==1||t-1>=0&&x[t-1]==1)returnfalse; returntrue; } intgetC(intx)//x中含1的个数 { intsum=0; while(x>0) { sum+=(x%2); x>>=1; } returnsum; } voidinit()//初始化各状态 { dfs(0); inti,j,temp; r=newint[n][top]; c=newint[n][top]; for(i=0;i { temp=0; for(j=0;j { if(board[i].charAt(j)=='P')temp+=v[j]; } for(j=0;j { r[i][j]=temp&s[j]; c[i][j]=getC(r[i][j]); //System.out.println(r[i][j]+""+c[i][j]); } } f=newint[n][top][top]; } intfindMax()//构造最优解 { inti,j,k,max,h; for(i=0;i { for(j=0;j { f[0][i][j]=c[0][i]; } } if(n>1) { for(i=0;i { for(j=0;j { max=0; for(k=0;k { if((r[1][i]&r[0][j])==0&&max { max=f[0][j][k]; } } f[1][i][j]=max+c[1][i]; } } } for(k=2;k { for(h=0;h { for(i=0;i { max=0; for(j=0;j { if((r[k][h]&r[k-1][i])==0&&(r[k-1][i]&r[k-2][j])==0&&(r[k][h]&r[k-2][j])==0&&max { max=f[k-1][i][j]; } } f[k][h][i]=max+c[k][h]; } } } max=0; for(i=0;i { for(j=0;j { if(max max=f[n-1][i][j]; } } returnmax; } voidout() { init(); System.out.println(findMax()); } } publicclassMain{ publicstaticvoidmain(Stringargs[])throwsIOException { intn,m,i; Stringstr[]; Dpdata; n=cin.nextInt(); m=cin.nextInt(); str=newString[n]; for(i=0;i { str[i]=cin.next(); } data=newDp(str,n,m); data.out(); } } 开关问题 Description(poj1830) 有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。 你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。 对于任意一个开关,最多只能进行一次开关操作。 你的任务是,计算有多少种可以达到指定状态的方法。 (不计开关操作的顺序) Input 输入第一行有一个数K,表示以下有K组测试数据。 每组测试数据的格式如下: 第一行一个数N(0 第二行N个0或者1的数,表示开始时N个开关状态。 第三行N个0或者1的数,表示操作结束后N个开关的状态。 接下来每行两个数IJ,表示如果操作第I个开关,第J个开关的状态也会变化。 每组数据以00结束。 Output 如果有可行方法,输出总数,否则输出“Oh,it'simpossible~! ! ”不包括引号 SampleInput 2 3 000 111 12 13 21 23 31 32 00 3 000 101 12 21 00 SampleOutput 4 Oh,it'simpossible~! ! Hint 第一组数据的说明: 一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3(不记顺序) /*高斯消元,然后根据消元后的矩阵得到答案,若有矛盾的行则无解 否则解的个数为2^kk为矩阵全为0的行数 */ importjava.io.BufferedReader; importjava.io.IOException; importjava.io.InputStreamReader; importjava.util.Arrays; importjava.util.StringTokenizer; classcin { staticBufferedReaderin=newBufferedReader(newInputStreamReader(System.in)); staticStringTokenizerst; staticintleave=0; staticintnextInt()throwsIOException { returnInteger.parseInt(next()); } staticStringnext()throwsIOException { while(leave==0) { st=newStringTokenizer(in.readLine()); leave=st.countTokens(); } leave--; returnst.nextToken(); } staticbooleanhasNext()throwsIOException { while(leave==0) { Stringtemp=in.readLine(); if(temp==null)returnfalse; st=newStringTokenizer(temp); leave=st.countTokens(); } returntrue; } } classGaus { inta[][],num; staticintM=2; Gaus(intm[][],intn) { a=m; num=n; } intmod(inta)//对M求余 { return(a%M+M)%M; } voidswap(intx,inty)//交换a[x],a[y] { inttemp[]; temp=a[x]; a[x]=a[y]; a[y]=temp; } voidchange()//矩阵变换 { inti,j,k,max; for(i=0;i { max=i; for(j=i+1;j { if(a[j][i]>a[max][i]) max=j; } if(a[max][i]==0)continue; swap(i,max); for(j=i+1;j { if(a[j][i]==0)continue; for(k=i+1;k<=num;k++) { a[j][k]=mod(a[j][k]*a[i][i]-a[i][k]*a[j][i]); } a[j][i]=0; } } } intnoUse()//返回全
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- POJ 经典 算法