社区讨论

啊?求调

P3879[TJOI2010] 阅读理解参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@logkl6x0
此快照首次捕获于
2023/11/02 10:31
2 年前
此快照最后确认于
2023/11/22 21:29
2 年前
查看原帖
rt,调了几十次了(尊嘟没在滥用评测机资源qwq),这份是90pts的码AC+WA,chk数组的120开大了会变成MLE+WA,然后再大一点就MLE+AC。
就,挺抽象的(
CPP
#include<bits/stdc++.h>
using namespace std;

int n,m,nxt[500100][26],lcnt = 0;
bool chk[500100][120];

int trans(char c){return c - 'a';}

void insert(string s,int word_num){
	int pos = 0;
	for(int i = 0;i < s.length();i++){
		if(nxt[pos][trans(s[i])] != 0){
			pos = nxt[pos][trans(s[i])];
		}
		else{
			lcnt++;
			nxt[pos][trans(s[i])] = lcnt;
			pos = lcnt;
		}
	}
	chk[pos][word_num] = true;
	return;
}

void check(string s){
	int pos = 0;
	for(int i = 0;i < s.length();i++){
		if(nxt[pos][trans(s[i])] == 0){
			cout << endl;
			return;
		}
		pos = nxt[pos][trans(s[i])];
	}
	bool flag = false;
	for(int i = 1;i <= n;i++){
		if(chk[pos][i]){
			if(flag) cout << " ";
			else flag = true;
			cout << i;
		}
	}
	cout << endl;
	return;
}

int main(){
	cin >> n;
	for(int i = 1,j;i <= n;i++){
		cin >> j;
		while(j--){
			string str;
			cin >> str;
			insert(str,i);
		}
	}
	cin >> m;
	for(int i = 1;i <= m;i++){
		string s;
		cin >> s;
		check(s);
	}
	return 0;
}

回复

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

正在加载回复...