HDU3682 To Be an Dream Architect

To Be an Dream Architect

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:

  
   

    2
3 2
Y=1,Z=3
X=3,Y=1
10 2
X=3,Y=3
Y=3,Z=3
   

  
   

    5
19
   

lcy&zhengfeng

（先吐槽下，比个赛过程中被叫出去开会2次（都还开了很长时间）。中国会多，美国税多。。。）

这题吧，昨晚YY出一种方法，结合容斥原理的思想，n*m'(m要去重复的，代码中的k就是m') - 2条直线相交的对数(记作代码中的f)+3条直线相交的对数(记作代码中的all) =答案

首先我用数组xy[]（平行于Z轴，x值为下标，y值为xy[x][]的值），

                     yz[]（平行于X轴，y值为下标，z值为xy[x][]的值），

                     zx[]（平行于Y轴，z值为下标，X值为xy[x][]的值）;

去存储输入的直线。

for(j=0;j<m;j++){getchar();scanf("%c=%d,%c=%d",&p,&a,&q,&b);if((p=='X'&&q=='Y')||(p=='Y'&&q=='X')){if(p=='X'&&q=='Y') xy[a].push_back(b);elsexy[b].push_back(a);} else if((p=='Y'&&q=='Z')||(p=='Z'&&q=='Y')){if(p=='Y'&&q=='Z')yz[a].push_back(b);elseyz[b].push_back(a);}else if((p=='Z'&&q=='X')||(p=='X'&&q=='Z')){if(p=='Z'&&q=='X')zx[a].push_back(b);elsezx[b].push_back(a);}}

然后使用sort排序，结合vector的unique和erase删除重复的输入。

for(i=1;i<=1000;i++){if(xy[i].size()){sort(xy[i].begin(),xy[i].end());xy[i].erase(unique(xy[i].begin(),xy[i].end()),xy[i].end());}if(yz[i].size()){sort(yz[i].begin(),yz[i].end());yz[i].erase(unique(yz[i].begin(),yz[i].end()),yz[i].end());}if(zx[i].size()){sort(zx[i].begin(),zx[i].end());zx[i].erase(unique(zx[i].begin(),zx[i].end()),zx[i].end());}}

接下来分别计算m',f,all;

m':

         m' 只需累加每个vector的size（）；

f:

          累加具有相同x |  y  | z 值得之间对数，实现方法会在下面的all中提到。

all:

vec数组     下标      值   （请注意下标和值的含义，上面有提到）

   xy[]         i        xy[i][]

   yz[]         j        yz[j][]

   zx[]         k       zx[k][]

如果2直线有交点，那么 xy[i][]=j ||  yz[j][]=k  ||   zx[k][]=i  ; 结果累加可以得到f;

如果3直线有交点，那么 xy[i][]=j  &&  yz[j][]=k  &&   zx[k][]=i  ; 结果累加可以得到all;

                  for(i=1;i<=1000;i++){if(xy[i].size()){k+=xy[i].size();//	printf("%d %d\n",xy[i][0],xy[i].size());for(int g=0;g<xy[i].size();g++){f+=yz[xy[i][g]].size();for(int s=0;s<yz[xy[i][g]].size();s++){for(int r=0;r<zx[yz[xy[i][g]][s]].size();r++){if(zx[yz[xy[i][g]][s]][r]==i)all++;}} }				}if(yz[i].size()){k+=yz[i].size();for(int g=0;g<yz[i].size();g++)f+=zx[yz[i][g]].size();}if(zx[i].size()){k+=zx[i].size();for(int g=0;g<zx[i].size();g++)f+=xy[zx[i][g]].size();}}

输出结果就可以了：

printf("%d\n",n*k-f+all);

贴出完整代码：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
#include<string>
#include<map>
#include<set>
#include<string.h>
using namespace std;vector<int> xy[1001],yz[1001],zx[1001];
int main(){//freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){int a,b,i,j,k=0,n,m,all=0,f=0;char p,q;//memset(xy,0,sizeof(xy));//memset(yz,0,sizeof(yz));//memset(zx,0,sizeof(zx));scanf("%d%d",&n,&m);for(i=0;i<=1000;i++){xy[i].clear();yz[i].clear();zx[i].clear();}for(j=0;j<m;j++){getchar();scanf("%c=%d,%c=%d",&p,&a,&q,&b);if((p=='X'&&q=='Y')||(p=='Y'&&q=='X')){if(p=='X'&&q=='Y') xy[a].push_back(b);elsexy[b].push_back(a);} else if((p=='Y'&&q=='Z')||(p=='Z'&&q=='Y')){if(p=='Y'&&q=='Z')yz[a].push_back(b);elseyz[b].push_back(a);}else if((p=='Z'&&q=='X')||(p=='X'&&q=='Z')){if(p=='Z'&&q=='X')zx[a].push_back(b);elsezx[b].push_back(a);}}for(i=1;i<=1000;i++){if(xy[i].size()){sort(xy[i].begin(),xy[i].end());xy[i].erase(unique(xy[i].begin(),xy[i].end()),xy[i].end());}if(yz[i].size()){sort(yz[i].begin(),yz[i].end());yz[i].erase(unique(yz[i].begin(),yz[i].end()),yz[i].end());}if(zx[i].size()){sort(zx[i].begin(),zx[i].end());zx[i].erase(unique(zx[i].begin(),zx[i].end()),zx[i].end());}}for(i=1;i<=1000;i++){if(xy[i].size()){k+=xy[i].size();//	printf("%d %d\n",xy[i][0],xy[i].size());for(int g=0;g<xy[i].size();g++){f+=yz[xy[i][g]].size();for(int s=0;s<yz[xy[i][g]].size();s++){for(int r=0;r<zx[yz[xy[i][g]][s]].size();r++){if(zx[yz[xy[i][g]][s]][r]==i)all++;}} }				}if(yz[i].size()){k+=yz[i].size();for(int g=0;g<yz[i].size();g++)f+=zx[yz[i][g]].size();}if(zx[i].size()){k+=zx[i].size();for(int g=0;g<zx[i].size();g++)f+=xy[zx[i][g]].size();}}//printf("%d %d %d\n",k,f,all);printf("%d\n",n*k-f+all);} return 0;
}	

结果：0 ms

注：我参考了一下的博文，觉得博主讲很好，让我学到很多。

http://blog.csdn.net/angelniu1024/article/details/12784261

另外，刚刚发现hdu排名的优先级是（time->memory->code len）,很希望知道大神们的消耗的存储空间怎么这么小，求大家指点一下，谢谢！