文章

68

粉丝

691

获赞

26

访问

575.7k

头像
巧妙的题解
P1098 中山大学2018年机试
发布于2020年5月13日 13:09
阅读数 9.7k

依次遍历每个输入的字符串和目前已经形成的组别,如果与现有的一个组的所有字符串不互为前缀,那么将他加入该组,如果与某个组中的字符串冲突,那么如果该组中的前缀字符串短,则将其替换成较长的,如果他与所有组都冲突,那么另开一个组存它。

为什么选最长的?比如 如果一个组中现在是 

acm
yuou

现在输入一个

yuoufsdaf

显然yuou和yuoufsdaf是冲突的,如果我们保留yuou,那么遇到yuout这两个也是冲突的,但是如果我们将yuou换成yuoufsdaf,显然yuout也可以加入该组,贪心的选择长度较长的字符串替换短的,可以使得改组的字符串个数尽可能的多。也可能数据比较水哈,欢迎大佬指正

#define ll int
#define inf 0x3ffffff
#define vec vector<ll>
#define MAX 105

string a[MAX]; 
bool isT[MAX][MAX];

//检查a,b字符串是否一个是另一个的前缀
bool check(string a, string b) {
	if (a.size() > b.size()) swap(a, b);
	if (a == b.substr(0, a.size()))return true;
	else return false;
}

int main() {
	ll n; 
	while (cin >> n && n) {
		cin.get();
		for (int i = 1; i <= n; i++)getline(cin, a[i]);
		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++)
				isT[i][j] = check(a[i], a[j]);
		vector<int> v[MAX]; ll cnt = 0, res = 0;//v存储的是字符串的编号
		for (int i = 1; i <= n; i++) {//遍历所有字符串
			ll sign = 0...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发