哈希_类似哈希的构造序列

听说巨佬暴力随机函数过了……

https://cn.vjudge.net/problem/ZOJ-4093

紧接上一题的搜索，希望我们设计出一条超级指令（超级指令超度依然为243（3^5）），实现捡起95%的垃圾。

受指令的操作种类是类似哈希的做法，设哈希值为H，哈希值的映射公式为下图，（说白了就是三进制）

哈希_类似哈希的构造序列

当H的最高位为2时，代表当前位置有垃圾，所以，指令集中，所有3进制最高位为2的位置都设为‘P’。同理，次高位为2的位置都设为’U’，以此类推。（优先编码：某些进制代表的位置的编码优先权高）。

（巨佬解释：由于取那个位置的指令是根据当前位置及上下左右共5个位置的状态哈希运算出来了，我们可以根据哈希值来确定该位置的策略。）

5个位置都不为2的情况：即附近没有垃圾往哪里走。

如果给4个方位不同的优先级，如果优先级高的地方能走，就走，不能走就判断下一个方向，我也不知道为什么会WA。

巨佬优化：

哈希_类似哈希的构造序列

#include<bits/stdc++.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+233;
int d[10];
void digit(int x){
   int p=0;
   while(x){
       d[p++]=x%3;
       x/=3;
   }
}
char ans[250];
char ch[7]="UDLR";
int main()
{
   memset(ans,'?',sizeof(ans));
   for(int i=0;i<243;i++){
       digit(i);
       //2xxxx
       if(d[4]==2){
           ans[i]='P';
           continue;//此语句必不可少！！！！！！
           //少了就会重复赋值，导致违背哈希值代表的意思
       }
       if(d[3]==2){
           ans[i]='U';
           continue;
       }
       if(d[2]==2){
           ans[i]='D';
           continue;
       }
       if(d[1]==2){
           ans[i]='L';
           continue;
       }
       if(d[0]==2){
           ans[i]='R';
           continue;
       }
//srand((unsigned int)time(0));
// ans[i]=ch[rand()%4];
// continue;
       if(d[3] == 1 &&d[1] == 1){//上左
           ans[i]='R';
           continue;
       }
       if(d[3] == 1 && d[0] == 1){//上右
           ans[i]='D';
           continue;
       }
       if(d[2] == 1 && d[0] == 1){//下右
           ans[i]='L';
           continue;
       }
       if(d[1] == 1 && d[2] == 1){//下左
           ans[i]='U';
           continue;
       }
       if(d[0]==1){//右
           ans[i]='D';
           continue;
       }
       if(d[2]==1){//下
           ans[i]='L';
           continue;
       }
       if(d[1]==1){//左
           ans[i]='U';
           continue;
       }
       if(d[3]==1){//上
           ans[i]='R';
           continue;
       }
       ans[i]='R';

}
ans[243]='\0';

printf("%s\n",ans);
return 0;
}

哈希_类似哈希的构造序列

相关推荐