BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆,如果合并他对先手有利,那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利,那肯定这堆石子最后会被合并。

并且在取完之前,合并这个动作无论在何时发生,都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了,然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种:

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并,成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

#洛谷 P1860 新魔法药水

神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD

#洛谷3917 异或序列

对于100% 的数据,1≤n≤105

做法是求异或前缀和然后按位讨论贡献

如果当前位k有奇数个1那么贡献为(numof1×numof0)×(1<<k)

 

USACO 玉米田迷宫 Corn Maze

这题是一个大坑。

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

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

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

 

这不清真

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

 

 

这也不清真

 

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

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

传送门I hate you

 

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

 

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

 

 

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

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

 

[USACO07OCT] 障碍路线Obstacle Course

这道题可以用一个特殊的BFS来求解。每次把队首元素四个方向上的点扩展到队尾,用桶来记录转弯次数。

1.初始状态

A(起点)的转弯次数为-1。

2.产生结点的规则

现在,起点位于队首。

从队首的点向四周逐“层”扩展,每一“层”扩展到的新点入队列,这些新点显然不需要转弯就可以达到(起点任意方向),所以他们的转弯次数记录为0 (也就是起点+1,你的疑问马上就会得到解答)

这就是产生新结点的策略。

3.记录每个点的转弯次数

扩展到的新点的转弯次数=队首点的转弯次数+1。(由于BFS的特点,新点未被访问过才可以被加入队尾)

下面是证明。

如果扩展到的新点是不转90°(直走)就可以到的,那该点一定被扩展了队首点的点(队首点的父结点,不知道这么说对不对)访问过,此时该点不会被当作新点处理。同理,转弯180°的点也一定被扩展了队首点的点访问过。

所以,扩展到的新点一定是转弯90°(左或右)才能走到的。

此时,到新点的转弯次数=队首点的转弯次数+1。

证明完毕。