BZOJ – Tgotp-Blog

1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店

背包问题f[i]表示花费了i元所能凑出来的方案数。注意高精度…

c++代码如下:

 

1645: [Usaco2007 Open]City Horizon 城市地平线

没注意到是左闭右开区间…卡了半天。
考虑用线段树可以很好的维护区间信息,那么考虑使用线段树。
对于区间max很明显可以随便维护。
重点在于数据范围1e9,考虑离散化,
若令tru[i]表示把一个数离散成i这个数与他上一个数的差值,
那么只用在统计答案的时候再乘以这个值即可。
但是略微[……]

Read more

1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典

令f[i]表示前i个字符中最多匹配多长,那么对于每个位置暴力匹配即可。

树状数组维护一下前i个当中最大的f[j]

c++代码如下:

 

1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

考虑令f[i]表示至少把前i个点打扫了所需要的最小花费,

那么对于第i个奶牛打扫的即为f[a[i].e] = min(f[a[i].s-1]+a[i].w);

考虑更新了f[a[i].e]实际上也对于前a[i].e个点均有影响,所以还需对f[j]取min j < a[i].e[……]

Read more

1697: [Usaco2007 Feb]Cow Sorting牛排序

容易发现,对于所有数,构成了很多个置换,选择每一个循环内最小的数开始操作就会得到当前循环到a[i] == i的最小花费,但是还有一种情况是取全局最小与加入当前排列参入循环,比较一下即可。。。

我沙茶的用了离散化,比较好理解一点吧。。

c++代码如下:
[crayon-5a6336dbe[……]

Read more

1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

首先化成max(|(a.x+a.y – (b.x + b.y)|,|a.x-a.y – (b.x-b.y)|);

然后对于x维护一个滑动窗口,对于y用set维护即可

c++代码如下:

 

1691: [Usaco2007 Dec]挑剔的美食家

将每次满足条件价格最小的w放入对应的。

用set维护即可

c++代码如下:

 

1670: [Usaco2006 Oct]Building the Moat护城河的挖掘

裸的凸包,直接造一个凸包,然后算一下长度就好了

c++代码如下:

 

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

随便跑跑floyd,然后按顺序相加即可。

c++代码如下:

 

1629: [Usaco2007 Demo]Cow Acrobats

已知:对于 两个相邻的牛,他们交换只会改变他们两个的相互关系,不会影响其余的条件。

那么只用比较a.w – b.s 与b.w – a.s即可。

c++代码如下: