2 sugarbliss

尚未进行身份认证

我想要的不多,只是和多数人不一样。

等级
TA的排名 7k+

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

题目链接:https://ac.nowcoder.com/acm/contest/889/H题意:有棵树和次询问。每次询问表示在到的范围内砍次,将所有的树高都砍为,但是要保证每一刀砍出来的长度(砍去树高于该高度的和)都是相同的。问你第次砍的时候砍的高度在哪里。有精度误差。每次只对本次操作有影响,操作完后,树回到原来的高度。思路:先求出所有树的高度之和,那么表示...

2019-08-20 18:23:23

P2661 信息传递 - (并查集求最小环)

题目链接:https://www.luogu.org/problem/P2661思路:如果有两个点祖先节点相同,那么就可以构成一个环,长度为两个点到祖先节点长度之和+1,新加入的一条边的两个端点在并查集中同祖先,则一定成环。#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definei...

2019-08-17 10:40:38

2019牛客暑期多校训练营(第九场) - E - All men are brothers(并查集+组合数)

题目链接:https://ac.nowcoder.com/acm/contest/889/E题意:有N个人M个操作,每次操作让两个人互相认识,认识关系可以互相传递,求每次操作完毕后,选4个互相不认识的人的方案数。思路:首先未操作之前,考虑每次操作对答案的影响,我们设合并的两个集合是,,对于,集合未合并之前,我们可以在,,集合中各挑选一个数,然后在,,集合外挑选两个数,注意集合外挑选时要排除...

2019-08-16 18:27:12

2019牛客暑期多校训练营(第九场) - D - Knapsack Cryptosystem(折半枚举)

题目链接:https://ac.nowcoder.com/acm/contest/889/D题意:挑选若干个数使得和为s。思路:考虑二进制枚举,但是n的范围是36,直接枚举会超时,所以我们把数组分两部分枚举,然后用map映射一下即可。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongll...

2019-08-16 17:54:05

P5268 [SNOI2017]一个简单的询问(莫队)

**题目链接:**https://www.luogu.org/problem/P5268**思路:**对于只查询不修改,而且查询有关元素出现次数的要求,我们要用莫队做,但是莫队是用来处理一类双端点询问,所以我们要把式子拆成四个双端点询问。题目中原式是这样的:∑x=1∞get(l1,r1,x)∗get(l2,r2,x)\large\sum\limits_{x=1}^\infty\text{ge...

2019-08-14 12:08:37

STL 之 equal_range用法

equal_range是C++STL中的一种二分查找的算法,lower_bound返回区间的第一个大于等于的迭代器,upper_bound返回区间的第一个大于的迭代器,而equal_range则是以pair的形式将两者都返回。可以用来查询有序区间数字出现的次数。#include<bits/stdc++.h>usingnamespacestd;intmain()...

2019-08-13 17:34:29

牛客小白月赛15 - H - 数据结构题(主席树)

题目链接:https://ac.nowcoder.com/acm/contest/917/H思路:询问区间内出现的次数,注意的情况即可。#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm&g...

2019-08-13 09:03:00

牛客小白月赛9 - E - 换个角度思考(主席树)

题目链接:https://ac.nowcoder.com/acm/contest/275/E思路:求区间内小于的个数(分块和树状数组也可写),主席树保存的是值域,当我们查询到时,说明此时左子树的值全部满足小于直接加即可,当查到叶子节点直接返回两颗线段树的差值即可。#include<cstdio>#include<vector>#include&l...

2019-08-13 08:55:11

SPOJ - DQUERY(主席树)

题目链接:https://vjudge.net/problem/SPOJ-DQUERY题意:询问区间不同数字的个数。思路:这题莫队,树状数组都可以写,主席树做法:我们需要维护每个数最后一次出现位置,所有最后一次出现位置对整个区间有1的贡献,也就是对每一个数建一棵线段树,如果这个数之前出现过则再建一棵树删除。#include<cstdio>#include<ve...

2019-08-12 15:50:46

POJ- 2104 - K-th Number(主席树)

题目链接:http://poj.org/problem?id=2104思路:静态区间第k小,主席树模板题。#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm>usingnamespace...

2019-08-12 15:36:07

2019牛客暑期多校训练营(第八场)- C - CDMA(构造)

题目链接:https://ac.nowcoder.com/acm/contest/888/C题意:给你一个,,构造一个的矩阵,矩阵由和组成,并且矩阵的任意两行相乘的和为0。思路:首先时的答案已经知道,考虑用构造出的解,不妨设方阵为的解,那么下面这个方阵则是的一个解:。#include<bits/stdc++.h>usingnamespacestd...

2019-08-10 18:11:06

HDU - 5249 - KPI(权值线段树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5249题意:有三种操作:inx表示加入数x。 out表示弹出最早元素。 query表示查询当前的序列中位数即第floor(m/2)+1的数字。思路:用队列找最早的元素,权值线段树查询即可,本题需要离散化。#include<bits/stdc++.h&...

2019-08-09 16:20:40

HDU - 6630 - permutation 2(打表找规律)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6630题意:给你~数字组成的序列固定开头和结尾,并且相邻两个数字绝对值之差小于等于2,问方案数?思路:打表发现~的方案为,那么其余情况也与~的方案有关,观察发现时方案为,其他为。#include<bits/stdc++.h>usingnamespacestd...

2019-08-07 10:57:53

HDU - 6629 - string matching(扩展KMP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6629题意:给你一个字符串,让你求对于每一个字符串的后缀(),与匹配最长公共前缀的总次数。思路:对于和做扩展KMP,得到数组(表示与的最长公共前缀),然后从开始统计即可。#include<bits/stdc++.h>#definelllonglongusing...

2019-08-05 17:40:51

2019牛客暑假多校训练赛第六场 - D - Move (假二分)

题目链接:https://ac.nowcoder.com/acm/contest/886/D题意:给你个物品的体积和个相同体积的盒子,让你将个物品装进个盒子,在物品体积小于盒子体积的前提下尽量先装体积较大的物品。问盒子的最小体积。思路:本题不具有单调性(物品的体积不连续),暴力枚举答案即可。#include<bits/stdc++.h>usingna...

2019-08-04 18:39:06

2019牛客暑期多校训练营(第六场)- J - Upgrading Technology(思维)

题目链接:https://ac.nowcoder.com/acm/contest/886/J题意:你有个技能每个技能有级,从级升级到级需要支付元(时表示获得元),当所有技能都升级到级时,获得额外奖励元(时表示失去元)元,询问最大的利润,最小利润为0(即升级0个技能)。思路:枚举所有技能的最低等级,然后判断每一个技能在最低等级的基础上能不能获得额外的利润(和...

2019-08-04 16:18:01

2019牛客暑期多校训练营(第六场)- B - Shorten IPv6 Address(模拟)

题目链接:https://ac.nowcoder.com/acm/contest/886/B题意:您将获得一个IPv6地址,该地址是128位二进制字符串。请根据以下规则确定其最短的表示:以十六进制表示形式表示地址,并使用冒号':'分割每四个十六进制数字。每四个数字称为一个字段。例如,'0000:0000:0123:4567:89ab:0000:0000:0000'。可以省略字段中的前导零...

2019-08-03 18:00:29

Codeforces Round #576 (Div. 2) - D. Welfare State(思维 or 线段树)

题目链接:http://codeforces.com/contest/1199/problem/D题意:给你一个序列,有两个操作:将p位置改为x。 将小于x的值改为x。思路:先说思维,我们想一下如果只有操作2,那么是不是只有操作2中最大的x起作用,那么引入操作1,那么就是操作1之后的最大x有关系,所以我们维护操作1修改的位置,维护一个后缀mx(因为后面影响前面),如果没有操作1,那直...

2019-08-01 09:29:24

2019牛客暑期多校训练营(第一场)H - XOR(线性基+组合数学)

题目链接:https://ac.nowcoder.com/acm/contest/881/H题意:给你n个数,让你求每一个异或和为零子集大小的总和。线性基的常用性质:线性基中的数字都是线性无关的。 线性基里面的任意一些数异或起来都不能得到0。 若一个数字无法加入线性基中,说明该数字可被线性基中的若干个数字异或得到。 对于一个序列线性基可能有若干个,但每一个线性基内元素的个数是一定...

2019-07-30 17:30:57

BZOJ - 2460 - 元素(贪心+线性基)

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2460思路:我们发现选元素的过程就是构造线性基的过程,为使得总的魔力值最大,我们对元素按魔力值排序按权值从大到小插入到线性基中就可以保证得到的线性基中的元素是权值之和最大的。#include<bits/stdc++.h>usingnamespacestd;c...

2019-07-30 12:05:26

查看更多

勋章 我的勋章
  • 领英
    领英
    绑定领英第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。