4 SSimpLe_Y

尚未进行身份认证

人一我百,人十我万,然而我做不到。

等级
TA的排名 2w+

hihocoder 1742 树的权重(51Nod-1405 树的距离之和)(树形DP)

描述给定一棵包含N个节点的树,节点编号1~N。  请你对于每一个节点,计算它到所有其他节点的距离之和。(每条边的长度为1)输入第一行包含一个整数N。  以下N-1行,每行包含两个整数a和b,代表ab之间有一条边。  对于30%的数据,1 ≤ N ≤ 1000  对于100%的数据,1 ≤ N ≤ 100000输出输出N行,依次对于1~N号节点输出答案。样例输入4 1 2 2 3 2 4...

2018-05-13 15:21:14

Codeforces Round #479 F. Consecutive Subsequence(DP)

You are given an integer array of length nn.You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other...

2018-05-09 11:23:23

SPOJ DQUERY - D-query (莫队算法)

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the ...

2018-04-11 22:07:00

2460: [BeiJing2011]元素 (线性基)

Description  相传,在远古时期,位于西方大陆的 Magic Land 上,人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到,一个法杖的法力取决于使用的矿石。一般地,矿石越多则法力越强,但物极必反:有时,人们为了获取更强的法力而使用了很多矿石,却在炼制过程中发现魔法矿石全部消失了,从而无法炼制出法杖,这个现象被称为“魔法抵消” 。特别地,如果在炼制过程中使用超过一块同一种矿石,那...

2018-04-11 20:48:10

hihocoder 1723 : 子树统计 (线性基)

描述给定一棵N个节点的有根树,树上每个节点有一个非负整数权重Wi。定义节点集合S={i1, i2, ……, ir}的总权重为:(⊕是异或运算)每次询问一棵子树内所有可能出现的总权重数量,即令E为所询问的子树内节点的集合,|T|即为可能出现的总权重数量。输入第一行包含两个整数N,Q,表示树的节点数目和询问数目,节点1总是这棵树的根部。第二行包含N-1个整数,第i个整数P_i表示i+1号节点的父亲节点...

2018-04-10 20:52:40

线性基(处理集合异或的强力工具)

看了好多篇关于线性基的博客,只是说明了怎么求线性基,但是大都没有说明为什么这样求线性基。定义:有一个集合 S  = {a1,a2...,an},T的满足下面条件的一个最小子集A = {a1,a2,....,ak}A的所有子集的异或和的值域与T的所有子集的异或和的值域相同,那么A就是T的线性基。预备知识:1、张成:S的所有子集,其异或和的所有可能的结果组成的集合,为S的张成,记作span(S)。2、...

2018-04-10 20:37:59

最小公倍数取模

题目:求一个最小的整数,能被1~n中的所有数整除。n的范围为 1 <= n <= 100000,答案对1e9+7取模。 思路:一上来有些人可能认为可以先求最小公倍数然后再取模,这样显然是不可以的,因为求最小公倍数中有除法,除法是不能直接取模的,就算用了逆元,也是不对的。我们可以把每一个数进行质因数分解,之后求最小公倍数,最后用快速幂求出答案并取模就正确了。举个例子:...

2018-04-10 20:08:04

查询区间内等于x的数的个数(分块)

问题:有一个有n个数的数组,q次查询,每次查询l, r ,x,查询区间[l,r]内等于x的数的个数思路:分块。就把这题当成是分块的入门题来讲解一下分块。分块其实就是一种比较优美的暴力(我觉得),一般的分块都是把长度为n的数组分成每一块为sqrt(n)个数的多个块。然后对于区间的操作就可以不再是一个一个数进行处理,而是可以一个块一个块的处理,每次查询最多会涉及到sqrt(n)个块,这样复杂度就降了下...

2018-03-24 17:02:22

Codeforces Round #466 (Div. 2) E. Cashback (dp+树状数组+RMQ)

Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount.You are given an array a of length n and an integer c.The value of some array b of lengt...

2018-02-24 21:09:36

Codeforces Round #464 (Div. 2) E. Maximize!

You are given a multiset S consisting of positive integers (initially empty). There are two kind of queries:Add a positive integer to S, the newly added integer is not less than any number in it.Find ...

2018-02-17 22:32:43

Codeforces Round #464 (Div. 2) D. Love Rescue

Valya and Tolya are an ideal pair, but they quarrel sometimes. Recently, Valya took offense at her boyfriend because he came to her in t-shirt with lettering that differs from lettering on her pullove...

2018-02-17 22:20:12

Codeforces Round #464 (Div. 2) C. Convenient For Everybody

In distant future on Earth day lasts for n hours and that's why there are n timezones. Local times in adjacent timezones differ by one hour. For describing local time, hours numbers from 1 to n are us...

2018-02-17 22:12:51

分类占坑

图论:最短路网络流强连通生成树匹配数据结构:线段树树状数组RMQLCA字符串后缀数组字典树数学相关莫比乌斯反演计算几何数论矩阵FFT其他:二分搜索DP...

2018-02-12 13:11:11

BZOJ 2442[Usaco2011 Open] 修剪草坪 (dp+单调队列)

Description在一年前赢得了小镇的最佳草坪比赛后,FJ变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,FJ希望能够再次夺冠。然而,FJ的草坪非常脏乱,因此,FJ只能够让他的奶牛来完成这项工作。FJ有N(1 <= N <= 100,000)只排成一排的奶牛,编号为1…N。每只奶牛的效率是不同的,奶牛i的效率为E_i(0 <= E_i <= ...

2018-02-12 12:10:48

Codecraft-18 and Codeforces Round #458 D. Bash and a Tough Math Puzzle(线段树)

Bash likes playing with arrays. He has an array a1, a2, ... an of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess i

2018-01-21 13:22:11

Codecraft-18 and Codeforces Round#458 C. Travelling Salesman and Special Numbers(数位DP)

The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer x and reduce...

2018-01-21 13:10:30

SGU 144. Meeting(概率)

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between X 

2017-10-14 19:11:56

SGU 143. Long Live the Queen(树形DP)

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen's name. This new co

2017-10-14 18:22:04

SGU 142. Keyword(暴力枚举)

Kevin has invented a new algorithm to crypt and decrypt messages, which he thinks is unbeatable. The algorithm uses a very large key-string, out of which a keyword is found out after applying the algo

2017-10-14 16:55:13

SGU 134. Centroid(树的重心)

You are given an undirected connected graph, with N vertices and N-1 edges (a tree). You must find the centroid(s) of the tree. In order to define the centroid, some integer value will be assosciate

2017-10-13 16:50:01

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!