首页 > 代码库 > hdu3682 To Be an Dream Architect
hdu3682 To Be an Dream Architect
http://acm.hdu.edu.cn/showproblem.php?pid=3682
To Be an Dream Architect
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2868 Accepted Submission(s): 826
Problem Description
The “dream architect” is the key role in a team of “dream extractors” who enter other’s dreams to steal secrets. A dream architect is responsible for crafting the virtual world that the team and the target will dream into. To avoid the target noticing the world is artificial, a dream architect must have powerful 3D imagination.
Cobb uses a simple 3D imagination game to test whether a candidate has the potential to be an dream architect. He lets the candidate imagine a cube consisting of n×n×n blocks in a 3D coordinate system as Figure 1. The block at bottom left front corner is marked (1, 1, 1) and the diagonally opposite block is marked (n, n, n). Then he tells the candidate that the blocks on a certain line are eliminated. The line is always parallel to an axis. After m such block eliminations, the candidate is asked to tell how many blocks are eliminated. Note that one block can only be eliminated once even if it is on multiple lines.
Here is a sample graph according to the first test case in the sample input:
Cobb uses a simple 3D imagination game to test whether a candidate has the potential to be an dream architect. He lets the candidate imagine a cube consisting of n×n×n blocks in a 3D coordinate system as Figure 1. The block at bottom left front corner is marked (1, 1, 1) and the diagonally opposite block is marked (n, n, n). Then he tells the candidate that the blocks on a certain line are eliminated. The line is always parallel to an axis. After m such block eliminations, the candidate is asked to tell how many blocks are eliminated. Note that one block can only be eliminated once even if it is on multiple lines.
Here is a sample graph according to the first test case in the sample input:
Input
The first line is the number of test cases.
In each test case, the first line contains two integers n and m( 1 <= n <= 1000, 0 <= m <= 1000).,meaning that the cube is n x n x n and there are m eliminations.
Each of the following m lines represents an elimination in the following format:
axis_1=a, axis_2=b
where axis_i (i=1, 2) is ‘X’ or ‘Y’, or ‘Z’ and axis_1 is not equal to axis_2. a and b are 32-bit signed integers.
In each test case, the first line contains two integers n and m( 1 <= n <= 1000, 0 <= m <= 1000).,meaning that the cube is n x n x n and there are m eliminations.
Each of the following m lines represents an elimination in the following format:
axis_1=a, axis_2=b
where axis_i (i=1, 2) is ‘X’ or ‘Y’, or ‘Z’ and axis_1 is not equal to axis_2. a and b are 32-bit signed integers.
Output
For each test case output the number of eliminated blocks.
Sample Input
2 3 2 Y=1,Z=3 X=3,Y=1 10 2 X=3,Y=3 Y=3,Z=3
Sample Output
5 19
Source
2010 Asia Hangzhou Regional Contest
题意:每次对立方体切割一条线上的块,问切割了多少个。
思路:暴力。。。把每个小立方块哈希编号为x*n*n+y*n+z,然后最后排序判重下就好。。。。。
stl大法好。。直接用unique。。。
/** * @author neko01 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cmath> #include <set> #include <map> using namespace std; typedef long long LL; #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define pb push_back #define mp(a,b) make_pair(a,b) #define clr(a) memset(a,0,sizeof a) #define clr1(a) memset(a,-1,sizeof a) #define dbg(a) printf("%d\n",a) typedef pair<int,int> pp; const double eps=1e-9; const double pi=acos(-1.0); const int INF=0x3f3f3f3f; const LL inf=(((LL)1)<<61)+5; vector<int>ans; int main() { int n,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); getchar(); ans.clear(); while(m--) { char c1,c2; int a,b; scanf("%c=%d,%c=%d",&c1,&a,&c2,&b); getchar(); if(c1=='X') { if(c2=='Y') for(int i=1;i<=n;i++) ans.pb(a*n*n+b*n+i); else for(int i=1;i<=n;i++) ans.pb(a*n*n+i*n+b); } else if(c1=='Y') { if(c2=='X') for(int i=1;i<=n;i++) ans.pb(b*n*n+a*n+i); else for(int i=1;i<=n;i++) ans.pb(i*n*n+a*n+b); } else { if(c2=='X') for(int i=1;i<=n;i++) ans.pb(b*n*n+i*n+a); else for(int i=1;i<=n;i++) ans.pb(i*n*n+b*n+a); } } sort(ans.begin(),ans.end()); int sz=unique(ans.begin(),ans.end())-ans.begin(); printf("%d\n",sz); } return 0; }
hdu3682 To Be an Dream Architect
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。