首页 > 其他分享 >[ARC157F] XY Ladder LCS 题解

[ARC157F] XY Ladder LCS 题解

时间:2024-03-07 16:38:08浏览次数:27  
标签:nxt 匹配 状态 题解 Ladder ST XY 我们 dp

我们尝试给这个抽象题来一篇题解。

思考过程还是很重要的。

首先看了这个题,一看数据范围 \(n\le 50\),然后就不懂了,你告诉我这玩意可以状压??

然后我们一顿乱想,发现如果 \(n\) 除以一个 \(3\),那我们是不是就可以状压了。

那怎么除以 \(3\) 呢。

接着我们手玩一下样例,发现似乎这个答案他不是很小啊。

然后我们继续,我们发现,如果答案够大,那么我们公共子序列的两对匹配点,假设在 \(S,T\) 分别为 \((i_1,j_1),(i_2,j_2)\),他就可以保证 \(|\max \{i_2-i_1,j_2-j_1\}|\le n-ans\)。

所以,如果我们的答案 \(ans \ge \dfrac{n}{3}\)(向下取整),那我们就可以把两对匹配点之间的交换状况直接状压出来。

那么我们胡乱证明一下:

我们可以把这个序列分成若干个长度为 \(3\) 的连续段,例如 \([1,3],[4,6],[7,9]\) 之类。

然后由于 \(S_i,T_i\in\{X,Y\}\),所以我们可以在里面把 \(2^6\) 种情况全部暴力枚举出来,然后发现里面至少会产生一个长度为 \(2\) 的公共子序列,所以答案必然 \(\ge \dfrac{2n}{3}\)。

最终我们就通过一系列联想得到了这个结论。

然后有一个非常重要的东西,如果我们把 \(X\) 当作 \(1\),\(Y\) 当作 \(0\),那么最终答案就是这个二进制串的最大值,完美将方案输出,字典序最小,还有个数最大结合在一起。

然后我们考虑怎么状压。

这个状态是真的抽象啊,考场上纯属乱想的状态,好难解释。。

我们定义 \(dp_{i,ST}\),表示当前在 \(S,T\) 中考虑到了 \(i\),从上次匹配点到当前点的状态为 \(ST\) (这个 \(ST\) 我很难解释,就是指在中间这一段中,你的 \(S,T\) 可以取的字符,\(X\) 为 \(1\),\(Y\) 为 \(0\),由于可以交换,所以我们就将 \(S,T\) 不区分开,不然你对两个都要打一个状态),的最小字典序(这个字典序就用上述的二进制串表示,其实就是这个二进制串的最大值)。

考虑顺推,这逆推太难了。

以及,为了方便,我们将 \(1\) 作为初始状态,因为我们后面要从最高位开始向下找第一个满足条件的,所以需要先把最高位立在前面。

我们钦定 \(S_i=X\) 是,\(a_i=0\),否则 \(a_i=1\)。对于 \(T_i\) 对应 \(b_i\) 同理。

然后,如果我们不在这一步进行匹配,由于没有区分 \(S,T\),就有下面两种情况:

  • \(dp_{i+1,ST<<1|a_i} = \max\{dp_{i+1,ST<<1|a_i},dp_{i,ST}\}\)

  • \(dp_{i+1,ST<<1|b_i} = \max\{dp_{i+1,ST<<1|b_i},dp_{i,ST}\}\)

(当然,进行这一步的前提是,你左移之后不会超过 \(2^{\frac{2n}{3}}\))

接着,如果我们要用 \(S_i,T_i\) 进行匹配,那么分为 \(3\) 种情况:

  • 用 \(S_i\) 匹配 \(T_i\),也就是 \(S_i=T_i\) 时。那么显然有 \(dp_{i+1,0} = \max \{ dp_{i+1,0},dp_{i,ST} << 1|a_i\}\)。

  • 用 \(S_i\) 匹配前面的状态。我们从最高位开始(因为是左移,所以越高位越前面,而我们当然贪心的希望去选前面的符合要求的来匹配)找到第一个二进制位上等于 \(a_i\) 的位置,将后面全部删掉,然后再将 \(b_i\) 加入这个状态的首位(因为他没使用),假设操作完毕的状态为 \(nxt\),那么有 \(dp_{i+1,nxt}=\max \{dp_{i+1,nxt},dp_{i,ST}<<1|a_i\}\)。

  • 用 \(T_i\) 同理,将第二种情况的 \(a,b\) 和 \(S,T\) 交换一下就行。

由于此时时间复杂度已经达到 \(n\times 2^{\frac{n}{3}}\),所以对于 \(nxt\),我们直接用一个 \(Nxt[ST][0/1][0/1]\) 来预处理即可。

这部分之前考试都有想到,但是范智打错。。

我们可以在思考一下正确性,就是你每次遇到 \(S_i,T_i\) 要么将两者互相匹配,要么在后续状态中也只会选择其中的一个进行匹配,故状态只需要维护一个。

最后找到 \(dp_{n,i}\) 的最大值(因为是二进制串),然后转化为 \(X,Y\) 输出即可。

话说这题二进制串的到处乱移是真恶心。

\(\texttt{Code}\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long dp[65][1 << 21];
int nxt[1 << 21][2][2];
int n;
char a[65], b[65];
signed main()
{
//	freopen("try.in", "r", stdin);
//	freopen("try.out", "w", stdout);
	scanf("%lld", &n);
	scanf("%s", a + 1), scanf("%s", b + 1);
	int limit = ceil(n / 3.0); 
	for (int i = 1; i < (1 << limit); ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			for (int k = 0; k < 2; ++k)
			{
				int pos = -1;
				for (int l = (__lg(i) - 1); l >= 0; --l) if(((i >> l) & 1) == j)
				{
					pos = l;
					break;
				}
				if(pos == -1) continue;
				nxt[i][j][k] = (((i & ((1ll << pos) - 1)) + (1 << pos)) << 1) + k;
			}
		}
	}
	dp[0][1] = 1;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < (1 << limit); ++j)
	{
		if(!dp[i][j]) continue;
		int p = (a[i + 1] == 'X'), q = (b[i + 1] == 'X');
		if(nxt[j][p][q]) dp[i + 1][nxt[j][p][q]] = max(dp[i + 1][nxt[j][p][q]], (dp[i][j] << 1) + p);
		if(nxt[j][q][p]) dp[i + 1][nxt[j][q][p]] = max(dp[i + 1][nxt[j][q][p]], (dp[i][j] << 1) + q);
		if(((j << 1) + p) < (1 << limit)) dp[i + 1][(j << 1) + p] = max(dp[i + 1][(j << 1) + p], dp[i][j]);
		if(((j << 1) + q) < (1 << limit)) dp[i + 1][(j << 1) + q] = max(dp[i + 1][(j << 1) + q], dp[i][j]);
		if(p == q) dp[i + 1][1] = max((dp[i][j] << 1) + p, dp[i + 1][1]);
	}
	long long ans = 0;
	for (int i = 0; i < (1 << limit); ++i) ans = max(ans, dp[n][i]);
	int cnt = __lg(ans);
	for (int i = cnt - 1; i >= 0; --i) if((ans >> i) & 1) putchar('X'); else putchar('Y');
	return 0;
}

标签:nxt,匹配,状态,题解,Ladder,ST,XY,我们,dp
From: https://www.cnblogs.com/SFsaltyfish/p/18059182

相关文章

  • [青少年CTF训练平台]web部分题解(已完结!)
    文章管理系统首先打开环境(>ω<。人)ZZz♪♪既然要做题,就要做全面了,图上说了,既然有假flag我就先找出来:假flag:打开vmware,使用sqlmap进行处理:sqlmap-uhttp://challenge.qsnctf.com:31645/?id=1--dbs记得中间的url换成自己的看到了六个可能:{*]ctftraining[*]information......
  • CF1353E K-periodic Garland 题解
    分析考虑DP。定义状态函数\(f_i\)表示处理完前\(i\)个字符且第\(i\)个字符为\(1\)时的最小代价。则对于\(i\),有两种情况:\(i\)不是第一个\(1\),则上一个\(1\)的位置必定为\(i-k\)。\(i\)是第一个\(1\),没有上一个\(1\)。得到转移方程:\(f_i=\min(f_{\max(......
  • P10120『STA - R4』冰红茶 题解
    分析出得很好,模板套模板,希望下次再来。难点在于维护最后连续喝的DS饮料数量。设这次喝原味饮料的区间为\([l,r]\),上一次为\([l',r']\)。则有两种情况:\([l,r]\)与\([l',r']\)不相交。如:在\([l',r']\)和\([l,r]\)两个区间中的DS连续喝的同种饮料数量都会变成\(k......
  • AT_abc343_f [ABC343F] Second Largest Query 题解
    分析考虑乱搞。对于求次大值,用线段树维护就行了。记录下每个区间的最大、次大值。则两个子区间的父区间的最大值就是这四个最大的,次大值就是这四个次大的。复杂度\(O(\logn)\)。求次大值的出现次数,乱搞就行了。因为带修,带修莫队或者分块有些麻烦。其实用线段树就行。在维护区......
  • P8058 [BalkanOI2003] Farey 序列 题解
    分析考虑二分答案。对于当前二分的答案\(x\),设\(cnt\)表示Farey序列中\(\frac{p}{q}\lex\)的满足条件的数量。对于一组\((i,j)\),若\(\frac{j}{i}\lex\),则\(j\le\lfloori\timesx\rfloor\)。得到暴力式子:\[cnt=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloo......
  • P9989 [Ynoi Easy Round 2023] TEST_69 题解
    分析考虑线段树。\(20\)分统计节点懒标记,在每次询问之前统一下传\((lst,i-1)\)的修改懒标记,\(lst\)是上一次询问的位置。\(40\)分在统一下传的过程中打标记,如果当前节点的某个儿子所在子树中没有需要下传懒标记的节点,则不更新那个儿子的内容。\(70\)分注意到\(a\)......
  • CF1915G Bicycles 题解
    分析参照去年普及组T4,很显然能发现就是一个暴力最短路。设\(dis_{i,j}\)表示从\(1\)走到\(i\)且能得到的\(s\)最小为\(j\)时的最短路。那么答案就是\(\min\{dis_{n,i}|1\lei\leV\}\)。考虑最短路转移。对于当前的\(dis_{u,j}\),走到\(v\)的代价将会是\(w_{u......
  • AT_abc252_g [ABC252G] Pre-Order 题解
    分析考虑区间DP。定义状态函数\(\mathit{f}_{l,r,1/0}\)表示在\(P_l,P_{l+1},\dots,P_r\)这些点中,\(P_l\)是或不是唯一(子)树根时的答案。对于\(\mathit{f}_{l,r,1}\),\(P_l\)的第一个儿子一定是\(P_{l+1}\)。所以有:\(f_{l,r,1}=f_{l+1,r,1/0}\)(\(P_{l+1}\)是或不是\(P......
  • AT_abc338_f [ABC338F] Negative Traveling Salesman 题解
    分析考虑状压。定义状态函数\(f_{i,j}\)表示在经过点的情况为\(i\)且最后停在点\(j\)的最小花费。那有:\(f_{i,j}=\min\{f_{i',k}+w_{k\toj}|k\toj\}\)。然后就过不了样例一。根据样例一,可以发现\(f_{3,2}=f_{2,2}+w_{2\to1}+w_{1\to2}\)。也就是说我们在原本已经走......
  • P4958 [COCI2017-2018#6] Mate 题解
    分析考虑DP。先考虑\(A\)的答案。定义状态函数\(f_{i,j}\)表示在子串\(S_{1\dotsi}\)中选\(j\)个,且第\(S_i\)必选的方案数。则有:\(f_{i,j}=C_{i-1}^{j-1}\)。再考虑\(B\)的答案。枚举每一个位置\(x\)。令\(sum_x=\sum\limits_{i=1}^{x-1}f_{i,n-1}[S_i=A]\)。......