2 ltrbless

尚未进行身份认证

暂无相关简介

等级
TA的排名 5w+

2017年ICPC中国大陆区域赛 - Sum of xor sum (线段树维护子段)

题意:链接:https://vjudge.net/contest/319951#problem/T给你 n 个数,和 q 次询问,每次询问给你 [ l , r ] ,让输出在区间 [ l , r ] 里每一个子区间亦或和加和。比如: 给你三个数 1、2、3、和一个询问 [ 1 , 3 ] , 需要输出 1 + 2 + 3 + 1 ^ 2 + 2 ^ 3 + 1 ^ 2 ^ 3 。(1 ≤ ...

2019-08-20 11:43:42

2019牛客暑期多校训练营(第九场)Cutting Bamboos (主席树+二分)

题意:链接:https://ac.nowcoder.com/acm/contest/889/H给你 n 棵树每一棵树的高度,每一棵树从左到右编号为 1, 2, ... n 。Q 次询问,每次询问(l, r, x, y)代表在编号为 [l, r] 这个闭区间内的树,我需要砍 y 次把这些树砍成高度为 0 ,但是每次砍只能规定一个高度,这个高度以上的需要全部砍去,下面的不动,且每次砍的高度之和...

2019-08-16 16:16:30

Nonsense Time HDU - 6635 (思维 + LIS + 路径标记)

题意:链接:HDU - 6635给你 n 不同的且属于 [1, n] 的数列 p,然后在给你 n 个数 k1 - kn,代表 n 次操作,开始数列是被冻住的只有解冻的数才可以使用,按照给的n次操作,每次操作解冻一个位置,并输出当前所有被解冻的数的最长上升子序列的长度。解题思路:有句非常关键的语句:It is guaranteed that p1,p2,...,pn and k1,k...

2019-08-14 20:44:04

2019HDU多校第六场 - 11 Dimensions HDU - 6644(思维+数位dp+康拓展开思想)

题意:链接:HDU - 6644给你一个长度为 n 的数字,但是把其中的某些位使用 "?" 遮住了,然后让你把 "?" 遮住的部分填上数字,使得填填上后的数字 n ,满足 n % m == 0 。 有 q 次询问,每次询问要你输出满足条件的第 k 小的 n。n,m,q(1≤n≤50000,2≤m≤20,1≤q≤100000) T(1≤T≤10000) k(1≤k≤10^18)It...

2019-08-14 20:02:35

E - Snowy Smile HDU - 6638 (线段树维护最大连续子段和)

题意:链接:https://vjudge.net/contest/319475#problem/E给你n个点,每个点告诉你坐标还有权值(有正有负),让你画一个矩形把一些点括起来,问你矩形括起来的权值最大是多少,可以让矩阵面积为 0 ,也就是不括。解题思路:首先对 x 和 y 轴离散化,枚举一个上边界,然后从上边界开始一行一行的加入线段树中,每加一行就取一个最大,每次更新上边界就需要...

2019-08-14 09:22:51

Bond UVA - 11354 (按秩合并优化的并查集)

题意:链接:https://vjudge.net/problem/UVA-11354给你 n 个点,m 条边无向边,每条边告诉起点和终点还有权值,q次询问,每次询问从 s 点到 t 点的路径上的最小的最大权值(最大权值最小化)解题思路:首先如果把这个无向图建成一个最小生成树,那么在最小生成树的任意两点有仅有一条路,并且也使得最大权值最小化了,但是每次都要花费 o(n) 的时间搜索,...

2019-08-13 10:22:07

2019牛客暑期多校训练营(第八场)E - Explorer (线段树+离散化+按秩合并优化的并查集+并查集的拆除)

题意:链接:https://ac.nowcoder.com/acm/contest/888/E给你 n 个点,m 条边,每条边给你一组数 (u, v, l, r) 代表如果你想从u点走到v点,你的身高需要满足范围 [ l , r ] ,问你从 1 走到 n 点,你有多少种身高可以选择。1 ≤ n,m ≤ 10^5,1 ≤ u < v ≤ n,1 ≤ l ≤ r ≤ 10^9解...

2019-08-12 21:14:54

2019牛客暑期多校训练营(第七场)H-Pair (数位dp)

题意:链接:https://ac.nowcoder.com/acm/contest/887/H给你三个数 A、B、 C, 令 x ∈[ 1, A ],y ∈ [ 1, B ] ,至少符合 x & y > C 和 x ^ y < C 其中的一个条件,问你有多少个符合条件的 (x, y) 。解题思路:首先看他问的至少符合 x & y > C 和 x ^...

2019-08-12 11:42:03

不要62 HDU - 2089 (数位dp解法)

题意:题目链接:https://vjudge.net/problem/HDU-2089给你一个区间[ l, r ],让你输出在该区间中满足以下两个条件的数有多少个,条件一:数字的每一位不能出现4,条件二:数字的连续两位不可以是 62 。解题思路:由于这个题目的数据比较弱,预处理下直接输出。假设这个题目的范围变成 : (1 <= l <= R <= 1e18) 就不...

2019-08-09 16:38:56

2019牛客暑期多校训练营(第七场) Find the median(权值线段树+离散化)

题意+解题思路:给你一种计算规则,让你计算出 L [ i ] , R [ i ] ,( i 取值是 1 - n )。然后每次增加 L[ i ] - R[ i ] 这些数,然后让你求当前的中位数,如果是偶数个(如 6 个 取第3个)。比如 L[ 1 ] = 5 , R [ 1 ] = 15 . 就会增加 5、6、7 ... ... 13、14、15 这些数。又因为区间大小为 1 - 10^9 ...

2019-08-09 12:05:28

2019牛客暑期多校训练营(第七场)A、B、C、D、E

A -String(暴力)题意:链接:https://ac.nowcoder.com/acm/contest/887/A给你一个01串,让你分成尽可能少的段的个数并且保证每个段字典序最小(这里的字典序最小是经过循环后最小,比如 0110 就不满足最小,因为可以经过循环变成 0011 )解题思路:按 01 组合分块,比如: 11001101100100 首先分成: 11 00...

2019-08-09 12:02:16

Cutting Sticks UVA - 10003(DP - 四边形不等式优化)

四边形不等式优化:花费用 表示 四边形不等式 : 称其满足凸四边形不等式决策单调性 : 三个定理:定理一: 如果 同时满足四边形不等式 和 决策单调性 ,则 也满足四边形不等式定理二:当定理一的条件满足时,让取最小值的 为,则定理三: 为凸当且仅当 由定理三知 判断 是否为凸即判断 的值随着i的增加是否递减于是求 值的时...

2019-08-05 17:13:18

Color Length UVA - 1625 (DP)

题意:链接:https://vjudge.net/problem/UVA-1625给你两个由大写字母组成的序列,让你把这两个序列按这两个序列的原序列的字母顺序拼接成一个新的串,让你输出这个新的串的距离的最小值(这里的距离的最小值的定义是:相同字母的最远距离之和 如: ACACA -> 距离为 4(A与A的最远距离) + 2(C与C的最远距离) = 6 )解题思路:这个dp...

2019-08-05 15:10:06

2019牛客暑期多校训练营(第五场)A、B、G、H

A -digits 2题意:链接:https://ac.nowcoder.com/acm/contest/885/A给你一个数 n (1 <= n <= 100) ,让你输出一个数 x ,x 满足两个条件 : 1 . x 是 n 的倍数,2 . x 的每一位数字加起来的和也是 n 的倍数。解题思路:暴力打表到70多就比较满了,所以肯定是构造,怎么构造呢? 首先...

2019-08-02 09:56:16

Keen On Everything But Triangle HDU - 6601 (主席树)

题意:题目链接:https://vjudge.net/contest/315593#problem/C给你 n 个数,q 次询问,每次询问一个区间 [l, r],在这个区间里让你找可以构成三角形的最大周长。1 <= n <= 10^5解题思路:首先很容易想到对这 l - r 个数排序,然后从后相邻三个为一组往前找就行,但是询问区间都要排序时间复杂度太高,就可以用主席树来...

2019-07-31 19:19:13

Find the answer HDU - 6609 (权值线段树)

题意:链接:https://vjudge.net/contest/315593#problem/GQ组样例,给你 n 个数,和一个上限值 m ,让你求在第 i 个位置时,为了使前 i 个数的和(包括第 i 个数)不超过 m ,问你最少删除第 i 个数之前的几个数(不可以删除第 i 个数)。让你把 i 取 1 - n 时都输出出来。(1<=n<=2*10^5 1<=m&l...

2019-07-31 19:11:08

2019牛客暑期多校训练营(第四场)A、C、J、K

A - meeting (树的直径)题意:链接:https://ac.nowcoder.com/acm/contest/884/A给你一颗由 n 个点构成的树,和 k 个不同的点,让你找一点,使得该点到那 k 个点的最大距离最小,输出最小距离。解题思路:两次dfs求出树的直径(注:全都要是那 K 个点的,其他点不算,就是求树的直径的起点和终点都必须是这k个点里的点,因为 题意说...

2019-07-28 10:23:52

2019牛客暑期多校训练营(第二场)Second Large Rectangle (单调栈)

单调栈讲解:已经会单调栈的可以直接跳过看2019牛客暑期多校训练营(第二场)Second Large Rectangle单调栈:先来说下单调栈,单调栈按字面意思就是栈,但是里面的值是单调的。举个例子:给你一组序列 : 2 1 4 5 1 3 3 让这组序列进单调栈,步骤:1. st : 22. st : 1 (因为 1 比 2 为了保证单调递增,所以把 2 先出栈,再把 ...

2019-07-25 16:30:45

2019牛客暑期多校训练营(第一场)Integration(数学裂项求积分)

题目链接:https://ac.nowcoder.com/acm/contest/881/C解题思路:AC代码:#include<bits/stdc++.h>#define up(i, x, y) for(ll i = x; i <= y; i++)#define down(i, x, y) for(ll i = x; i >= y; i--)...

2019-07-24 14:54:51

2019暑假训练日常收获1

1. 用c++判断一个数是否超过 long long的小技巧,前段时间做了一道题目,这道题目可能爆long long ,但是知道爆 long long 之后应该输出什么,所以可以用这种方式:long long x;scanf("%lld", &x);if(x < 0) puts("long long");但是需要注意的是: cin 不可以,如果用 cin>&g...

2019-07-24 10:35:23

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。