社区讨论
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 条回复,欢迎继续交流。
正在加载回复...