USACO 草鉴定Grass Cownoisseur

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ’s paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.

INPUT: (file grass.in)

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.

OUTPUT: (file grass.out)

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

四句话题解(非常简单):

Tarjan瞎缩一波点

然后单原SPFA求点1能到的点的答案贡献

然后跑单汇SPFA求能到点1的点的答案贡献

最后枚举反边判相连求答案

 

USACO 2007MAR Face The Right Way

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6005 Accepted: 2777

Description

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K  N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

Input

Line 1: A single integer: N 
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

Output

Line 1: Two space-separated integers: K and M

Sample Input

Sample Output

Hint

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)
呐 题意就这样
然后我们考虑枚举k做一个O(n^3)显然很简单
优化?尺取法
枚举k,从左到右对背面的牛操作
考虑能够影响当前牛的操作,是当前减去(k-1)的区间
然后统计一下这个区间有多少个操作对2取模就可以得到当前判断。
这样用一个类似前缀和的东西维护就行了 见代码
O(n^2)

USACO 3.4 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲,发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐,一首歌不能分装在两张CD中。CD数量可以用完,也可以不用完

不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择:

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注:第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

一开始我看见这道题打了一道背包……

结果很惨的GG了……

我们设f[n][m][k]表示前n首歌按顺序尽量向m张盘里装,然后附加k分钟所能装的最多歌曲数

那么,显然k<=T,因为……如果k>T那f[i][j][k]等价于f[i][j+1][k-T],所以k>T是没有意义的

我们来考虑第n首歌装到第m+1张盘里的决策,也就是转移f[n][m][k] (因为m张盘外加k分钟,如果用那k分钟,也就是向m+1张里面装)

先初始化一下,也就是尝试放弃第i首歌

如果第j+1张盘的前k分钟能装的下,

那就不装,或者用前j张和j+1张的前k-a[i]分钟装前i-1首,第j+1张的最后a[i]分钟(歌曲的长度)装第i首

这两个里面取max

如果第j+1张盘的前k分钟装不下,

那么,假如说存在第j张盘(可以有j=0而k>0,也就是装第一张),那么就不装,或者用前j-1张盘外加第j张盘的T-a[i]分钟装前i-1首,用第j张盘装第i首试一下 (那么,就相当于尽量把第i首歌往j整张盘里装,如果a[i]小于T,那一定能装上,而如果T<a[i]了,那这首歌显然只能放弃)。

我们为什么要有第二个方程?原因在于k不一定大于a[i],而如果这首歌对决策有影响,那么T一定大于a[i],所以有必要试着装一下。

那么整个方程……

然后这是代码……

USACO 低价购买 Buy Low

这貌似是一道求最长下降序列的线性DP。

首先最长下降序列的状态转移方程是最简单的了QAQ

 

 

当然了f[i]默认值是1;

或者可以这样

 

接下来是统计方案 如果不计重的话貌似很好办,但要是计重的话,就应该倒推,如果前面的元素k和目前的元素i相等,那么f[k]==f[i],{这是因为统计了最长下降序列(如果是不上升序列的话还要稍微改动一下i对答案的贡献)}

所以k对答案的贡献应是和i相等的,这时可以把i对答案的贡献去掉了,因为以i结尾的组合把i换为k都成立这是由于由k结尾的最长下降序列的方案数只取决于k前面的几个元素(不同元素的组合)而与k无关

 

从而得出整个状态转移方程:

注意这里n初始化为1,组合数必定大于等于1

所以,完成了全部程序:

 

 

USACO 牛的旅行 Cow Tours

一道比较困难的Floyd题目。

首先路径肯定都会算,就不说了。其次,Floyd也没有什么问题。

我们的策略是枚举两个不联通的点,把他们联通,求出新牧区的最小直径。

关键细节看代码

(如果有哪位dalao知道为什么要 if (i!=k && j!=k && i!=j) 麻烦您在评论中回复我

 

 

 

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。

证明完毕。