当前位置: 开发笔记 > 编程语言 > 正文

BZOJ3238:[Ahoi2013]差异后缀自动机树形dp

作者：借钱买黄瓜 | 来源：互联网 | 2023-05-17 20:40

http:www.lydsy.comJudgeOnlineproblem.php?id3238就算是全局变量，也不要忘记，初始化（吐血）。长得一副lca样，没想到是个树形dp（小丫

http://www.lydsy.com/JudgeOnline/problem.php?id=3238

就算是全局变量，也不要忘记，初始化（吐血）。

长得一副lca样，没想到是个树形dp（小丫头还有两幅面孔呢）。

看代码实现吧，不大容易口头解释，把加的和减的分开算就可以了，减去的通过倒着建sam（相当于建一棵后缀树），然后算每个len取的次数实现，注意树归中一些避免重复操作。

 1 /**************************************************************
 2     Problem: 3238
 3     User: 137shoebills
 4     Language: C++
 5     Result: Accepted
 6     Time:3816 ms
 7     Memory:130688 kb
 8 ****************************************************************/
 9  
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 using namespace std;
17 const int maxn=500010;
18 char ch1[maxn]={};
19 int siz;
20 struct nod{
21     int sig[26];
22     int f,len;
23 }t[maxn*2];int tot=1,la=1;
24 void add(int z){
25     int x=++tot;int i=la;
26     t[x].len=t[la].len+1;
27     for(;i&&!t[i].sig[z];i=t[i].f)
28         t[i].sig[z]=x;
29     if(!i)t[x].f=1;
30     else{
31         int p=t[i].sig[z];
32         if(t[p].len==t[i].len+1)t[x].f=p;
33         else{
34             int y=++tot;
35             t[y]=t[p];t[y].len=t[i].len+1;
36             t[x].f=t[p].f=y;
37             for(;i&&t[i].sig[z]==p;i=t[i].f)
38                 t[i].sig[z]=y;
39         }
40     }
41     la=x;
42 }
43 struct node{
44     int y,next;
45 }e[maxn*2];int cnt=0;
46 int head[maxn*2]={};
47 long long dp[maxn*2]={},sum=0;
48 void init(int x,int y){e[++cnt].y=y;e[cnt].next=head[x];head[x]=cnt;}
49 void dfs(int x){
50     int y;
51     long long num=dp[x]*dp[x];
52     for(int i=head[x];i;i=e[i].next){
53         y=e[i].y;
54         dfs(y);dp[x]+=dp[y];
55         num+=dp[y]*dp[y];
56     }
57     sum+=(dp[x]*dp[x]-num)*t[x].len;
58 }
59 long long solve(){
60     int j=1;
61     for(int i=siz;i>=1;i--){
62         j=t[j].sig[ch1[i]-‘a‘];
63         dp[j]++;
64     }
65     for(int i=2;i<=tot;i++)
66         init(t[i].f,i);
67     dfs(1);
68     return sum;
69 }
70 int main(){
71     memset(t,0,sizeof(t));
72     scanf("%s",ch1+1);siz=strlen(ch1+1);
73     for(int i=siz;i>=1;i--)add((int)(ch1[i]-‘a‘));
74     long long ans=0;
75     for(int i=1;i<=siz;i++)ans+=(long long)i*(siz-1);
76     printf("%lld\n",ans-solve());
77     return 0;
78 }

View Code

BZOJ 3238: [Ahoi2013]差异后缀自动机树形dp

推荐阅读

main
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
main
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
import
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
import
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
import
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
lua
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
lua
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
import
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
list
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
list
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
list
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
list
基于layUI的图片上传前预览功能的2种实现方式

本文介绍了基于layUI的图片上传前预览功能的两种实现方式：一种是使用blob+FileReader，另一种是使用layUI自带的参数。通过选择文件后点击文件名，在页面中间弹窗内预览图片。其中，layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块，并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]

蜡笔小新 2023-12-14 17:06:58
list
Alink回归预测的不完善问题及期待

本文讨论了Alink回归预测的不完善问题，指出目前主要针对Python做案例，对其他语言支持不足。同时介绍了pom.xml文件的基本结构和使用方法，以及Maven的相关知识。最后，对Alink回归预测的未来发展提出了期待。 ... [详细]

蜡笔小新 2023-12-14 14:25:33
list
后台获取视图对应的字符串

1.帮助类后台获取视图对应的字符串publicclassViewHelper{将View输出为字符串(注：不会执行对应的ac ... [详细]

蜡笔小新 2023-12-13 18:03:01
client
ABAP开发发送邮件程序的配置和代码整理

本文介绍了通过ABAP开发往外网发邮件的需求，并提供了配置和代码整理的资料。其中包括了配置SAP邮件服务器的步骤和ABAP写发送邮件代码的过程。通过RZ10配置参数和icm/server_port_1的设定，可以实现向Sap User和外部邮件发送邮件的功能。希望对需要的开发人员有帮助。摘要长度：184字。 ... [详细]

蜡笔小新 2023-12-13 15:50:17

借钱买黄瓜

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章