- 博客(183)
- 收藏
- 关注
RSS订阅原创 Educational Codeforces Round 2 E. Lomsat gelral（树上启发式合并）
You are given a rooted tree with root in vertex1. Each vertex is coloured in some colour.Let's call colourcdominating in the subtree of vertexvif there are no other colours that appear in the subtree of vertexvmore times than colourc. So it's po...
2021-09-14 16:01:03
260
原创 牛客网 华华和月月种树（dfs序+区间更新树状数组）
题目链接：https://ac.nowcoder.com/acm/problem/23051题目描述华华看书了解到，一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了，所以他们种的树是信息学意义下的。华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：操作 1：输入格式1i，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是.
2020-08-20 11:09:55
503
原创 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
1057
原创 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
592
原创 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
634
原创 2460: [BeiJing2011]元素 （线性基）
Description 相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使用超过一块同一种矿石，那...
2018-04-11 20:48:10
608
原创 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
776
原创 线性基（处理集合异或的强力工具）
看了好多篇关于线性基的博客，只是说明了怎么求线性基，但是大都没有说明为什么这样求线性基。定义：有一个集合 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
1671
原创 最小公倍数取模
题目：求一个最小的整数，能被1~n中的所有数整除。n的范围为 1 <= n <= 100000，答案对1e9+7取模。 思路：一上来有些人可能认为可以先求最小公倍数然后再取模，这样显然是不可以的，因为求最小公倍数中有除法，除法是不能直接取模的，就算用了逆元，也是不对的。我们可以把每一个数进行质因数分解，之后求最小公倍数，最后用快速幂求出答案并取模就正确了。举个例子：...
2018-04-10 20:08:04
2100
1
原创 查询区间内等于x的数的个数（分块）
问题：有一个有n个数的数组，q次查询，每次查询l, r ,x，查询区间[l,r]内等于x的数的个数思路：分块。就把这题当成是分块的入门题来讲解一下分块。分块其实就是一种比较优美的暴力（我觉得），一般的分块都是把长度为n的数组分成每一块为sqrt(n)个数的多个块。然后对于区间的操作就可以不再是一个一个数进行处理，而是可以一个块一个块的处理，每次查询最多会涉及到sqrt(n)个块，这样复杂度就降了下...
2018-03-24 17:02:22
3016
1
原创 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
988
原创 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
1075
原创 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
1228
原创 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
1171
原创 分类占坑
图论：最短路网络流强连通生成树匹配数据结构：线段树树状数组RMQLCA字符串后缀数组字典树数学相关莫比乌斯反演计算几何数论矩阵FFT其他：二分搜索DP...
2018-02-12 13:11:11
370
原创 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
971
原创 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
1112
原创 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
957
原创 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
819
原创 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
865
原创 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
617
原创 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
976
原创 SGU 125. Shtirlits（dfs）
There is a checkered field of size N x N cells (1 Ј N Ј 3). Each cell designates the territory of a state (i.e. N2 states). Each state has an army. Let A [i, j] be the number of soldiers in the stat
2017-10-10 20:06:03
797
原创 SGU 124. Broken line（射线法判断一个点是否在一个多边形内）
There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of K segments. You have to determine, whether a give
2017-10-09 21:03:55
831
原创 SGU 116. Index of super-prime（完全背包+输出路径）
Let P1, P2, … ,PN, … be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prim
2017-09-27 14:38:22
930
原创 SGU 115. Calendar （基姆拉尔森公式）
irst year of new millenium is gone away. In commemoration of it write a program that finds the name of the day of the week for any date in 2001.InputInput is a line with two positive integer
2017-09-27 12:37:24
822
原创 Codeforces Round #436 (Div. 2) E. Fire（01背包+输出路径）
Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take tiseconds to save i-th item. In addition, for each item
2017-09-26 18:12:08
1156
2
原创 Manthan, Codefest 17 C. Helga Hufflepuff's Cup（树形DP）
Harry, Ron and Hermione have figured out that Helga Hufflepuff's cup is a horcrux. Through her encounter with Bellatrix Lestrange, Hermione came to know that the cup is present in Bellatrix's famil...
2017-09-25 08:43:29
1368
原创 Manthan, Codefest 17 E. Salazar Slytherin's Locket（数位DP）
Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and
2017-09-25 07:34:25
825
原创 2017北京网络赛 && hihocoder 1582 Territorial Dispute（凸包）
In 2333, the C++ Empire and the Java Republic become the most powerful country in the world. They compete with each other in the colonizing the Mars.There are n colonies on the Mars, numbered from 1
2017-09-24 19:46:28
765
原创 大数模板 （kuangbin模板的修订版）
以前直接用kuangbin的模板，发现一直过不了题，今天又做了一题，发现原来是减法函数里有一个地方写错了，改正之后就可以了（不保证其他的没有问题）。#include#include#include#include#define LL long longusing namespace std;/** 完全大数模板* 输出cin>>a* 输出a.print();* 注
2017-09-21 15:17:30
1599
6
原创 Codeforces Round #435 (Div. 2) C. Mahmoud and Ehab and the xor
Mahmoud and Ehab are on the third stage of their adventures now. As you know, Dr. Evil likes sets. This time he won't show them any set from his large collection, but will ask them to create a new set
2017-09-20 08:58:35
1186
5
原创 SGU 103. Traffic Lights （SPFA）
In the city of Dingilville the traffic is arranged in an unusual way. There are junctions and roads connecting the junctions. There is at most one road between any two different junctions. There is
2017-09-18 13:57:25
1036
原创 Codeforces Round #434 D. Polycarp's phone book （字典树）
There are n phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct.There is the latest version
2017-09-18 08:20:19
999
原创 Codeforces Round #433 C. Planning（贪心）
Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are n flights that must depart today, the i-th of them is planned to depart at the i-th minute of the
2017-09-07 08:01:11
1659
原创 Codeforces Round #433 D. Jury Meeting
Country of Metropolia is holding Olympiad of Metrpolises soon. It mean that all jury members of the olympiad should meet together in Metropolis (the capital of the country) for the problem preparation
2017-09-07 00:15:51
798
原创 2017 广西邀请赛&& hdu 6191 Query on A Tree（字典树启发式合并）
Problem DescriptionMonkey A lives on a tree, he always plays on this tree.One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted t
2017-09-01 12:03:49
826
原创 bzoj 2733: [HNOI2012]永无乡（线段树启发式合并）
Description永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q
2017-08-31 21:35:34
777
原创 bzoj 2301 [HAOI2011]Problem b （莫比乌斯反演）
Description对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。Input第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k Output共n行，每行一个整数表示满足要求的数对(x,y)的个数 Sample In
2017-08-16 10:21:10
884
原创 spoj 7001 VLATTICE - Visible Lattice Points（莫比乌斯反演）
Consider a N*N*N lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0) ? A point X is visible from point Y iff no other latti
2017-08-15 10:48:22
814
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人