目录
????????G - Tempter of the Bone
A - Shuffle'm Up
思路：
-
考察点：搜索，BFS，规律，STL
B - Prime Path
思路：
-
考察点：搜索，BFS，素数筛
C - Function Run Fun
题意：
设定函数w(a, b, c)，其值为：
w(a, b, c)==1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a<=0||b<=0||c<=0
w(a, b, c)==w(20, 20, 20)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a>20||b>20||c>20
w(a, b, c)==w(a, b, c-1)+w(a, b-1, c-1)-w(a, b-1, c)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a<b&&b<c
w(a, b, c)==w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1, b-1, c-1)? ? ? ? ? ?其他情况
思路：
正如题意一样，苍白而暴力。
递归求就完事了。
不过容易超时，所以要想一个办法。
如果w(a, b, c)与w(a, b-1, c)中间都需要计算w(2, 3, 4)，我们只需要在第一次算的时候把w(2, 3, 4)值先存起来，下一次需要的时候直接用就可以了。
记忆化搜索。
-
?考察点：记忆化搜索，递归
代码：
#include<iostream>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
int value[25][25][25];
int dfs(int a,int b,int c)
{
if(a<=0||b<=0||c<=0)
return 1;
if(a>20||b>20||c>20)
return dfs(20,20,20);
if(value[a][b][c])
return value[a][b][c];
if(a<b&&b<c)
value[a][b][c]=dfs(a,b,c-1)+dfs(a,b-1,c-1)-dfs(a,b-1,c);
else
value[a][b][c]=dfs(a-1,b,c)+dfs(a-1,b-1,c)+dfs(a-1,b,c-1)-dfs(a-1,b-1,c-1);
//cout<<"value["<<a<<"]["<<b<<"]["<<c<<"]="<<value[a][b][c]<<endl;
return value[a][b][c];
}
int main()
{
int a,b,c;
memset(value,0,sizeof(value));
while(cin>>a>>b>>c){
if(a==-1&&b==-1&&c==-1) break;
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<dfs(a,b,c)<<endl;
}
}
D - 蜘蛛牌
题意：
中题你我？懂？
思路：
一个简单的DFS，每次都从最小的牌开始处理，存储方式：
pos[X]==i pos[X]:纸牌X的位置-
考察点：搜索，DFS，思维
代码：
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,t,sx,sy,ex,ey,flag;
bool vis[20];
int pos[20];
int step;
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
void dfs(int n,int n_step)
{
if(n==9)
{
if(n_step<step)
step=n_step;
return;
}
for(int i=1; i<=10; i++)
{
if(!vis[i])
{
for(int j=i+1; j<=10; j++)
{
if(!vis[j])
{
int new_s=n_step+abs(pos[i]-pos[j]);
if(new_s>=step)
break;
vis[i]=true;
dfs(n+1,new_s);
vis[i]=false;
break;
}
}
}
}
}
int main()
{
int t,x;
cin>>t;
while(t--)
{
for(int i=0; i<10; i++)
{
cin>>x;
pos[x]=i;
}
memset(vis,false,sizeof(vis));
step=inf;
dfs(0,0);
cout<<step<<endl;
}
}E - Nightmare Ⅱ
题意：
小E梦到他和他女朋友被困在一个迷宫里，迷宫里‘ . ’代表路，‘ M ’代表小E，‘ G ’代表他的女友，‘ Z ’代表鬼魂（有两个），‘ X ’代表墙体。小E每秒可以移动3格，鬼魂移动2格（但是会穿墙），女友只能移动一格。
请问小E能和女友安全相聚吗？
思路：
真的是，这快到七夕了，连你个搜索题也来虐狗？
打**，上票！寄！
首先鬼魂先手行动，在k秒过后，所有与鬼魂距离不超过2*k的格子都将被鬼魂占领。
利用这一点，每一次计算人与鬼魂的曼哈顿距离寻找当前可能性。
其次，小E的3格不一定是直走，所以我们干脆就用3次bfs，每次走一格，模拟小E的路线。
同时BFS女友的路线，一旦两者有交汇之处说明可以相遇，输出时间。
-
考察点：搜索，BFS，曼哈顿距离，数学，思维
-
坑点：如何判定是否被鬼魂抓到
代码：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y;
node(int xx=0,int yy=0):x(xx),y(yy) {}
};
node boy,girl,ghost[2];
int t,n,m,bx,by,gx,gy,timet;
int gx1,gx2,gy1,gy2;
bool flag;
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
char mp[805][805];
int vis[805][805];
queue<node> q[2]; //q[0]:男孩的bfs，q[1]:女孩的bfs
bool check(int x,int y,int k)
{
if(x < 1 || x > n || y < 1 || y > m)
return 0;
if(mp[x][y] == 'X')
return 0;
if(abs(x - ghost[0].x) + abs(y - ghost[0].y) <= 2*k)
return 0;
if(abs(x - ghost[1].x) + abs(y - ghost[1].y) <= 2*k)
return 0;
return 1;
}
bool bfs(int x)
{
int len = q[x].size();
while(len--)
{
node tmp = q[x].front();
q[x].pop();
if(!check(tmp.x,tmp.y,timet))
continue;
for(int i=0; i<4; i++)
{
int xx = tmp.x + dx[i];
int yy = tmp.y + dy[i];
if(check(xx,yy,timet))
{
if(vis[xx][yy] && (vis[xx][yy]&1) != ((x+2)&1))
return true;
else if(!vis[xx][yy]){
q[x].push(node(xx,yy));
vis[xx][yy] = x+2;
}
}
}
}
return false;
}
int solve()
{
while(!q[0].empty())
q[0].pop();
while(!q[1].empty())
q[1].pop();
q[0].push(boy);
q[1].push(girl);
vis[boy.x][boy.y] = 2;
vis[girl.x][girl.y] = 3;
timet = 0;
while(!q[0].empty() || !q[1].empty())
{
timet++;
if(bfs(0))
return timet;
if(bfs(0))
return timet;
if(bfs(0))
return timet;
if(bfs(1))
return timet;
}
return -1;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int cnt = 0;
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
{
scanf("%s",mp[i]+1);
for(int j=1; j<=m; j++)
{
if(mp[i][j] == 'M')
boy = node(i,j);
else if(mp[i][j] == 'G')
girl = node(i,j);
else if(mp[i][j] == 'Z')
ghost[cnt++] = node(i,j);
}
}
cout<<solve()<<endl;
}
}
F - Color the ball
题意：
现在有n个气球，每次选中一个区间进行染色。
最后问每个气球被染了几次色？
思路：
差分数组模板题。
-
考察点：差分数组，枚举
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int a[maxn];
int main(){
int n;
while(cin>>n&&n){
memset(a,0,sizeof(a));
int x,y;
for(int i=0;i<n;i++){
cin>>x>>y;
a[x]++;
a[y+1]--;
}
int sum=0;
for(int i=1;i<=n;i++){
sum+=a[i];
if(i!=1) cout<<" ";
cout<<sum;
}
cout<<endl;
}
}
G - Tempter of the Bone
题意：
狗狗被困在n*m的迷宫中，S代表狗狗，D代表出口，狗狗必须在T时刻到达出口。
问狗狗是否可以逃出迷宫。
思路：
DFS，但是需要剪枝。
-
考察点：搜索，DFS，奇偶剪枝
代码：
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
int n,m,t,sx,sy,ex,ey,flag;
string mp[100];
bool vis[100][100];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void dfs(int x,int y,int num) //(x,y) num
{
//cout<<x<<" "<<y<<endl;
if(flag) return; //有答案
if(x==ex&&y==ey)
{
if(num==t) flag=1;
return;
}
int dis=(t-num)-(abs(ex-x)+abs(ey-y)); //曼哈顿距离
if(dis<0||dis%2) return; //当前步数已无法满足最理想状态
for(int i=0;i<4;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=m) continue;
if(mp[xx][yy]=='X') continue;
if(!vis[xx][yy]){
vis[xx][yy]=true;
dfs(xx,yy,num+1);
vis[xx][yy]=false;
}
}
}
int main()
{
while(cin>>n>>m>>t&&n&&m&&t)
{
for(int i=0; i<n; i++)
cin>>mp[i];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(mp[i][j]=='S')
sx=i,sy=j;
if(mp[i][j]=='D')
ex=i,ey=j;
}
flag=0;
memset(vis,false,sizeof(vis));
vis[sx][sy]=true;
dfs(sx,sy,0);
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}