redoCxz

未归档

ACM练习赛(18) ACM练习题(418) BZOJ刷题(5) C++算法模板(20) codeforce(4) hdu(8) java(16) Java算法模板(24) kotlin(1) Leetcode(12) Lintcode(26) 剑指offer(1) 拓展欧几里德(1) 最小生成树(1) 杂七杂八(41) 水题(1) 牛客网(2) 牛客网错题总结(1) 算法四(2) 题解(1)

/ 注册

全部文章 / 未归档（共13篇）

【算法学习】回文树

#include <bits/stdc++.h> using namespace std; const int N=1e5+50; struct PT{ //回文树中每个节点表示一个回文串，所以有偶数长度的树和奇数长度的树两棵 //next指针 next[u][i]表示u...

算法回文树字符串

2019-07-25

0 436

2019杭电多校第一场

6581 Vacation 题意从右到左分别为0-n辆车，每辆车有长度l，起始位置s和速度v，0坐标在左边，不能超车，单车道，问0号车到达0坐标的最短时间。分析最短时间考虑二分时间，然后按这个时间从左边第一辆车开始依次计算最终位置，最后判断0号车的位置即可。代码 #include...

二分答案图论最短路网络流最小割字符串序列自动机贪心题解

2019-07-26

0 605

2019杭电多校第二场

6595 Everything Is Generated In Equal Probability 题意给定一个\(n\)，从\([1,n]\)中等概率取出一个数，再等概率生成一个\(n\)的全排列，再计算这个全排列的函数值，求这个函数值的期望。函数表达为输入一个全排列，计算其逆序数，再等...

题解概率思维主席树字符串回文树字符串哈希

2019-07-26

0 481

2019牛客多校第四场

A meeting 题意给一棵树，以及树上的\(k\)个点，要求一个点使得这k个点到这个点的最大距离最小。分析简单的做法就是求出这\(k\)个点在树上的最远距离，类似于求树直径的做法，然后点肯定取在直径一半处。代码 #include <bits/stdc++.h> u...

题解字符串后缀数组回文树单调队列线段树 dfs 最短路分层图最短路 dp 树的直径

2019-07-27

0 491

2019牛客多校第三场

B Crazy Binary String 题意给一个01字符串，求0和1个数相同的最长子序列和子串长度。分析子序列长度就是\(min(cnt(0),cnt(1))*2\)，子串的长度也是原题，记录一下0和1个数差的前缀和，然后用一个数组记录前面扫过的0个数和1个数差值的最左位置，前缀...

题解前缀和字符串单调队列模拟

2019-07-28

0 496

2019牛客多校第六场

A Garbage Classification 题意给定一个字符串代表垃圾，26个字符每个字符代表某种组成成分，根据题意判断垃圾类别。分析温暖的签到题，注意别写成除法就行。代码 #include <bits/stdc++.h> using namespace std...

题解模拟字符串模拟字符串回文树 dfs dp 枚举二分蔡勒公式全排列前缀和

2019-08-05

0 433

2019牛客多校第七场

A String 题意给定一个01串，求最少的划分次数，使得每部分的01串都是循环字典序最小。分析从最长的整个串贪心，暴力判断是否是循环字典序最小，若是，直接输出前面的串，然后后面的串再进行新一轮判断。代码 #include <bits/stdc++.h> using...

题解贪心字符串模拟前缀和线段树思维权值线段树

2019-08-09

0 523

luoguP2444_[POI2000]病毒

题意给定多个01模式串，问是否存在一个无限长的字符串不包含任何一个模式串。分析好像数据有点水，网上一大堆题解连样例都没过？？？多模式串，先把AC自动机建出来再说。反向考虑，若存在一个无限长的字符串不包含任何一个模式串，那就说明这个字符串可以在AC自动机上无限匹配，所以我...

题解字符串 AC自动机 dfs

2019-08-22

0 458

2019CCPC网络赛

hdu6703 array 题意给定一个1到\(n\)的全排列，两种操作，将\(a_{pos}\)修改为\(a_{pos}+1000000\)，询问第一个大于等于\(k\)的且不在\(a_1...a_r\)的数。分析由于\(k<=n\)，因此操作二询问的答案最大是\(n+1...

题解权值线段树后缀数组字符串主席树优先队列图论

2019-08-25

0 626

poj3415_Common Substrings

题意给定两个字符串，求长度大于等于k的公共子串数。分析将两个字符串中间加个特殊字符拼接，跑后缀数组。将题目转化为对每一个后缀求\(\sum_{j=1}^{i-1}lcp(i,j)\)，且后缀\(i\)和\(j\)属于不同字符串。由于\(lcp\)只跟\(h\)数组的区间...

题解后缀数组单调栈字符串

2019-08-25

0 333