111qqz的小窝
Home
ACM-ICPC
深度学习 icon
caffe源码阅读笔记 推荐系统 计算机视觉
公开课 icon
6.828 CS341 CSAPP
工程 icon
cpp cuda levelDB源码笔记 linux 前端 图像处理 容器
随笔杂谈
面试
About
🌐
English Chinese
  • 【施工中】SAM学习笔记

    Nov 4, 2017 · 4 min read · 后缀自动机

    ***在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机*** 怕是老年人的最后一篇算法学习笔记了 心情不好,此文无限期tj 概述 主要讲解在我学习的过程中比较难理解的地方..并不保证全面 首先,后缀自动机是一个能且只能接受一个字符串的所有后缀的确定性有限状态自动机,也就是DFA SAM同时具有自动机和树的性质。 节点(状态) SAM中的节点,也叫状态。 明确一个说法:“一个节点所表示的字符串”。 由于一个字符串的子串一定是某个后缀的前缀。 因此一个字符串的子串一定可以在SAM上运行。 因此“一个节点Q所表示的字符串”的含义是说,从初始状态开始,运行该字符串后,到达的状态是Q. 一个节点所表示的字符串长度属于范 …


    Read More
  • poj 1509 Glass Beads (后缀自动机求最小循环表示)

    Nov 4, 2017 · 2 min read · 后缀自动机 最小表示法

    题意: 给定一个循环字符串,问字典序最小的串的开始位置。 思路: 之前用poj 1509 解题报告-字符串的最小表示法 A过 字符串的最小表示法的复杂度是O(n),代码也不是很难写,不过由于最近在学SAM,所以用SAM写了一下。 参照张天扬的论文: 把原串复制一遍到后面,然后构建后缀自动机。 从初始状态开始,每次走字典序最小的转移,走|S|之后得到的就是最小循环表示。 如果求的是最小后缀,就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后,再添加一遍原串。 /* *********************************************** Author :111qqz Created Time …


    Read More
  • hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)

    Nov 4, 2017 · 2 min read · 后缀自动机

    http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意: 给一个字符串,给出若干询问,每组询问给一个区间[l,r],问区间中本质不同的字符串的个数。 思路: 观察发现,有10000组查询,字符串的长度最多才2000,所以可以预处理一波。 我们先考虑如何处理整个区间中,本质不同的子串数量。 考虑SAM,由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串,同时后缀自动机是最简的,所以问题也就变成了从初始状态开始不同路径的数量。 每个节点 u 表示的子串长度在 [min[u],max[u]]范围内. 又由于max(u.fail) = min(u)-1 因此u表示的子串的长度就是变成 …


    Read More
  • SPOJ LCS Longest Common Substring (后缀自动机模板题)

    Nov 3, 2017 · 5 min read · 后缀自动机

    题意: 给出2个字符串(2.5E5),问最长公共子串的长度。 思路: 拿一个串建SAM 由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿另一个串在SAM上面跑就行了 20171110UPdate:我好像说得太简略了。。 参考clj的冬令营讲稿: * 给两个长度小于100000的字符串A和B,求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM * 对于SAM的每个状态s,令r为Right(s)中任意的一个元素,它代表的是结束位置在r的,长度在[Min(s),Max(s)]之间的所有子串。 * 我们不妨对状态s,求出所有B的子串中,从任意r开始往前能匹配的最大长度L,那么min(L,Max(s))就可以更 …


    Read More
  • HDU 5970 | 2016 CCPC HeFei onsite J 最大公约数 (打表找规律)

    Nov 2, 2017 · 2 min read · 打表

    题意: 有这样一个有关最大公约数的函数: 函数 f(x, y): { c=0 当 y>0: { c +=1 t = x % y x = y y = t } 返回 c * x * x } 给出三个正整数n,m,p,你需要计算: $$ \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{i*j}{f(i,j))} \right \rfloor $$ n <= 666,666,666, m <= 666, p <= 666,666,666。 思路: 打表找规律。 但是找规律也要按照基本法 观察到m比较小,对于固定的j,容易看出f(i,j)和f(i+j*k,k)是等价 …


    Read More
  • hdu 6038 | 2017 Multi-University Training Contest - Team 1 E Function (置换群找循环节)

    Nov 1, 2017 · 2 min read · 循环节 置换群

    http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意: 给出两个序列 a 和 b ,求满足 f[i]= b_{f[a[i]]} 的函数个数。 思路: 分别找两个序列的循环节,这一点是比较容易想到的。 由于点都在0..n-1 或者0..m-1,因此没必要建图跑dfs找循环节,直接while就可以了。 然后发现一个循环节如果符合条件,那么对答案的贡献是循环节长度。 但是没有想清楚,什么才是符合条件的循环节。 结论是,b的循环节长度当且近当是A的循环节的长度的因子时,b的这个循环节会对答案贡献其长度的大小。 对于A的每个循环节,都是互不影响的。 而且我们只关心循环节的长度。 因此O(n) …


    Read More
  • hdu 6034 2017 Multi-University Training Contest - Team 1 B Balala Power! (贪心)

    Nov 1, 2017 · 3 min read · 贪心

    http://acm.hdu.edu.cn/showproblem.php?pid=6034 题意: 有一个仅由小写字母组成的字符串,要求将a..z的字母,对应到0..25,每个数字只能被一个字母对应,得到一个26进制的数,现在问这个数最大是多少。注意不允许有前导0,除非这个数本身就是0. 思路: 贪心。看哪个字母的权值最大。 可以用类似高精度加法的方式处理。 对于前导0的部分,用一个bool标记首位(如果字符串长度为1就不标记) 对于26个高精度数的排序,可以用交换id的技巧。 以及,如果排序之后,发现权值最小的数被对应到数字0,但是又在某个长度大于1的字符串的首字母位置出现过。 我初始想当然得,把该字母和最小的可以出现在首位的字 …


    Read More
  • BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改,区间查询)

    Nov 1, 2017 · 2 min read · lazy标记 线段树

    1230: [Usaco2008 Nov]lites 开关灯 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1676 Solved: 874 [Submit][Status][Discuss] Description Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= …


    Read More
  • hdu 6043 | 2017 Multi-University Training Contest - Team 1 K KazaQ's Socks (循环节)

    Oct 31, 2017 · 1 min read · 循环节

    http://acm.hdu.edu.cn/showproblem.php?pid=6043 题意: n双袜子标号1到n,初始在抽屉里,每天早晨穿一双标号最小的袜子,晚上把脏袜子放到盆里,如果放完之后喷子里已经有了n-1双脏袜子,那么就要洗,然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。 思路: 手写了几个发现对于n双袜子,标号出现的情况是: 1,2,3...n,1,2,3...n-2,n-1,1,2,3...n-2,n 所以特判k<=n的情况然后算循环的次数即可。 /* *********************************************** Author :111qqz Created …


    Read More
  • hdu 6033 | 2017 Multi-University Training Contest - Team 1 A Add More Zero

    Oct 31, 2017 · 1 min read

    http://acm.hdu.edu.cn/showproblem.php?pid=6033 题意: 问最大的x,满足 $$ 10^{x} \geq 2^{m}-1 $$ 思路: 看到指数的比较大小,直觉就是取下对数啦 其实直接可以把1忽略,因为2的幂次显然不会出现末尾是0,所以不会影响结果 两边对10取对数得到 $$ x\leq \log_{10} 2^{m} $$ 右边用换底公式就是 $$ \frac{m}{\log_{2}10 } $$ 代码: /* *********************************************** Author :111qqz Created Time :2017年10月31日 …


    Read More
    • ««
    • «
    • 17
    • 18
    • 19
    • 20
    • 21
    • »
    • »»

111qqz

深度学习框架工程师@Tencent, ex-ICPCer@HUST
Read More

Recent Posts

  • caffe 源码阅读笔记
  • Goodbye 2024
  • [施工中] cupy与torch的导入顺序不同对计算结果的影响
  • 写在毕业五年之后
  • Build Onnxruntime With Bazel
  • Goodbye 2022
  • 【施工中】gitlab ci docker executor指定用户执行
  • [施工中]caffe 源码学习笔记(11) softmax

Categories

ACM 913 其他 90 DEEP-LEARNING 68 面试 63 随笔杂谈 62 工程 59 计算机视觉 21 MOOC 15 优化 10 C++ 4 生活 1

Series

CAFFE源码阅读笔记 13 LEVELDB代码阅读笔记 9 CSAPP 7 CPP-FAQ 1 MODERN-CPP 1

Tags

DP 71 MATH 49 线段树 43 BRUTE-FORCE 39 LEETCODE 38 GREEDY 36 DFS 34 NUMBER-THEORY 27 CPP 26 模拟 24 博弈论 22 构造 22 BINARY-SEARCH 21 母函数 21
All Tags
01背包9 2-SAT1 6.8284 AC自动机4 ANACONDA1 ANCHOR-BOX1 ANTI-SG2 ARCHLINUX2 ASYNC1 ATOM1 AVX1 AWK1 BAZEL1 BFS20 BINARY-SEARCH21 BINARY-SEARCH-TREE1 BITSET优化4 BLOG1 BOOST1 BOOSTING1 BRUTE-FORCE39 BSGS4 C++7 C++111 CACHE1 CAFFE14 CAFFE21 CALL-STACK1 CALL_ONCE1 CDQ分治3 CHECKPOINT1 CHROMEBOOK1 CI1 CMAKE1 CODEFORCES1 CONDITION_VARIABLE1 CONVOLUTIONAL-NEURAL-NETWORK1 CPP26 CS231N1 CS3411 CSAPP7 CSE599W1 CUDA6 CUMULATIVE-MATCH-CHARACTERISTI1 CUPY1 D1 DFS34 DFS序1 DIJKSTRA2 DISCOURSE1 DL-SYS1 DOCKER6 DP71 EIGEN1 END-TO-END1 FACTORIAL-NUMBER-SYSTEM1 FASTER-RCNN3 FEATURE-PYRAMID-NETWORKS1 FEDORA1 FISH1 FLOYD10 FLOYD-判圈2 FPN1 FUTURE2 G++1 GALLIUMOS1 GCC1 GCD2 GDB1 GEDIT1 GEEKOS4 GITHUB1 GITLAB1 GOLANG1 GREEDY36 GRPC2 GRUB1 GRUNDY1 HALIDE2 HAPROXY1 HASH13 HASH-MAP1 HASKELL1 HIGH-PERFORMANCE-COMPUTING1 HUGO2 IMAGE-DENOISING1 INCEPTION1 JAVA5 JAVASCRIPT1 JDK1 JETSON-NANO2 JSON1 K-MEANS2 K-SUM3 K8S2 KAFKA1 KD-TREE6 KM14 KMP19 KM算法1 LATENT-FACTOR-MODEL1 LATEX1 LAZY标记9 LCA10 LEETCODE38 LEVELDB10 LINEAR-CLASSIFICATION1 LINUX9 LINUX-MINT1 LIS5 LOG2 LRU2 LSTM1 LUA1 LUCAS定理3 MANACHER4 MANJARO3 MAP6 MATH49 MEAN-AVERAGE-PRECISION1 METRIC-LEARNING1 MILLER-RABIN素数测试1 MODEL-CONVERTOR1 MODEL-DISTILLATION1 MODERN-CPP10 MPI1 MST6 MURMURHASH1 MUTUAL-LEARNING1 MYSQL3 NERDTREE1 NETWORK1 NIM游戏4 NLP1 NMS1 NON-LOCAL-MEANS1 NON-LOCAL-NEURAL-NETWORKS1 NUMBER-THEORY27 NUMPY1 OBJECT-DETECTION2 ONCE_FLAG1 ONNXRUNTIME1 PACKAGED_TASK1 PCA2 PERFECT-FORWARDING1 PIPLINE1 POSE-DRIVEN1 PRIM1 PROMISE2 PROPERTY_TREE1 PROTOBUF1 PYTHON11 PYTORCH2 QT5 REACT3 REDIS1 REDUX1 REID3 RESNET2 RETINANET1 RMQ17 RNN1 SET8 SG函数12 SHADOWSOCKS2 SIMD1 SIMHASH1 SIMILARITY-LEARNING1 SINGLE-STATE-DETECTOR1 SJ定理2 SLIDING-WINDOWS1 SLIM1 SORT1 SORTINGS3 SPFA10 SPRING2 SSD1 STDANY1 STDSHARED_PTR1 STEAM2 STL16 STREAM1 SUPERCOMPUTING1 SUPERVISOR1 TARJAN2 TENSORFLOW12 TENSORRT2 THREADING-BUILDING-BLOCKS1 THRUST1 TREE7 TRIE7 TRIPLET-LOSS1 TSP2 TWO-POINTER5 TYPESCRIPT1 UNICODE1 VALUE-CATRGORY1 VARIADIC-FUNCTION1 VARIETY1 VECTOR2 VIM6 VUNDLE1 WHITENING1 WORDPRESS1 YOUCOMPLETEME1 YUV-IMAGE-FORMAT1 一致性哈希1 三分2 中国剩余定理4 主席树5 乱搞6 二分2 二分图5 二分图匹配4 二分图最佳匹配14 二次剩余4 二维线段树1 二进制1 二项式定理1 交互题1 交叉染色法6 京东1 优先队列4 传递闭包5 位运算4 依赖注入1 偏度1 光流法1 内存屏障1 凸包1 分块12 分布式消息系统1 分治2 分类讨论1 前端6 前缀和17 剩余系3 剪枝1 动态线段树1 动态连通性1 勾股数1 匈牙利算法15 区间DP13 区间合并1 区间第K大2 区间计数1 协同过滤1 单调性优化1 单调栈10 单调队列3 博弈论22 反向传播1 反素数5 可持久化数据结构5 同构1 后缀和1 后缀数组10 后缀自动机13 哥德巴赫猜想1 四叉树1 回文串2 回文自动机7 图像处理2 图论16 图论基础1 基础图论1 字符串14 字符串DP1 字符串循环同构4 完全背包2 容斥原理5 对拍1 射线法1 尺取2 尺取法10 局部敏感HASH2 峰度1 差分序列1 巴什博奕5 年终总结1 并查集9 并行计算2 康托展开1 康托展开/逆展开2 循环展开1 循环节8 快速乘1 快速幂20 快速筛2 思维1 思维题7 打表2 扩展BSGS2 扩展欧几里得算法8 扫描线4 抽屉原理6 拆点6 拓扑排序7 括号匹配2 指数循环节7 排列组合8 推荐系统3 数位DP17 数值计算方法2 数字图像处理2 数据压缩1 数据结构2 数论2 文明1 斐波那契7 斜率优化3 无向图的环3 曼哈顿距离4 最大独立集1 最大连续区间和3 最大连续和1 最小生成树2 最小表示法7 最小覆盖子串3 最小覆盖子矩形1 最小路径覆盖2 最小顶点覆盖2 最短路5 最长下降子序列1 最长公共字串4 最长路2 构造22 枚举子集4 染色问题1 栈1 树套树1 树形DP6 树状数组20 树的直径9 梯度下降1 概率13 模型转换1 模拟24 模拟退火5 次小生成树2 欧拉函数4 欧拉路1 正则表达式1 母函数21 水5 水题7 泰勒展开3 游戏1 激活函数1 爬山法1 爬虫2 状压DP1 状态压缩1 百度1 矩形周长并1 矩形面积交1 矩阵20 矩阵快速幂5 离散化11 符号可见性1 符号表1 第二类斯特林数1 筛法1 系统调用1 线段树43 组合数学10 组合模式1 组成原理1 细节题1 结论题1 编译原理1 编译器1 置换群1 莫队算法10 蓄水池抽样1 虚点1 裴蜀定理5 观察者模式1 计数排序2 计数问题10 计算几何20 计算机视觉2 计组1 记忆化搜索2 设计模式2 贝尔数2 贪心1 费马小定理3 费马点1 路径DP1 路径记录2 输入挂2 辛普森积分2 连通性2 逆元5 逆序对5 递推2 重心1 链式前向星1 错排公式2 面试1 面试经历3 预处理1 高斯消元1 高精度2
[A~Z][0~9]
111qqz的小窝

Copyright  111QQZ的小窝. All Rights Reserved