社区讨论

放弃 Trie，睡了睡了

cconcert_B
P1012[NOIP 1998 提高组] 拼数参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mkpi6spd
此快照首次捕获于
2026/01/22 21:44
4 周前
此快照最后确认于
2026/01/23 17:20
4 周前
查看原帖
第三版代码被 hack，不想调了。
虽然洛谷一群 xxs 跟风举报让我很不爽（明明没有参与 hack 或证伪代码，却嘲笑新生做法），虽然因为学术问题删帖非常神奇。但是我承认我没有能力继续调了。
感谢 Kagamine_Rin 以及 meyi 持续不断的 hack，这才是应有的学术态度。
给出三版代码，希望有心人来证伪或完善它。
FIRSTCPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int tr[N][10];
pair<int,int> fa[N];
int ed[N];
int ans[N],tot;
int n,cnt=1;
void insert(char* s){
	int l=strlen(s),p=1;
	for(int i=0;i<l;i++){
		int c=s[i]-'0';
		if(!tr[p][c])	tr[p][c]=++cnt,fa[cnt]=make_pair(p,c);
		p=tr[p][c];
	}
	ed[p]++;
	return;
} 
void erase(int p){
	if(ed[p]>1){
		ed[p]--;
		return;
	}
	for(int i=0;i<10;i++)
		if(tr[p][i]){
			ed[p]--;
			return;
		}
	ed[p]--;
	while(!ed[p]&&p!=1){
		int c=0;
		for(int i=0;i<10;i++)
			if(tr[p][i])	c++;
		if(c)	break;
		tr[fa[p].first][fa[p].second]=0;
		p=fa[p].first;
	}
	return;
}
void work(){
	int p=1;
	while(1){
		int F=1;
		while(!ed[p]){
			int f=-1;
			for(int c=9;c>=0;c--){
				if(!tr[p][c])	continue;
				ans[++tot]=c;
				f=c;
				p=tr[p][c];
				F=0;
				break;
			}
//			cout<<p<<'\n';
			if(f==-1){
				break;
			}
		}
		if(F&&p!=1){
			erase(p);
			p=1;
			continue;
		}
		if(F)	break;
//		cout<<p<<'\n';
		int t1=1,t2=p;
		while(1){
//			cout<<t1<<' '<<t2<<'\n';
			int c1=-1,c2=-1;
			for(int c=9;c>=0;c--){
				if(!tr[t1][c])	continue;
				c1=c;
				t1=tr[t1][c];
				break;
			}
			for(int c=9;c>=0;c--){
				if(!tr[t2][c])	continue;
				c2=c;
				t2=tr[t2][c];
				break;
			}
			if(c2==-1){
				erase(t2);
				p=1;
				break;
			}
			if(c1==c2){
				ans[++tot]=c1;
				continue;
			}
			if(c1>c2){
				ans[++tot]=c1;
				erase(p);
				p=t1;
				break;
			}
			if(c2>c1){
				ans[++tot]=c2;
				p=t2;
				break;
			}
		}
	}
	return;
}
char a[20];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		insert(a);
	}
//	for(int i=1;i<=cnt;i++,cout<<i-1<<'\n')
//		for(int j=0;j<10;j++)
//			cout<<tr[i][j]<<' ';
	work();
	for(int i=1;i<=tot;i++)
		cout<<ans[i];
	return 0;
}
SECONDCPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int tr[N][10];
pair<int,int> fa[N];
int ed[N];
int ans[N],tot;
int n,cnt=1;
void insert(char* s){
	int l=strlen(s),p=1;
	for(int i=0;i<l;i++){
		int c=s[i]-'0';
		if(!tr[p][c])	tr[p][c]=++cnt,fa[cnt]=make_pair(p,c);
		p=tr[p][c];
	}
	ed[p]++;
	return;
} 
void erase(int p){
	if(!ed[p])	return;
	if(ed[p]>1){
		ed[p]--;
		return;
	}
	for(int i=0;i<10;i++)
		if(tr[p][i]){
			ed[p]--;
			return;
		}
	ed[p]--;
	while(!ed[p]&&p!=1){
		int c=0;
		for(int i=0;i<10;i++)
			if(tr[p][i])	c++;
		if(c)	break;
		tr[fa[p].first][fa[p].second]=0;
		p=fa[p].first;
	}
	return;
}
void work(){
	int p=1;
	while(1){
		int F=1;
		while(!ed[p]){
			int f=-1;
			for(int c=9;c>=0;c--){
				if(!tr[p][c])	continue;
				ans[++tot]=c;
				f=c;
				p=tr[p][c];
				F=0;
				break;
			}
//			cout<<p<<'\n';
			if(f==-1){
				break;
			}
		}
		if(F&&p!=1){
			erase(p);
			p=1;
			continue;
		}
		if(F)	break;
//		cout<<p<<'\n';
		int t1=1,t2=p;
		while(1){
			if(t1==t2)	break; 
//			cout<<t1<<' '<<t2<<'\n';
			int c1=-1,c2=-1;
			for(int c=9;c>=0;c--){
				if(!tr[t2][c])	continue;
				c2=c;
				t2=tr[t2][c];
				break;
			}
			if(c2==-1){//WRONG 
				t2=1;
				continue;
			}
			for(int c=9;c>=0;c--){
				if(!tr[t1][c])	continue;
				c1=c;
				t1=tr[t1][c];
				break;
			}
			if(c1==-1){//WRONG 
				erase(p);
				erase(t1);
				p=1;
				break;
			}
			if(c1==c2){
				ans[++tot]=c1;
				continue;
			}
			if(c1>c2){
				ans[++tot]=c1;
				erase(p);
				p=t1;
				break;
			}
			if(c2>c1){
				if(t2<t1)
					erase(p);
				ans[++tot]=c2;
				p=t2;
				break;
			}
		}
	}
	return;
}
char a[20];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		insert(a);
	}
//	for(int i=1;i<=cnt;i++,cout<<i-1<<'\n')
//		for(int j=0;j<10;j++)
//			cout<<tr[i][j]<<' ';
	work();
	for(int i=1;i<=tot;i++)
		cout<<ans[i];
	return 0;
}
THIRDCPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int tr[N][10];
pair<int,int> fa[N];
int ed[N];
int ans[N],tot;
int n,cnt=1;
void insert(char* s){
	int l=strlen(s),p=1;
	for(int i=0;i<l;i++){
		int c=s[i]-'0';
		if(!tr[p][c])	tr[p][c]=++cnt,fa[cnt]=make_pair(p,c);
		p=tr[p][c];
	}
	ed[p]++;
	return;
} 
void erase(int p){
	if(!ed[p])	return;
	if(ed[p]>1){
		ed[p]--;
		return;
	}
	for(int i=0;i<10;i++)
		if(tr[p][i]){
			ed[p]--;
			return;
		}
	ed[p]--;
	while(!ed[p]&&p!=1){
		int c=0;
		for(int i=0;i<10;i++)
			if(tr[p][i])	c++;
		if(c)	break;
		tr[fa[p].first][fa[p].second]=0;
		p=fa[p].first;
	}
	return;
}
void work(){
	int p=1;
	while(1){
		while(!ed[p]){
			int f=-1;
			for(int c=9;c>=0;c--){
				if(!tr[p][c])	continue;
				ans[++tot]=c;
				f=c;
				p=tr[p][c];
				break;
			}
//			cout<<p<<'\n';
			if(f==-1){
				break;
			}
		}
		int F=1;
		for(int c=9;c>=0;c--){
			if(!tr[p][c])	continue;
			F=0;
			break;
		}
//		cout<<p<<'\n';
		if(F&&p!=1){
			erase(p);
			p=1;
			continue;
		}
		if(F)	break;
//		cout<<p<<'\n';
		int t1=1,t2=p,tmp;
		while(1){
			if(t1==t2)	break; 
//			cout<<t1<<' '<<t2<<'\n';
			int c1=-1,c2=-1;
			for(int c=9;c>=0;c--){
				if(!tr[t2][c])	continue;
				c2=c;
				t2=tr[t2][c];
				break;
			}
			if(c2==-1){//WRONG 
				tmp=t2;
				t2=1;
				continue;
			}
			for(int c=9;c>=0;c--){
				if(!tr[t1][c])	continue;
				c1=c;
				t1=tr[t1][c];
				break;
			}
//			cout<<t1<<' '<<t2<<' '<<c1<<' '<<c2<<'\n'; 
			if(c1==-1){//WRONG 
				erase(p);
				erase(t1);
				p=1;
				break;
			}
			if(c1==c2){
				ans[++tot]=c1;
				continue;
			}
			if(c1>c2){
				ans[++tot]=c1;
				erase(p);
				p=t1;
				break;
			}
			if(c2>c1){
				if(t2<t1)
					erase(tmp);
				ans[++tot]=c2;
				p=t2;
				break;
			}
		}
	}
	return;
}
char a[20];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		insert(a);
	}
//	for(int i=1;i<=cnt;i++,cout<<i-1<<'\n')
//		for(int j=0;j<10;j++)
//			cout<<tr[i][j]<<' ';
	work();
	for(int i=1;i<=tot;i++)
		cout<<ans[i];
	return 0;
}
/*
3
2
29
293829
*/

回复

共 2 条回复，欢迎继续交流。

正在加载回复...