BZOJ2028 | SHOI2009 Booking 会场预约

题目描述

PP大厦有一间空的礼堂,可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间(个别的可能只需要一天),不过场地只有一个,所以不同的会议的时间申请不能够冲突。也就是说,前一个会议的结束日期必须在后一个会议的开始日期之前。所以,如果要接受一个新的场地预约申请,就必须拒绝掉与这个申请相冲突的预约。一般来说,如果PP大厦方面事先已经接受了一个会场预约,例如从10日到15日,就不会在接受与之相冲突的预约,例如从12日到17日。不过,有时出于经济利益,PP大厦方面有时会为了接受一个新的会场预约,而拒绝掉一个甚至几个之前预订的预约。于是,礼堂管理员QQ的笔记本上笔记本上经常记录着这样的信息: 本题中为方便起见,所有的日期都用一个整数表示。例如,如果一个为期10天的会议从“90日”开始到“99日”,那么下一个会议最早只能在“100日”开始。最近,这个业务的工作量与日俱增,礼堂的管理员QQ希望参加SHTSC的你替他设计一套计算机系统,方便他的工作。这个系统应当能执行下面两个操作: A操作:有一个新的预约是从“start日”到“end日”,并且拒绝掉所有与它相冲突的预约。执行这个操作的时候,你的系统应当返回为了这个新预约而拒绝掉的预约个数,以方便QQ与自己的记录相校对。 B操作:请你的系统返回当前的仍然有效的预约的总数。


输入格式

输入文件的第一行是一个整数n,表示你的系统将接受的操作总数。接下去n行每行表示一个操作。每一行的格式为下面两者之一: “A start end”表示一个A操作; “B”表示一个B操作。


输出格式

输出文件有n行,每行一次对应一个输入。表示你的系统对于该操作的返回值。

二分+树状数组/线段树

还是用树状数组吧。

我们考虑所有接受的预约的开始时间都是严格递增的,那么我们建立Fenwick Tree,add(i,1)表示开始时间为i的预约存在,加入fwt

然后考虑拒绝的情况

二分查找所有开始时间小于等于当前预约结束时间的预约(只有这样才有可能被拒绝)

然后找到:开始时间与当前预约的结束时间最接近的一个预约。检查它的结束时间是否大于等于当前预约的开始时间建议画区间图

考虑未加入当前预约之前所有预约的开始、结束时间都是满足严格递增关系的,如果找到的最接近结束时间的都不与当前预约冲突,那在它之前的所有预约其结束时间严格递减,更不可能被拒绝。

所以直接break

而考虑右边(时间轴),如果能找到开始时间在当前预约的结束时间左边的预约,那就不可能跑到当前预约的右面。整体在当前预约右面的也一定不会被二分找到。

所以这样考虑到了所有情况

然后就统计一下输出就行了。

注意拒绝的时候还要add(position,-1),还有就是一开始就要查一下在当前预约的结束时间左边一共有多少预约。用这个二分。

BZOJ1880 | SDOI2009 Elaxia的路线

Description

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

Input

第一行:两个整数N和M(含义如题目描述)。 第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤ ≤ N),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别 x1,y1和x2,y2)。 接下来M行:每行三个整数,u、v、l(1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000),表 u和v之间有一条路,经过这条路所需要的时间为l。 出出出格格格式式式::: 一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)。

Output

一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

如果你没有意识到两个人即使对头走也算的话(既一个从x1到y1,一个从y2到x2)那你可以和我一样吐槽出题人的语文功底了。

(如果不反过来做的话建了两条边,就出环了)

先跑四次最短路

然后我们枚举所有满足条件的边Ei,j,使

dis[x1][i]+dis[j][y1]+Ei,j等于dis[x1][y1]且dis[x2][i]+dis[j][y2]+Ei,j等于dis[x2][y2]

翻译成人话也就是枚举一条公共边,使这条公共边在x1到y1的最短路上且在x2到y2的最短路上。

然后建一个新图,把这条边换成有向边加到图上去。

最后就是拓扑排序跑最长路。

注意还要反过来再做一遍(dis[x1][i]+dis[j][x2]+Ei,j = dis[y2][i]+dis[j][x2]+Ei,j)

POJ 2985 The k-th Largest Group

题目大意是这样的      查看原题

某人养了很多猫,从1-n编号,他想给她们(??!)分成几组,给出m个操作,其中可以

1)给出第i群猫和第j群猫,把她们合并。(注意猫i代表了第i群猫,而如果,猫k也在这群猫里,那猫k也能代表这群猫)

2)在线询问某次操作之后第k大的猫群有多大

考虑1)显然是一个并查集。

2)可以按照猫群大小建Fenwick Tree然后查找区间第k大数就可以了。

特别推荐这篇博文(虽然弱弱的我看了好久才看懂)

Press Here

然后是Code

 

#洛谷 P1120 小木棍

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。

现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

先写一个暴力……

暴力最好写了,然后再考虑剪枝

这是暴力:记录一下当前那根大木棍已经接了多长,已经接了多少根大木棍和一根大木棍应该有多长。

当然暴力也可以加一个简单的剪枝:记录一下总长度,如果当前枚举的一根大木棍的应有长度不能整除总长度那就不搜。

然后剪枝:

1.我们按长度排序,如果当前正在拼一根新的木棍,而且最大的一根小木棍加上当前的长度(应该是0)都不能满足枚举到的当前大木棍长度那就剪掉。

2.还是上述操作,不过是剪掉:整整一根小木棍都比当前枚举到的大木棍的长度长的情况(那样显然无解)

3.还是排序之后,记录一下上次尝试了哪一根小木棍(也就是长度)如果这次枚举到的小木棍的长度和上次相等那么也剪掉。

4.如果搜的目标是拼最后一根大木棍了,而且最后还无解,回溯回来了,那这组直接放弃。

就这些?

对,一共就这么六个剪枝 (排序&暴力的剪枝&1234)

试试刚刚才意识到的高亮操作

NOIp2017集训总结 (3)

最近进步挺大的,Edu Round Rank600多(从第30min开始做的……要不就A掉E题了)

校内Day3凭借运气成分和暴力拿到Rank1 (其实是zzy大爷没发挥好)

但是还是有很多的不足

第一点当然是学会写出所有的暴力分。

NOIp其实就是考谁更会暴力。所以暴力的分数一点也不能丢。

现在只要正解思路稍微卡住了,就先写暴力

写的时候对数据怎么处理也会有一个更清晰的过程

然后也许还能往正解的方向上走的更远。

有一点想吐槽的是,校内Day3第三题是一道二分+线段树(虽然校队没人AK此题),但是暴力sort却有60分。

这会让写出std的人很伤心的。

花了很长时间码出来的接近200行的线段树+二分居然才高40分??

当然,如果有这种题,NOIp顶多给15分暴力(这么暴力的话)

离散化太弱了

应该开始学数学了。

调试能力有提高。

刷了一部分省选简单题之后,做题速度有提高。

但是还不够。

要求是暴力5min码完,无论是搜索的暴力还是枚举的暴力

搜索题限时,不写剪枝必须20min写对

最重要的一点是,思路不够灵活

思考题现在经常被卡进死胡同了

大概和加强难度也有关系。

此外还有一些脑残错误

1.线段树调不出来……

2.搜索的时候注意崩溃情况处理

3.注意位运算优先级

4.注意未赋值数据会不会被用到

5.区间前缀和注意加减号

6.删掉调试输出再交题

#洛谷P1967 货车运输

题目描述

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入输出格式

输入格式:

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路 

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 

输出格式:

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货

车不能到达目的地,输出-1。

先Kruskal跑一下最大生成树,就是把边权改成从大到小排序就行。

然后用倍增思想在有根树上记录一个minp[i][k]数组,表示这个点i上跳2k的高度,经过路径的最小边权:

显然它等于minp[i][k-1]和minp[l[i][k-1][k-1]中的最小值。也就是它向上跳2k-1高度的minp和从depth[i]-2k-1高度再往上跳2k-1高度的minp(参照倍增的思想)

而向上跳2k-1高度能够达到点l[i][k-1],这个就属于LCA的基本操作了吧……

注意初始化。

还要维护一下点的联通行……用Kruskal留下来的UFS就行。

BZOJ1924 | SDOI2010 所驼门王的宝藏

在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种:

  1. “横天门”:由该门可以传送到同行的任一宫室;
  2. “纵寰门”:由该门可以传送到同列的任一宫室;
  3. “自由门”:由该门可以传送到以该门所在宫室为中心周围8格中任一宫室(如果目标宫室存在的话)。

深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册,书册上详细记录了每扇传送门所属宫室及类型。而且,虽然宫殿内外相隔,但他自行准备了一种便携式传送门,可将自己传送到殿内任意一间宫室开始寻宝,并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次,且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制,每间宫室也可以多次出入。

现在Henry已经打开了便携门,即将选择一间宫室进入。为得到尽多宝藏,他希望安排一条路线,使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。

 

[无耻地借用洛谷的图片]

首先缩一下点……

然后跑DP……

很简单QAQ

在BZOJ写了7000B,成功拿到『最近几页的最长代码』成就

在洛谷跑了400ms,超级快。//好像空间还用的很少

#洛谷P1312 Mayan游戏

大模拟+搜索

写了一个下午 这么弱也是没谁了。

题目描述

Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个 7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:

1 、每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图6 到图7 );如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图1 和图2);

2 、任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参见图1 到图3)。

注意:

a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图4 ,三个颜色为1 的方块和三个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块)。

b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除(例如下面图5 所示的情形,5 个方块会同时被消除)。

3 、方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。

上面图1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0, 0 ),将位于(3, 3 )的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态,此时在一竖列上有连续三块颜色为4 的方块,满足消除条件,消除连续3 块颜色为4 的方块后,上方的颜色为3 的方块掉落,形成图 3 所示的局面。

说明

【输入输出样例说明】

按箭头方向的顺序分别为图6 到图11

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是:(2 ,1 )处的方格向右移动,(3,1 )处的方格向右移动,(3 ,0)处的方格向右移动,最后可以将棋盘上所有方块消除。

【数据范围】

对于30% 的数据,初始棋盘上的方块都在棋盘的最下面一行;

对于100%的数据,0 < n≤5 。

注意剪枝:

1.向左面换的话只有左面是空才换(要不然等价于左面那块向右,而且解不比那样优)

2.剩下不足三个剪掉

3.走了n+1步没搞完剪掉

4.同样色块没必要换

注意处理消除:

1.超过三个都能消掉

2.注意共用一块,最好解决方案是复制下来判断

3.注意消完之后要处理下落,还有可能能继续消,开一个flag判断。

BZOJ1922 | SDOI2010 大陆争霸

Description

在一个遥远的世界里有两个国家:位于大陆西端的杰森国和位于大陆东端的 克里斯国。两个国家的人民分别信仰两个对立的神:杰森国信仰象征黑暗和毁灭 的神曾·布拉泽,而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。 幻想历 8012年 1月,杰森国正式宣布曾·布拉泽是他们唯一信仰的神,同 时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。 幻想历 8012年 3月2日,位于杰森国东部小镇神谕镇的克里斯国教徒发动 起义。 幻想历 8012年 3月7日,神谕镇的起义被杰森国大军以残酷手段镇压。 幻想历 8012年 3月8日,克里斯国对杰森国宣战。由数十万大军组成的克 里斯军团开至两国边境,与杰森军团对峙。 幻想历 8012年 4月,克里斯军团攻破杰森军团防线进入神谕镇,该镇幸存 的克里斯国教徒得到解放。 战争随后进入胶着状态,旷日持久。战况惨烈,一时间枪林弹雨,硝烟弥漫, 民不聊生。 幻想历 8012年 5月12日深夜,斯普林·布拉泽降下神谕:“Trust me, earn eternal life.”克里斯军团士气大增。作为克里斯军团的主帅,你决定利用这一机 会发动奇袭,一举击败杰森国。具体地说,杰森国有 N 个城市,由 M条单向道 路连接。神谕镇是城市 1而杰森国的首都是城市 N。你只需摧毁位于杰森国首都 的曾·布拉泽大神殿,杰森国的信仰,军队还有一切就都会土崩瓦解,灰飞烟灭。 为了尽量减小己方的消耗,你决定使用自爆机器人完成这一任务。唯一的困 难是,杰森国的一部分城市有结界保护,不破坏掉结界就无法进入城市。而每个 城市的结界都是由分布在其他城市中的一些结界发生器维持的,如果想进入某个 城市,你就必须破坏掉维持这个城市结界的所有结界发生器。 现在你有无限多的自爆机器人,一旦进入了某个城市,自爆机器人可以瞬间 引爆,破坏一个目标(结界发生器,或是杰森国大神殿),当然机器人本身也会 一起被破坏。你需要知道:摧毁杰森国所需的最短时间。

Input

第一行两个正整数 N, M。 接下来 M行,每行三个正整数 ui, vi, wi,表示有一条从城市ui到城市 vi的单 向道路,自爆机器人通过这条道路需要 wi的时间。 之后 N 行,每行描述一个城市。首先是一个正整数 li,维持这个城市结界所 使用的结界发生器数目。之后li个1~N 之间的城市编号,表示每个结界发生器的 位置。如果 Li = 0,则说明该城市没有结界保护,保证L1 = 0 。

Output

仅包含一个正整数 ,击败杰森国所需的最短时间。

这种访问次序恰巧符合Dijkstra的特点,因为每个点只会走一次。

记录一下点权,先访问点权为0的点,再检查结界生成器可以使哪些点的点权减小

顺便当某个点的点权减小为0的时候讨论机器人到了城市但是有结界,需要等候的情况。

最后直接一波Dijkstra最短路就好了【然而写了很久……虚啊

#洛谷P2258 子矩阵

不看题解写不出来系列……

第一篇状压DP。

题目描述

给出如下定义:

  1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。

例如,下面左图中选取第2、4行和第2、4、5列交叉位置的元素得到一个2*3的子矩阵如右图所示。

9 3 3 3 9

9 4 8 7 4

1 7 4 6 6

6 8 5 6 9

7 4 5 6 1

的其中一个2*3的子矩阵是

4 7 4

8 6 9

  1. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
  2. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

本题任务:给定一个n行m列的正整数矩阵,请你从这个矩阵中选出一个r行c列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

PJ比TG难系列。

dfs一下选哪些行,处理一下前缀和,然后按照列DP一下就行了。