[洛谷U40581]树上统计treecnt 题目大意: 给定一棵\(n(n\le10^5)\)个点的树. 定义\(Tree[l,r]\)表示为了使得\(l\sim r\)号点两两连通,最少需要选择的边的数量. 求\(\sum_{l=1}^n\sum_{r=l}^nTree[l,r]\). 思路: 对于每个边考虑贡献,若我们将出现在子树内的点记作\(1\),出现在子树外的点记作\(0\),那么答案就是\(\frac{n(n-1)}2-\)全\(0\).全\(1\)串的个数.线段树合并,维护前缀/后

题目链接 dalao们怎么都写的线段树合并啊.. dsu跑的好慢. \(Description\) 给定一棵\(n(n\leq 10^5)\)个点的树. 定义\(Tree[L,R]\)表示为了使得\(L\sim R\)号点两两连通,最少需要选择的边的数量. 求\[\sum_{l=1}^n\sum_{r=l}^nTree[l,r]\] \(Solution\) 枚举每条边,计算它的贡献. 那么我们要判断有多少连续区间的点跨过这条边,并不好算,反过来去求在这条边的两侧分别有多少个连续区间. 那么显然

Подпалиндромы Problem's Link: http://informatics.mccme.ru//mod/statements/view.php?chapterid=1750# Mean: 给你一个长度不超过1e5的字符串,要统计总共有多少个回文串.(第一次刷俄语题,还好有google翻译). analyse: 如果题目说是不同回文串的话,这题就是一个裸的回文树. 由于要求所有子串的回文数,所以我们在插入的时候还需要使用suffixLink往上走统计答案. Time comp

#1014 : Trie树 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进. 这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?” 身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字

HDU 6035 Colorful Tree Problem : 给一棵树,每个结点有一种颜色,定义每条路径的权值为这条路径上颜色的种数,询问所有路径(C(n,2)条)的权值之和. Solution : 分开考虑每种颜色对答案的贡献.对于一种颜色,一共有C(n,2)条路径,再考虑问题的反面.不含有这种颜色的路径的数量,即为将这棵树上所有这种颜色的点删去后,所有剩下的树的路径数量. 问题关键在于统计删去点之后每颗树的大小,对于每个节点要计算删去其所有相同颜色的子树,用栈进行维护.即每次访问到每个节

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1671 Problem Description Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers: 1. Emergenc

用记录附加信息的val数组记录次数即可. trie的原理:每个可能出现的字目给一个编号c,那么整个树就是一个c叉树 ch[u][c]表示 节点u走c边过去之后的节点 PS:trie树还有种动态写法,使用指针和动态分配内存代替了连续的ch数组,更加节省内存. Reference:http://blog.csdn.net/architect19/article/details/8966247 #include <cstdio> #include <cstring> #include &

HDU 6070 Partition Problem : 给一段长度为n的序列,要求找出一段区间,使得这段区间的数字种类除以区间长度最小.输出最后的答案即可.(n <= 60000)(9s时限) Solution : 显然,答案是0~1中的一个数字,可以很自然的想到二分答案的做法.假设目前二分到的答案为mid,那么需要判断 \[\frac{cnt(l, r)}{r- l + 1} <= mid\] 其中cnt(l,r)为l到r这个区间内的数字种类.变化一下式子可以得到: \[cnt(l, r)

输入 输入的第一行为一个正整数n.表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦).单词由不超过10个的小写英文字母组成,可能存在同样的单词.此时应将其视作不同的单词.接下来的一行为一个正整数m.表示小Hi询问的次数,其后m行.每一行一个字符串.该字符串由不超过10个的小写英文字母组成,表示小Hi的一个询问. 输出 对于小Hi的每个询问.输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数. 例子输入 5 babaab babbbaaaa ab

---恢复内容开始--- Tunnel Warfare Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description During the War of Resistance Against Japan, tunnel warfare was carried out extensively in the vast areas of north China Plain. Genera

#44. [HNSDFZ2016 #6]可持久化线段树 统计 描述 提交 自定义测试 题目描述 现有一序列 AA.您需要写一棵可持久化线段树,以实现如下操作: A v p x:对于版本v的序列,给 ApAp 增加 xx. Q v l r:对于版本v的序列,询问 A[l,r]A[l,r] 的区间和. C v:拷贝一份版本v的序列,编号为当前版本总数+1. 版本号从 11 开始:版本 11 的序列,所有元素均为 00. 格式 输入格式 第一行,两个正整数 n,mn,m,表示序列的长度和操作个数. 接

目标: 想要在MAC的Terminal中查看文件夹中所有文件的树型结构及文件夹.文件树统计. 安装方法: 1.brew安装 官网:http://brew.sh/ brew是Mac中安装软件的神器,一定要安装一个,一定要,一定要. ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" 验证brew安装是否成功 ➜ brew -v Homebrew (git rev

Description 一棵树,统计距离不大于 \(k\) 的点对个数. Sol 点分治. 发现自己快把点分治忘干净了... 找重心使所有儿子的最大值尽量小,然后每次处理全部子树,再减去每个子树的贡献,这样就得到子树间的贡献了,然后再搞子树就可以,这就是一个子问题了. Code /************************************************************** Problem: 3365 User: BeiYu Language: C++ Result

Attack Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 2523    Accepted Submission(s): 805 Problem Description Today is the 10th Annual of “September 11 attacks”, the Al Qaeda is about to attac

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5877 题意:给一棵树和各点的权值a,求点对(u,v)个数,满足:1.u是v的祖先,2.a(u)*a(v)<=k. 对于这棵树,我们先存好树的结构.再离散化,最后dfs的时候往线段树里插点,那对应idx的值就是1.然后二分找不大于k/a[v]的下标,线段树统计计数就行了.换儿子的时候记得抹去上一个兄弟. #include <bits/stdc++.h> using namespace std;

题目链接:http://poj.org/problem?id=3237 You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on th

另开一文分析字符串相关的各种算法,以及用到的各种数据结构,包括前缀树后缀树等各种树. 先来一个汇总, 算法: 本文中提到的字符串匹配算法有:KMP, BM, Horspool, Sunday, BF, KR, AC(其中用到了Trie树) 统计字符出现个数.获取KV内容:Trie树(字典树.前缀树) 回文子串长度算法有:Manacher's Algorithm 题目: 最长回文子串 最长重复子串 最长不重复子串 以下为正文: 最长连续回文串(Longest Palindromic Substri

题目大意 给定一个序列a[1],a[2]--a[n] 接下来给出m种操作,每种操作是以下形式的: l r d 表示把区间[l,r]内的每一个数都加上一个值d 之后有k个操作,每个操作是以下形式的: x y 表示把第x种操作一直到第y种操作都执行一遍 最终输出在k个操作结束之后的序列 题目大意 就是线段树的成段更新嘛~~~先用线段树统计每种操作的次数,然后再执行m次成段更新,最后查询到底的查询即可~~~树状数组也可搞,似乎写起来还更简单些~~~还有一个更犀利的O(n)的算法,不过我暂时还没弄懂~~

方法介绍 1.1.什么是Trie树 Trie树,即字典树,又称单词查找树或键树,是一种树形结构.典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是最大限度地减少无谓的字符串比较,查询效率比较高. Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. 它有3个基本性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串. 每

KiKi's K-Number Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2546    Accepted Submission(s): 1174 Problem Description For the k-th number, we all should be very familiar with it. Of course,t