首页 > B-Suffix Array
开通博客写题解
头像 Scarlet_Hypoc
发表于 2020-07-16 07:41:16
A. B-Suffix Array 给出一个字符串，定义一个字符串 ~ 对应的 ~ 满足 ，如果不存在这样的 ，那么 ，现在要求将 的所有后缀按照其对应的 序列的字典序排列。 题解很神，用到一个神仙结论直接切飞，原文为（为了好看些，我自己稍微加了点 LaTeX 元素）： Let T 展开全文
去ta的博客 赞 (25) 回复(0) 收起
头像 帅小🐠
发表于 2020-07-13 22:50:56
传送门 求(贝塔函数运用) 证明： 法二： [贝塔函数---链接](https://baike.baidu.com/item/%E8%B4%9D%E5%A1%94%E5%87%BD%E6%95%B0/4643050?fr=aladdin)考点： 费马定理 $$ 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 bbqd
发表于 2020-07-12 17:15:20
https://ac.nowcoder.com/acm/contest/5666/F #include <iostream> #include <cstdio> #include <cstdlib> #include <string> using na 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 Vanishment
发表于 2020-07-18 00:57:48
[A-B-Suffix Array] 证明+基于sais的实现 前言 很棒的一道题目。（知识增加.jpg） 下面简述一下证明，因为本人水平较菜，且本篇为阅读了"Parameterized Suffix Arrays for Binary Strings"后的半笔记性质的记录，故本文证明过程可能包含： 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 daicon
发表于 2020-09-19 16:24:19
做法 对于字符串的第 个字符，定义对偶函数 ，其含义为：对于原串的第 个字符，找到它之后与它相同的字符位置 ，结果的第 个元素即为 。如果不存在这样的字符，相应的结果为 。就像题中的函数 ，一个字符串的函数 就是由每个位置的 组成。定义 上的小于关系为字典序从大到小，并且前缀优先。 举例 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 daicon
发表于 2020-09-19 16:27:50
考虑使用拉格朗日乘数法$$求偏导 可得 代入运算可得 代码 #include <bits/stdc++.h> using namespace std; #define paii pair<int,int> #define fr first #define sc second 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 daicon
发表于 2020-09-19 16:32:59
题解 可以证明该三元组满***换律和结合律，同时单位元为(1,0,0),满足快速幂，但是幂次可以达到存不下，使用JAVA或者PYTHON大数也显然会T，然后选择将幂次对进行取模（别问我为什么，我也不知道），然后就好做了。###代码 #include <bits/stdc++.h> usi 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 eat12ac
发表于 2020-07-30 23:36:07
A 思维 思路 函数 关于字符串 的后缀数组并不好求，因为每个 的后缀并不是 的后缀，我们尝试正难则反。 因此，我们考虑函数 ，满足：1、2、3、如果找不到这样的 ， 可以发现一个01字符串 ，它对应的 越大，那么它的 越小，可知 与 是反序关系。 由于每个 的后缀就是 的后缀 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”