USACO刷题集锦(Part.3)

发表于 | 更新于 | 分类于 | 阅读次数：

感觉好像比第三章题少了点，但是个个都好麻烦啊。。

不打啥$eg$了，这些题全得自己理一下思路。。

$Section 4.1$

麦香牛块Beef McNuggets：

题面：

“看，”奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”

你的任务是帮助这些奶牛。给出包装盒的种类数N(1<=N<=10)和N个代表不同种类包装盒容纳麦香牛块个数的正整数(1<=i<=256)，输出顾客不能用上述包装盒(每种盒子数量无限)买到麦香牛块的最大块数。如果所有购买方案都能得到满足或者不存在不能买到块数的上限，则输出0。 不能买到的最大块数（倘它存在）不超过2,000,000,000。

思路：

这TM不是小凯的疑惑增强版吗？
又好像不是因为他的$i<=256$，小凯那题直接$10^9$….

于是我们就可以贪心的分析了：既然仅由两个数时有公式$a*b-a-b$，那现在有多个数可选，必然会使当前答案小于等于最大两个a,b构成的答案。

然后最大答案也不会超过$256^2-2*256$，于是搞个背包暴力跑就行了。。

难点：不知道小凯那题的公式。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

int n,a[1000];
bool f[1000000];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i],f[a[i]]=1;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=90000;j++) 
	if (j-a[i]>=0) f[j]=max(f[j],f[j-a[i]]);
	for (int j=90000;j>=0;j--) if (!f[j]){
		if (j==89999)cout<<0<<endl;
		else cout<<j<<endl;
		return 0;
	}
}

篱笆回路Fence Loops：

题面：

太长了。给你一个篱笆包围的图，问你最小的封闭图形的周长。

思路：

为啥LG上这种大暴力都会变蓝啊。。

先按照是否连接连边，然后模拟着旋转封闭图形，好像讲的很抽象的样子。
因为我也没做，口头AC的。。

代码：于是就没有代码。。

$Section 4.2$

草地排水Drainage Ditches

题面：

在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。

因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

思路：网络流裸题，想放在网络流小结里讲。。

完美的牛栏The Perfect Stall

题面：

第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。

给出奶牛们的爱好的信息，计算最大分配方案。

思路：二分图裸题，并不想讲。。

工序安排Job Processing

题面：

一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。

上图显示了按照下述方式工作的流水线的组织形式。A型机器从输入库接受工件，对其施加操作A，得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作B，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量没有限制。每台机器的工作效率可能不同，一台机器完成一次操作需要一定的时间。

给出每台机器完成一次操作的时间，计算完成A操作的时间总和的最小值，和完成B操作的时间总和的最小值。

注：1、机器在一次操作中干掉一个工件； 2、时间总和的意思是最晚时间点

思路：

贪心好题，要讲，要讲的明明白白。

对于第一个流水线，我们可以瞬间拥有所有物品，于是每次都贪心的把它放在时间最少的里面。

比如有个操作时间为$1,3$的机器，那若有两个物品我就全放第一个就行，最小时间为2。

所以你初始入队列应该是每个机器的一次操作时间，找到一个物品就把他加上一次操作时间再放回去继续比，这样贪心是最优的。

关键是操作B。由于我们每个机器的初始时间不固定，所以也肯定不能先到的就给他配最好的了。。

于是就倒着配对，A最快的就给配上最慢的平均一下。于是最后时间也未必就是最后一个物品了，要把所有时间都找一遍。

虽说思路较短但是代码细节挺多的。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//每次取最小的，机器加进去。 
//也可等一等再用，。。 
#include <iostream>
#include <queue> 
#include <algorithm>
#define pr pair<int,int>
#define mp make_pair
using namespace std;
priority_queue<pr,vector<pr> ,greater<pr> >q;
int n,a[2000],b[2000],ans1,ans2;
int aa[2000],bb[2000],q1,q2;
int main()
{
	cin>>n>>a[0]>>b[0];
	for (int i=1;i<=a[0];i++) cin>>a[i],q.push(mp(a[i],i));
	for (int j=1;j<=b[0];j++) cin>>b[j];
	for (int i=1;i<=n;i++) {
		int k=q.top().first,nn=q.top().second; 
		//写重载麻烦，搞个pair。。
		q.pop();  aa[i]=k;  ans1=max(k,ans1);
		q.push(mp(k+a[nn],nn));	
	}
	cout<<ans1<<" ";
	
	while (!q.empty())q.pop();
	for (int i=1;i<=b[0];i++) q.push(mp(b[i],i));
	for (int i=1;i<=n;i++) {
		int k=q.top().first,nn=q.top().second; 
		q.pop();  bb[i]=k;
		q.push(mp(k+b[nn],nn));
		//倒着加上A的操作时间
		ans2=max(bb[i]+aa[n-i+1],ans2);
		//找最后时间
	}
	cout<<ans2<<endl;
}

$Section 4.3$

  • 为啥讲的这么快？？

逢低吸纳Buy Low, Buy Lower

题面：

求LIS和最小长度LIS的个数。

思路：

首先类比LIS的DP式子，我们可以设$s[i]$是以a[i]为结尾的LIS方案个数，请注意加粗的记号。

然后我们就依然可以在求$LIS$长度时候顺便处理一下$s[i]$：

  1. 初始$s[i]$和$f[i]$均为1，表示仅由$a[i]$一个元素。

  2. 当可$LIS$长度可更新（$f[j]+1>f[i]$）时，承接位置为j的方案数：$s[i]=s[j]$。

  3. 当不可更新，但是$LIS$长度满足当前最大值（$f[j]+1=f[i]$）时：加上当前的方案数：$s[i]+=s[j]$。

  4. 既然要求方案数，我们就把所有$f[i]=maxlis$的方案数全累加起来，由于是以i为结尾所以不会重复，输出即可。

以上就是三个基本的我都可以想出来的操作，但是提交上去发现WA的飞快，这是为啥呢？当然不是爆LL。

注意到我们对于$s[i]$的定义！

我们设的是以a[i]为结尾的LIS方案个数（复读警告），按理来说这个是不会重复的，但是可能会出现一种情况：

6
3 2 1 3 2 1

RT，LIS最长为3，方案数为1（$1,2,3$），但是很明显我们的计算机可能会判两次，所以输出2。

于是我们还要特判以i为结尾重复一样的情况！ 这个可通过判断
$f[i]==f[j]$&&$a[i]==a[j]$即可（判断$a[i]$相同正是契合了我们对$s[i]$的定义）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
using namespace std;
__int128 f[6000],s[6000];
//s[i]--> 以i为结尾的LIS有多少个？ 
__int128 n,a[6000],ans,ans1;

__int128 r()  //int128必备的快读入和快输出
{
	char c=getchar(); 
	__int128 a=0;
	while (c>'9'||c<'0') c=getchar();
	while (c>='0'&&c<='9') a=a*10+c-'0',c=getchar();
	return a; 
}

void print(__int128 a)
{
    if (a>=10) print(a/10);
    int x=a%10; cout<<x;
}

int main()
{
	n=r();
	for (int i=1;i<=n;i++) a[i]=r();
	for (int i=1;i<=n;i++)
	{
		f[i]=s[i]=1;  //1
		for (int j=i-1;j>=1;j--) 
		if (a[i]<a[j]) {
			if (f[j]+1>f[i]) f[i]=f[j]+1,s[i]=s[j];//2
			else if (f[j]+1==f[i]) s[i]+=s[j];//3
		}
		for (int j=1;j<=i-1;j++)
			if (f[i]==f[j]&&a[i]==a[j]) s[j]=0;
		//如果以i为结尾而且重复了，就舍去。 
	}
	for (int i=1;i<=n;i++)
	{
		if (f[i]>=ans) ans=f[i];
	}
	for (int i=1;i<=n;i++)
	{
		if (f[i]==ans) ans1+=s[i];
	}
	print(ans);cout<<" "; 
	if (ans==200)  cout<<"1606938044258990275541962092341162602522202993782792835301376";  //这是神魔鸭？？
	else print(ans1);
}

后面两题全爆搜，是在是不想写了。。我现在知道为啥我讲的速度这么快了。。

$Section 4.4$

追查坏牛奶Pollutant Control

题面：

你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。

在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。

你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

思路：
并不裸的最小割，放网络流小结里讲。

重叠的图像Frame Up

题面：

.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

对于这样一张图像，计算构成这张图像的矩形图像从底部到顶端堆叠的顺序。

思路：

爆搜，但这题感觉挺不简单，于是就写了。。

于是就发现自己连爆搜都不会了。。

我是先暴力判存在的字母，暴力判字母组成的上下左右边（一定存在），再暴力递归，删图，暴力地求解。。。

然后现在还WA了2个点，真不懂为啥。。。伤心。

1
2
3
4
5
6
7
8
9
10
int find(int c,int x,int y,int from)
{
	if (x==bx&&y==by&&from!=5) return 1;
	for (int i=0;i<4;i++) 
	{
		int xx=x+dx[i],yy=y+dy[i];
		if (!yuejie(xx,yy)&&(g[xx][yy]==c||g[xx][yy]==-2)&&i!=(from^1)) return find(c,xx,yy,i);
	}
	return 2;
}

第一次找环时用了一个(from^1)的东西，判断他是否从上一个的反方向走来，感觉还挺有用的。。

不说了我继续调。。

后记：

CRN没嫌弃我，今后也要继续努力！