洛谷 P1660 数位平方和

最大的 xS(999999) \,\, (K=6) ,这个数字是 3188646 。其余待求函数值的 x 都小于这个数字。

所以最多是 4 \times 10^6 个元素求函数值然后再求个和,直接暴力。

试一下样例发现会出环,环上答案为环上最小值。

做完了。

 

BZOJ1085 | SCOI2005 骑士精神

这题很经典也很简单就不放思路了QAQ

留个代码防我健忘

 

JLOI2009 二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为:

深度:4 宽度:4(同一层最多结点个数)

结点间距离: ⑧→⑥为8 (3×2+2=8)

⑥→⑦为3 (1×2+1=3)

注:结点间距离的定义:由结点向根方向(上行方向)时的边数×2,

与由根向叶结点方向(下行方向)时的边数之和。

 

输入输出格式

输入格式:

输入文件第一行为一个整数n(1≤n≤100),表示二叉树结点个数。接下来的n-1行,表示从结点x到结点y(约定根结点为1),最后一行两个整数u、v,表示求从结点u到结点v的距离。

输出格式:

三个数,每个数占一行,依次表示给定二叉树的深度、宽度及结点u到结点v间距离。

无耻的借用洛谷的图片

这题就是个智障

首先dfs一下然后bfs一下然后lca一波就行了

一开始忘记讨论深度了然后使劲在那WA。。

//我知道不用写LCA和BFS但我就是想写你打我啊!!!!

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),还有就是一开始就要查一下在当前预约的结束时间左边一共有多少预约。用这个二分。

#洛谷 P1120 小木棍

题目描述

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

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

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

先写一个暴力……

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

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

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

然后剪枝:

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

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

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

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

就这些?

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

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

#洛谷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判断。

Codeforces Round#124B Infinite Maze

题目描述

We’ve got a rectangular n × m-cell maze. Each cell is either passable, or is a wall (impassable). A little boy found the maze and cyclically tiled a plane with it so that the plane became an infinite maze. Now on this plane cell (x, y) is a wall if and only if cell  is a wall.

In this problem  is a remainder of dividing number a by number b.

The little boy stood at some cell on the plane and he wondered whether he can walk infinitely far away from his starting position. From cell (x, y) he can go to one of the following cells: (x, y - 1)(x, y + 1)(x - 1, y) and (x + 1, y), provided that the cell he goes to is not a wall.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1500) — the height and the width of the maze that the boy used to cyclically tile the plane.

Each of the next n lines contains m characters — the description of the labyrinth. Each character is either a “#“, that marks a wall, a “.“, that marks a passable cell, or an “S“, that marks the little boy’s starting point.

The starting point is a passable cell. It is guaranteed that character “S” occurs exactly once in the input.

Output

Print “Yes” (without the quotes), if the little boy can walk infinitely far from the starting point. Otherwise, print “No” (without the quotes).

什么玩意……还是看看翻译

幻象迷宫可以认为是无限大的,不过它由若干个N*M的矩阵重复组成。矩阵中有的地方是道路,用’.’表示;有的地方是墙,用’#’表示。LHX和WD所在的位置用’S’表示。也就是对于迷宫中的一个点(x,y),如果(x mod n,y mod m)是’.’或者’S’,那么这个地方是道路;如果(x mod n,y mod m)是’#’,那么这个地方是墙。The Little Boy可以向上下左右四个方向移动,当然不能移动到墙上。

请你告诉他能否走出幻象迷宫,如果他能走到距离起点无限远处,就认为能走出去。

也是好久之前做的题了,一开始被题意卡了好久,果然语文不好毁一生啊……

大概就是说给出一个01迷宫类的地图,按照这个地图来扩展新地图,类似这样

然后问你是不是可以走无限远。

那么,我们可以很清晰的意识到,如果可以从点(x,y)出发,达到比如(-x,y)或者(x,-y) , (-x,-y) , (x+m,y+n) [假设宽m高n]  , 就可以从这个点再次达到相同的点(即可以从(x,y)出发,达到(i,j)且|i|%n=x , |j|%m=y。),一直这么走下去。

那就搜好了。开一个三维vis数组第一维记录有无被访问,第二维记录被访问时横坐标,第三维纵坐标。

判断重复到达且横纵坐标不同即可。应该注意先判什么后判什么。如果是同一个分矩阵走过去的话自然tx==vis[x][y][0]此处x为|tx|%n,y为|ty|%m,即映射到中心矩阵的位置),就会被判掉。

而且注意tx!=vis[x][y][0]ty!=vis[x][y][1]满足一个即可。

没啥好说的了。。。数据很大注意搜索优化。

 

IOI1998 Starry Night 夜空繁星

BFS,超级麻烦

推荐A这道模拟方块转换

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图所示。(图片搬运自Luogu Online Judge)

 

 

懒癌了,我就贴上来吧……我用了一个特殊的表来判断是不是相似

详见代码

 

 

 

 

#洛谷 通往奥格瑞玛的道路

题面对我来说貌似有毒,看了很长时间才看懂这是一个最大值最小问题 果断二分答案。

主要思想是先跑一边Bellman-Ford+队列优化(也叫SPFA)把二分值设定成+∞ 然后看一看如果到终点的花费大于血量就输出AFK(away from keyboard)

如果可行就快排点权+二分下标 如果当前二分值可以跑到终点(跑SPFA判)就向左找(升序sort),不然就向右找。

跑SPFA的时候传一个upat也就是二分值 把点权大于二分值的点都判(删)掉 

 

还有一点就是最后还要判一下二分值。链式前向星+SPFA+手写Sort,没有注释……

 

 

 

USACO 玉米田迷宫 Corn Maze

这题是一个大坑。

首先我们想到了BFS,这个题就是一个简单到不能再简单的Maze加上传送门就是了。

但是有一点是传送门不费时啊!!什么鬼。所以我们要先判传送门

为什么呢?我记得有一组测试数据包括了这种情况

 

这不清真

另外,好像还有一个点是全都是传送门的情况。

 

 

这也不清真

 

判传送门(并不是判队首元素位于传送门,而是队首坐标移动之后),传送过去之后耗时不加,队列保存传送后的位置,这样就不会产生无限传送死循环的问题。

但是关于情况2怎么办?我们利用BFS的性质,把传送门(传过去之后)打上标记,然后就不用他了。(每一次用都是最早用他)

传送门I hate you

 

读入的时候记录传送门的相对坐标,像这样:

 

之后碰到传送门直接查表。,顺便记下起点sxsy和重点exey

 

 

其实这个题处理好了传送门,你会发现,其实不难……(输出调试大法好)

记得用checked数组标记已经访问的点和传送门,要不无限使用传送门