horbivores

分类

anti-sg(1) 动态规划(3) 天梯赛-20分(2) 开始补题(2) 未归档(10) 树状数组(1) 算法(4) 线性基(1) 线段树(2) 题解(3)

/ 注册

全部文章（共29篇）

牛客多校第八场 I题 Interesting Computer Game

题目大意是每次给你两个数，你只能在其中选一个没有选过的数，可以不选。问你最多选多少个数我们可以把两个数当成一条边，由于数字会很大，所以先离散化。然后就转化成了一个图的问题。题目意思等价于在图中有若干条边，对于每条边，你可以选择它所连接的两个顶点中的一个，问你最多可以选择多少个不同的点。我们知道...

2020-08-03

2 569

K-Bag

题目大题：K—Bag：数组是由若干个长度为k的全排列组成的，然后在开头和结尾都可以删去位置连续的若干个元素。最后要你判断是否是K-Bag 我们定义一种边（u, v)；若u=1 或v=n+1，则要求a[u],a[u+1],..,a[v-1]都是由不同的数字组成的反之，我们要求 v-u == k, ...

2020-07-27

3 565

D Drop Voicing

题目大意：有两种操作，1.整个数组执行若干次循环移位，2.前n-1个元素执行若干个循环移位。问，把一个全排列排成升序最少要执行多少次第二种操作。我们再把两种操作组合一下，按照1 2 1来组合，我们发现可以等价于把任意一个数放在任意的地方。直觉证明：1 2 3 4 5我们通过三个操作把5放在3前面...

2020-07-25

1 388

JDNzMvwJSW

2019-07-19

0 343

HDU4893-线段树

题目给你三种操作： 1：将第i个数加上j； 2：求一个区间内数的和 3：将一个范围内的数改成与它最接近的斐波那契数，若距离两个相邻的数字距离一样取小的那个。数组内所有数初始值为0 经典的线段树维护区间修改单点修改，区间查询。只要维护一个原数组和改变后的数组即可。区间更新的时侯直接赋值就可以了 A...

2019-07-19

0 427

HDU3466-排序+背包

题目地址转移剩余的空间，当前的剩余的容量为j，则dp[j] 由 dp[j+a[i].p] 转移过来。但是由于物品出现的位置不确定，所以要排个序。不理解要排序的可以用这两组样例试一下： 2 10 1 10 10 2 9 10 2 10 2 9 10 1 10 10 正解为20； ac代码： #...

2019-07-09

0 421

树状数组与LIS

求LIS的方法有很多，现在我知道的有三种，分别是dp，贪心+二分，树状数组。这篇博客就重点写一点用树状数组解决LIS相关的题目。预备知识：树状数组，离散化。一个板子题：题目我就简单的说一下用树状数组的思路：首先数据很大，很自然的想到离散化。然后树状数组维护什么呢？[1-i]（i为离散化后的相...

树状数组

2019-07-03

0 621

HDU-1907-anti-sg

题目经典的anti-nim题目。和普通的nim差不多，判断结局的方式不一样：游戏的SG函数不为0且游戏中某个单一游戏的SG函数值大于1，游戏的SG函数为0且没有某个单一游戏的SG函数大于1，先手必胜。 ac代码： #include<bits/stdc++.h> using name...

anti-sg

2019-07-03

0 391

牛客小白月赛15-E-线段树+01背包

原题地址没仔细看题目。以为一个人只能选一次。。这样的话用线段树搞一下就可以，求出每个信号要抹去的最小代价，然后一个01背包就可以求出答案啦。 #include<bits/stdc++.h> using namespace std; typedef long long LL; cons...

2019-06-15

0 411

牛客小白月赛15-H-分块/主席树/技巧二分

题目题目意思很简单，方法很多，就做个解法集合。 1.分块：分块也是挺好写的。（写的少，出了好多细节问题）刚开始想每块用个map维护的，然后超内存了，还是老老实实用vector。坑点，l,r的大小不一定。顺便分享一个stl函数，equal_range()，返回有序容器中valu对应的区间，返...

2019-06-15

0 589