POJ-3630的解题思路有哪些？

本文共计1233个文字，预计阅读时间需要5分钟。

GCC编译器+版本号+编译选项+编译时间

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的还要再理理。