社区讨论

本地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 条回复,欢迎继续交流。

正在加载回复...