### 求助:构造函数不特判直接全部点tle了,加了特判直接ac
  • 板块P5507 机关
  • 楼主st_u_dy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/6 16:00
  • 上次更新2024/12/6 19:10:09
查看原帖
### 求助:构造函数不特判直接全部点tle了,加了特判直接ac
483857
st_u_dy楼主2024/12/6 16:00

求助:为什么构造函数里面不加if(((s>>(i*2))&3)!=0)会全部tle,这样能慢多少。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=(1<<24);
int f[maxn],g[maxn],ch[maxn],ans[maxn],nxt[12][4],st;
struct node{
	int state;
	double F;
	node(int s):state(s){
		//每个点的状态
		F=0;
		for(int i=0;i<12;i++){
			if(((s>>(i*2))&3)!=0)//为什么不加这个特判会炸
				F+=4-((s>>(i*2))&3);
		}
		F=F+g[s];
	}
	bool operator < (const node y)const{
		return this->F > y.F;
	}
};
priority_queue<node> que;
int main(){
	int b;
	for(int i=0;i<12;i++){
		cin>>b;
		b--;
		st|=(b<<(i*2));
		for(int j=0;j<4;j++){
			cin>>nxt[i][j];
			nxt[i][j]--;
		}
	}
	que.push(node(st));
	while(!que.empty()){
		int state=que.top().state;
		que.pop();
		if(state==0)break;
		for(int i=0;i<12;i++){//12个点
			//当前转动第i个点,第i个点的状态si
			int si=(state>>(i*2))&3;
			int nx=nxt[i][si];
			int nxSi=(state>>(nx*2))&3;
			int nxst=state^(si<<(i*2))^(((si+1)&3)<<(i*2));
			nxst=nxst^(nxSi<<(nx*2))^(((nxSi+1)&3)<<(nx*2));
			if(!g[nxst]){//nxst表示下一个状态
				f[nxst]=state;//表示nxst的前一个状态
				//ch[nxst]表示到达nxst这个状态之前用了什么按钮
				ch[nxst]=i+1;
				g[nxst]=g[state]+1;
				que.push(node(nxst));
			}
		}
	}
	int state=0,cnt=0;
	while(state!=st){
		ans[++cnt]=ch[state];
		state=f[state];
		// cout<<state<<" ";
	}
	// cout<<endl;
	cout<<cnt<<endl;
	for(int i=cnt;i>=1;i--){
		cout<<ans[i]<<" ";
	}
	return 0;
}
2024/12/6 16:00
加载中...