3 Top_xiao

尚未进行身份认证

暂无相关描述

等级
博文 211
排名 3w+

bzoj 4571: [Scoi2016]美味 (xor主席树)

题意:一家餐厅有n道菜,编号1…n,大家对第i道菜的评价值为ai(1≤i≤n)。有m位顾客,第i位顾客的期望值为bi,而他的偏好值为xi。因此,第i位顾客认为第j道菜的美味度为biXOR(aj+xi),XOR表示异或运算。第i位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第li道到第ri道中选择。...

2019-07-18 11:59:26

CF813E Army Creation (主席树)

题意:n个数a[i]a[i],qq次询问,n,a[i],q<=105每次问[l,r]内最多可以选多少个数,满足同一个数的出现次数不超过k?思路假设我们想找一个[l,r]区间内的数,什么时候这个区间里的数是有效的呢?那肯定是这个数x出现不超过k次,如果超过k次就无效了,也就是说,向前找和这个数x一样的数,直到向前找k个,如果这个数的位置pos小...

2019-07-18 09:19:16

CF Gym ACM Tax (主席树, LCA)

求树上两点间路径上边权的中位数.就是z=lca(x,y)xy减去两倍的z.#include<bits/stdc++.h>usingnamespacestd;constintN=5e4+100;intHead[N],Next[N*2],To[N*2],Val[N*2],cnt;intdep[N],f[N][23];intls[...

2019-07-17 20:35:09

Luogu P4559 [JSOI2018]列队 (区间问题, 主席树)

题目:https://www.luogu.org/problemnew/show/P4559一句话:教官会指定一个区间[l,r]和集合点K,所有编号在[l,r]内的学生都必须赶到集合点列队。简单来说,就是在主席树中我们要知道这个区间的学生要向什么方向移动,知道了向什么方向移动就好办了,还要知道这个区间的学生要移动到什么位置.就是一个区间的学生移动到给定的...

2019-07-17 09:11:37

HDU 6562 Lovers (线段树)

题意:有n个字符串,每个字符串一开始是空的.然后有m个操作,两种类型,一个是修改,一个是查询,修改操作:xyz区间[x,y]中的每个字符串的首尾都加上一个数字z,这个z是一个数字字符查询操作:xy,区间[x,y]中把字符串转换为数字然后全加起来是多少.这里有五个变量:val1就是每个区间的最终答案val2就是每个区间...

2019-07-16 19:15:35

Luogu P4587 [FJOI2016]神秘数 (主席树)

题目描述一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13},1=12=1+13=1+1+14=45=4+16=4+1+17=4+1+1+18无法表示为集合S的子集的和,故集合S的神秘数为8。现给定n个正整数a[1]..a[n],m个询问,每次询问给定一个区间l,r,求由a[l]...

2019-07-16 09:23:16

bzoj 1935: [Shoi2007]Tree 园丁的烦恼 ( 树状数组 )

题目:就是求矩形内点的个数这个没有修改,但是数据范围很大,所以要离散化,用树状数组就好了,没有必要用CDQ.求ans的时候,分成求四个点到原点的矩阵和,加加减减就好了#include<bits/stdc++.h>#definelow(x)(x&(-x))usingnamespacestd;constintN=1e6+10;...

2019-07-15 15:57:30

bzoj 1176: [Balkan2007]Mokia (CDQ 分治, 两种方法的 )

描述:维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.思路:三维,时间一维,x轴一维,y轴一维,按照一维排序之后,然后用左区间更新右区间;树状数组进行维护.这里有两种写法,一种是用时间分治,一种是用x轴分治,用时间分治:这种用...

2019-07-15 14:13:24

LCIS HDU - 3308 (线段树,区间合并,求连续最长严格上升序列)

思路:线段树记录三个值,从左到右的,从右到左的,还有一个区间最长的,值得注意的一点就是 pushup的时候要仔细,不要少合并了.#include<bits/stdc++.h>#definelsonnow<<1#definersonnow<<1|1usingnamespacestd;constintN...

2019-07-14 14:48:35

HDU - 4578 Transformation (线段树 有点复杂)

这个博客讲的很详细了。但是有一个地方是错误的https://blog.csdn.net/HelloWorld10086/article/details/48084941这个地方要在乘一个b。代码:#include<bits/stdc++.h>#definelsnow<<1#definersnow<<1|1u...

2019-07-12 16:16:45

Codeforces Round #375 (Div. 2) E. One-Way Reform (并查集,欧拉回路)

题意翻译给出一个n个点m条边的无向图,你需要给每条边定向,使得有尽量多的点,入度等于出度,并构造方案一共有t组数据t,n<=200思路:题目给的无向图,没有重边,自环,但是他有可能不是一个连通图,所以我们要用到并查集来做,分成一个一个的小块。然后每个小块我们加上一些边,使得这个小块可以跑欧拉回路。然后输出边的时候我们要注意把那些我们手动加入的边去掉就可以了。存...

2019-07-11 13:17:50

VK Cup 2012 Finals, Practice Session C. Trails and Glades (欧拉回路,并查集)

题目描述给定一个n个点,m条边的无向图,可能有重边和自环,求最少添加几条边,使得图中所有边都在从1出发的欧拉回路上。注意点:1、这个题强制了从 1 开始走2、要走题目中给的所有边3、孤立的点可以不走,如果有自环的话一定要走4、无论什么情况,1 这个点一定要走,思路:这个题我用了并查集来做。然后就是分类讨论了。并查集首先求出来有多少个联通块,这个时...

2019-07-11 00:18:50

Codeforces Round #296 (Div. 1) C. Data Center Drama

给你一个无向图。要求加最少的边,然后给这些无向图的边定向,使得每一个点的出入度都是偶数。输出定向后的边数和边集。n<=10^5,m<=2*10^5n<=105,m<=2∗105思路:先添加边,让图可以跑欧拉回路,就是让所有点的度数为偶数,然后跑一次欧拉回路,记录一下路径,然后输出来就可以了。#include<bits/stdc...

2019-07-10 18:53:18

sublime vscode 配置c++

windows下sublime配置c++{"cmd":["g++","${file}","-o","${file_path}/${file_base_name}","-Wall","-Wextra","-g"],"file_regex":"^(..[^:]*):([0-9]+):?([0-9]+)?:?(.*)$","working_di...

2019-06-29 16:03:32

报错: watchdog: BUG: soft lockup - CPU#0 stuck for 23s

转载:https://www.cnblogs.com/nulige/p/8000490.html解决办法:#追加到配置文件中echo30>/proc/sys/kernel/watchdog_thresh#查看[root@git-node1data]#tail-1/proc/sys/kernel/watchdog_thresh30#临时生效sysc...

2019-06-28 17:12:46

Python外星人入侵

写这篇文章的意义主要是记录一下自己犯了那些错误安装就不说了使用pygame.rect的时候,rect有好多参数,当我们修改的一个参数的时候,其他的参数也会随之改变。按下响应键的时候,event.typeevent.key是不一样的东西,要注意区分一下当我们使用模块中的类的时候,一定不要忘记了继承这个东西。...

2019-06-02 11:09:15

Codeforces Round #562 (Div. 2) (C - E )题解

C.IncreasingbyModulo这个题是一个二分答案题。首先我们二分一个值出来,然后check,关键是如何check。我们首先假定最小的一个值是0,然后遍历一遍数组,把数组上的值在允许的范围内尽量改小就好,如果最后满足题目要求,那么这个二分的数就是满足条件的。#include<bits/stdc++.h>usingnam...

2019-05-30 20:32:37

Codeforces Round #556 (Div. 2) (A - E题解)

A.StockArbitraging贪心选最小最大就可以了。B.TilingChallenge模拟暴力就可以了。C.PrefixSumPrimes这个题因为只有1和2,所以我们贪心一下,如果加1是质数的话,那么就加1,否则优先使用2.D.ThreeReligions首先预处理出来一个idx数组,代表从i这个位置开始,字母c...

2019-05-29 16:29:00

P4139 上帝与集合的正确用法 (扩展欧拉函数)

扩展欧拉函数:然后线性筛求欧拉函数。#include<bits/stdc++.h>usingnamespacestd;constintN=1e7+10;intcnt,phi[N],p[N/10];boolvis[N];voidGet_phi(intn){phi[1]=1;for(inti=2;...

2019-05-26 16:06:32

Luogu P1438 无聊的数列 (线段树)

题目背景无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天,无聊的YYB想出了一道无聊的题:无聊的数列。。。(K峰:这题不是傻X题吗)题目描述维护一个数列{a[i]},支持两种操作:1、1LRKD:给出一个长度等于R-L+1的等差数列,首项为K,公差为D,并将它对应加到a[L]~a[R]的每一个数上。即:令a[L]=a[L]+K,a[L+1]=a[L+1]+K+D,...

2019-05-26 12:41:50
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。