• 等级
  • 10593 访问
  • 165 原创
  • 0 转发
  • 35055 排名
  • 8 评论
  • 5 获赞

牛客小白9 换个角度思考(离线+树状数组)

title: 牛客小白9 换个角度思考(离线+树状数组) date: 2018-11-29 15:25:18 tags: [离线,树状数组] categories: ACM 题目链接 题目描述 给定一个序列,有多次询问,每次查询区间里小于等于某个数的元素的个数 即对于询问 (l,r,x),你需要输出 的值 其中 [exp] 是一个函数,它返回 1 当且仅当 exp 成立,其中 exp 表示某个...

2018-11-29 15:38:52

第二次讲课内容(函数和快速幂)

函数 在c语言中**main()**就是一个函数,它是程序的主函数。 函数定义的一般格式: 返回类型 函数名(参数列表){ 函数体 } 返回类型 一个函数可以返回一个值,返回类型就是对应的值的类型。常见的有int、long long、bool、double、float、struct,如果函数没有返回值就用void 函数名 自定义名称 字母、数字、下划线混合使用,但是只能以字母和下划线开始...

2018-10-23 18:59:58

ZOJ-3494 BCD Code (ac自动机+数位dp)

title: ZOJ-3494 BCD Code (ac自动机+数位dp) date: 2018-10-06 22:32:51 tags: [数位dp, AC自动机] categories: ACM 题目链接 Problem Description Binary-coded decimal (BCD) is an encoding for decimal numbers in which ea...

2018-10-07 22:44:07

AC自动机

AC自动机 //借鉴kuangbin模板 struct Trie{ int next[N][26], fail[N], end[N]; int root, L; int newnode() { for (int i = 0; i < 26; ++i) next[L][i] = -1; e...

2018-10-07 22:42:18

扩展欧几里得

(1)ax1 + by1 = gcd(a, b) (2)bx2 + (a% b)y2 = gcd(b, a % b) a % b = ab⋅\frac{a}{b}\cdotba​⋅ b + a % b带入(2)化简得到 x1 = y2 y1 = x2 - ab⋅\frac{a}{b}\cdotba​⋅ x1 // 递归 LL extgcd(LL a, LL b, LL &x, LL &am...

2018-09-25 23:04:19

状态压缩 LIS

LIS LIS(最长上升子序列),nlogn的方法是维护一个数组,每次插入一个数字,插入到第一个大于等于这个数的位置上, 这样能保证后面的数尽可能多的插入数组中 状态压缩 如果已知LIS最长为10个, 那么我们就可一个用状态压缩的方法计算LIS,这样每个LIS的状态也能用一个数字保存下来 int update(int pos, int x) { // 在之前存在的数字中找到第一...

2018-09-16 23:06:34

LCA 最近公共祖先,树上两点距离,线段重合长度

对于LCA的一些理解 dfs处理树 对于一个树形结构,可以用dfs将一颗树转化成数组,数组中记录每个点的标号,这样数组就按照dfs的顺序把树存了下来 确定祖先的范围 对于询问的节点X和Y, X、Y的祖先一定存在于数组中X、Y第一次出现的区间内,而且祖先就是区间内深度最小的节点 RMQ dfs的复杂度就是树边数的二倍,所以区间查询需要优化,这里可以用RMQ算法,预处理结果O(1)得到最值 ...

2018-09-10 10:49:25

RMQ

原理 可以用来求区间最值,类似线段树,dp[ i ][ j ]的含义是从第i个数开始的长度为(1 << j)的区间的最值, 状态转移方程dp[ i ][ j ] = min(dp[ i ] [ j - 1 ] , dp[ i + (1 << ( j - 1) ) ][ j - 1]) 两个循环预处理,在查询某个区间时,因为所查询的区间的长度不一定是2的次方,所以把区间分...

2018-09-07 21:39:32

Problem - 6111迷宫出逃

Problem Description 小明又一次陷入了大魔王的迷宫,在无人机的帮忙下,小明获得了整个迷宫的草图。不同于一般的迷宫,魔王在迷宫里安置了机关,一旦触碰,那么四个方向所在的格子,将翻转其可达性(原先可通过的格子不可通过,反之亦然,机关可以反复触发)。为了防止小明很容易地出逃,魔王在临走前把钥匙丢在了迷宫某处,只有拿到钥匙,小明才能开门在出口处离开迷宫。万般无奈之下,小明想借助聪明的你...

2018-09-03 12:50:20

F-子序列(组合数,打表,扩展欧拉,容斥)

题目链接 题目描述 给出一个长度为n的序列,你需要计算出所有长度为k的子序列中,除最大最小数之外所有数的乘积相乘的结果 输入描述: 第一行一个整数T,表示数据组数。 对于每组数据,第一行两个整数N,k,含义如题所示 接下来一行N个整数,表示给出的序列 保证序列内的数互不相同 输出描述: 对于每组数据,输出一个整数表示答案,对取模 每组数据之间以换行分割 输...

2018-08-30 20:11:26

HDU Problem - 5918 Sequence I

题目链接 Problem Description Mr. Frog has two sequences a1,a2,⋯,ana1,a2,⋯,ana_1,a_2,\cdots ,a_n and b1,b2,⋯,bmb1,b2,⋯,bmb_1,b_2,\cdots ,b_m and a number p. He wants to know the number of positions q suc...

2018-08-29 11:52:53

牛客练习赛25 B-最长区间

题目链接: 题目描述 给你一个长度为 n 的序列 a ,求最长的连续的严格上升区间的长度。 同时会进行 m 次修改,给定 x , y ,表示将 ax 修改为 y ,每次修改之后都要求输出答案。 输入描述: 第一行 2 个数 n,m,表示序列长度,修改次数; 接下来一行 n 个数表示 ; 接下来 m 行,每行 2 个数 x , y ,描述一次修改。 输出描述: ...

2018-08-28 18:05:24

HDU Problem - 5976 Detachment(逆元,阶乘打表,数学)

题目链接 Problem Description In a highly developed alien society, the habitats are almost infinite dimensional space.In the history of this planet,there is an old puzzle.You have a line segment with x u...

2018-08-28 17:04:02

HDU Problem - 5971 Wrestling Match(染色)

题目链接 Problem Description Nowadays, at least one wrestling match is held every year in our country. There are a lot of people in the game is “good player”, the rest is “bad player”. Now, Xiao Ming is...

2018-08-27 11:31:33

HDU Problem - 5935 Car(模拟)

题目链接 Problem Description Ruins is driving a car to participating in a programming contest. As on a very tight schedule, he will drive the car without any slow down, so the speed of the car is non-de...

2018-08-27 09:25:28

Codeforces Round #506 (Div. 3) - F. Multicolored Markers (思维)

题意 给两种颜色的数量 a 和 b,这两种颜色恰好组成一个长方形,而且至少有一种颜色在整个长方形里面也是个长方形,求满足条件中周长最小的情况 AC 当a是里面的长方形,把A能组成的长方形的宽记录一下,然后枚举大的长方形的宽 i ,当大长方形的长sum(a + b)/ i 大于等于小长方形的长a / i,这是就可以构成一个合理的长方形 按照上面的思路分别假设a、b为里面的小长方形 #in...

2018-08-26 20:23:03

遍历一颗树

遍历整棵树,计算一个点到所有点的距离并记录前驱节点 节点从1标号 - bfs遍历整棵树 vector<int> g[N]; int pre[N], dis[N]; struct point{ int num, dis; }; bool vis[N]; void bfs(int x) { queue<point> que; que.push(...

2018-08-26 17:27:18

Codeforces Round #506 (Div. 3) - E. Tree with Small Distances

题目链接 题意 给你一棵树,最多加几条边,使点1到所有的点的最大距离不超过2 AC 贪心 从距离最远的点开始,找到他的父节点,然后把父节点相连的点删去,这样最好的情况可以删除三层点 遍历树的时候有两种方法: // bfs #include <iostream> #include <cmath> #include <map> #include &l

2018-08-26 17:20:51

Codeforces Round #506 (Div. 3) - D. Concatenated Multiples(思维)

题意 给你N个数字和一个K,问一共有几种拼接数字的方式使得到的数字是K的倍数,拼接:“234”和“123”拼接得到“234123” AC N <= 2e5,简单的暴力O(N^2)枚举肯定超时 数字A和B拼接,B的位数最多10位,如果我们知道位数为(1-10)的数字和A拼接满足是K的倍数这样的数字有几个,就可以在N*10的复杂度下完成所有的拼接 在读入数据的时候,我们可以统计出数字...

2018-08-26 13:25:41

Codeforces Round #506 (Div. 3) - C. Maximal Intersection (思维,模拟)

这里写链接内容 题意 给你N个线段(一条直线上),问删去一个之后,最长公共长度 AC 先考虑不删边,有两种情况 所有直线在一起分布 显然公共部分是排序之后的(第一个右端点 - 最后一个左端点) 直线不在一起分布 这时按照(第一个右端点 - 最后一个左端点)得到的结果是负数,最后可以加个判断,可以解决这个情况 知道上面的两种情况后,可以在O(1)的时间求出最长的公共部分,将所...

2018-08-25 10:27:52

henuyh

关注
  • 学生
  • 中国 河南省 郑州市
奖章
  • 持之以恒