正文索引 [隐藏]

传送门

题目大意

一个序列s，题目定义两种编码方式：

第一种方式是p，其中pi表示第i个右括号之前的左括号数；
第二种是w，其中wi表示第i个右括号(包括它本身)之前完成匹配的括号对数。

现给出序列s在p方式下的编码，求出它在w方式下的编码序列。

思路

已知条件是p序列，那就从p序列入手。

对于pi，设j<i，那么pi-pj的含义显然是第j个右括号与第i个右括号之间的左括号数。而且不难得知，wi能达到的最大值就是i-j，因为括号能匹配成功的前提是有富余的右括号。那么按照这个逻辑去枚举每一对(i,j)就行了。

代码

#include <cstdio>
#include <iostream>

using namespace std;

int t, n;
int str[110];

int main() {
	cin >> t;
	while(t--) {
		cin >> n;
		for(int i = 0; i < n; i++) {
			scanf("%d", &str[i]);
			int j = i - 1;
			while(str[i] - str[j] < i - j) j--;
			printf("%d ", i - j);
		}
		cout << endl;
	}
	return 0;
}