专栏文章

题解：CF123C Brackets

__ckx_
CF123C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0mipf
此快照首次捕获于
2025/12/01 18:37
3 个月前
此快照最后确认于
2025/12/01 18:37
3 个月前
查看原文
题意就不写了，直接写思路吧。

分析

所有的从 (1,1)(1,1) 到 (n,m)(n,m) 的路径都是合法括号串，看看能不能发现一些性质：
如上图，绿色路径与红色路径都是合法括号序，而两者只有一个位置有区别，所以这两个位置必相同（即上图啊 (1,3)(1,3) 和 (2,2)(2,2) 必相同），以此类推，每一条从左下到右上的斜线上的括号都相同。
有了这个结论，我们相当于知道一条路径，就能推出整个矩形，所以每个长度为 n+m−1n+m-1 的合法括号序都对应一个合法括号矩形。
此时，每个位置的优先级（即原 cc 数组）就是其代表的斜线上的位置的 cc 的值的 min⁡\min。
然后我们就可以按优先级从小到大贪心放括号了：首先尝试当前位置放左括号，算出合法的括号序数量 ss，如果 s≥ks \ge k，那么当前位置就放左括号，否则就放右括号，并将 kk 减去 vv。
现在我就只剩求出：确定了某些位置的合法括号序数量，直接 DP：fi,jf_{i,j} 表示前 ii 个括号，左括号数量与右括号数量的差为 jj 的方案数，最终结果就是 fn+m−1,0f_{n+m-1,0}。
这道题就结束了，时间复杂度 O(n3)O(n^3)。

code

CPP
#include <bits/stdc++.h>
using namespace std;
typedef unsigned __int128 ll;
#define pii pair<ll ,ll>
#define ft first
#define sd second
 
ll read()
{
    ll ret = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -f : f), ch = getchar();
    while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int n ,m; ll k;
const int inf = 1e9;
const int N = 210;
int a[N][N] ,s[N];
pii b[N];
ll f[N][N];

int main()
{
	n = read() ,m = read() ,k = read();
	
	for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) a[i][j] = read();
	
	for (int i = 1;i <= n + m - 1;i++)
	{
		int x = (i > m ? i - m + 1 : 1) ,y = (i > m ? m : i);
		int mn = inf;
		for ( ;x <= n && y >= 1;x++ ,y--)
			mn = min(mn ,a[x][y]);
		b[i] = {mn ,i};
	}
	
	memset(s ,-1 ,sizeof(s));
	n = n + m - 1;
	sort(b + 1 ,b + 1 + n); //按优先级排序贪心 
	for (int i = 1;i <= n;i++)
	{
		s[b[i].sd] = 0; // s = 0 表示左括号 
		memset(f ,0 ,sizeof(f));
		f[0][0] = 1; // DP 求合法括号序数量 
		for (int j = 1;j <= n;j++)
			if (s[j] == 0)
				for (int k = 1;k <= n;k++)
					f[j][k] = f[j - 1][k - 1];
			else if (s[j] == 1)
				for (int k = 0;k < n;k++)
					f[j][k] = f[j - 1][k + 1];
			else
				for (int k = 0;k <= n;k++)
				{
					f[j][k] = f[j - 1][k + 1];
					if (k) f[j][k] = f[j][k] + f[j - 1][k - 1];
				}
		if (f[n][0] < k) k -= f[n][0] ,s[b[i].sd] = 1; //放右括号 
	}
	
	//还原矩阵 
	n = n - m + 1;
	for (int i = 1;i <= n + m - 1;i++)
		if (i <= m) a[1][i] = s[i];
		else a[i - m + 1][m] = s[i];
	for (int i = 2;i <= n;i++)
		for (int j = m - 1;j >= 1;j--)
			a[i][j] = a[i - 1][j + 1];
	
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
			printf("%c",a[i][j] == 0 ? '(' : ')');
		puts("");
	}
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...