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

    2017-02-22 · 1 min read · 前缀和

    题目链接

    题意:给一棵树。。问是否存在一条从树根到叶子的路径,使得路径上每个点的val之和等于给定的sum。

    思路:。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。


    阅读更多
  • BZOJ 1303: [CQOI2009]中位数图(前缀/后缀和乱搞)

    2017-01-30 · 2 min read · 乱搞 前缀和 后缀和

    1303: [CQOI2009]中位数图

    Time Limit: 1 Sec  Memory Limit: 162 MB Submit: 2480  Solved: 1529 [Submit][Status][Discuss]

    Description

    给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。


    阅读更多
  • codeforces 381 div 2 D. Alyona and a tree(二分+前缀和)

    2016-11-28 · 2 min read · binary search 前缀和

    题目链接

    d:题意:一棵树,给出边权和点权,定义点v控制点u,当且仅当u是v的子树中的点,并且dis(u,v)<=a[u],其中dis(u,v)为点u到点v路径上的边权和,a[u]为点u的点权,现在问对于每个节点v,其能控制的点有多少个。


    阅读更多
  • hdu 1559 最大子矩阵 (二维前缀和)

    2016-08-03 · 1 min read · 前缀和

    hdu 1559

    题意:给你一个m×n的整数矩阵,在上面找一个x×y的子矩阵,使子矩阵中所有元素的和最大。

    思路:二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。


    阅读更多
  • poj 2796 Feel Good (前缀和,单调栈)

    2016-08-03 · 2 min read · 前缀和 单调栈

    poj 2796

    题意:给出一个人n(1E5)天的情绪值(0..1E6),一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。

    现在求value的最大值,并且输出得到这个最大值的区间。


    阅读更多
  • poj 2082 Terrible Sets (前缀和,单调栈)

    2016-08-03 · 1 min read · 前缀和 单调栈

    poj 2082 题目链接

    题意:这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度,这些矩形并排顺次排列在x轴上,问最大面积。


    阅读更多
  • BZOJ 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 (前缀和)

    2016-04-11 · 2 min read · 前缀和

    1651: [Usaco2006 Feb]Stall Reservations 专用牛棚

    Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 700  Solved: 393 [Submit][Status][Discuss]

    Description

    Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= …


    阅读更多
  • BZOJ 1637: [Usaco2007 Mar]Balanced Lineup (前缀和乱搞)

    2016-04-08 · 3 min read · 乱搞 前缀和

    1637: [Usaco2007 Mar]Balanced Lineup

    Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 503  Solved: 336 [Submit][Status][Discuss]

    Description

    Farmer John 决定给他的奶牛们照一张合影,他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线,每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事,当然这次照相也不例外。他只给一部分牛照相,并且这一组牛的阵容必须是“平衡的”。平衡的阵容,指的是在一组牛 …


    阅读更多
  • BZOJ 1635: [Usaco2007 Jan]Tallest Cow 最高的牛 (差分序列(前缀和的逆))

    2016-04-07 · 2 min read · 前缀和 差分序列

    1635: [Usaco2007 Jan]Tallest Cow 最高的牛

    Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 472  Solved: 278 [Submit][Status][Discuss]

    Description

    FJ’s N (1 <= N <= 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only …


    阅读更多
  • 前缀和问题总结

    2016-02-19 · 2 min read · 前缀和
    There are two types of problems solvable by partial sum.

    1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).

    Solution of all of this problems are the same. You just need to know how to solve one of them.

    Example : You are asked some queries on an array …


    阅读更多
  • hdu 5416 CRB and Tree ( 2015 多校 #10 )

    2016-02-19 · 2 min read · dfs 前缀和

    http://acm.hdu.edu.cn/showproblem.php?pid=5416

    题意:给出一棵树(n<=1E5),定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询(q<=10),每组一个s,问有多少对无序点对(u,v)满足f(u,v)=s. 思路:类似codeforces #340 div 2 E XOR and Favorite Number 先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍,统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);


    阅读更多
  • hdu 5327 Olympiad (2015 多校 #4 )

    2016-02-19 · 1 min read · 前缀和

    http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意:问给出的区间[a,b]中有多少个美丽数,美丽数的定义是所有数字都不相同,如123是,100不是,333也不是。 思路:预处理1..100000的美丽数,可以把每个数字拆开放在set里,比较set的size和位数来实现。 然后用前缀和。


    阅读更多
  • codeforces #340 div 2 E XOR and Favorite Number

    2016-02-15 · 2 min read · 前缀和 莫队算法

    http://codeforces.com/contest/617/problem/E

    题意:给出n个数,m个查询,每个查询给定l,r,问在区间【l,r】内,有多少对i,j,满足i^(i+1)^(i+2)^…^j的值为给定的常数k.


    阅读更多
  • cf 611 A||codeforces goodbye 2015 C. New Year and Domino

    2016-01-01 · 1 min read · 前缀和 模拟

    http://codeforces.com/contest/611/problem/C 题意:给出一个n*m的地图,.表示可以空,#表示墙。一个东西需要占两个相邻的格子,问给定一个矩形,放一个东西的方案数。 思路:q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下,每次标记到后一个点。然后二维的前缀和。然后每次询问的时候,去掉最上边和最左边两条边界上对应的多加的点。


    阅读更多
  • codeforces 18 C. Stripe

    2015-12-29 · 1 min read · 前缀和

    http://codeforces.com/contest/18/problem/C 题意:将一个序列分成两个非空的部分,保证和相等,问有多少种方法。 思路:做过一个三部分的。。。两部分直接一个前缀和就好了把。。。有一个需要注意的是。。判断负数是否是奇数的时候需要加个绝对值。。。


    阅读更多
  • codeforces #336 div 2 B. Hamming Distance Sum

    2015-12-23 · 1 min read · 前缀和

    http://codeforces.com/contest/608/problem/B 题意:给定两个字符串a,b,问b中的每个连续的长度为a的子串与a的哈密顿距离的和是多少。哈密顿距离是对应位置的字符的差的绝对值的和。由于是01串,也就是字符不同的位置数。 思路:类似前缀和。0和1分别搞。注意开long long


    阅读更多
  • hdu 5480|| bestcoder   #57 div 2 Conturbatio(前缀和||树状数组)

    2015-09-26 · 2 min read · 前缀和 树状数组

    比较水.

    唯一一点需要注意的是…

    可能有重复元素…

    因为我的思路是用两棵一维树状数组搞..

    每个点标记为1

    然后看矩形的两个方向中是否至少有一个方向上和等于长度…


    阅读更多

111qqz

ex-ICPCer@HUST, engineer@Tencent
阅读更多

最新文章

  • caffe 源码阅读笔记
  • [施工中] cupy与torch的导入顺序不同对计算结果的影响
  • Build Onnxruntime With Bazel
  • 【施工中】gitlab ci docker executor指定用户执行
  • [施工中]caffe 源码学习笔记(11) softmax
  • 浅谈 Cpp Value Categories
  • redis学习笔记
  • [施工中] levelDB 代码阅读笔记 06 iterator
  • levelDB 代码阅读笔记 05 arena
  • levelDB 代码阅读笔记 04 filter

分类

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

专栏

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

标签

算法竞赛 236 DP 73 MATH 49 线段树 43 BRUTE FORCE 39 LEETCODE 39 GREEDY 36 DFS 34 NUMBER THEORY 27 CPP 26 模拟 24 博弈论 22 构造 22 BINARY SEARCH 21 母函数 21
所有标签
01背包9 2-SAT1 6.8284 ACM2 AC自动机3 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 CODEFORCES3 CONDITION_VARIABLE1 CONVOLUTIONAL NEURAL NETWORK1 CPP26 CS231N1 CS3411 CSAPP7 CSE599W1 CUDA6 CUMULATIVE MATCH CHARACTERISTI1 CUPY1 D1 DFS34 DFS序1 DIJKSTRA2 DISCOURSE1 DL-SYS1 DOCKER7 DP73 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 LEETCODE39 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 DISTILLATION1 MODEL-CONVERTOR1 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 STD::ANY1 STD::SHARED_PTR1 STEAM2 STL16 STREAM1 SUPERCOMPUTING1 SUPERVISOR1 TARJAN2 TENSORFLOW12 TENSORRT2 THREADING BUILDING BLOCKS1 THRUST1 TODO4 TREE7 TRIE7 TRIPLET LOSS1 TSP2 TWO POINTER5 TYPESCRIPT1 UNICODE1 VALUE CATRGORY1 VARIADIC FUNCTION1 VARIETY1 VECTOR2 VIM6 VUNDLE1 WHITENING1 WORDPRESS1 YOUCOMPLETEME1 YUV IMAGE FORMAT1 巴什博奕5 百度1 贝尔数2 编译器1 编译原理1 并查集9 并行计算2 博弈论22 差分序列1 拆点6 尺取2 尺取法10 抽屉原理6 传递闭包5 次小生成树2 错排公式2 打表2 单调队列3 单调性优化1 单调栈10 递推2 第二类斯特林数1 动态连通性1 动态线段树1 对拍1 二次剩余4 二分2 二分图5 二分图匹配4 二分图最佳匹配14 二进制1 二维线段树1 二项式定理1 反素数5 反向传播1 斐波那契7 费马点1 费马小定理3 分布式消息系统1 分块12 分类讨论1 分治2 峰度1 符号表1 符号可见性1 概率13 高精度2 高斯消元1 哥德巴赫猜想1 勾股数1 构造22 观察者模式1 光流法1 后缀和1 后缀数组10 后缀自动机13 回文串2 回文自动机7 基础图论1 激活函数1 计数排序2 计数问题10 计算机视觉2 计算几何20 计组1 记忆化搜索2 剪枝1 交叉染色法6 交互题1 结论题1 京东1 局部敏感HASH2 矩形面积交1 矩形周长并1 矩阵20 矩阵快速幂5 康托展开2 康托展开/逆展开1 可持久化数据结构5 快速乘1 快速幂20 快速筛2 扩展BSGS2 扩展欧几里得算法8 括号匹配2 离散化11 连通性2 链式前向星1 路径DP1 路径记录2 乱搞6 曼哈顿距离4 枚举子集4 面试2 面试经历3 模拟24 模拟退火5 模型转换1 莫队算法10 母函数21 内存屏障1 逆序对5 逆元5 欧拉函数4 欧拉路1 爬虫2 爬山法1 排列组合8 裴蜀定理5 偏度1 其他1 前端6 前缀和17 区间DP13 区间第K大2 区间合并1 区间计数1 染色问题1 容斥原理5 三分2 扫描线4 筛法1 设计模式2 射线法1 剩余系3 输入挂2 树的直径9 树套树1 树形DP6 树状数组20 数据结构2 数据压缩1 数论2 数位DP17 数值计算方法2 数字图像处理2 水5 水题7 思维1 思维题7 四叉树1 算法竞赛236 随笔杂谈7 拓扑排序7 泰勒展开3 贪心1 梯度下降1 同构1 凸包1 图论16 图论基础1 图像处理2 推荐系统3 完全背包2 位运算4 文明1 无向图的环3 系统调用1 细节题1 线段树43 协同过滤1 斜率优化3 辛普森积分2 匈牙利算法15 虚点1 蓄水池抽样1 循环节8 循环展开1 一致性哈希1 依赖注入1 优先队列4 游戏1 预处理1 栈1 正则表达式1 指数循环节7 置换群1 中国剩余定理4 重心1 主席树5 状态压缩1 状压DP1 字符串14 字符串DP1 字符串循环同构4 组成原理1 组合模式1 组合数学10 最大独立集1 最大连续和1 最大连续区间和3 最短路5 最小表示法7 最小顶点覆盖2 最小覆盖子串3 最小覆盖子矩形1 最小路径覆盖2 最小生成树2 最长公共字串4 最长路2 最长下降子序列1
[A~Z][0~9]
111qqz的小窝

Copyright  111QQZ的小窝. All Rights Reserved