电商网站开发计划,手机网店开店网站,安徽池州做企业网站,公司网站建设推荐乐云seoproblem
luogu-P3342
solution
你感觉这道题没考什么#xff0c;又感觉考了什么
通过样例以及题面#xff0c;我们并未获取到『立方体每个小方块的编号是按一定规则命名』的信息。
也就是说#xff0c;我们需要通过输入的每个小方块相邻的编号的信息来建出这个立方体的…problem
luogu-P3342
solution
你感觉这道题没考什么又感觉考了什么
通过样例以及题面我们并未获取到『立方体每个小方块的编号是按一定规则命名』的信息。
也就是说我们需要通过输入的每个小方块相邻的编号的信息来建出这个立方体的坐标系。
我的做法较暴力但不用思考太多简单易上手。你值得拥有 首先我们先随便找一个三度点只有三个水晶和该水晶有公共面钦定为 (1,1,1)(1,1,1)(1,1,1)。 然后以这个点 bfs\text{bfs}bfs 搜得到每个点的距离我们记为 dis0dis_0dis0。 其次我们再随便找一个与上一个点距离恰好为 2n−22n-22n−2 的点即 dis0(i)2n−2dis_0(i)2n-2dis0(i)2n−2钦定为 (n,n,1)(n,n,1)(n,n,1)。 然后以这个点 bfs\text{bfs}bfs 搜得到每个点的距离我们记为 dis1dis_1dis1。 接着我们仍随便找一个与上两个点距离恰都为 n−1n-1n−1 的点即 dis0(i)dis1(i)n−1dis_0(i)dis_1(i)n-1dis0(i)dis1(i)n−1钦定为 (n,1,1)(n,1,1)(n,1,1)。 然后以这个点 bfs\text{bfs}bfs 搜得到每个点的距离我们记为 dis2dis_2dis2。
这里的距离指的是曼哈顿距离 x,y,zx,y,zx,y,z 三维坐标差的绝对值之和。
考虑小方块 iii 的距离信息点对 (dis1(i)−dis0(i),dis2(i)−dis0(i))\Big(dis_1(i)-dis_0(i),dis_2(i)-dis_0(i)\Big)(dis1(i)−dis0(i),dis2(i)−dis0(i))。
observation1:\text{observation1}:observation1: 该点对与 iii 的真正的 zzz 坐标无关。
observation2:\text{observation2}:observation2: 该点对与小方块的真正 (x,y)(x,y)(x,y) 坐标存在一一对应关系。这只能自己臆想了 而 dis0(i)(x,y,z)↔(1,1,1)dis_0(i)(x,y,z)\leftrightarrow (1,1,1)dis0(i)(x,y,z)↔(1,1,1)所以我们可以选择通过 dis0(i)dis_0(i)dis0(i) 与已经求出的 x,yx,yx,y 来推出小方块的 zzz 坐标。
最后只用 dfs\text{dfs}dfs 暴搜枚举每个特殊发光小水晶扩散的方向O(6n)O(6^n)O(6n)。
然后 check\text{check}check 沿着该方向枚举一路上的水晶用 visvisvis 标记是否已经访问过了非第一次访问不计入发光贡献。
最后清空 vis\text{vis}vis 数组也是按照方向清空。不然就是 O(a3)O(a^3)O(a3) 的复杂度了。
时间复杂度 O(6na)O(6^na)O(6na)。
code
#include bits/stdc.h
using namespace std;
#define maxn 400000
#define MAX 150
struct node { int x, y, z; }pos[MAX 2][MAX 2];
vector int G[maxn];
vector node NB;
int g[maxn], dir[maxn];
int dis[3][maxn];
int vis[MAX][MAX][MAX], val[MAX][MAX][MAX];
int Min 1e9, Max -1e9, n, m;
queue int q;void bfs( int s, int *dis ) {dis[s] 0; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int v : G[u] ) if( dis[v] dis[u] 1 ) dis[v] dis[u] 1, q.push( v );}
}void calc() {int sum 0;for( int k 0;k NB.size();k ) {int x NB[k].x, y NB[k].y, z NB[k].z;switch( dir[k] ) {case 0 : {for( int i 1;i x;i )if( ! vis[i][y][z] )vis[i][y][z] 1, sum val[i][y][z];break;}case 1 : {for( int i x;i n;i )if( ! vis[i][y][z] )vis[i][y][z] 1, sum val[i][y][z];break;}case 2 : {for( int i 1;i y;i )if( ! vis[x][i][z] )vis[x][i][z] 1, sum val[x][i][z];break;}case 3 : {for( int i y;i n;i )if( ! vis[x][i][z] )vis[x][i][z] 1, sum val[x][i][z];break;}case 4 : {for( int i 1;i z;i )if( ! vis[x][y][i] )vis[x][y][i] 1, sum val[x][y][i];break;}case 5 : {for( int i z;i n;i )if( ! vis[x][y][i] )vis[x][y][i] 1, sum val[x][y][i];break;}}}Min min( Min, sum ), Max max( Max, sum );for( int k 0;k NB.size();k ) {int x NB[k].x, y NB[k].y, z NB[k].z;switch( dir[k] ) {case 0 : for( int i 1;i x;i ) vis[i][y][z] 0; break;case 1 : for( int i x;i n;i ) vis[i][y][z] 0; break;case 2 : for( int i 1;i y;i ) vis[x][i][z] 0; break;case 3 : for( int i y;i n;i ) vis[x][i][z] 0; break;case 4 : for( int i 1;i z;i ) vis[x][y][i] 0; break;case 5 : for( int i z;i n;i ) vis[x][y][i] 0; break;}}
}void dfs( int x ) {if( x NB.size() ) return calc(), void();for( int i 0;i 6;i ) dir[x] i, dfs( x 1 );
}int CalcDis( int x, int y, int a, int b ) { return fabs( x - a ) fabs( y - b ); }int main() {memset( dis, 0x3f, sizeof( dis ) );scanf( %d, n );m n * n * n;for( int i 1, id;i m;i ) {scanf( %d, g[i] );do { scanf( %d, id ), G[i].push_back( id ); } while( getchar() ! \n );}int p1, p2, p3;for( int i 1;i m;i ) if( G[i].size() 3 ) p1 i;val[1][1][1] g[p1]; bfs( p1, dis[0] );for( int i 1;i m;i ) if( G[i].size() 3 and dis[0][i] (n - 1 1) ) p2 i;val[n][n][1] g[p2]; bfs( p2, dis[1] );for( int i 1;i m;i ) if( G[i].size() 3 and dis[0][i] n - 1 and dis[1][i] n - 1 ) p3 i;val[n][1][1] g[p3]; bfs( p3, dis[2] );for( int i 1;i n;i )for( int j 1;j n;j ) {int d0 CalcDis( 1, 1, i, j );int d1 CalcDis( n, n, i, j );int d2 CalcDis( n, 1, i, j );pos[MAX d1 - d0][MAX d2 - d0] { i, j, 1 };}for( int i 1;i m;i ) {node p pos[MAX dis[1][i] - dis[0][i]][MAX dis[2][i] - dis[0][i]];p.z dis[0][i] - CalcDis( 1, 1, p.x, p.y ) 1;val[p.x][p.y][p.z] g[i];if( ! g[i] ) NB.push_back( p );}dfs( 0 );printf( %d %d\n, Min, Max );return 0;
}
