POJ 3087 解题报告-白红宇

POJ 3087 解题报告

阅读量：4203 次

发布时间：2019-05-26

本文共 1867 字，大约阅读时间需要 6 分钟。

2个多月来的第一道题。。。

实际上很简单。按题意模拟就可以了。这里用的是trie查重，如果遇到重复就说明无论接下来洗多少次牌都不会洗出目标序列了。由于本题trie查重每次都需要查找到最后一层才有可能发现重复（所有洗牌后的序列的长度是一样的），所以trie不是很有效。看discuss直接用map也就过了。

提交后遇到runtime error是因为char字符串末尾处没有初始化成‘\0’。

Accepted

476K

16MS

1914B

/* ID: thestor1 LANG: C++ TASK: poj3087 */#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;const int MAXC = 100 + 1;class Trie{public: // 'H' - 'A' + 1 Trie *next[8]; Trie() { for (int i = 0; i < 8; ++i) { next[i] = NULL; } }};bool insert(Trie *root, char s[]){ bool existed = true; for (int i = 0; s[i] != '\0'; ++i) { int next = s[i] - 'A'; // we have never been here in this test case if (root->next[next] == NULL) { existed = false; root->next[next] = new Trie(); } root = root->next[next]; } return existed;}bool isSame(char s1[], char s2[]) { int i; for (i = 0; s1[i] && s2[i]; ++i) { if (s1[i] != s2[i]) { return false; } } return !s1[i] && !s2[i];}int main(){ int N; scanf("%d", &N); char s1[MAXC], s2[MAXC], s12[2 * MAXC], merged[2 * MAXC]; for (int t = 0; t < N; ++t) { int C; scanf("%d", &C); scanf("%s", s1); scanf("%s", s2); scanf("%s", s12); merged[2 * C] = '\0'; // printf("s1:[%s], s2:[%s]\n", s1, s2); // printf("s12:[%s]\n", s12); int cnt = 0; bool found = false; Trie *root = new Trie(); while (true) { for (int i = 0; i < C; ++i) { merged[2 * i] = s2[i]; merged[2 * i + 1] = s1[i]; } cnt++; // printf("merged:"); // for (int i = 0; i < 2 * C; ++i) { // printf("%c", merged[i]); // } // printf("\n"); if (isSame(merged, s12)) { found = true; break; } if (insert(root, merged)) { break; } for (int i = 0; i < C; ++i) { s1[i] = merged[i]; s2[i] = merged[C + i]; } } if (found) { printf("%d %d\n", t + 1, cnt); } else { printf("%d -1\n", t + 1); } } return 0; }

转载地址：http://qvxli.baihongyu.com/

你可能感兴趣的文章