UVA11732 “strcmp()“ Anyone?

D e s c r i p t i o n Description Description

传送门(洛谷真香
给 n n n个字符串，求两两进行 s t r c m p strcmp strcmp函数比较的总次数
n ≤ 4000 , l e n ( s ) ≤ 1000 n\leq4000,len(s)\leq1000 n≤4000,len(s)≤1000

S o l u t i o n Solution Solution

把每个串加入 T i r e Tire Tire中
d f s dfs dfs统计
串结尾的'\0'也要加进去

A c c e p t e d   c o d e Accepted\ code Accepted code

#include<cstdio>
#include<cstring>
#include<iostream>

#define int long long

using namespace std;

const int MAX_NODE = 4e6 + 5;

struct Line {
	int to, next;
}e[MAX_NODE];

char s[1005];
int n, k, ans, cnt, caze;
int num[MAX_NODE], last[MAX_NODE];

int read() {
	int f = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) f = f * 10 + c - 48, c = getchar();
	return f;
}

int get_id(char c) {
	if (c >= '0' && c <= '9') return c - 48;
	if (c >= 'A' && c <= 'Z') return c - 55;
	if (c >= 'a' && c <= 'z') return c - 61;
	return 62;
}

void insert(char *s) {
	int p = 0, len = strlen(s); ++num[0];
	for (int i = 0; i <= len; ++i) {
		int c = get_id(s[i]);
		int j = last[p], flag = 0;
		for (; j; j = e[j].next)
			if (e[j].to == c) { flag = 1; break; }
		if (!flag)
			e[++cnt] = (Line){c, last[p]}, last[p] = j = cnt;
		++num[(p = j)];
	}
	return;
}

void dfs(int deep, int now) {
	if (!last[now]) { ans += num[now] * (num[now] - 1) * deep; return; }
	long long sum = 0;
	for (int i = last[now]; i; i = e[i].next)
		sum += num[i] * (num[now] - num[i]);
	ans += (sum >> 1) * (2 * deep + 1);
	for (int i = last[now]; i; i = e[i].next)
		dfs(deep + 1, i);
	return;
}

signed main() {
	while ((n = read()) != 0) {
		memset(num, 0, sizeof num);
		memset(last, 0, sizeof last);
		k = ans = cnt = 0;
		for (int i = 1; i <= n; ++i)
			scanf("%s", s), insert(s);
		dfs(0, 0);
		printf("Case %d: %lld\n", ++caze, ans);
	}
}