[PA 2021] Butelki

一道神秘题目，根本会不了一点点。

从暴力入手，如果打一个正常的 bfs 会发现跑的莫名其妙的快。

这是因为状态数是非常小的，我们进行一次操作之后，必然有一个是满的或空的。

我们假设这个空的或者满的是第一个。

那么对应的，剩下的总量是确定的，即 A+B+C 或 B+C。

所以我们的总量是很小的。

代码↓

点击查看代码

#include <bits/stdc++.h>
using namespace std;
const int MN=1e5+115;
const int inf=0x3f3f3f3f;
int A, B, C, a, b, c, ans[MN];
map <pair<int,int>,bool> vis;
struct State{int x, y, z, step;
};
void update(int x, int y, int z, int step){if(x>=0&&x<=A&&y>=0&&y<=B&&z>=0&&z<=C){ans[x]=min(ans[x],step);ans[y]=min(ans[y],step);ans[z]=min(ans[z],step);}
}
void Solve(){for(int i=0; i<MN; ++i) ans[i]=inf;queue <State> q;q.push({a,b,c,0});vis[{a,b}]=true;//vis[a][b]=true;while(!q.empty()){State now=q.front(); q.pop();int x=now.x, y=now.y, z=now.z, step=now.step;update(x,y,z,step);if(x>0&&y<B){int to=min(x,B-y);int nx=x-to, ny=y+to, nz=z;if(!vis[{nx,ny}]){vis[{nx,ny}]=true;q.push({nx,ny,nz,step+1});}}if(x>0&&z<C){int to=min(x,C-z);int nx=x-to, ny=y, nz=z+to;if(!vis[{nx,ny}]){vis[{nx,ny}]=true;q.push({nx,ny,nz,step+1});}}if(y>0&&x<A){int to=min(y,A-x);int nx=x+to, ny=y-to, nz=z;if(!vis[{nx,ny}]){vis[{nx,ny}]=true;q.push({nx,ny,nz,step+1});}}if(y>0&&z<C){int to=min(y,C-z);int nx=x, ny=y-to, nz=z+to;if(!vis[{nx,ny}]){vis[{nx,ny}]=true;q.push({nx,ny,nz,step+1});}}if(z>0&&x<A){int to=min(z, A-x);int nx=x+to, ny=y, nz=z-to;if(!vis[{nx,ny}]){vis[{nx,ny}]=true;q.push({nx,ny,nz,step+1});}}if(z>0&&y<B){int to=min(z,B-y);int nx=x, ny=y+to, nz=z-to;if(!vis[{nx,ny}]){vis[{nx,ny}]=true;q.push({nx,ny,nz,step+1});}}		}for(int i=0; i<=C; ++i){if(ans[i]==inf) cout<<-1<<" ";else cout<<ans[i]<<" ";}return;
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>A>>B>>C>>a>>b>>c;Solve();return 0;
}