DQS DQS

[BZOJ1045] [HAOI2008] 糖果传递 中位数

in 算法,其他 read (76)
Description 有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 第一行一个正整数nn<=1'000'000,表示小朋友的个数. 接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数. O...

线段树合并学习笔记

in 算法,线段树&&树状数组,数据结构 read (135)
被Splay的启发式合并的坑爹常数坑了无数次之后决定学习一下新姿势… 一些证明 正确性前提:对于同样值域的权值线段树,它们的结构是相同的。 所以可以同时递归处理,合并两子树可以直接把两子树根节点信息合并。 复杂度证明:两个线段树合并时,如果一个为空则返回另一个。否则递归合并...

每日刷题记录(update:10.10)

in 人生相关,算法 read (154)
9.25 打了场CF #436div2 写崩了,各种奇妙的WA…幸亏过题数还能看。 CF864A ##CF864B CF864C 贪心 车在坐标0和a之间往返k次,坐标f点有加油站(0<f<a),油箱上限b。每次加满油,问最少加多少次油。 情况: 考虑能否到加油...

2017ACM-ICPC亚洲区(西安赛区)网络赛-A.Tree LCA|树剖|矩阵

in 矩乘,bitset,算法,图论,LCA,数论,STL,树链剖分 read (173)
题目链接 题意:给你n个点的树,每个点上有一个01矩阵(给定种子生成)。每次询问u到v路径上的矩阵顺次乘起来得到的矩阵(每个点模2,也就是说得到的也是01矩阵),通过公式计算输出对应数字(简化输出)。$n<=3000,Q<=30000$。时限9s。 简单地说就...

[hdu6200]mustedge mustedge mustedge tarjan|树剖|并查集|树状数组|LCA

Problem Description Give an connected undirected graph with n nodes and m edges, (n,m≤105) which has no selfloops or multiple edges initi...
雷姆
拉姆