qrfkickit - 博客园
摘要: 题意: 给出一个数组,要求把他们排成升序,两个数字交换的代价是x + y,求代价的总和。 思路: 简单的逆序对变形,树状数组维护小于的cnt和sum即可。 代码:阅读全文
posted @ 2018-05-24 04:55 qrfkickit 阅读(6) 评论(0) 编辑
摘要: 题意: 给出一个N * N * N规模的矩阵,有2种操作:1.把A[i, j, k]反转,(x1<=i<=x2,y1<=j<=y2,z1<=k<=z2). 2.查询A[x,y,z]的值。 思路: 三维树状数组裸题,得画图好好推导一下。 区间更新,单点查询。 代码:阅读全文
posted @ 2018-05-24 04:52 qrfkickit 阅读(3) 评论(0) 编辑
摘要: 题意:二维平面上一开始所有星星都是暗淡的。 给出3种操作: 1.将x,y处的星星点亮; 2.将x,y处的星星灭掉; 3.统计x1,y1,x2,y2区间内有多少颗亮的星星。 思路: 二维树状数组裸题。 注意x1,x2,y1,y2数据给出的并不是有序的,这是一个坑点。 代码:阅读全文
posted @ 2018-05-24 04:49 qrfkickit 阅读(3) 评论(0) 编辑
摘要: 题意: 最开始有一个空的数组,有3中操作: 1.插入一个元素 2.删除一个元素 3.查询比a大的第k个元素是多少。 思路: 主要是第三个操作 树状数组求第k大是用的二分,判断满足的条件是大于等于0 这题首先得求出小于等于a的元素,假设是cnt,那么大于它的第k个元素,求的就是整个数组的第cnt + 阅读全文
posted @ 2018-05-24 04:46 qrfkickit 阅读(2) 评论(0) 编辑
摘要: 题意: 有若干棵树,每棵树有横坐标xi和高度hi。 把若干棵树按照x递增排序,每棵树的rank是ri,那么定义两颗树的F为abs(ri-rj)。 把若干棵树按照高度递增排序,每棵树的rank是ri,定义两棵树的D为min(ri,rj)。 两棵树的不和谐度定义为D * F。 求n棵树中任意两棵树的不和阅读全文
posted @ 2018-05-23 16:58 qrfkickit 阅读(2) 评论(0) 编辑
摘要: 题意: 有一棵树,这棵树上有很多果子,一开始每个果子都在,给出下面两种操作: 1.C x,改变果子x的状态,如果有,那么久摘下来;没有,就变为有; 2.Q x,问在x上面的(包括x)有多少个果子。 思路: 多叉树,朴素的更新方法就是从叶子到根的路径上的点的值全部更新,但是这样每更新的复杂度是O(n)阅读全文
posted @ 2018-05-23 16:01 qrfkickit 阅读(7) 评论(0) 编辑
摘要: 题意: 若干头牛排列在一条坐标轴上(位置都不同),每头牛都有一个音量vi,任意两头牛i,j之间要交流,他们发出的音量就是max(vi,vj) * 它们的距离。 问n / (n-1)对牛交流的音量的总和。 思路: 先无脑n ^ 2了一波,果然tle了,是我太naive。 首先把牛按照音量递增排序,对于阅读全文
posted @ 2018-05-23 04:03 qrfkickit 阅读(1) 评论(0) 编辑
摘要: 题意: 给出一个矩阵,有两种操作: 1.翻转给定的子矩阵; 2.查询a[i][j]的值。 思路: 树状数组是从小到大更新的。 这个题用二维树状数组可以解决,假设是一维树状数组, 0 0 0 0 0 0 我们把第三个到第四个翻转,变成 0 0 1 1 -1 0 sum[1] = 0,sum[2] = 阅读全文
posted @ 2018-05-22 23:11 qrfkickit 阅读(3) 评论(0) 编辑
摘要: 题意: 对一个矩阵有2种操作: 1.把某个元素设为x。 2.查询以(x1,y1)为左上角 以(x2,y2)为右上角的矩阵中的数字的和。 思路: 二维树状数组入门题,同时对横坐标和纵坐标做前缀和就行了。 代码:阅读全文
posted @ 2018-05-22 19:44 qrfkickit 阅读(2) 评论(0) 编辑
摘要: 题意: 给出一个矩阵,其中某些格子有树,用给定的一个规模的方框去圈,问最多可以圈到多少树。 思路: 二维树状数组裸题。 代码:阅读全文
posted @ 2018-05-22 18:36 qrfkickit 阅读(2) 评论(0) 编辑
摘要: 题意: 输入若干个区间,对于一个区间(a,b),如果存在一个区间(x,y)满足x <= a && y >= b && y - x > b - a,那么就说(x,y)比(a,b)大。 求比每一个区间大的区间有多少。 思路: 树状数组,这题最关键的其实是有重复的区间。 首先把区间按照起点升序排序,如果起阅读全文
posted @ 2018-05-22 11:29 qrfkickit 阅读(3) 评论(0) 编辑
摘要: 题意: 把一个数组分成若干组,保证每组的size >= k并且一组中任意两个数字的差的绝对值 <= d,问存不存在这样的分法。 思路: 线性dp。 用dp[i]表示前i个数是否有分法。 设j为满足a[i] - a[j] <= d的最小的a[j]的下标,那么dp[i]就可以从dp[j-1] ~ dp[阅读全文
posted @ 2018-05-22 10:45 qrfkickit 阅读(40) 评论(0) 编辑
摘要: 题意: 有n * k块木板,每个木桶由k木板组成,每个木桶的容量定义为它最短的那块木板的长度。 任意两个木桶的容量v1,v2,满足|v1-v2| <= d。 问n个木桶容量的最大的和为多少,或者说明不可能做出这样的n个木桶。 思路: 贪心 要满足|v1-v2| <= d,那么就要满足最大的木桶容量和阅读全文
posted @ 2018-05-22 10:05 qrfkickit 阅读(56) 评论(2) 编辑
摘要: 题意: 有n个开关,m盏灯。 一个开关可以控制多个灯,一旦一个灯开了之后,之后再对这个灯的操作就没用了。 问是否存在一个开关,去掉了这个开关之后,按下其它开关之后所有的灯还是亮的。 思路: 首先统计每个灯被按了几次,然后枚举每个开关,把这个开关的贡献去掉,判断是否所有灯的次数大于等于1,然后再回复这阅读全文
posted @ 2018-05-22 09:18 qrfkickit 阅读(50) 评论(0) 编辑
摘要: 题意: 移动最少的步数,使得所有的棋子在同一颜色的格子中。 每次一个棋子只能向左或者向右移动一步,不能移到有棋子的格子中。 思路: 枚举全黑和全白的情况。 对于每一个需要移动的棋子,它移动到的位置一定是从1开始第一个可以移动的位置,不交叉移动,保证了步数最小。 代码:阅读全文
posted @ 2018-05-22 09:14 qrfkickit 阅读(27) 评论(0) 编辑