P7537 [COCI2016-2017#4] Rima
由于题目涉及到后缀,不难想到用 trie 树处理。
将每个字符串翻转插入 trie,后缀就变成了前缀,方便处理。
条件 LCS ( A , B ) ≥ max ( ∣ A ∣ , ∣ B ∣ ) − 1 \text{LCS}(A,B) \ge \max(|A|,|B|)-1 LCS(A,B)≥max(∣A∣,∣B∣)−1,说明 ∣ ∣ A ∣ − ∣ B ∣ ∣ ≤ 1 \left||A|-|B|\right|\le1 ∣∣A∣−∣B∣∣≤1。
所以两个字符串押韵当且仅当在 trie 树上二者是父子或兄弟关系。
考虑树型 DP,设 f i f_i fi 表示 i i i 所代表的字符串在序列最右边的最长序列长度, v a l i val_i vali 表示节点 i i i 是否(1/0)有单词, s z i = ∑ x ∈ s o n i v a l x sz_i=\sum\limits_{x\in son_i}val_x szi=x∈soni∑valx。
显然有转移 f i = max x ∈ s o n x ( f x ) + s z i − 1 + v a l i f_i=\max\limits_{x\in son_x}(f_x)+sz_i-1+val_i fi=x∈sonxmax(fx)+szi−1+vali。
如果 v a l i = 0 val_i=0 vali=0,说明都没有字符串, f i = 0 f_i=0 fi=0。
更新答案时,记录儿子 f s o n i f_{son_i} fsoni 的最大和次大,再加上剩余儿子和自己的 v a l val val。(感性理解,一条链只有两个位置是“自由”的,由此设出 DP 状态)
本题卡空间,所以建 trie 树时要动态开点。
具体实现参见代码。
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int cnt=1,n,f[N],ans;
char a[N];
struct node
{vector<pair<int,int> > son;int fa,val;
}tr[N];
void insert(int rt,char a[],int len)
{for(int i=0;i<len;i++){int x=a[i]-97;for(auto j:tr[rt].son){if(j.first==x){rt=j.second;goto a;}}tr[rt].son.push_back(make_pair(x,++cnt));rt=tr[rt].son.back().second;a:;}tr[rt].val++;
}
void dfs(int rt)
{int aa=0,bb=0,x=0,y=0,sum=0;for(auto i:tr[rt].son){dfs(i.second);sum+=tr[i.second].val;f[rt]=max(f[rt],f[i.second]);if(f[i.second]>aa){bb=aa;aa=f[i.second];y=x;x=tr[i.second].val;}else if(f[i.second]>bb) bb=f[i.second],y=tr[i.second].val;}f[rt]+=sum-x;if(!tr[rt].son.size()) ans=max(ans,tr[rt].val);else ans=max(ans,aa+bb-x-y+sum+tr[rt].val);if(!tr[rt].val) f[rt]=0;else f[rt]++;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",a);int len=strlen(a);reverse(a,a+len);insert(1,a,len);}dfs(1);cout<<ans;
}
相关文章:
P7537 [COCI2016-2017#4] Rima
由于题目涉及到后缀,不难想到用 trie 树处理。 将每个字符串翻转插入 trie,后缀就变成了前缀,方便处理。 条件 LCS ( A , B ) ≥ max ( ∣ A ∣ , ∣ B ∣ ) − 1 \text{LCS}(A,B) \ge \max(|A|,|B|)-1 LCS(A,B)≥max(∣A∣,∣B∣)−1&…...
SwiftUI Swift CoreData 计算某实体某属性总和
有一个名为 Item 的实体,它有一个名为 amount 的 Double 属性,向你的 View 添加一个计算属性: Code: struct ContentView: View {Environment(\.managedObjectContext) private var viewContextFetchRequest(sortDescriptors: [NSSortDescri…...
docker安装skyWalking笔记
确保安装了docker和docker-compose sudo docker -v Docker version 20.10.12, build 20.10.12-0ubuntu4 sudo docker-compose -v docker-compose version 1.29.2, build unknown 编写docker-compose.yml version: "3.1" services: skywalking-oap:image: apach…...
【Codeforces】 CF1097G Vladislav and a Great Legend
题目链接 CF方向 Luogu方向 题目解法 首先一个套路是普通幂转下降幂(为什么?因为观察到 k k k 很小,下降幂可以转化组合数问题,从而 d p dp dp 求解) 即 f ( X ) k ∑ i 0 k { k i } i ! ( f ( X ) i ) f(X)^k…...
力扣每日一题36:有效的数独
题目描述: 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考…...
钉钉数字校园小程序开发:开启智慧教育新时代
随着信息技术的快速发展和校园管理的日益复杂化,数字校园已成为现代教育的重要趋势。钉钉数字校园小程序作为一种创新应用,以其专业性、思考深度和逻辑性,为学校提供了全新的管理、教学和沟方式。本文从需求分析、技术实现和应用思考三个方面…...
数据结构与算法--其他算法
数据结构与算法--其他算法 1 汉诺塔问题 2 字符串的全部子序列 3 字符串的全排列 4 纸牌问题 5 逆序栈问题 6 数字和字符串转换问题 7 背包问题 8 N皇后问题 暴力递归就是尝试 1,把问题转化为规模缩小了的同类问题的子问题 2,有明确的不需要继续…...
矩阵键盘行列扫描
/*----------------------------------------------- 内容:如计算器输入数据形式相同 从右至左 使用行列扫描方法 ------------------------------------------------*/ #include<reg52.h> //包含头文件,一般情况不需要改动,头文件包含…...
unity 实现拖动ui填空,并判断对错
参考:https://ask.csdn.net/questions/7971448 根据自己的需求修改为如下代码 使用过程中,出现拖动ui位置错误的情况,修改为使用 localPosition 但是吸附到指定位置却需要用的position public class DragAndDrop : MonoBehaviour, IBeginDr…...
《机器学习》第5章 神经网络
文章目录 5.1 神经元模型5.2 感知机与多层网络5.3 误差逆传播算法5.4 全局最小与局部最小5.5 其他常见神经网络RBF网络ART网络SOM网络级联相关网络Elman网络Boltzmann机 5.6 深度学习 5.1 神经元模型 神经网络是由具有适应性的简单单元组成的广泛并行互连的网络,它…...
FPGA project : flash_erasure
SPI是什么: SPI(Serial Peripheral Interface,串行外围设备接口)通讯协议,是Motorola公司提出的一种同步串行接口技术,是一种高速、全双工、同步通信总线,在芯片中只占用四根管脚用来控制及数据…...
AC修炼计划(AtCoder Regular Contest 166)
传送门:AtCoder Regular Contest 166 - AtCoder 一直修炼cf,觉得遇到了瓶颈了,所以想在atcode上寻求一些突破,今天本来想尝试vp AtCoder Regular Contest 166,但结局本不是很好,被卡了半天,止步…...
Android---Android 是如何通过 Activity 进行交互的
相信对于 Android 工程师来说,startActivity 就像初恋一般。要求低,见效快,是每一个菜鸟 Android 工程师迈向高级 Android 工程师的必经阶段。经过这么多年的发展,startActivity 在 google 的调教下已经变得愈发成熟,对…...
【论文解读】单目3D目标检测 MonoCon(AAAI2022)
本文分享单目3D目标检测,MonoCon模型的论文解读,了解它的设计思路,论文核心观点,模型结构,以及效果和性能。 目录 一、MonoCon简介 二、论文核心观点 三、模型框架 四、模型预测信息与3D框联系 五、损失函数 六、…...
Angular知识点系列(5)-每天10个小知识
目录 41. Angular的路由守卫42. 处理文件的上传和下载43. Angular的动画系统44. 使用第三方库和选择评估45. 性能优化46. AOT和JIT编译47. 处理响应式布局和适配不同屏幕尺寸48. Angular的国际化(i18n)49. Angular的PWA开发50. 使用Angular Material或其…...
基于海洋捕食者优化的BP神经网络(分类应用) - 附代码
基于海洋捕食者优化的BP神经网络(分类应用) - 附代码 文章目录 基于海洋捕食者优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.海洋捕食者优化BP神经网络3.1 BP神经网络参数设置3.2 海洋捕食者算法应用 4…...
Lift, Splat, Shoot图像BEV安装与模型详解
1 前言 计算机视觉算法通常使用图像是作为输入并输出预测的结果,但是对结果所在的坐标系却并不关心,例如图像分类、图像分割、图像检测等任务中,输出的结果均在原始的图像坐标系中。因此这种范式不能很好的与自动驾驶契合。 在自动驾驶中,多个相机传感器的数据一起作为输…...
MySQL简介
数据库管理系统 1、关系型数据库管理系统: Oracle:Oracle是一种商业级关系型数据库管理系统,支持高可用性、高安全性以及广泛的企业级应用需求。SQL Server:SQL Server是Microsoft开发的企业级关系型数据库管理系统,广泛应用于Windows环境下的软件开发。MySQL:MySQL是一…...
php代码优化---本人的例子
直接上货: 1:数据统计 店铺数量、提现金额、收益金额、用户数量 旧: // //店铺// $storey db( store )->whereTime( addtime, yesterday )->count();//昨天// $stored db( store )->whereTime( addtime, d )->count();//今天…...
EMC Unity存储(VNXe) service Mode和Normal Mode的一些说明
本文介绍下EMC unity存储设备(也包含VNXe存储设备)的两种工作模式: Service mode:也叫做rescue mode,存储OS工作不正常或者有其他故障,就会进入这个模式,无法对外提供服务Normal modeÿ…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
