首页 > 其他分享 >ABC215E 题解

ABC215E 题解

时间:2023-06-03 19:44:35浏览次数:54  
标签:ABC215E int 题解 字母 text include dp

前言

题目传送门!

更好的阅读体验?

萌萌 DP 题。

思路

题目就是在说从 \(a\) 里面按顺序掏出来一些字母,使得相同的字母都是相邻的(比如 AABBBBCD 可行,AAABBCAA 不行)。

看起来很不可做,突破口在于 \(\text{A} \sim \text{J}\) 一共只有 \(10\) 个字母,考虑状压


设 \(dp_{i,s}\) 表示选第 \(i\) 个字母,当前选取的子集为 \(s\)(二进制状压),方案数。

直接刷表。对于子集 \(s\) 中的一个已选位 \(i\),枚举 \(i < j \le n\):

  • 如果 \(a_i = a_j\),说明可以将 \(s\) 扩充上 \(a_j\),所以 \(dp_{j,s} \gets dp_{i,s}\)。
  • 如果 \(a_j \ne a_j\),分两种情况:
    • \(a_j\) 已经在 \(s\) 里出现过。由于 \(a_i \ne a_j\),所以 \(a_j\) 与它之前的伙伴并不相邻,不合法。
    • \(a_j\) 并没有出现过。于是可以新开一个伙伴的组合,即 \(dp_{j, s \cap a_i} \gets dp_{i, s}\)。

初始化 \(dp_{i, \{a_i\}} = 1\),答案即 \(\sum\limits_{} dp_{i, s}\)。

代码

时间复杂度 \(O(n^2 2^T)\),\(T\) 是 \(a\) 出现的不同字母数。注意到代码里的两层枚举都有剪枝,所以实际跑起来飞快。

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 998244353;
int dp[1005][(1 << 10) + 5]; //dp[i][j] : 当前选第 i 个字母,选取子集为 j,方案数
int main()
{
	int n; string a;
	cin >> n >> a;
	for (char &x : a) x -= 'a';
	a = '%' + a;
	
	for (int i = 1; i <= n; i++) dp[i][1 << a[i]] = 1;
	for (int s = 0; s < (1 << 10); s++)
		for (int i = 1; i <= n; i++)
			if (s & (1 << a[i]))
				for (int j = i + 1; j <= n; j++) {
					if (a[i] == a[j])             (dp[j][s] += dp[i][s]) %= mod;
					else if (!(s & (1 << a[j])))  (dp[j][s | (1 << a[j])] += dp[i][s]) %= mod;
				}
	int ans = 0;
	for (int s = 0; s < (1 << 10); s++)
		for (int i = 1; i <= n; i++)
			ans = (ans + dp[i][s]) % mod;
	cout << ans;
}

希望能帮助到大家!

标签:ABC215E,int,题解,字母,text,include,dp
From: https://www.cnblogs.com/liangbowen/p/17454445.html

相关文章

  • 道路翻修题解
    \(\mathcal{Description}\)给定一张无向图,为每条边定向,定义每个点的价值为出度与入度之差的绝对值,求最大价值和。对于\(40\%\)的数据,\(1\leqn,m\leq20\)。对于\(70\%\)的数据,\(1\leqn\leq17\)。对于\(90\%\)的数据,\(1\leqn\leq22\)。对于所有数据,\(1\leqn\leq25\)......
  • CF1808E3 题解
    题意传送门求有多少包含\(n\)位数码的\(k\)进制数,满足存在一位数等于其他\(n-1\)位数的总和模\(k\)。\(1\len\le10^{18},1\lek\le2000\)。题解简单的组合数学都不会了……蔬菜越来越多,我该怎么办?条件等价于存在某一位\(x\),满足\(2x\equivs\pmodk\)。容易想到......
  • P1545 [USACO04DEC] Dividing the Path G 题解
    丢一发好理解又好写的线段树优化dp。题目传送门简要题意给定一个长为\(l\)的线段,求出尽量少的不相交区间覆盖整段线段,要求题目给的所有子区间只被\(1\)个区间覆盖。分析显然题目给的子区间\([s,e]\)中只有\(s\)和\(e\)端点能作为线段端点,所以我们应该给\([s+1,......
  • 【Pytorch】ValueError: not enough values to unpack (expected 2, got 1)问题解决
    在运行开源项目时出现了这个问题,网上很多说删回车或者都改成英文符号,但是我都试了,没用后来自己摸索出的方法是:先更改数据集的格式,之前分隔符是\t,把数据集中的分隔符改成空格,再把语句中的\t也换成空格,然后就不会报错了。改前:改后:......
  • python pip安装库时遇到fatal error的问题解决
    当时的图片没有留,写点东西做备忘吧。一开始尝试pipinstallxx库,cmd提示pip不是批处理文件或命令,解决方法:去属性的高级设置里,在用户变量的Path里增加pip所在的路径,如果不知道pip在哪里,就在cmd里输入wherepip查询,查不到就在文件管理里用查询。解决这个问题后,再尝试安装,错误提示......
  • 杂项题解
    JOISC2017_JAbduction2由于权值较高的路不会被权值较低的路线影响,所以首先考虑将\(h+w\)条边按照权值降序排序,再考虑应该的最优决策方案。注意到每一条路都横跨原始的矩形,这样以出发点为中心向上下左右发散就会有4条边构成一个小矩形。考虑维护这个矩形每条边的最大路径......
  • [ROI 2018] Innophone 题解
    [ROI2018]Innophone看了半天网上仅有的一篇题解……才堪堪写出来不过在LOJ上看提交,全是KTT,看得我瑟瑟发抖(不会题意翻译在平面上有一些点,你需要在这个平面上任意确定一个点(不要求是给定的点),定义其贡献为横坐标\(\times\)其右侧的点\(+\)纵坐标\(\times\)其左上方的......
  • docker apt-get update失败问题解决
    一、问题描述docker容器相当于linux系统的精简版,内部很多指令是无法直接使用的,例如vim指令,为了使用vim指令,我们需要进入容器内部进行安装,安装步骤为:apt-getupdateapt-getinstallvim很多时候我们发现安装会失败,这里是由于下载源问题。二、解决方案1.进入宿主机下cd/e......
  • 问题解决:Ubuntu18.04显示器分辨率不正常
    在Ubuntu18.04下出现显示器分辨率不正确的情况,只能选择1024x768的分辨率,没有其它选项,显示器本身可以支持1920x1080的分辨率。经查询,采用cvt,xrandr的方法不成功,显示xrandr:Failedtogetsizeofgammaforoutputdefault的错误,采用修改grub的方法如下解决方法修改/etc/defaul......
  • k8s问题解决 - 删除命名空间长时间处于terminating状态
    一行命令解决,注意替换两处待删命名空间字样kubectlgetnamespace"待删命名空间"-ojson\|tr-d"\n"|sed"s/\"finalizers\":\[[^]]\+\]/\"finalizers\":[]/"\|kubectlreplace--raw/api/v1/namespaces/待删命名空间/finali......