当前位置:首页 >> 学科竞赛 >>

搜索的综合题


搜索的综合题

? 在数学分析、贪心策略和动态规划 中经常在局部环节上使用搜索
? 搜索不数学解析“相伴而行”

【GCD & LCM Inverse 】

【问题描述】给出两个正整数a和b,我们可以很容 易地计算a和b的最大公约数(the greatest common div isor (GCD

))和最小公倍数(the least common multiple (LCM))。但如果反其道而行之呢?也就是说,给出G CD和LCM,求a和b。 输入:输入包含多个测试用例,每个测试用例给出 两个正整数GCD和LCM。本题设定这两个数都小于 2^63。 输出:对每个测试用例,按升序输出a和b。如果有 多组解,输出最小的a+b那一对。

首先计算N= LCM/GCD。若N=1,则 满足题意的数字对为(GCD,LCM);否

则计算计算满足下述条件的数对(a,b):
LCM=lcm(a,b),GCD=gcd(a,b), a*b=LCM*GCD且a+b最小。

? 设a=t*gcd,b=lcm/t =n*gcd/t ,即a: b=t:n/t 。 显然,a+b最小,即为t+n/t 最小。t的计算方 法如下: ? 分解N的素因子式N=p1e1 *…*pkek,建立素因 子的次幂表a[],其中a[i]=piei (1≤i≤k)。 ? 然后通过调用递归程序dfs(0,1,n)计算满足 条件的t。

void dfs(i,t’ ,n){ //i为N的素因子次幂表a[]的指针, a与b的比率因 子为t’ , n为 lcm/gcd if(i==m+1){ //若a[]表分析完 if(minx==-1||(t’+n/t’ <minx)), //若未计算出a+b或a+b为目前最小, 则记下 minx= t’+n/ t’; t=t’; } return; //回溯 } dfs(i+1,t’ *a*i+,n); //a与b的比率因子为t’*a*i+,分析N的第i+1 个素因子次幂 dfs(i+1,t’ ,n); // a与b的比率因子为t’ ,分析N的第i+1个素因 子次幂 } 递归dfs(0,1,n)后得出t。若t2>n,则t=n/t。由此得出满足条件的 数对(t*GCD, LCM/t)。

?【 Color a Tree】
【问题描述】Bob对树的数据结构非常感兴趣,一棵树是 一个有向图,有一个特定的节点只有出度,被称为树的 “根”,从根到树的每个其他节点只有唯一的一条路径。 Bob打算用一只铅笔为树的所有的节点着色,一棵树有N 个节点,编号为1, 2, ..., N。假设对1个节点着色要用1个单 位时间,并且只有在对一个节点着色好了以后,他才可以 对另一个节点着色。此外,他只能在一个节点的父节点已 经被着色了以后,才能对这个节点着色。显然,Bob只能 首先对根进行着色。 每个节点有一个“着色费用因子”Ci。每个节点的着色费 用基于Ci和Bob完成这个节点的着色时间。起始时的时间 被设置为0,如果节点i的着色完成时间是Fi,那么节点i的 着色费用是Ci*Fi。

例如,一棵树有5个节点,如图1所示。每个节点的着色费 用因子是1, 2, 1, 2和4。Bob可以对这棵树按1, 3, 5, 2, 4的次 序着色,最小的总着色费用是33。

给出一棵树以及每个节点的着色费用因子,请您帮助Bob 找到对所有节点着色的可能的最小着色费用。 输入:输入包含若干测试用例,每个测试用例第一行给 出两个整数N和R (1 ≤ N ≤ 1000, 1 ≤ R ≤ N),其中N是一棵树 的节点数,R是根节点的节点编号。第二行给出N个整数, 第i个整数是Ci (1 ≤ Ci ≤ 500),表示节点i的着色费用因子。 接下来的N-1行每行给出两个用空格分开的节点编号V1和 V2,表示树的一条边的两个端点,V1是V2的父亲节点,每 条边仅出现一次,且所有的边都被列出。 N = 0和R = 0表示输入结束,程序不必处理。 输出:对每个测试用例,输出一行,给出Bob 对所有节点 着色的最小着色费用。 ?注: ? 试题来源:ACM Beijing 2004 ?在线测试:POJ 2054,ZOJ 2215,UVA 3138

1、由于染色是按照先父后子的顺序进行,因此先通过

dfs搜索计算每个节点的父指针。
2、染色过程看作是一个合并过程,父子边(k,x), 染色父亲k后才能染x,将节点x并入节点k。设now[i] 为合并后节点i的费用,即被合并到i的所有节点的费 用平均值;cnt[i]为节点i合并的节点数。初始时, now[i]=节点i的着色费用因子;cnt[i]=1(1≤i≤n)。 x染色后,节点k的费用和合并的节点数调整为

now[k]=(now[k]*cnt[k]+now[x]*cnt[x]) /(cnt[k]+cnt[x]),
cnt[k]=cnt[k]+cnt[x] 这样的合并过程进行n-1次。

贪心策略:每次合并在未染色的节点中选 费用(即now值)最大的节点先染色。
依次进行n-1次合并: 在根以外未被合并的节点中寻找费用最大的节点k,节点k 合并; 其父f和k进入染色顺序; 沿父指针寻找离k最近且还未被合并的节点f,即合并后k的 父节点; 调整now[f]和cnt[f]; 最后从根出发,沿染色顺序表计算Bob 对所有节点着色的最小 着色费用 ans= i * 染色顺序表中第 i 个节点的着色费用因子

?
i ?1

n

? const int maxN=1100;

? int
root,n,fa[maxN],l[maxN],next[maxN],cnt[maxN],c[maxN],e[max

N][maxN];
? //根为root;n为节点数;fa[]记录每个节点的父亲;next[]为

染色顺序表,x节点染色之后染色节点next[x];cnt[]记录每个
节点合并了多少个节点;c[]为节点的着色费用因子;e[][]为

树的邻接矩阵
? double now[maxN]; //记录合并之后每个节点的着色费用

? void init() //输入n个节点的着色费用因子和边信息,构造邻接矩 阵e[][] ? { ? ? ? ? ? ? ? } int x,y; memset(e,0,sizeof(e)); for (int i=1;i<=n;i++) scanf("%d",&c[i]); for (int i=1;i<n;i++) { scanf("%d%d",&x,&y); e[x][++e[x][0]]=y; e[y][++e[y][0]]=x;}

void dfs(int x) //计算树中每个节点的父指针 { int y; for (int i=1;i<=e[x][0];i++) //递归x的每个儿子, 将其父指针设为x { y=e[x][i]; if (fa[y]==0) { fa[y]=x;dfs(y);} } }

? void addedge(int x,int y) //确定x和 y的染色顺序,即y在x最近被染色 的树枝后被染色 ?{ ? while (next[x]) x=next[x]; ? next[x]=y; ?}

计算对所有节点着色的最小着色费用
memset(fa,0,sizeof(fa)); //每个节点的父指针初始化为空 fa[root]=-1; dfs(root); //遍历以root为根的树,确立父子关系 for (int i=1;i<=n;i++) now[i]=c[i]; //合并后每个节点的着色费用初 始化 bool flag[maxN]; //节点被合并的标志 int k,f;

double max;
//初始时,设置每个节点未被合并,染色的后继指针为空,合并 的节点数为1 memset(flag,1,sizeof(flag)); memset(next,0,sizeof(next)); for (int i=1;i<=n;i++) cnt[i]=1;

for (int i=1;i<n;i++)

//依次进行n-1次合并

{ max=0;

//在根以外未被合并的节点中寻找费用最大的节点k
//确定f和k的染色顺序

for (int j=1;j<=n;j++) if ( (j!=root)&&(flag[j])&&(max<now[j])) { max=now[j];k=j}; f=fa[k];addedge(f,k);

while (!flag[f]) f=fa[f]; //沿父指针寻找离k最近且还未被合并的节点f,即合 并后k的父节点
flag[k]=false; //设k节点合并标志 now[f]=(now[f]*cnt[f]+now[k]*cnt[k])/(cnt[f]+cnt[k]); //合并后f的着色费用为 合并到一起的所有节点的着色费用的平均值 cnt[f]+=cnt[k]; } int p=root,ans=0; //从根出发,沿染色顺序累计最小着色费用和 for (int i=1;i<=n;i++) { ans+=i*c[p];p=next[p]; } printf("%d\n",ans); //输出最小着色费用 //将k合并的节点数累计入f合并的节点数



引水入城

一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边 际的沙漠。该国的行政区划十分特殊,刚好构成一个 N行 M 列 的矩形,如上图所示,其中每个格子都代表一座城市,每座城 市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城 市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。 蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水 池中。因此,只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。 而输水站的功能则是通过输水管线利用高度落差,将湖水从高 处向低处输送。故一座城市能建造输水站的前提,是存在比它 海拔更高且拥有公共边的相邻城市,已经建有水利设施。

由于第 N 行的城市靠近沙漠,是该国的干旱区,所 以要求其中的每座城市都建有水利设施。那么,这个 要求能否满足呢?如果能,请计算最少建造几个蓄水 厂;如果不能,求干旱区中不可能建有水利设施的城 市数目。 【输入】 输入文件名为 flow.in。输入文件的每行中两 个数之间用一个空格隔开。输入的第一行是两个正整 数 N和 M,表示矩形的规模。 接下来 N行,每行 M 个正整数,依次代表每座城市的海拔高度。 【输出】 输出文件名为 flow.out。 输出有两行。如果 能满足要求,输出的第一行是整数 1,第二行是一个 整数,代表最少建造几个蓄水厂;如果不能满足要求, 输出的第一行是整数 0,第二行是一个整数,代表有 几座干旱区中的城市不可能建有水利设施。
19

思维方向
1、怎样计算第1行有哪些点的水能流到n行, 其中每个点通往n行的供水区间是什么? 2、若所有供水区间不能覆盖[1..m],则失

败;否则计算第1行至少哪些点通往n行的供
水区间能够覆盖[1..m]

BFS+DP算法
1、确定第1行中BFS的出发点

若上一次BFS的出发点为j,,则按照”由高到低”规则, j点可流遍

递减区间[j,k],而递增区间[k,p]可被p点的水所流遍,因此下一次 BFS的出发点为p。
分别从第1行的满足上述条件的点出发进行BFS:按照“从

高往低”的规则扩展,遇到没做标记的点就将它加入队列,并 做标记。最后统计第n行的m个点中没做标记的点数ans。

2、若ans>0,则说明有ans个干旱区必定不能有水利设施, 输出失败信息,否则说明第1行的m个点,通过“从高往低”的 规则能够到达第n行的m个点。 3、此时有一个结论:第1行的任何一个点,能到达的第n行 的点是连续的*(证明在之后给出),可使用类似记忆化搜索的 方式计算第1行每个点到达第n行的区间。设 L[j]表示(1,j)通过“从高往低”规则能扩展到的第n行的最 左侧的点为L[j]、最右侧的点为R[j], 即(1,j)到达第n的区间为 [L[j], R[j]]

设顶行的ck点原来可达底行的区间为*I’,j’+,现计算出ck可达底 行的点i和点j,且i≤i’,j’ ≤j。由于Ck可达第n行的区间是连续的, 因此Ck可达底行的区间调整为[I,j],即L[CK]=i,R[CK]=j。

4、问题就转化为给定m条线段[L[i],R[i]],问用最少几 条线段能覆盖[1,m],这是经典的DP(贪心)

设f[i]为覆盖[n,1]‥[n,i]的最少线段数。显然f[0]=0 由左而右递推n行的每一列i(1≤i≤m): ①在覆盖i+1列的所有线段中,计算右端点的最 大值R= max { R [ K ]} ; ②调整[i+1,R]区间的f值:f[k]=maxi+1≤k≤R { f[i]+1,f[k]} 最后得出的f[m]即为问题解。 时间复杂度:O(n*m)。
1? k ? m , L [ k ]? i ? 1

结论:任何一个点,能到达的第n排的点集是连 续的。

证明:A点能到达的点集在图中用灰色区域表示(不包括 D点)。 假设A点能到达的第n排的点不连续,其中点D无法到达, 由于第一排的m个点能够通过“从高往低”的规则到达第n排 所有点,故必定存在点B,A点不能到达,它能到达点D。此 时,B点到达D点的路径必定和A点能到达的点相交,设为C点, 那么此时A点可以通过A?C?D来到达D,与假设矛盾。 24

数据结构
const /*i方向上的水平增量为tx[i],垂直增量为ty[i]*/ tx:array [1..4] of longint=(0,0,1,-1); ty:array [1..4] of longint=(1,-1,0,0); var n,m,sum,x:longint; /*矩形规模为n*m;第n行中sum个城市有水利设施; 线段数为x*/ s:array [1..2000000] of record /*队列(存储坐标)或线段序列(第1行中点i到达 第n排的区间为[s[i].x,s[i].y])*/ x,y:longint; end; v:array [0..1000,0..1000] of boolean; /*(i,j)的搜索标志为v[i,j]*/ e:array [1..1000,0..1000] of longint; /*第1行中提供给(n,i)水源的蓄水厂 数为e[i,0],其中第j个蓄水厂的列位置为e[i,j]*/ h:array [0..1000,0..1000] of longint; /*(i,j)的海拔高度为h[i,j]*/ p,q:array[1..1000] of longint; /*第i条线段为[p[i],q[i]]*/ f:array [0..1000] of longint; /*覆盖[n,1]‥[n,i]的最少线段数为 f[i]*/

proc init; /*输入矩形规模和矩形中每座城市的海拔高度 */ var i,j:longint; { fillchar(h,sizeof(h),0); readln(n,m); /*输入矩形规模和矩形中每座城市的海拔 高度 */ for i←1 to n do for j←1 to m do read(h[i,j]); };/* init */ proc bfs(c:longint); /*计算(1,c)可以提供给第n行中哪些城 市水源*/ var p,q,i,ux,uy,ox,oy:longint; { fillchar(v,sizeof(v),0); p←1;q←1;/*队列的首尾指针初始化*/ s[1].x←1;s[1].y←c; v[1,c]←true;/*(1,c)入队,并标记*/

while p<=q do /*若队列非空,则按照“从高往低”规则扩展*/ { if s[p].x=n /*若队首元素位于n行,则(n,e[s[p].y)增加一 个供水源,水源由(1,c)的蓄水池提供*/ then{ inc(e[s[p].y,0]);e[s[p].y,e[s[p].y,0]]←c };/*then*/ ux←s[p].x;uy←s[p].y; /*搜索队首元素的4个相邻方向中未 标记、且海拔低的相邻位置(ox,oy),标记该位置并入队*/ for i←1 to 4 do { ox←ux+tx[i];oy←uy+ty[i]; if (ox=0) or (ox=n+1) or (oy=0) or (oy=m+1)or(h[ox,o y]>=h[ux,uy] ) or(v[ox,oy]) then continue; v[ox,oy]←true; inc(q);s[q].x←ox;s[q].y←oy };/*for*/ inc(p);/*出队*/ };/*while*/ };/* bfs */

proc run; var i,j,k,max:longint; { fillchar(s,sizeof(s),0); for i←1 to m do { s[i].x←maxlongint;s[i].y←0};/*for*/ for i←1 to m do /*搜索第n行的每一列*/ for j←1 to e[i,0] do /*搜索第1行中供给(n,i)水源的所有蓄水厂*/ { if i<s[e[i,j]].x then s[e[i,j]].x←i;/*调整蓄水厂j的供水区间*/ if i>s[e[i,j]].y then s[e[i,j]].y←i };/*for*/ x←0; /*线段数初始化*/ for i←1 to m do/*若(1,i)能够供给n行水,则增加一条线段,供 水区间的左右指针存入p和q序列*/ if (s[i].x<maxlongint) and (s[i].y>0) then{ inc(x);p[x]←s[i].x; q[x]←s[i].y };/*then*/ 以左指针(p)为关键字排列区间(p和q);

计算和输出第1行最少建造的蓄水厂数

for i←0 to m do f[i]←maxlongint;

f[0]←0;
for i←0 to m do { max←i; /*在覆盖i+1列的所有线段中,计算右端点的最大值max*/

for j←1 to x do if (p[j]<=i+1) and (q[j]>max) then max←q[j]; for k←i+1 to max do /*调整[i+1,max]区间的f值*/

if f[i]+1<f[k] then f[k]←f[i]+1; };/*for*/

writeln(1);
writeln(f[m]);

/*输出成功信息和最少建造的蓄水厂数*/

};/* run */

proc work; var i,j:longint; { fillchar(e,sizeof(e),0); i←1;j←1; while true do { while h[i,j]<h[i,j-1] do inc(j); /*“从高往低”的规 则计算第1个丌能接受左方城市供水的城市j*/ if j>m then break; /*若第1行所有城市 能接受供水,则退出循环*/ while h[i,j]<h[i,j+1] do inc(j); /*继续搜索递增区 间的尾指针j*/ bfs(j); /*计算(1,j)可以提供给第n行中哪些城市水源*/ inc(j); /*分析第1行的下一列*/ };/*while*/

主算法

sum←0; for i←1 to m do if e[i,0]>0 then inc(sum);/* 统计第n行中有水利设施的城市数*/ if sum<m /*若有水利设施的城市数丌足m个, 则返回失败信息和缺乏水利设施的城市数*/ then { writeln(0); writeln(m-sum); close(input);close(output);/*关闭输 入输出文件后退出程序*/ halt };/*then*/ run;/*计算和输出第1行最少建造的蓄水厂数*/ };/* work */

主程序
{ assign(input,'flow.in');reset(input);/*输入输出文件 初始化*/ assign(output,'flow.out');rewrite(output); init; /*输入信息*/ work; /*主算法*/ close(input);close(output); /*关闭输入输出文件*/ }./*main*/


相关文章:
搜索题目
广度优先搜索 【上机练习】 上机练习】 7,细胞(cell.pas) 细胞(cell.pas) ...最少转弯问题【问题描述】 题描述】 给出一张地图,这张地图被分为 n×m(n...
文献检索试题及答案
一、填空题: 1、 文献按其加工深度不同可以划分为...搜索软件说明书 C. 搜索科技期刊 D. 搜索报刊 35...对其内容进行分析、研究、综合、整理而编写出来的文献...
综合测试题
综合测试题_从业资格考试_资格考试/认证_教育专区。...判断题......错 6. Google 图书搜索的检索语法支持逻辑算符“AND”。错 7. Google 图书搜索可以用减号...
2015年信息检索与利用试题及答案
信息检索与利用试卷 1、分别列举搜索引擎、馆藏检索...必须综合考虑检索系统的特点、 收录的学科范围、各...从而开拓思路,发现问 题、深入研究、获得知识的创新...
信息检索考题汇总
· 《中国期刊网》的“主题”字段表示同时搜索文献的___ 题名/摘要/关键词...航空发动机用钛合金盘模锻件规范,中国航空综合技术研究所, 2011, 该篇文献的...
网络信息检索试题及答案
A、专科型 B、专题型 C、综合型 D、混合型 C ...A、著作途径 B、主题途径 C、号码途径 D、题名...能认识到何时需要信息,有效地 搜索、评估和使用所需...
网络信息检索试题及答案
A、专科型 B、专题型 C、综合型 D、混合型 C ...A、著作途径 B、主题途径 C、号码途径 D、题名...32、在百度搜索引擎的高级搜索页面中, 有以下 4 ...
4.搜索引擎推广试题4
在线互动式文档分享平台,在这里,您可以和千万网友分享自己手中的文档,全文阅读其他用户的文档,同时,也可以利用分享文档获取的积分下载文档
信息检索题目(含答案)
多选题(每题 2 分,共 5 题,10 分) 46.CASHL 收藏的文献类型有(A、B、...(对) 正确 94.搜索引擎按其收录资源的学科范围不同可划分为:综合搜索引擎和...
文献检索试题和答案
( 33.利用 Google 搜索引擎查找网络信息资源时,如果只希望获得关于“职业生涯...其中内容特征途径有:_分类途径_和_ 主题途径_;外表特征途径有_题名途径_和_...
更多相关标签:
中考圆的综合题 | 二次函数与圆的综合题 | 中考数学圆的综合题 | 圆的综合题 | 二次函数的综合题 | 2016中考圆的综合题 | 一次函数的综合题 | 抛物线与圆的综合题 |