\(Atcoder-Beginner-Contest-312\)

AB过于简单，在此略去。

\(C-Invisible\) \(Hand\)

题意：给定长为 \(n\) 的数组 \(a\)，长为 \(m\) 的数组 \(b\)，找到最小的非负整数 \(x\)，使得 \(\sum_{i=1}^n[a_i\le x]\ge \sum_{i=1}^m[b_i\ge x]\)

题解：

容易发现，随着 \(x\) 的增大，右式单调不升，左式单调不降，故答案具有单调性。

将两数组排序，二分答案。可以使用 lower_bound 和 upper_bound 快速统计出左右两式。

sort(a+1,a+n+1);sort(b+1,b+m+1);
	int l=0,r=0x3f3f3f3f;
	while(l<r){
		int mid=l+r>>1;
		int x=upper_bound(a+1,a+n+1,mid)-a-1;
		int y=lower_bound(b+1,b+m+1,mid)-b;
		y=m+1-y;
		if(x>=y)r=mid;
		else l=mid+1;
	}
	cout<<l<<"\n";

\(D-Count\) \(Bracket\) \(Sequences\)

题意：给定一个残缺的由 \(\text{(,?,)}\) 构成的括号序列 \(s\)，有若干位置不确定，要求将其补全为完整的括号序列，求方案数，\(n\le 3000\)。

合法括号序列的充要条件是在任意前缀中左括号数量不小于右括号数量，且左括号总数量等于右括号总数量。

复杂度要求 \(O(n^2)\)，显然是动态规划。

考虑设 \(f_{i,j}\) 表示前 \(i\) 个符号里，左括号数量减去右括号数量为 \(j\) 的方案数。

初始化：\(f_{0,0}=1\)

目标：\(f_{n,0}\)

转移：

\[f_{i,j}= \begin{cases} f_{i-1,j-1} & s_i=\text{(}\\ f_{i-1,j+1} & s_i=\text{)}\\ f_{i-1,j-1}+f_{i-1,j+1} & s_i=\text{?} \end{cases} \]

注意边界。

    f[0][0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]=='(') for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];
		else if(a[i]==')') for(int j=0;j<n;j++)f[i][j]=f[i-1][j+1];
		else for(int j=1;j<=n;j++)f[i][j]=(f[i-1][j+1]+f[i-1][j-1])%p;
	}
	cout<<f[n][0]<<"\n";