poj-1068

数组都开到100以后，AC了。。。

#include <stdio.h> 

 #include <string.h> 


 void fillS(char * S, int * P, int Plength, int * Pdst) { 

     if (P == Pdst + 1) { 

         return; 

     } 

     int leftParentheseNum = P[0]; 

     for (int i = 0; i < leftParentheseNum; i++) { 

         *(S + i) = '('; 

     } 

     *(S + leftParentheseNum) = ')'; 

     for (int i = 0; P + i <= Pdst; i++) { 

         *(P + i) -= leftParentheseNum; 

     } 

     fillS(S + leftParentheseNum + 1, P + 1, Plength, Pdst); 

 } 


 void getW(int * P, int Plength) { 

     char parenthesisArray[100] = {0}; 

     int W[100] = {0}; 

     fillS(parenthesisArray, P, Plength, P + Plength -1); 

     // printf("Fills"); 

     // printf("%s %d\n", parenthesisArray, (int)strlen(parenthesisArray)); 

     int WId = 0; 

     for (int i = 0; i < strlen(parenthesisArray); i++) { 

         if (parenthesisArray[i] == ')') { 

             for (int k = i-1; k >= 0; k--) { 

                 if (parenthesisArray[k] == '(') { 

                     parenthesisArray[k] = ' '; 

                     int rightNum = 0; 

                     // printf("%d %d\n", k + 1, i - 1); 

                     for (int j = k + 1 ; j <= i-1 ; j++) { 

                         if (parenthesisArray[j] == ')') { 

                             rightNum++; 

                         } 

                     } 

                     // printf("num: %d\n", rightNum + 1); 

                     W[WId] = rightNum + 1; 

                     WId++; 

                     break; 

                 } 

             } 

         } 

     } 


     for (int i = 0; i < Plength; i++) { 

         printf("%d ", W[i]); 

     } 

     printf("\n"); 

 } 


 void test() { 

     int P[21] = {4, 5, 6, 6, 6, 6}; 

     int Plength = 6; 

     getW(P, Plength); 

 } 


 int main() { 

     int caseNum = 0; 

     scanf("%d", &caseNum); 

     for (int i = 0; i < caseNum; i++) { 

         int P[100] = {0}; 

         int Plength = 0; 

         char tmp; 

         scanf("%d", &Plength); 

         for (int i = 0; i < Plength; i++) { 

             scanf("%d%c", P + i, &tmp); 

         } 

         getW(P, Plength); 

     } 
}

本题不难， 但是可选的方法挺多的，看discuss里很多用stack的，

我在这里从P 推导出 括号内容的时候用了分治法，

然后再由括号内容推P的时候用了最笨的挨个查找（其实这里就可以用栈了， 不过其实也不简单， 还要反复把右括号出进栈， 跟括号有关的很多都应该联想到栈）。

还有就是scanf接受本题这种类型的参数 可以用 %d%c将空格跳过。

发现自己还是太毛躁， 脑子没想清楚， 手就动了， 还做不到完整的在脑中勾勒出整个程序。

标记一下， 看discuss似乎该题有更简单的办法， 回头研究研究。