办公家具 技术支持 东莞网站建设,WordPress添加前台注册功能,wordpress怎样去掉手机自适应效果,app开发是什么专业出题人的意图#xff1a;这是一道基础的稍微带一点码量的搜索题#xff0c;状态数也很好分析嘛#xff01;#xff08;简单用一下鸽巢原理#xff09;
我的想法#xff1a;这题状态数怎么分析啊#xff0c;暴搜怎么过不了啊
下次不要犯这种错误了#x1f605;
首先这是一道基础的稍微带一点码量的搜索题状态数也很好分析嘛简单用一下鸽巢原理
我的想法这题状态数怎么分析啊暴搜怎么过不了啊
下次不要犯这种错误了
首先这道题目是可以拆位的。
理由对于初始相同的 ( a , b , m ) ( 0 / 1 , 0 / 1 , 0 / 1 ) (a,b,m)(0/1,0/1,0/1) (a,b,m)(0/1,0/1,0/1)经过相同的操作序列后得到的 ( c , d ) (c,d) (c,d)一定也是相同的。因此本质不同的询问只有 5 8 5^8 58种也可以用鸽巢原理来理解
剩下的就是大力搜索了。
其实和 CF1103D Professional layer 的优化思路差不多但是就是没想到
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define db double
using namespace std;
int T,a,b,c,d,m;
int fac5[9],bit[8];
int dis[390625];
int get(int x,int y){return x/fac5[y]%5;
}
queueintQ;
int solve(int s,int op){int t(0);for(int i0;i8;i){int xget(s,i);if(x4){tfac5[i]*4;continue;}int a!!(x2),b!!(x1),mi1;if(op0)ab;else if(op1)a|b;else if(op2)b^a;else b^m;tfac5[i]*(a*2b);}return t;
}
void work(int x,int y){if(dis[x]y){dis[x]y;Q.push(x);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);fac5[0]1;for(int i1;i8;i)fac5[i]fac5[i-1]*5;memset(dis,0x3f,sizeof dis);for(int i0;ifac5[8];i){int ok1;for(int j0;j8;j){int xget(i,j);int a!!(j4),b!!(j2),mj1;int a2!!(x2),b2x1;if(x!4(a!a2||b!b2)){ok0;break;}}if(ok){dis[i]0;Q.push(i);}}while(Q.size()){int uQ.front();Q.pop();for(int i0;i4;i)work(solve(u,i),dis[u]1);}cinT;while(T--){cinabcdm;int ok1;for(int i0;i8;i)bit[i]-1;for(int i0;i30;i){int a2ai1,b2bi1,c2ci1,d2di1,m2mi1;int tmp(a22)(b21)m2,tmp2(c21)d2;if(bit[tmp]-1)bit[tmp]tmp2;else if(bit[tmp]!tmp2){ok0;break;}}if(ok0){cout-1\n;continue;}int tmp0;for(int i0;i8;i){if(bit[i]-1)tmpfac5[i]*4;else tmpfac5[i]*bit[i];}cout(dis[tmp]inf?-1:dis[tmp])\n;}
}
