USACO刷题集锦(Part.1)

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

P.S：（不知道怎么总结这些玩意儿，我就整体评价一下然后挑几道经典/重点题说说看）

第一章

  • 都是些大水题，做着时候你总会以为有啥数学式子要你推，其实一个大暴力解决一切。
  • 比较有意义的题是P1214，还有一些进制转换题+回文题。

$eg_1:P1214$

题意：在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方 + q的平方的数的集合,其中p和q为非负整数)S中长度为n的等差数列。N(3<= N<=25)，M(1<= M<=250)

思路：说着比较有意义其实本质还是暴力。M比较小先处理所有平方和的数再unique一下。然后枚举公差和首项，暴力枚举N项看符不符合就结束了。

难点：难想到是暴力，还以为数学。拍完序要unique判重，然后枚举的时候可以稍微剪一些枝。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[1000000],ans[1000000][2],p,maxx;
bool v[1000000];
int main()
{
    cin>>n>>m;
    for(int i=0;i<=m;i++)
    for (int j=0;j<=i;j++) a[++p]=i*i+j*j,v[i*i+j*j]=1,maxx=max(maxx,i*i+j*j);
    sort(a+1,a+p+1); unique(a+1,a+p+1);
    // for (int i=1;i<=p;i++) cout<<a[i]<<" ";
    p=0;
    for (int i=1;i<=maxx;i++) //search for d
        for (int j=1;a[j]<=maxx-i*(n-1);j++)  //search for a
        {
            int k=a[j],f=1; 
            for (int q=1;q<=n-1&&f;q++,k+=i) if (!v[k+i]) f=0;
            if (f)  ans[++p][0]=a[j],ans[p][1]=i;
        }
        if (p==0) cout<<"NONE"<<endl;
    for (int i=1;i<=p;i++) cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
}

第二章：

  • 写了一个礼拜才写完，一想到有的神犇1个月$AK~training$就细思极恐。。
  • 说是图论但是全TM是搜索，就2，3道题靠的是图论板子。。。
  • 说是数据结构全TM是模拟，估计就数组能和数据结构搭边。。
  • 动态规划倒是有点东西，接下来分栏慢慢讲。
  • $P1457,P1459,P1466,1472,1475,1519,1522$未必都是难题，但有些细节值得推敲。

一.图论：

$USACO$的图论以搜索为主，最短路为辅，主要考察建图能力。

$eg_1:P1457$

题面：城堡的平面图被划分成M*N(1 <=M,N<=50）个正方形的单位，一个这样的单位可以有0到4面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。移去箭头所指的那面墙，可以使2个房间合为一个新房间，且比移去其他墙所形成的房间都大。要求算出：

  1. 城堡的房间数目。
  2. 最大的房间的大小
  3. 移除一面墙能得到的最大的房间的大小
  4. 移除哪面墙可以得到面积最大的新房间。

思路：建好图用BFS进行洪水填充(就是走迷宫…)找出所有房间，再枚举每一面墙打掉，比较出两房间新的最大面积即可。。

难点： 建图极其恶心。。

因为墙是不占空间的，可用一个状态P表示上下左右的墙，并用简单位运算判断即可。

比如说可以这样来判断右边是否有墙：

1
2
3
4
bool rt(int x,int y)
{
	return (map[x][y]&4); 
}

$eg_2:P1519$

题面：有多个出口走迷宫，问最远那个点要花多久出去？

思路： 由于出口的不确定性，可以利用逆向思维，从出口处进行洪水填充，找到最远的点。

难点： 依然是建图。。因为墙是不占空间的，所以还是可以类似上一道题的建图来做。

其次还有逆向思维很重要，另一道板子题也是如此

当无向图中终点较少或可控且起点较多或不可控时，常常反向走图。若为有向图，反向建图即可。

但由于不可控因素超时了，貌似是爆栈，但是并不是很清楚；烂题一道，因为建图类似再拿出来讲讲。。

$eg_3:P1522$

题面：农民 John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。

John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。输出在所有牧场中最小的可能的直径。

思路： 难点是思路…
我们再冷静下来，分析我们要求什么 子问题：

  1. 最终目标是所有牧场可能的最小直径，那首先得枚举所有牧场；
  2. 如何区分不同牧场？染色即可，或用并查集维护（我是并查集）
  3. 枚举任意两个牧场，再枚举两牧场中任意边，求得他们的最远点的距离
  4. 如何求一个牧场内部的最远点距离？可以用$Floyd$进行预处理。
  5. 一个重要的事实：连接$i,j$后，整个牧场最远点距离=i到A牧场的最远距离+$dis(i,j)$+j到B牧场的最远距离
  6. 最后与所有牧场的最远距离进行比较，取最大值。
  7. $Over$！

难点：听完上面思路是不是很恶心。。但他就是本题难点。。

除此之外的小细节：

1.用并查集找牧场时候可以整个搜一遍，找爸爸仍是自己的，然后把所有儿子也加进去。

但是找儿子的时候得用getfather(i)==me来判断，不能用fa[i]=me，因为可能之前路径压缩的时候不彻底，导致有几个点没压到。。

2.两两牧场打擂台的时候，最后要把所有牧场的最长直径都搜一遍，包括自己！！

因为你加的边可能并不会使原来的直径变大，而且也不会变小。因为如果变短至少会有一次松弛操作，但是你只增加了一条边且另一点不会连通，所以也不会更新最小值。。

  1. 然后就是一些小技巧了，可以把判断语句打一个void调用，这样美观

代码（不用看，太丑）:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;

struct fie{
	int s,a[200];
	double d,g[200][200];
}fl[200];
int st,n,x[200],y[200],f[200];
double maxx=10000000000000000;
char c[200][200];


double dis(int i,int j)
{
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void csh(int x)
{
	for (int i=1;i<=n;i++) 
	for (int j=1;j<=n;j++) fl[x].g[i][j]=(i==j)?0:10000000000000000;
}

void print(int x)
{
	for (int i=1;i<=n;i++,cout<<endl)
	for (int j=1;j<=n;j++) if (fl[x].g[i][j]>10000) cout<<"I "; else cout<<fl[x].g[i][j]<<" ";
	cout<<endl;
}

double check(int x,int y)
{
	double d1=0,d2=0,di=10000000000000000;
	
//	print(x); print(y);
	
	for (int i=1;i<=fl[x].s;i++)
	for (int j=1;j<=fl[y].s;j++)
	{
		d1=0; d2=0;
		for (int k=1;k<=fl[x].s;k++) d1=max(d1,fl[x].g[fl[x].a[i]][fl[x].a[k]]);
		for (int k=1;k<=fl[y].s;k++) d2=max(d2,fl[y].g[fl[y].a[j]][fl[y].a[k]]);
		di=min(di,d1+d2+dis(fl[x].a[i],fl[y].a[j]));
	}
	for (int i=1;i<=st;i++) di=max(di,fl[i].d);
	return di;
}

//初始化 
void make(int x)
{
	/*过毒瘤已隐藏*/
}

//并查集 
int gf(int x)
{
	if (x==f[x]) return f[x];
	else return f[x]=gf(f[x]);
}

void merge(int x,int y)  //对两牧区合并 
{
	int fx=gf(x),fy=gf(y);
	if (fx==fy) return; else f[fy]=fx;
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) f[i]=i;  
	
	for (int i=1;i<=n;i++)cin>>x[i]>>y[i];
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++) {
		cin>>c[i][j]; if (c[i][j]=='1') merge(i,j);
	}	
	for (int i=1;i<=n;i++) if (gf(i)==i) make(i);
	
	
	for (int i=1;i<st;i++)  //两两牧场打擂台 
		for (int j=i+1;j<=st;j++) maxx=min(maxx,check(i,j));
	cout<<fixed<<setprecision(6)<<maxx<<endl;
}

二.DP

  • 没啥好讲，因为没啥好题，几个套背包DP模型的应用。
  • 本来可以放下面一起说，但是怕忘了就先讲了。。

$eg_1:P1466$

题面： 对于从1到N的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。给出N，你的程序应该输出划分方案总数。

思路： 因为两集合内数字和相同，那么奇数肯定先死掉，剩下的问题就可以等价为：在$[1,n]$内找任意个数，使其和等于$(n+1)n/4$，总和一半，求可能的方案数。

这玩意可以类比背包模型，将数的大小看作重量，价值为1，搞一个01背包做就行了。。

难点： 不同于普通背包，设$f[i]$是总和为i时的方案数，先上代码：

1
2
3
4
5
6
7

for (int i=1;i<=n;i++)
{
	for (int j=s-i;j>=1;j--) if (f[j]) 
		f[j+i]+=f[j]; //方案数直接加上即可
	f[i]++;
}

注意到最底下有f[i]++，因为总有一种方案成立，那就是选自己。。

$eg_2:P1475$

不知道为啥这题难了，好像之前想拿隐式图来搞但最后咕了，那就咕吧。

$eg_3:P1472$

题面：农民约翰准备购买一群新奶牛。 在这N个的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。有多少深度为K不同的家谱结构?

思路：

一开始想拿深度做，发现越到下面可能性越多，然后就自闭了。。

虽然正解是用深度，但是民间有一个更好的方法：因为深度难做，那我们用前缀和的思想，算出深度<=k的所有种类，最后$f[n][k]-f[n][k-1]$即可。

难点： 对于动态规划一点不懂的蒟蒻我来说简单版本都很麻烦。。

于是用记忆化搜索，设法同上，但发现一点优化的感觉也没有??

结果是因为f[i][j]可能出现搜过但答案是0的情况，判断的时候要加一个vis数组记录一下，活活卡了0.5h。。。

代码：

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

//f[i][j]-->剩i节点，深度<=j
#include <iostream>
#include <cstring>
#define mo 9901 
using namespace std;

int n,k,f[300][200];
bool v[300][200];
int dfs(int s,int h,int now)
{
	if (h<=0) return 0;	
	if (v[s][h]) return f[s][h]; 
	/* 剪枝 */
//	for (int i=1;i<=now;i++) cout<<" "; cout<<s<<" "<<h<<" "<<f[s][h]<<endl;
	v[s][h]=1;
	for (int i=1;i<s;i+=2) f[s][h]=(f[s][h]%mo+(dfs(i,h-1,now+1)%mo*dfs(s-i-1,h-1,now+1)%mo)%mo)%mo;
	return f[s][h]%mo; 
}

int main()
{
	cin>>n>>k;
	for (int i=1;i<=k;i++) v[1][i]=f[1][i]=1; 
	int now=dfs(n,k,0);
	dfs(n,k-1,0); cout<<(now-f[n][k-1]+mo)%mo<<endl;
}

三.其他

$eg_1:P1468$

参考lg题解吧，蓝的福祉了：就是这里！

$eg_2:P1459$

题面：
现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。

思路：

  1. 当时脑子里想的全是逆序对这些。。没试过能不能做
  2. 但是由于数量少，可以直接分成1,2,3所在位置的三类，分别讨论各自位置的出现情况。（在代码中理解）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int n,ans,a[2000],t[4],p[2000][4]; 
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i],t[a[i]]++; 
	for (int i=1;i<=t[1];i++) p[1][a[i]]++;
	for (int i=t[1]+1;i<=t[1]+t[2];i++) p[2][a[i]]++;
	for (int i=t[1]+t[2]+1;i<=n;i++) p[3][a[i]]++;
	int k1=min(p[1][2],p[2][1]);  //以下为三种简单错位情况
	int k2=min(p[2][3],p[3][2]);
	int k3=min(p[1][3],p[3][1]);
	
	ans=k1+k2+k3;

	ans+=(max(p[1][2],p[2][1])-k1)*2;  //可证明剩下为2,3,1完全乱序的次数肯定相同。
	cout<<ans<<endl;
}

MD第二章怎么就讲了那么多啊，接下来要不分个张杰吧。