社区讨论

RE爆零求助(145行报错)

P2761软件补丁问题参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhjtfnn8
此快照首次捕获于
2025/11/04 08:13
4 个月前
此快照最后确认于
2025/11/04 08:13
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,ans=1e18;
const ll N = 1e7+6,M=30;
vector<vector<ll> > b1;
vector<vector<ll> > b2;
vector<vector<ll> > f1;
vector<vector<ll> > f2;
ll t[106],dis[N];
bool check1(ll x,ll d){
	/*
		当前的状态是now
		要与b1,b2一一比对
		如果成立
		则根据f1,f2进行修改 	
					
		如果 now=1101100
	    b1={1,2,3}
					
	    当b1=1时
		削掉6位(n-b1)
		即:now>>(n-b1)
		如果此使&1结果是一,则证明存在错误  
	*/
	x=(x>>(n-d));
	if(x&1)return true;
	return false;
}
bool check2(ll x,ll d){
	x=(x>>(n-d));
	if(x&1) return true;
	return false;
}
ll change(ll now,ll d){
	/*
		若当前为 1101110
		 要将第1位变成0
		 在最前面你加一下
		 10101110再减一下
		 0101110
		 
		若当前为 0101110
		 不用变
		 
		怎么判断?(now>>(n-x))&1
	*/
	
	for(auto x:f1[d]){
		if((now>>(n-x))&1){
			now=now+(1<<(n-1))-(1<<n);
		}
	}

	/*
	  如果当前是10010
	  我要把第2位变成1
	  now=now+(1<<(n-x)) 
	  
	  如果是11010
	  则不用变
	  
	  怎么判断? (now>>(n-x))&1==0
	
	*/
	
	for(auto x:f2[d]){
		if((now>>(n-x))&1==0){
			now=now+(1<<(n-x));
		}
	}
	return now;
}
ll BFS(){
	queue<ll> q;
	q.push((1<<n)-1);
	for(ll i = 0;i <= (1<<n);++i){
		dis[i]=1e18;
	}
	dis[(1<<n)-1]=0;
	while(q.size()){
		ll st=q.front();
	//	cout << st << " " << dis[st] << endl;
		q.pop();
		for(ll i = 1;i <= m;++i){
			ll now=st;
			bool f=0;
			for(auto d:b1[i]){
				
				if(check1(now,d)==false){
					f=1;
					
					
					break;
				}
			}				
			for(auto d:b2[i]){
			//	cout << "H" << endl;
			//	cout << now << " " << d << " " << check2(now,d) << endl << endl;
				if(check2(now,d)){
					f=1;
					break;
				}
			}
			
			if(f==0){
				now=change(now,i);
			}
			if(dis[now]>dis[st]+t[i]){
				dis[now]=dis[st]+t[i];
				q.push(now);
			}
		}	
	}
	if(dis[0]==1e18) return 0;
	return dis[0];
}
int main(){
//	vector<vector<ll>> a;
//	a[1].push_back(1);
//	cout << a[1][0] << endl;
//	cout << (1<<(7-1)) << endl;
//	cout << ((now&(1<<(n-1)))>>(n-1));
	cin>>n>>m;
	for(ll i = 1;i <= m;++i){
		cin>>t[i];
		string s1,s2;cin>>s1>>s2;
		ll len1=s1.size();
		ll len2=s2.size();
		s1=" "+s1;
		s2=" "+s2;
		
		for(ll j = 1;j <= len1;++j){
			if(s1[j]=='+'){
				
				b1[i].push_back(j-1);
			}
			else if(s1[j]=='-'){
				b2[i].push_back(j-1);
			}
		}
		for(ll j = 1;j <= len2;++j){
			if(s2[j]=='-'){
				
				f1[i].push_back(j-1);
			//	cout << "HelloWorld" << endl;
			}
			else if(s2[j]=='+'){
				f2[i].push_back(j-1);
			}
		}
	}
	cout << BFS() << endl;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...