当前位置: 首页 > news >正文

【做题记录】P9753 [CSP-S 2023] 消消乐

Tags:

  • DP状态设计
  • 观察性质

题目链接

这道题状态设计十分巧妙。

直接转移显然不切实际。我们不妨“消消乐”的性质入手:

如果区间 \([i,j],[j+1,k]\) 都是可消除的,那么 \([i,k]\) 一定也是可消除的。根据此性质,我们设置辅助数组 \(g\) 维护当前字符可以和之前那个字符形成区间并且区间是可消除的。

具体步骤如下:

  • 我们从 \(j=i-1\) 开始,一直往前跳 \(j=g_j -1\),这样如果遇到有一个位置 \(s_j=s_i\) 的话,新的 \(g_i\) 就是 \(j\) 了。

状态的转移:\(f_i=f_{g_i-1}+1\)

最终答案:\(\sum_{i=1}^n f_i\)

代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N(2e6+5);
int n,g[N];
ll f[N],ans;
string s;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>s;for(int i(1);i<=n;++i){for(int j(i-1);j>0;j=g[j]-1){if(s[j-1]==s[i-1]){g[i]=j;break;}}if(g[i])f[i]=f[g[i]-1]+1,ans+=f[i];}cout<<ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=33900

相关文章:

  • 南京icpc-c题:
  • 题解:P14254 分割(divide)
  • 学生信息管理系统(DAO模式重构)项目报告
  • 思科公司分析
  • 桃星中央关于重大去向问题的初步决定
  • Google Deepmind 宣布与 CFS 合作开发核聚变
  • 10.18
  • 开源嵌入模型对比:让你的RAG检索又快又准
  • C++lambda表达式简单笔记
  • 智慧城市基础设施漏洞分析与国家安全影响
  • ️ PostgreSQL 数据类型
  • CSP-J/S 2025 第一轮游记
  • 【汇编和指令集 . 第2025 .10期】万般皆为投影
  • 小作业 12
  • Python 潮流周刊#123:你可能不需要单例模式
  • Python 潮流周刊#122:Python 3.14 来了,速度如何?
  • 机器学习在视频质量检测中的技术应用
  • 基于博客园和xmlrpc的Typora图片上传脚本
  • 一位焦虑的普通二本软件工程的学生
  • C++类的运算符重载
  • 10.18 CSP-S模拟34/2025多校CSP模拟赛6 改题记录
  • 微软Office LTSC 2021(KpoJIuK直装版)x64 v16.0.14334.20344 10月版
  • 征程 6 | 征程 6 工具链如何支持 Matmul/Conv 双 int16 输入量化?
  • 结对项目:自动生成小学四则运算题目的命令行程序
  • 做题技巧与结论证明
  • 1. 两数之和
  • CSP-S模拟34/2025多校冲刺CSP模拟赛6
  • PostgreSQL 逻辑结构
  • 随机数技术