题意分析

题目背景

本题属于字符串处理与括号匹配问题，要求将括号字符串的P序列转换为对应的W序列。两种序列的定义如下：

1. P序列：表示每个右括号之前出现的左括号总数。
2. W序列：表示每个右括号与其匹配的左括号之间的括号对数（包括自身）。

输入输出

• 输入：
  • 测试用例数量$t$。
  • 每个测试用例包含：
    • 整数$n$（右括号数量）。
    • P序列（$n$个整数）。
• 输出：对应的W序列。

示例分析

对于输入：

6
4 5 6 6 6 6

• P序列解释：
  • 第1个右括号前有4个左括号。
  • 第2个右括号前有5个左括号（比前一个多1，说明中间有1个左括号）。
  • 以此类推，最终括号字符串为(((()()())))。
• W序列计算：
  • 第一个右括号匹配最内层左括号，之间无其他括号对，输出1。
  • 第四个右括号匹配最外层左括号，之间有3对括号，输出4。

解题思路

1. 重建括号字符串

• 步骤：
  1. 初始化空字符串$s$。
  2. 遍历P序列，计算相邻元素的差值$d = p[i] - p[i-1]$（$p[-1]=0$）。
  3. 每次添加$d$个左括号'('，再添加一个右括号')'。
  4. 记录每个右括号的位置到数组$a$。

2. 计算W序列

• 步骤：
  1. 对于每个右括号位置$a[i]$：
     • 向左搜索匹配的左括号，统计之间的括号对数。
     • 遇到右括号时计数器$count$加1，遇到左括号时减1。
     • 当$count=0$时停止，此时$max$即为W序列值。

3. 关键算法

• 括号匹配：通过栈模拟或计数器实现。
• 复杂度优化：直接遍历重建的字符串，避免显式构建栈。

算法实现

代码框架

#include<bits/stdc++.h>
using namespace std;
char s[200];  
int p[200], w[200], a[200]; 
void k(int n)
{
    int count, max, i;
    
  
    for (i = 0; i < n; i++)
    {
        count = 1; 
        max = 1;   
        
        do
        {
            if (s[a[i] - 1] == ')') 
            {   
                count++;
                max++;  
            } 
            else
                count--;
        
            a[i]--; 
        } while (count);
        
        w[i] = max; 
    }
}
 
int main()
{
    int x, n, i, j, m, k1, k2, a1;
    
    
    cin>>x;
    for (i = 0; i < x; i++)
    {
        cin>>n;
        for (j = 0; j < n; j++)
            cin>>p[j];
        m = 0;  
        k1 = 0;
        a1 = 0; 
        
     
        for (j = 0; j < n; j++)
        {
            for (k2 = 0; k2 < p[j] - m; k2++) 
            {
                s[k1 + k2] = '(';
            }
            
            s[k1 + k2] = ')'; 
            a[a1] = k1 + k2;  
            a1++;            
            k1 += (p[j] - m + 1);
            m = p[j];
        }
 
        k(n);
        
        for (j = 0; j < n; j++)
            cout<<w[j]<<" ";
        
        cout<<"\n";
    }
 
    return 0;
}

关键步骤

1. 重建字符串：
   • 根据P序列差值动态添加括号。
   • 记录右括号位置。
2. 计算W值：
   • 反向遍历匹配左括号，统计深度。
   • 输出括号对数（$max\_depth / 2$）。

复杂度分析

• 时间：$O(t \cdot n^2)$，其中$n$为括号数量，最坏情况下需遍历字符串多次。
• 空间：$O(n)$，存储字符串和位置数组。