2014暑假集训搜索专题

2024-09-07 19:18
文章标签 搜索 集训 暑假 专题 2014

本文主要是介绍2014暑假集训搜索专题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A - 漫步校园
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit

Status
Description
LL最近沉迷于AC不能自拔,每天寝室、机房两点一线。由于长时间坐在电脑边,缺乏运动。他决定充分利用每次从寝室到机房的时间,在校园里散散步。整个HDU校园呈方形布局,可划分为n*n个小方格,代表各个区域。例如LL居住的18号宿舍位于校园的西北角,即方格(1,1)代表的地方,而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择,LL希望每次的散步路线都不一样。另外,他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是,所有满足要求的路线一共有多少条。你能告诉他吗?

Input
每组测试数据的第一行为n(2=<n<=50),接下来的n行每行有n个数,代表经过每个区域所花的时间t(0<t<=50)(由于寝室与机房均在三楼,故起点与终点也得费时)。

Output
针对每组测试数据,输出总的路线数(小于2^63)。

Sample Input
3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1

Sample Output
1

6

思路:一开始我是想广搜n点,然后在进行一次dfs,但是TLE了。。。最后根据别人的思路,想出来一次bfs就可以求出每个点到终点的最短距离。

具体做法感觉用到了点动态规划的思想,从终点开始算,用cost数组记录每个点到终点所需要的最少花费,每一次拿前一个点的cost值和当前点mp值相加,与当前点的cost比较。

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
int n;
int mp[51][51];
int visit[51][51];
long long sum;
int dir[4][2] ={{0,-1},{0,1},{-1,0},{1,0} };
int cost[100][100];
long long  road_sum[51][51];
long long  dfs(int x,int y)
{
/*if(x == n && y == n) {sum += 1;return;}
for(int i = 0; i < 4 ; i++)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx > 0 && yy > 0 && xx <= n && yy <= n && !visit[xx][yy] &&
cost[xx][yy] < cost[x][y])
{
visit[xx][yy] = 1;
dfs(xx,yy);
visit[xx][yy] = 0;
}
}*/
if(road_sum[x][y] > 0) return road_sum[x][y];
if(x == n && y == n) return 1;
for(int i = 0; i < 4 ; i++)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx > 0 && yy > 0 && xx <= n && yy <= n &&
cost[xx][yy] < cost[x][y])
{
road_sum[x][y] += dfs(xx,yy);
}
}
return road_sum[x][y];
}
struct node
{
int x,y;
node(int i,int j) : x(i),y(j){}
node(){}
};
void  bfs()
{
int temp;
memset(visit,0,sizeof(visit));
queue<node> m;
m.push(node(n,n));//想想为什么从终点开始搜呢?因为只有终点的cost一开始就是确定的,从确定的点搜一次bfs即可
cost[n][n] = mp[n][n];
while( !m.empty() )
{
node r = m.front();
m.pop();
for(int i = 0; i < 4; i++)
{
int x = dir[i][0] +r.x;
int y = dir[i][1] +r.y;
if(x > 0 && y > 0&& x <= n && y <= n)
{
temp = cost[r.x][r.y] + mp[x][y]; //核心代码,有点动态规划思想
if(cost[x][y] == -1 || temp < cost[x][y])//cost等于-代表这个点第一次经过
{
m.push(node(x,y));
cost[x][y] = temp;
}
}
}
}
}
int main()
{
while(cin>>n)
{
sum = 0;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1; j<=n; j++)
{
cin>>mp[i][j];
cost[i][j] = -1;
}
}
bfs();
memset(visit,0,sizeof(visit));
memset(road_sum,0,sizeof(road_sum));
dfs(1,1);
cout<<road_sum[1][1]<<endl;
}
return 0;
}



hdu1072

C - Nightmare
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit

Status
Description
Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.

Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.

Here are some rules:
1. We can assume the labyrinth is a 2 array.
2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.

Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth.
There are five integers which indicate the different type of area in the labyrinth:
0: The area is a wall, Ignatius should not walk on it.
1: The area contains nothing, Ignatius can walk on it.
2: Ignatius' start position, Ignatius starts his escape from this position.
3: The exit of the labyrinth, Ignatius' target position.
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.

Output
For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.

Sample Input
3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1

Sample Output
4
-1
13

题意:2代表起点,3代表终点,0代表墙,1可以走,4代表可以重置炸弹时间,炸弹时间是6秒,求炸弹爆炸前能走到终点的最短时间,如果走不出去输出-1

思路:一开始我用visit数组标记已走过的路程,后来发现不行,因为有些点可以重复走,要重置炸弹嘛。。。
但是问题又来了,不标记bfs不就跳不出去吗?然后,你想一想,为什么路会重复走?因为走过之后再走这个点,必定这个点的时候炸弹的时间已经被重置过,说明时间延长了,所以如果第二次走这点比第一次走这点事炸弹的时间延长了那么就可以走,否则不可以走,利用这个标记即可

#include <iostream>
#include <queue>
using namespace std;
int mp[10][10];
bool visit[10][10];
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1} };
int n,m;
int mark[10][10];//标记炸弹剩余时间
struct node
{
int x,y,time,cent;//time是炸弹剩余时间,cent是已走过的时间
node(int i,int j,int k,int p):x(i),y(j),time(k),cent(p){}
node(){}
};
bool jugde(int x,int y)
{
if(x <= 0 || x > n || y <= 0 || y >m)
return false;
return true;
}
int bfs(int x1,int y1,int x2,int y2)
{
queue<node> m;
m.push(node(x1,y1,6,0));
mark[x1][y1] = 6;
while( !m.empty() )
{
node r = m.front();
m.pop();
for(int i = 0; i < 4; i++)
{
int x = dir[i][0] +r.x;
int y = dir[i][1] + r.y;
if(jugde(x,y)  && mp[x][y] != 0 && r.time-1>0 && mark[x][y] < r.time - 1)//mark[x][y]是上一次走过该点炸弹的时间
{
visit[x][y] = 1;
if(mp[x][y] == 4)
{
m.push(node(x,y,6,r.cent + 1));
mark[x][y] = 6;
}
else {
if(x == x2 && y == y2 )
{
return r.cent+1;
}
m.push(node(x,y,r.time - 1,r.cent+1));
mark[x][y] = r.time - 1;
}
}
}
}
return -1;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
int x1,x2,y1,y2;
for(int i = 1 ; i <= n; i++)
{
for(int j = 1; j <= m ; j++)
{
cin>>mp[i][j];
if(mp[i][j] == 2)
{
x1 = i;
y1 = j;
}
if(mp[i][j] == 3)
{
x2 = i;
y2 = j;
}
mark[i][j] = 0;
}
}
int ans = bfs(x1,y1,x2,y2);
cout<<ans<<endl;
}
}

E - Paid Roads
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit

Status
Description
A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city ai to city bi:

in advance, in a city ci (which may or may not be the same as ai);
after the travel, in the city bi.
The payment is Pi in the first case and Ri in the second case.

Write a program to find a minimal-cost route from the city 1 to the city N.

Input
The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of ai, bi, ci, Pi, Ri (1 ≤ i ≤ m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ Pi , Ri ≤ 100, Pi ≤ Ri (1 ≤ i ≤ m).

Output
The first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word ‘impossible’.

Sample Input
4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50
Sample Output
110

题意:有n个点,求1——n点花费最少,如果a到b事先走过c则花费p,否则花费r,问最少花费

思路:这又是点可以重复走的题,那么怎么标记跳出dfs呢?每个点只能重复走的上线时m/2次,多了就会形成环()

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int visit[11];
int n,m,Mincost;
struct node
{
int a,b,c,p,r;
}road[11];
void dfs(int a, int free)
{
if(a == n && Mincost > free)
{
Mincost = free;
}
for(int i = 1; i <= m ; i++)
{
if(a == road[i].a && visit[road[i].b] < m/2)
{
visit[road[i].b]++;
if(visit[road[i].c])
{
dfs(road[i].b,free+road[i].p);
}
else dfs(road[i].b,free+road[i].r);
visit[road[i].b] -- ;
}
}
return;
}
int main()
{
while(cin>>n>>m)
{
memset(visit,0,sizeof(visit));
visit[1]=1; 
Mincost=2000;
for(int i=1;i<=m;i++)
{
cin>>road[i].a>>road[i].b>>road[i].c>>road[i].p>>road[i].r;
}
dfs(1,0);
if(Mincost==2000)
cout<<"impossible"<<endl;
else
cout<<Mincost<<endl;
}
return 0;
}
F - USACO ORZ
Time Limit:1500MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit

Status
Description
Like everyone, cows enjoy variety. Their current fancy is new shapes for pastures. The old rectangular shapes are out of favor; new geometries are the favorite.
I. M. Hei, the lead cow pasture architect, is in charge of creating a triangular pasture surrounded by nice white fence rails. She is supplied with N fence segments and must arrange them into a triangular pasture. Ms. Hei must use all the rails to create three sides of non-zero length. Calculating the number of different kinds of pastures, she can build that enclosed with all fence segments.
Two pastures look different if at least one side of both pastures has different lengths, and each pasture should not be degeneration.

Input
The first line is an integer T(T<=15) indicating the number of test cases.
The first line of each test case contains an integer N. (1 <= N <= 15)
The next line contains N integers li indicating the length of each fence segment. (1 <= li <= 10000)

Output
For each test case, output one integer indicating the number of different pastures.

Sample Input
1
3
2 3 4

Sample Output
1


题意:给出n个数字,求全部用上它们,能够组成多少个非全等三角形,记住可以两个数字加起来和另外两个构成三角形
思路:利用set的唯一性,将每对a,b,c存入set,而且默认a<=b<=c,这样相当于一次减枝。。。然后利用dfs爆搜
#include <iostream>
#include <set>
using namespace std;
int n;
int save[30];
set<__int64> se;
void dfs(int a, int b, int c, int num)
{
if(num == n)
{
if(a > b || b > c || a > c)
return;
if(a && b && c && a + b > c)
{
se.insert(a + b*1000000+ c*10000000);//这里要确保值不一样,b,和c要乘以足够大的数,不然会WA。。。
}
return;
}
dfs(a + save[num+1], b ,c ,num+1);
dfs(a,b+save[num+1],c,num+1);
dfs(a,b,c + save[num+1], num+1);
}
int main()
{
int T;
cin >>T;
while(T--)
{
cin >> n;
for(int i = 1; i <= n ; i++)
cin>> save[i];
se.clear();
dfs(0,0,0,0);
cout<<se.size()<<endl;
}
return 0;
}



Hdu4227

XCOM-Enemy Unknown是一款很好玩很经典的策略游戏.

在游戏中,由于未知的敌人--外星人入侵,你团结了世界各大国家进行抵抗.



随着游戏进展,会有很多的外星人进攻事件.每次进攻外星人会选择3个国家攻击,作为联盟的指挥者,你要安排有限的联盟军去支援其中一个国家,抵抗进攻这个国家的外星人.




战斗胜利之后这个被支援的国家恐慌值就会-2点(恐慌值最少减为1),而其他两个未被支援的国家恐慌值就会+2点,同时和这两个国家在相同大洲的其他国家恐慌值也会+1点.
当一个国家的恐慌值超过5点,这个国家就会对联盟失去信心从而退出联盟.
现在给你外星人将会进攻的地点,问你最多能在不失去任何一个国家信任的情况下抵挡多少次外星人的进攻.

Input
第一行有一个整数T代表接下来有T组数据
每组数据第一行是三个整数,n,m,k分别代表联盟国家的个数,大洲的个数,外星人的进攻次数.
第二行是n个数字代表各个国家所属的大洲(大洲序号从0到m-1)
第三行是n个数字代表各个国家初始的恐慌值
接下去k行代表外星人进攻
每行有三个数字,表示该次外星人进攻的国家(国家序号从0到n-1)

[Technical Specification]
0<T<=100
8<n<=16
2<m<=5
0<k<=100
0<初始恐慌值<=5
每个州至少有三个国家
每次外星人进攻一定发生在不同州的三个国家

Output
首先输出case数(见sample),接着输出在不失去任何一个国家的情况下能抵挡外星人进攻最多的次数.

Sample Input
1
9 3 2
0 0 0 1 1 1 2 2 2
3 3 3 3 3 3 3 3 3
0 3 6
0 3 6

Sample Output
Case #1: 1

Hint
第一次如果选择了0,那么3和6的恐慌值就会增加到5,第二次不管怎么选择,3和6总会有一个超过5.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n,m,k;
int st[20],fear[20];
vector<int>myv[6];
struct Node
{
int a[3];
}fi[110];
bool flag;
int ans;
void dfs(int cur,int *afr)
{
if(flag)
return ;
for(int i=0;i<n;i++)
{
if(afr[i]>5) //超过5,说明上一次已经不行了,所以为cur-2
{
ans=max(cur-2,ans);
return ;
}
}
if(cur>k) //能够抵抗所有的攻击
{
flag=true;
ans=k;
return ;
}
int tmp[20];
for(int i=0;i<3;i++) //选择保护的国家
{
for(int j=0;j<n;j++)
tmp[j]=afr[j];
tmp[fi[cur].a[i]]-=2; //保护国家恐惧值减少2
if(tmp[fi[cur].a[i]]<1)
tmp[fi[cur].a[i]]=1;
for(int j=1;j<=2;j++) //处理其他两个国家
{
int k=(i+j)%3;
int sta=st[fi[cur].a[k]];
for(int p=0;p<myv[sta].size();p++)
{
tmp[myv[sta][p]]+=1;
}
tmp[fi[cur].a[k]]++;
}
dfs(cur+1,tmp);
}
}
int main()
{
int t;
scanf("%d",&t);
for(int ca=1;ca<=t;ca++)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
myv[i].clear();
for(int i=0;i<n;i++)
{
scanf("%d",&st[i]); //所在的洲
myv[st[i]].push_back(i); //洲中所有的国家
}
for(int i=0;i<n;i++)
scanf("%d",&fear[i]); //每个国家的恐惧值
for(int i=1;i<=k;i++)
for(int j=0;j<3;j++)
scanf("%d",&fi[i].a[j]); //外星人攻击的国家
ans=0;
flag=false;
dfs(1,fear);
printf("Case #%d: %d\n",ca,ans);
}
return 0;
}





这篇关于2014暑假集训搜索专题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145921

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;