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

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 AB1

所以两个字符串押韵当且仅当在 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=xsonivalx

显然有转移 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=xsonxmax(fx)+szi1+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

由于题目涉及到后缀&#xff0c;不难想到用 trie 树处理。 将每个字符串翻转插入 trie&#xff0c;后缀就变成了前缀&#xff0c;方便处理。 条件 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 的实体&#xff0c;它有一个名为 amount 的 Double 属性&#xff0c;向你的 View 添加一个计算属性&#xff1a; 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方向 题目解法 首先一个套路是普通幂转下降幂&#xff08;为什么&#xff1f;因为观察到 k k k 很小&#xff0c;下降幂可以转化组合数问题&#xff0c;从而 d p dp dp 求解&#xff09; 即 f ( X ) k ∑ i 0 k { k i } i ! ( f ( X ) i ) f(X)^k…...

力扣每日一题36:有效的数独

题目描述&#xff1a; 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考…...

钉钉数字校园小程序开发:开启智慧教育新时代

随着信息技术的快速发展和校园管理的日益复杂化&#xff0c;数字校园已成为现代教育的重要趋势。钉钉数字校园小程序作为一种创新应用&#xff0c;以其专业性、思考深度和逻辑性&#xff0c;为学校提供了全新的管理、教学和沟方式。本文从需求分析、技术实现和应用思考三个方面…...

数据结构与算法--其他算法

数据结构与算法--其他算法 1 汉诺塔问题 2 字符串的全部子序列 3 字符串的全排列 4 纸牌问题 5 逆序栈问题 6 数字和字符串转换问题 7 背包问题 8 N皇后问题 暴力递归就是尝试 1&#xff0c;把问题转化为规模缩小了的同类问题的子问题 2&#xff0c;有明确的不需要继续…...

矩阵键盘行列扫描

/*----------------------------------------------- 内容&#xff1a;如计算器输入数据形式相同 从右至左 使用行列扫描方法 ------------------------------------------------*/ #include<reg52.h> //包含头文件&#xff0c;一般情况不需要改动&#xff0c;头文件包含…...

unity 实现拖动ui填空,并判断对错

参考&#xff1a;https://ask.csdn.net/questions/7971448 根据自己的需求修改为如下代码 使用过程中&#xff0c;出现拖动ui位置错误的情况&#xff0c;修改为使用 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 神经元模型 神经网络是由具有适应性的简单单元组成的广泛并行互连的网络&#xff0c;它…...

FPGA project : flash_erasure

SPI是什么&#xff1a; SPI&#xff08;Serial Peripheral Interface&#xff0c;串行外围设备接口&#xff09;通讯协议&#xff0c;是Motorola公司提出的一种同步串行接口技术&#xff0c;是一种高速、全双工、同步通信总线&#xff0c;在芯片中只占用四根管脚用来控制及数据…...

AC修炼计划(AtCoder Regular Contest 166)

传送门&#xff1a;AtCoder Regular Contest 166 - AtCoder 一直修炼cf&#xff0c;觉得遇到了瓶颈了&#xff0c;所以想在atcode上寻求一些突破&#xff0c;今天本来想尝试vp AtCoder Regular Contest 166&#xff0c;但结局本不是很好&#xff0c;被卡了半天&#xff0c;止步…...

Android---Android 是如何通过 Activity 进行交互的

相信对于 Android 工程师来说&#xff0c;startActivity 就像初恋一般。要求低&#xff0c;见效快&#xff0c;是每一个菜鸟 Android 工程师迈向高级 Android 工程师的必经阶段。经过这么多年的发展&#xff0c;startActivity 在 google 的调教下已经变得愈发成熟&#xff0c;对…...

【论文解读】单目3D目标检测 MonoCon(AAAI2022)

本文分享单目3D目标检测&#xff0c;MonoCon模型的论文解读&#xff0c;了解它的设计思路&#xff0c;论文核心观点&#xff0c;模型结构&#xff0c;以及效果和性能。 目录 一、MonoCon简介 二、论文核心观点 三、模型框架 四、模型预测信息与3D框联系 五、损失函数 六、…...

Angular知识点系列(5)-每天10个小知识

目录 41. Angular的路由守卫42. 处理文件的上传和下载43. Angular的动画系统44. 使用第三方库和选择评估45. 性能优化46. AOT和JIT编译47. 处理响应式布局和适配不同屏幕尺寸48. Angular的国际化&#xff08;i18n&#xff09;49. Angular的PWA开发50. 使用Angular Material或其…...

基于海洋捕食者优化的BP神经网络(分类应用) - 附代码

基于海洋捕食者优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于海洋捕食者优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码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代码优化---本人的例子

直接上货&#xff1a; 1&#xff1a;数据统计 店铺数量、提现金额、收益金额、用户数量 旧&#xff1a; // //店铺// $storey db( store )->whereTime( addtime, yesterday )->count();//昨天// $stored db( store )->whereTime( addtime, d )->count();//今天…...

EMC Unity存储(VNXe) service Mode和Normal Mode的一些说明

本文介绍下EMC unity存储设备&#xff08;也包含VNXe存储设备&#xff09;的两种工作模式&#xff1a; Service mode&#xff1a;也叫做rescue mode&#xff0c;存储OS工作不正常或者有其他故障&#xff0c;就会进入这个模式&#xff0c;无法对外提供服务Normal mode&#xff…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...