月度归档:2017年03月

Codeforces Round #407 (Div. 2)做题记录

被学长和myk大爷carry了,但是人太菜,居然还写挂了一个D题。。无语了。。。所以机房开车众都一夜上紫了,而我还是在div2鱼塘里沉迷。。。

A. Anastasia and pebbles

题意:给出n堆不同颜色的石子,k个相同颜色的石子可以放到一个口袋内,但是1天只有两个口袋。需要判断出最少需要多少天把所有石子弄完。n<=10^5

比赛的时候一开始按照2*k分堆了,一直wa,后来就按照k来分堆了。把所有种类的石子都分成k个1堆,如果剩余的话就在弄一堆。

B. Masha and geometric depression

题意:就是给你一个等比的序列,告诉你这个序列中的绝对值不能超过l,而且有若干数是不能选的。问最终这个序列最终有多少个数字。

分类讨论q=0,q=1,q=-1,以及首项小于l的情况,总之情况需要好好判断。。。然后wa惨了,不过还好搞过了。

C. Functions again

题意:给出n个数,组成一个a[i]的序列。定义:,求整个序列的最大的f值。

维护一个数组,它类似于差分数组,只过是在第奇数个差分数组的值前面乘1,在偶数面前乘-1。这是因为f(l,r)中的相邻差分值随着起点的不同而正负改变。假设起点为奇数的位置,那我们就需要在这个新数组内找寻一个区间连续最大值。假设起点为偶数的位置,那么我们就需要在这个新数组内找寻一个区间连续的最小值,最后把这个最小值取负就好啦。取区间连续的最大值可以O(n)扫一遍就好了。

D. Weird journey

题意:图中有n个点,m条边,现在你可以选择两条边只走一遍,其余边走两遍,使得可以一次走完所有的边。每个点存在最多一条的自环。问不同的方案数,不同的方案数定义为选取的只走一遍的边不完全相同。

题目要求一次走过所有的边,而不是所有的点,所以假如图中有孤立点,但是边可以一次走完,仍然是合法的,这里一定要注意。

问题等价于把原图中的边都复制一遍,然后要求选择两条边删去,使得剩余的边们可以形成一个欧拉路(或者欧拉回路)。因为原图中的边都复制了一遍,那么现在的图中每个点的度都是偶数的,那么如果原图是一个联通的,那么新图一定是个欧拉图。考虑自环和非自环的边的情况,假如删掉任意两个自环,那么我可以任意删去两个点的自环(因为一个点的自环最多只有一条)。这样的方案数是,其中C是有自环的点数目。假如删去一个非自环和一个自环的话,那么这样最多也只会改变两个点的度的奇偶性,所以肯定可以满足欧拉路的条件。那么这个方案数是(m-c)*c。也就是从非自环任选一条,自环任选一条。那么考虑删去两个非自环的边,假如删去的边没有公共顶点,那么会让4个点的度都从偶数变成奇数,无解。除非这两条边有一个公共顶点,这样保证只会影响到两个点。所以这部分答案就是

判无解的地方我比赛的时候写错了。。。。so sad。。。但是写挂自己菜,还是当时脑子一热了。。

 

E. The Great Mixing

题意:现在有k个物品ai/1000,可以重复选用物品,要求最后调制出n/1000的物品,求出最少使用多少个。k<=1000000,0<=n<=1000,0<=ai<=1000

比赛的时候只是看了看题,以为是个怎么背包的题目。。。赛后学长说可以bfs。。。去看了一下官方题解,果然可以。。。

首先我们可以把每个物品都减去一个n,这样变成了从任意件物品中可以重复选用凑成0的情况。因为物品实际种数不会超过1001(0-1000),所以我们可以以这些为起点去bfs找到他们能够到达的可行状态,从而找到到0这个点的最短路。注意一个点,就是我们可能会出现先加上一个数x(现在答案大于了n)再减去一个数(现在答案等于了n)。但是如果我们不卡住边界的话,状态就太多了。但是上面说的那个情况如果反过来,先减去再加上就可以了,所以说卡住边界为-1000到1000好了。

 

Codeforces Round #406 (Div. 2)做题记录

这一场好难,比赛的时候没调出来C狗带了,补题的时候补的也心好累。。。

A. The Monster

题意:给出a,b,c,d四个数字,求b+a,b+2a,b+3a….这样的等差数列和d+c,d+2c,d+3c这样的等差数列中是否有公共项,并输出最小的那个。

发现让求的是b+qa=d+pc。然后就是b-d=qa-pc了,那么就是根绝扩欧,判断一下a和c的gcd能不能整除b-d就可以判断是否无解了。然后找最小,因为范围才100,所以可以暴力做。

B. Not Afraid

题意:太扯了,忘了。。。

判一判。。。

C. Berzerk

题意:
问题概述:有n个点排成一个圈,第一个点的位置是黑洞。其中某个行星上有一个怪兽,第一个玩家和第二个玩家各有k1和k2个数字。每次他们可以把怪兽从之前的位置i移动到(i+x)的位置上去(x是选择的数字),两个玩家都会选择最优方案,那么对于怪兽所有可能的初始起点(2-n),第一行输出第一名玩家先手的输赢情况,第二行输出第二名家先手的输赢情况。注意存在平局的可能。

貌似被称为有向图博弈。就是按照必胜必败态的严格定义来搜吧。考虑假如面对一个当前点在黑洞的局面,肯定先手必败。那么从这个状态我们可以延伸到上一个人操作的时候必胜态(因为它可以操作到达必败态)。我们在每个点弄一个计数器,当对于一个点来说,无论先手怎么移动都到必胜态的时候,那么这个点就是必败态了。可以进一步搜索了。就是个bfs,但是可能我写法太丑细节有点多,比赛的时候太慌张了就没搞出来。。。。

D. Legacy

题意:给出三种有向边,一种边是从点到点,第二种是从点到一个区间,第三种是从区间到一个点。问从一个起始点开始到其余各点的最短路。n<=100000

就是区间到区间的连边不好处理,如果暴力连边的话是n^2的。学习到了新姿势,就是可以用线段树来优化建图。用线段树的一个节点来表示一整段区间(貌似线段树处理这种区间化点很常见?)。但是这个图是一个有向图,所以我们需要建立两棵线段树表示起点终点。对于表示点到区间的边,我们只需要从原图上的点向线段树中对应哪些点连边就好了,这个是O(logn)的。区间到点反过来就好了。但是其实这样做线段树和原图还是没有建立起完整的关系。首先对于终点线段树,他最后还是需要对应到原图上去,所以我们从线段树上的父亲节点向儿子节点连0边,同时叶子节点也要向原图中的节点连0边。另外一个反过来就好了。。。然后跑个dij。。。。

爆int …..

E. Till I Collapse
题意:给出n个人,每个人都有一个颜色,现在要让你把这n个人划分成若干小队,满足每个小队内的不同颜色种数不能超过k。求对于k=1,2,…n来说,最小的队列数。
膜了一下官方题解:O(nlognlogn)。。。
首先不管怎么说,肯定是能尽量拿尽量拿,保证一个队尽可能的长。然后我们在枚举k的时候,其实已经有了一个O(nlogn)的复杂度了:因为n+n/2+n/3+….n/n=nlogn。。。所以我们必须要在logn的时间内找到对于一个位置i而言,最大的一个j,满足i到j的颜色数不超过k。那也就需要知道[i,j]这样一段区间有多少个不同的颜色。
可以主席树维护一下这个东西,我们从位置1开始维护,用一个Next记录下来每种颜色的上一个位置在哪里。第i棵主席树表示的含义就是从1-i这样一段区间内的不同的颜色数目。也就是每个节点都存一下他所代表的区间内的颜色个数。因为我们记录下来了之前那种颜色的位置,所以新加入i位置的时候,在那个位置上减去1,在i位置上加上1.这样每次修改O(logn)个节点。从而满足统计出来1-i的颜色个数。
维护出来后就该找答案了。我们从后往前找,想从第n棵主席树开始,这样相当于固定了一个队伍的右端点,然后我们在这棵主席树上二分的走,当某一个节点右儿子所代表的的区间颜色个数大于k了,那我们的左端点一定在右儿子里面,所以往右子树走。当然反之的话就要往左子树里走了。走到叶子节点的话有两种情况,一种是叶子节点的颜色数目大于你现在需要的颜色数目,这样的话这个叶子是不能取的,返回l+1.否则的话就是这个叶子节点了,返回l。
好棒的题目啊,好久不写主席树了,回忆起来一点了。。。

 

BZOJ 2648: SJY摆棋子&2716: [Violet 3]天使玩偶 K-Dtree

Description

这天,SJY显得无聊。在家自己玩。在一个棋盘上,有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子,要么放上一个白色棋子,如果是白色棋子,他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子,输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M
以后M行,每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output


1
2
学习了一下K-Dtree,现在也只是学了个大概,简单说一下。。。如果有什么错误请尽情指出。
K-Dtree就是在k个维度这样一个空间上的一个划分,每个节点可以视为代表了一个矩形区域(在二维平面上来说)。它是一棵二叉树,而且类似于BST。毕竟如果k=1的时候,就相当于在数轴的一个划分,就是一棵BST了。
一般应用在二维平面上,比如这道题目就是在二维平面上找到一个点的最近点。
但是在二维或者更高维度上构建k-dtree的时候有一个问题,就是BST需要有一个比较,但是k个维度该怎么比较呢?有很多种方法,最简单的一种就是按照这k个维度的顺序进行轮流划分,比如对于二维平面,我们先按照x来划分这一层,找到一个根节点满足,他左儿子所代表的的矩形区域中的点都小于他的x坐标,右儿子所代表的矩形区域中的点都大于他的x坐标。这样的话每一次划分,都可以水平或者竖直的方向上把一个区域分成不相交的两部分,这样递归下去直到无法构建为止。
这样我们就知道了建树的方法,而节点信息我们主要维护的就是这个节点的x和y坐标,以及以他为根所代表的的这个矩形区域内,在x和y坐标的意义下的最大值和最小值。也就是说他所代表的那个矩形的边界信息。
当然我们可能需要维护一个Size域,因为我们可能需要动态的插入一些节点到k-dtree中,插入方式类比BST。但是这样有一个后果就是会导致k-dtree不再平衡。有一个简单的方法,就是替罪羊重构一下,来保证整棵树的平衡。
询问最近点的方式:维护一个全局变量ans,并初始为无穷大。我们先用当前根节点的信息来更新一下答案。然后拿(x,y)和根节点的左右儿子所代表的的矩形区域的边界进行比较,然后按照顺序,如果可以更优的话就更新递归下去,否则就退出。其实就是个暴力的剪枝。。。。
这样的复杂度在随机数据下是log的,但是如果构造的话是O(n)的。因为你本质上还是暴力嘛?什么数据?给你一个圆查圆心。。。。
网上很多人说是sqrt(n)其实是不对,k-dtree对于不同的询问信息复杂度不同,sqrt(n)貌似是剖矩形。。。
其实看看代码的话更好理解,了解了以上内容,那这两个题目就是裸题了。双倍经验撒花~~~