社区讨论
本地AC评测RE怎么办?
P1032[NOIP 2002 提高组] 字串变换(疑似错题)参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6of0fg
- 此快照首次捕获于
- 2025/11/20 08:11 4 个月前
- 此快照最后确认于
- 2025/11/20 08:11 4 个月前
CPP
#include <bits/stdc++.h>
#define L 1000005
#pragma comment(linker, "/HEAP:32000000")
using namespace std;
inline void write(int x){
int k = 0,lx = x;char put[20];
if (lx ==0) putchar('0');
if (lx < 0) putchar('-'),lx = -lx;
while (lx) put[++k] = (lx % 10) + '0',lx /= 10;
while (k) putchar( put[ k-- ] );
putchar('\n');
}
string a,b;
string x[7],y[7];
int m;
struct ZT{
string now;
int step;
}tmp,Now;
queue <ZT> Q;
int ans = 20;
bool Accept(int a,ZT Now,int f){
if (f+x[a].size()-1 > Now.now.size()) return false;
return Now.now.substr(f,x[a].size()) == x[a];
}
string Remove(int a,ZT Now,int f){
string ans = Now.now;
string part1 = Now.now.substr(0,f);
string part2 = Now.now.substr(f+x[a].size(),Now.now.size() - f - x[a].size());
return part1 + y[a] + part2;
}
bool Hash1[L],Hash2[L];
int hash1(string x){
int tot = 0;
for (int i = 0; i < x.size(); ++i) tot = ( tot * 7 + x[i] ) % 100006;
return tot;
}
int hash2(string x){
int tot = 0;
for (int i = 0; i < x.size(); ++i) tot = ( tot * 11 + x[i] ) % 1000003;
return tot;
}
void Pushhash(string x){
Hash1[hash1(x)] = 1,Hash2[hash2(x)] = 1;
}
bool Inhash(string x){
return Hash1[hash1(x)] && Hash2[hash2(x)];
}
int main(){
cin >> a >> b;
m = 1;
cin >> x[m] >> y[m];
while ( x[m] != "" && y[m] != "" ) ++m,cin >> x[m] >> y[m];
--m;
/*
cout << m <<'\n';
for (int i = 1; i <= m; ++i) cout << x[i] <<' ' << y[i] << '\n';
*/
tmp.now = a,tmp.step = 0,Q.push(tmp),Pushhash(tmp.now);
while (!Q.empty()){
tmp = Q.front(),Now.step = tmp.step + 1,Q.pop();
if (tmp.now == b) {ans = tmp.step;break;}
if (tmp.step == 10) continue;
for (int i = 1; i <= m; ++i){
for (int k = 0; k < tmp.now.size() ; ++k)
if (Accept(i,tmp,k)) {
Now.now = Remove(i,tmp,k);
if ( !Inhash(Now.now) ) Q.push(Now),Pushhash(Now.now);
}
}
}
if (ans > 10) puts("NO ANSWER!"); else write(ans);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...