1 PhoenixAres

尚未进行身份认证

暂无相关简介

等级
TA的排名 36w+

Tak and Cards —— dp

原题链接:Atcoder044C题意简述给出 n 个整数,在这些数中选择任意多个整数使得其平均数为A,求共有多少种方法思路分析dp[i][j] 表示选取 i 个数其和为 j 的方法数,初始状态 dp[0][0] = 1状态转移:每当读到第 i 个数 x 时,遍历选取 1 <= j <= i 个数和这 j 个数的和 k(即遍历dp[1~i] [ x~ A * n] ),更新其...

2020-04-25 14:23:07

Brackets —— 区间dp

原题链接:POJ-2955题意简述给出一串括号序列(圆括号和方括号),求其括号匹配数思路分析区间dp,dp[i][j]表示 i~j 区间内的最大匹配数。首先假设s[i]和s[j]不匹配,则dp[i][j] = dp[i+1][j],然后在区间k(i+1~j)之间寻找s[i]和s[k]匹配,状态转移 dp[i][j] = max(dp[i][j],dp[i+1][k-1]+dp[k+1][j...

2020-04-23 18:20:03

Fadi and LCM

原题链接:CF-1285C题意简述给定一个整数 x,求两个数 a,b,使得 a,b的最小公倍数为 x,且max( a , b)最小思路分析由 ab / gcd(a,b) = x ,设A = a / gcd(a,b) , B = b,则AB = x那么 A 和 B 肯定是互质的,且 A ≤ sqrt(x)从大到小枚举A,使gcd(A,B) = 1,A*B = X,第一个符合条件的A和B就...

2020-04-19 17:34:46

String Problem —— 最小表示法+KMP

原题链接:HDU-3374题意简述给出多组数据,每一组数据是一个字符串 s,问 s 的哪个位置是最小字符串,哪个位置是最大字符串,以及他们各出现了几次。思路分析利用最小表示法求出最小串的开始位置,最大字符串同理,然后利用 kmp 算法求出出现的次数源代码:#include<bits/stdc++.h>using namespace std;const int maxn...

2020-04-05 10:56:22

Glass Beads —— 最小表示法

题意简述给定字符串 s(仅由小写字母组成),定义 i 比 j 小为 s[ i ]s[ i+1 ] … s[ n ]s[ 1 ] … s[ i-1 ] 构成的字符串的字典序比 s[ j ]s[ j+1 ] … s[ n ]s[ 1 ] … s[ j-1 ] 构成的字符串小,求 s 中最小的 i 的位置。思路分析设两个指针 i 和 j 和一个记录相同前缀长度的 k , i 表示原串的起点, j ...

2020-04-02 13:06:44

str2int —— 后缀自动机

题意简述将 n 个只包含数字的字符串转化为 10 进制整数,然后求和,再求和对 2012 的余数思路分析广义SAM,每个点记录一个 ans,表示它代表的字符串的值的和。如果有前缀 0,需要单独记录,用 zr 记录有多少个串是有前缀 0 的。源代码:#include<bits/stdc++.h>using namespace std;const int maxn = 2e...

2020-04-02 12:16:17

String —— SA与SAM

原题链接:CF-123D题意简述给出一个字符串 s,求 s 的所有不同子串的贡献和,每种子串的贡献为 k*(k+1)/2,k 为该子串出现的次数思路分析后缀数组可以考虑将 k*(k+1)/2 进行分步求解,用 cnt 记录该子串出现的次数,每出现一次,cnt 加1,然后 ans += cnt,这样就可以一步一步求解贡献。后缀自动机直接SAM,然后把每一段 [ val [ fa[i]...

2020-03-29 15:51:06

Life Forms —— 后缀数组(一)

题意简述给出 n 个字符串,在这 n 个字符串中求一个最长子串使得其在 n/2 及以上个字符串中出现过,如果没有,输出 ?思路分析后缀数组 + 二分将 n 个字符串连接成一个长字符串,两两之间用不同的分隔符隔开,然后求其后缀数组 SA 和 height,然后二分子串长度进行查找,一旦找到符合要求的就进行输出源代码:#include<bits/stdc++.h>using...

2020-03-26 11:18:59

String —— AC自动机(二)

原题链接:HDU-6096题意简述给出 n 个字符串,再给出 q 个查询,每次查询读入两个字符串 p,s,求在 n 个字符串中以 p 为前缀且以 s 为后缀的字符串有多少个思路分析考虑 AC 自动机,其本质是求 n 个模式串在 1 个文本串中出现的次数,我们将每次查询时读入的 p,s 以 s + ‘#’ + p 的格式构建新的字符串,然后建立 trie 树,记录结点位置。然后将 n 个字符...

2020-03-26 11:08:54

Indie Album —— AC自动机(一)

原题链接:CF-1207G题意简述有 n 个字符串,第 i 个字符串由以下两种方式给定:一个小写字母,表示当前字符串一个数字 j(j < i),一个小写字母 c,表示当前字符串由第 j 个字符串后加一个字符 c 构成再给出 m 个查询,每个查询给定一个数字 i 和一个字符串 s,输出 s 在第 i 个字符串中出现了多少次思路分析如果 n = 1,即文本串只有一个,就是多模式...

2020-03-22 11:14:53

Dr. Evil Underscores —— trie树(一)

原题链接:CF-1285D题意简述给定 n 个整数,要求找到一个数 X,使得这 n 个数分别与 X 进行异或时的最大值最小,输出这个最小值思路分析提及异或,应当可以想到 01 trie,其本质试将 n 个数转换成 2 进制存储在 trie 树上。现在假设我们构造了一个 30 位的 01 trie 树,试图去寻找这样的 X,从高位到低位遍历 trie 树:如果一个结点只有一个分支,那么...

2020-03-21 09:59:04

Easy Problem —— 字符串dp(一)

原题链接:CF-1096D题意简述给定字符串 s (仅包含小写字母)及其长度 n,再给出 n 个整数 a [ n ],分别表示移除字符串 s 的每一个位置的字符的代价,要求最少代价,使得 s 中不存在 hard (可以不相邻,比如 hssacfrd 也包含 hard)。思路分析考虑 dp,如果用 dp[ i ] [ j ] 表示 s 的前 i 个字符清理到 hard 的第 j 个字符的最小...

2020-03-17 21:39:08

Matrix Matcher —— 字符串Hash(四)

原题链接崩了,在这给出题面:二维Hash模板原题题面Given an N × M matrix, your task is to find the number of occurences of an X × Y pattern.InputThe first line contains a single integer t (t ≤ 15), the number of test case...

2020-03-17 21:08:49

k-substrings —— 字符串Hash(三)

原题链接:CF-961F题意简述对于字符串 s ,其长度为 n,定义 s 的 k-子串为 s [ k , n - k + 1] ,其中 k = 1,2,3,……,⌈ n / 2 ⌉(大于等于 n / 2 的最小整数),要求在 s 的每一个 k-子串中找到长度最大的既是其前缀,又是其后缀的子串,输出该长度(长度为奇数),如果没有,则输出 -1思路分析对于一个字符串 s ,其每一个 k-子串都...

2020-03-15 11:08:45

Isomorphic Strings —— 字符串Hash(二)

原题链接:CF-985F题意简述给定字符串 s ,其长度为 n ,接下来依次给出 m 次询问,每一次询问包括三个整数 x ,y ,len,要求判断 s [ x , x + len - 1 ] 和 s [ y , y + len - 1 ] 这两个子串是否同构,如果为真,输出 YES ,否则输出 NO思路分析要判断两个子串是否同构,即判断能否找到一个映射,能够将一个子串映射到另一个子串,举...

2020-03-15 10:03:56

Camp Schedule —— KMP(二)

原题链接:CF-1137B题意简述给定两个由 0 和 1 构成的字符串 s,p,要求找到字符串 s 的一个排列(可以任意改变其中 0 和 1 的位置,但不能增加或减少),使得 p 在重新排列得到的字符串中出现的次数最多,如果答案有多个,输出任意一个,如果找不到这样一个排列,则输出 s 的任意一个排列,1 <= | s |,| p | <= 500000思路分析如果根据题意正向思...

2020-03-09 22:10:04

Restoring the Expression —— 字符串Hash(一)

原题链接:CF-898F题意简述给定一个字符串 s ,其中只包含数字0 ~ 9,要求将该字符串分成三段 a ,b ,c ,使得 a + b == c,然后按照 a + b = c 的格式输出,a ,b,c 均不含有前导0,输入保证有且仅有唯一解,其中 | s | <= 1e6思路分析根据题意,可以理解为将 ‘+’ 和 ‘=’ 插入字符串,将字符串分成 3 部分,如果暴力枚举,那么时间...

2020-03-09 17:22:10

Tavas and Malekas —— KMP(一)

原题链接:CF-535D题意简述给定原字符串长度 n 和模式串 p ,再给出 m 个原字符串中下标位置,若用模式串 p 能够成功覆盖这 m 个位置(字符串覆盖时不发生冲突),则输出原串的所有可能个数(均由小写字母组成),否则输出0。思路分析用 x 数组存放 m 个下标位置,按照题意,应依次进行字符串覆盖,即将 p 依次拷贝到这 m 个位置,设模式串 p 长度为 l ,那么显然:当 x ...

2020-03-07 14:23:16

C++ String类——溯源STL(一)

简介1. String类是模板类 typedef basic_string<char> string;3. 使用String类需要包含头文件 <string>4.

2020-02-23 13:14:24
勋章 我的勋章
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。