GCC 33264K 750MS
#include <stdio.h>
// #include <malloc.h>
#include <string.h>
// #include <queue>
// #include <string>
#include <stdlib.h>
#define CHAR_NUM 10
#define STATIC_CAP 700000
struct tireNode{
int childPos[CHAR_NUM];
int appearTime;
int usedTime;
};
typedef struct tireNode tireNode;
tireNode static_tire[STATIC_CAP];
int tire_array_index;
tireNode * tireTreeHead;
char checkAndBuildTireTree(char * word) {
int wordLength = strlen(word);
int currentPos = word[0] - '0';
// static_tire[currentPos].used = 1;
if (static_tire[currentPos].appearTime) {
return 1;
}
static_tire[currentPos].usedTime++;
for (int i = 1; i < wordLength; i++) {
int nextPos = static_tire[currentPos].childPos[word[i] - '0'];
if (nextPos) {
if (static_tire[nextPos].appearTime) {
return 1;
}
} else {
static_tire[currentPos].childPos[word[i] - '0'] = ++tire_array_index;
}
currentPos = static_tire[currentPos].childPos[word[i] - '0'];
static_tire[currentPos].usedTime++;
}
static_tire[currentPos].appearTime++;
if (static_tire[currentPos].usedTime >= 2) {
return 1;
}
return 0;
// printf("build %s %d\n", currentNode->val, currentNode->appearTime);
}
// void statisticTireTree() {
// int oddNum = 0;
// int evenNum = 0;
// queue<tireNode *> tireNodeQueue;
// if (!tireTreeHead) {
// printf("Possible\n");
// }
// tireNodeQueue.push(tireTreeHead);
// while(tireNodeQueue.size()) {
// tireNode * currentNode = tireNodeQueue.front();
// if (!currentNode) {
// break;
// }
// tireNodeQueue.pop();
// if (currentNode->appearTime) {
// // printf("%s %d\n", currentNode->val, currentNode->appearTime);
// if (currentNode->appearTime % 2) {
// oddNum++;
// } else {
// evenNum++;
// }
// }
// for (int i = 0; i < CHAR_NUM; i++) {
// if (currentNode->tireChildNode[i]) {
// tireNodeQueue.push(currentNode->tireChildNode[i]);
// }
// }
// }
// // printf("oddNum %d evenNum %d\n", oddNum, evenNum);
// if (2 == oddNum) {
// printf("Possible\n");
// } else {
// printf("Impossible\n");
// }
// }
int main() {
int caseNum = 0;
scanf("%d", &caseNum);
for (int i = 0; i < caseNum; i++) {
int phoneNum = 0;
scanf("%d", &phoneNum);
char NO = 0;
memset(static_tire, 0, sizeof(static_tire));
tire_array_index = 10;
for (int j = 0; j < phoneNum; j++) {
char c1[15] = {0};
scanf("%s", c1);
if (!NO) {
NO = checkAndBuildTireTree(c1);
}
}
NO ? printf("NO\n") : printf("YES\n");
}
}这道题是刷2513附带的， 本来以为2513单纯只考tire树，但是后来才发现还用了并查集和欧拉回路，这两个自己都不知道，于是决定先刷一个比较单纯的
tire树题，然后研读了并查集和欧拉回路以后，再干2513，结果没想到，自己掌握的动态tire树在3630上TLE了，看了disscuss，才知道有静态tire树。
于是正好试水， 一开始想的太静态了，搞了一个最大冗余数组（即一个完整10叉树， 每个父节点，不管是否真有相应的child，都给开了空间），结果一算，1后面10个0， 必然内存不足， 于是转变思路， 这样搞：
首先数组的node结构要搞成：
struct tireNode{
int childPos[CHAR_NUM];
int appearTime;
int usedTime;
};其中的childPos是关键,CHAR_NUM是10，因为最多有10个不同数字 0~9, childPos数组存储的是对于某个存在的child， 在静态tire数组中的下标，如果不存在，那么就等于0（-1更好，不过memset只能搞0，也不影响）。这样，这个静态数组的前10个空间被冗余占用（必须有一个这样的设置，否则最初的遍历进行不了）， 数组0~9依次对应着
字符串第一位为0~9的情况， 然后，再向下，就要动态的分配数组下标了，对于某个以k开头的字符串，检查相应的起始位置的childPos[字符串第二个字符-'0']是否为0，如果为0，那么说明此情况尚未分配过空间，那么就直接取得静态tire数组的第一个没有被使用的空间的下标，作为存储此种情况的空间，然后依次类推，直到最后遍历完了字符串，
那么就在当前的位置的tireNode将appearTime+1，标志此字符串又出现了一次.
下来来到对本题的判断，
有两种情况是NO：
（1）在向tire树加入字符串时，在遍历字符串的每个字符时发现，发现已经存在一个该字符串的前缀字符串
（2）在想tire树加入字符串时，在添加完此字符串时发现，该情况已经被一个更长的字符串标记过了。（一开始就在这里遗漏了）
这两种其实反应的都是一个问题：在这一堆字符串里，有字符串是另一个字符串的前缀，可以实现按照长度进行排序，这样就绝不会出现情况2.
也可以通过增加标记的办法来不排序解决。
case 1: 借助appearTime就可以，在加入的过程中，每到一个tirenode， 就检查此node的appearTime， 如果>=1，说明之前已经有完整的前缀串。NO
case 2: 借助usedTime，该变量标志着有几个字符串在加入的过程中经过此tirenode， 如果某个字符串在此node结束，而又发现之前已经有更长的字符串经过这里，那么
该字符串必是更长串的子串（这是因为只要两个字符串经过同一个node，那么必定在此node之前的字符全部都相等，否则不可能在此相遇）。NO
一个难点是确定tire静态数组的大小，一直找不到一个办法推导。
还要注意的就是静态数组每次使用前清空，并且数组的可用索引位置要从 10 开始（前0~9个已经被占用了）
tire树还要找几道练连, 静态tire的还要再理理。