icontofig | 发布于 2019-10-31 20:13:52 | 阅读量 304 | 二分 分数规划 树状数组
发布于 2019-10-31 20:13:52 | 二分 分数规划 树状数组
CCPC2017哈尔滨站 Server——01分数规划+树状数组
题目大意给出一些线段,给出这些线段的起始和终止位置,并给出这些线段选取的两个代价A和B,要求选取一些线段覆盖区间[1----t],使得ΣAi与ΣBi的比值最小。 题解很经典的01分数规划问题的形式。 当天训练的时候就想到了BUPT2019校赛的一道01分数规划问题,当时还是我们队拿的那题一血,可惜当时的队友现在因为一些原因分开了,真是令人感叹,sigh。 回归正题…… 这一类最经典的01分数规划的解题基本思路是十分固定的,如下: 1.二分一个目标值mid 2.贪心地去构造检验是否有一组可行解,使得ΣAi / ΣBi <= mid; 3.如果能构造出这样一组可行解,那么将二分区间向左缩进,
继续阅读
icontofig | 发布于 2019-09-08 00:15:37 | 阅读量 331 | 树状数组 偏序
发布于 2019-09-08 00:15:37 | 树状数组 偏序
The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序
题目大意给定一个1---n的排列和m次询问,每次询问区间 [l,r]之间min(pi,pj) = gcd(pi,pj)的数对的个数。 题解一开始看到是数对问题还以为是莫队,不过话说回来莫队WA了而不是T是怎么回事…… 首先我们需要注意min(pi,pj) = gcd(pi,pj)可以转化为pi和pj互为因数和倍数的关系(这样可以做一点常数上面的优化,也更好判断总体的数对的个数)。 然后我们要知道,所有的数对个数大概是O(nlogn)级别的。 于是我们可以枚举每个数的倍数预处理出所有的数对的位置对(i,j),我们尽量让i比j大,这有利于下面的思路。 然后有没有发现这个位置对很像是二维平面上的坐标
继续阅读
icontofig | 发布于 2019-09-02 23:23:58 | 阅读量 615 | 思维题 扫描线 树状数组
发布于 2019-09-02 23:23:58 | 思维题 扫描线 树状数组
2019 南京网络赛 A.The beautiful values of the palace 思维题+扫描线+树状数组
题目大意每个点的数值是通过一个从中心最大值开始的蛇形矩阵确定的。其中有m个点上的权值可用,对于q个询问,输出左下角为(x1,y1),右上角为(x2,y2)的矩阵区域内所有可用点的权值经过处理后的和。 处理的方法是,将原权值所有数位上的数相加。 题解此题估计是模仿NOIP2014普及组T3的蛇形矩阵出的规律题目。 首先n为奇数,n*n为奇数,地图大小为 一定为奇数,所以 x = x − n/2 − 1y = y  - n /2 - 1;t = max(abs(x),abs(y)); //确定该点在第几圈螺旋 if(x >= y)ans = n ∗ n
继续阅读
icontofig | 发布于 2019-05-31 00:46:09 | 阅读量 290 | 树状数组
发布于 2019-05-31 00:46:09 | 树状数组
BUPT校内训练 Codeforces Gym 101572 G Galactic Collegiate Programming Contest 离散化+树状数组计数
题目大意一场ICPC赛制比赛,有n支队伍和m次正确提交 每次正确提交包含a,b两个参数,a表示队伍编号,b表示此题的罚时。 要求对于每次事件,输出1号队伍的排名(并列的算同样的排名) 具体排名方法为:通过题目数多的队伍排名靠前,通过题目数相同的队伍总罚时低的靠前。 题解&分析如果暴力做的话,每一修改O(1),排序查询O(nlogn),总复杂度O(mnlogn),这对于10^6的数据是不现实的。 我们要求做到O(nlogn),也就是说不能有每修改一次就排序的操作。 我们可以注意到,每一次事件发生后,只会有一个队伍的成绩发生变化,其余的成绩是不动的。 所以我们可以读入所有数据,然后计算每一
继续阅读
icontofig | 发布于 2019-05-19 21:03:32 | 阅读量 362 | 莫队 树状数组
发布于 2019-05-19 21:03:32 | 莫队 树状数组
XTCPC2019 湘潭邀请赛 Problem C Chika and Friendly Pairs (莫队+树状数组)
 题意:给定n个数,m条询问,每个询问中包含l、r查询这个区间[l,r]中有多少个数对满足两个数的绝对值之差小于等于K 题解:上来一看区间查询,第一反应一般都是线段树/树状数组等数据结构。 但是看一下这道题要求什么,求区间内满足条件的数对个数。 我好像没有见过能维护数对个数的树状数组或者线段树什么的。 对于数对而言,一般都应该先枚举其中一个数,剩下的才能去判断吧。 如果两个数i,j满足绝对值之差小于等于K,那么肯定能有这样一个关系式:i−k<=j<=i+k 这样的话,对于某个区间内的所有数,能跟当前枚举出来的数x组成满足题意的数对的,一定在[x-k,x+k]这个区间里,我
继续阅读
icontofig | 发布于 2019-02-27 23:53:01 | 阅读量 194 | 树状数组
发布于 2019-02-27 23:53:01 | 树状数组
由于格式问题,这道题的题面就不往这里放了,给一个洛谷的链接吧:[POI2005]AUT-The Bus 题解这道题有中文题意,没有BZOJ权限号的可以去洛谷上搜到这道题。首先会想到DP,但是一看这个数据范围也太大了,离散化后也没法做二维DP。但是离散化也是要的,不然10的9次方的数据谁顶得住啊。考虑这是一个二维偏序问题。一般的二维偏序都是找比当前物品的两个值都小的问题,而这道题并不是,这道题要做的是维护最大前缀和。首先按照y排序并且离散化每个车站的y坐标,然后再按照x排序,使用树状数组维护最大前缀和即可(当然线段树应该也是可以的,只不过会比树状数组麻烦一点)。注意这里的树状数组不是维护的前缀和
继续阅读
icontofig | 发布于 2017-01-18 08:56:15 | 阅读量 204 | CDQ分治 树状数组
发布于 2017-01-18 08:56:15 | CDQ分治 树状数组
Description你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:命令 参数限制 内容1 x y A 1<=x,y<=N,A是正整数 将格子x,y里的数字加上A2 x1 y1 x2 y2 1<=x1<= x2<=N1<=y1<= y2<=N 输出x1 y1 x2 y2这个矩形内的数字和3 无 终止程序 Input输入文件第一行一个正整数N。 接下来每行一个操作。 Output对于每个2操作,输出一个对应的答案。 Sample Input41 2 3 32 1 1 3 31 2 2 22 2 2 3 43
继续阅读