USACO刷题集锦(Part.4)

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

仿佛活在题解的阴影里。。。

平均蓝题对于刚拿tg1=的我仍有些吃力，虽然题解一点就通但这没有刷题的任何效果。。

以后还是要克制一下自己的思考时间，不能那道题就翻题解，点TAG，你们这个功能害人不浅啊！

$Section 5.1$

[USACO5.1]圈奶牛Fencing the Cows

题面： 求凸包。

思路： 板子，没思路。几年前的代码忘了，近期并不想看。。

代码： 并不想放代码。

[USACO5.1]乐曲主题Musical Themes

题面：

我们用N(1 <= N <=5000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，每个数表示钢琴上的一个键。“主题”是整个音符序列的一个子串，它需要满足如下条件：

⒈长度至少为5个音符

⒉在乐曲中重复出现(可能经过转调，见下)

⒊重复出现的同一主题不能有公共部分。

“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。 给定一段乐曲，计算其中最长主题的长度(即音符数)。

思路：

提到加上或减去同一个值，肯定先差分转换成找最长公共子串问题。然而之前并没有接触过公共子串,LCS倒是写过题解。。

于是博客学了一下：

我们设$f[i][j]$为第一个序列到第i个，第二个序列到第j个字符的最长公共子串。

可以得到式子：

$$f[i][j]=f[i-1][j-1]+1~~(a[i]==a[j])$$

本来以为这样就OK了，结果WA了几个点为什么呢？

注意到题面中提到一句话： 重复出现的同一主题不能有公共部分。

但我们这个式子并没有对其处理，然后一些神犇就想出了这样的解决方案：我们将f[i][j]初值定为$j-i+1$即两元素距离，若超过此距离后面那串的子串肯定与前面的有交集了。

然后就没了。。代码巨短我依然不会，DP白痴一个。

代码：

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,a[10000],c[10000],f[6000][6000],ans;
//g[i][j]--> the list to i and to j,the max length
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) c[i]=a[i]-a[i-1];
	for (int i=1;i<n;i++)
	for (int j=i+1;j<=n;j++)
	if (c[i]==c[j]){
		f[i][j]=min(j-i-1,f[i-1][j-1]+1);;//这个值在怎么大也不能重复
		ans=max(ans,f[i][j]); 
	}
	if (ans>=4) cout<<ans+1<<endl;
	else cout<<0<<endl;
}

[USACO5.1]夜空繁星Starry Night

题面：

一个星座(cluster)是一群连通的星组成的非空连通星系。一个星座不能是另一个更大星座的一部分， 星座可以相似。如果两个星座有相同的形状，而且包括相同数目的星体，那么不管其方向性如何，就算相似。一般而言，星座可能的方向有八个。

夜空可以表示为一份天体图(sky map)，它是一个由字符0和1组成的二维矩阵，字符1表示所在的位置有一颗星；相似的星座必须用相同的字母标识，不同的星座表示为不同的字母。标识一个星座，就是将其中各星体对应的字符1替换为相应的小写字母，按字典序排序。

思路：

还是爆搜，只不过题面很有趣于是写了写，发现真不会。。

主要是这个旋转太烦了？想起第一章好像专门有一道题处理这个旋转，单单几个操作就60行了。。

于是题解里又有神仙了：当两个图形任意一点到各自其他点的距离和均相等，则两图形相同。还说这是啥小学奥数。。

然后就没了，找单独星座用了洪水填充，都是常规操作了。。

代码：太长了没有。

$Section 5.2$

[USACO5.2]蜗牛的旅行Snail Trails

题面：

萨丽总是垂直（向上或者向下）或水平（向左或者向右）地走。她可以从出发地（总是记作A1 ）向下或者向右走。一旦萨丽选定了一个方向，她就会一直走下去。如果她遇到棋盘边缘或者路障，她就停下来，并且转过90 度。她不可能离开棋盘，或者走进路障当中。并且，萨丽从不跨过她已经经过的格子。当她再也不能走的时候，她就停止散步。问最长路径。

思路：

对单独成章的题目产生恐慌。

这暴力思路这么清晰，脑子怎么老是犯怵？还是看题解看多了导致自己对代码中的细节没有掌握到位。。

直接想法就是每次撞墙时枚举四个方向深搜，直到碰到自己走过的路。走过的路可以开一个地图存，同时再开一个栈来存路径（方便你撤销步数）。

然后就是一些乱七八糟的小细节：

  1. 存图的时候后面数字会超过10，所以要读入一个字符一个整型。。
  2. 深搜的时候要判断当前是不是没有移动，直接continue防止死循。
  3. 一条路走死可能由于撞墙（或边界）或是走过的路，但往下深搜的时候只能是由于第一种情况。

代码：

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
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int v[200][200],g[200][200];
int ans,n,m;
stack<pair<int,int> > q;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
char c; int vv;
void out(int xx,int yy){
    int x=q.top().first,y=q.top().second;
    while (!q.empty()&&x!=xx||y!=yy)//坐标均不满足！！
    {
        q.pop();  v[x][y]=0;
        x=q.top().first,y=q.top().second;
    }
    //弹出 
}

bool yuejie(int x,int y)
{
    return (x<=n&&x>0&&y<=n&&y>0);
}

void dfs(int bx,int by,int sm,int dep)
{
    int now=sm; 
    for (int d=0;d<4;d++)  //four direction
    {	
        int x=bx+dx[d],y=by+dy[d]; 
   		while (!g[x][y]&&!v[x][y]&&yuejie(x,y)){
                q.push(make_pair(x,y)); v[x][y]=1; now++;
            	x=x+dx[d],y=y+dy[d];
        }
        x=x-dx[d],y=y-dy[d]; if (x==bx&&y==by)continue; //防死循 
		ans=max(ans,now); 
		if (!v[x+dx[d]][y+dy[d]]) dfs(x,y,now,dep+1);  //不因为走过而停止 
		now=sm;  out(bx,by); //还原 
		
    }
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>c>>vv;
        g[vv][c-'A'+1]=1;//"A11"意会 ,方向 
    }
    q.push(make_pair(1,1));  v[1][1]=1; dfs(1,1,1,1); 
    cout<<ans<<endl;
}

$Section 5.3$

三道题太恶心就没写，校园网这题 学tarjan时写了，所以就跳了。

$Section 5.4$

[USACO5.4]奶牛的电信Telecowmunication

题面： 求一个无向图的最小割。

思路： 。。放网络流小结里面讲吧

[USACO5.4]周游加拿大Canada Tour

题面：

旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次。

给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。

思路：

据说是IOI原题，很直接但由于是半个DP所以还是不会写。。
直接摘自写题时候的思路：

首先容易想得到把过去再回来的路径转换成两条不相交过去的路径

并不容易 设f[i][j]表示起点同时到i,j的最短路径。

容易 得f[i][j]=f[j][i] (3)

有点不容易 得答案应该是f[i][n],i与n连通，这样就可返回。

容易 想到既然(3)，那只要转移一维就可以了，f[i][j]=max{f[i][k]}+1，当g[j][k]=1

并不容易 如果有香蕉情况出现，则一定会重复经过某点，有f[i][i]答案不为0.

于是我们强制限制j>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

#include <iostream>
#include <map>
using namespace std;

int n,m,f[1000][1000];
int g[1000][1000],ans=1,num;
string s,s1,s2;

map<string,int> hash;
int main()
{

	cin>>n>>m;
	for (int i=1;i<=n;i++)
	 cin>>s,hash[s]=++num;
	for (int i=1;i<=m;i++)
	{
		cin>>s1>>s2;
		int k1=hash[s1],k2=hash[s2];
		g[k1][k2]=g[k2][k1]=1;
	}
	int ans=1;
	f[1][1]=1;
	for (int i=1;i<n;i++)
	  for (int j=i+1;j<=n;j++)
		for (int k=1;k<j;k++)
		if (g[j][k]&&f[i][k]) f[i][j]=f[j][i]=max(f[i][j],f[i][k]+1);
	for (int i=1;i<n;i++)
	if (g[i][n]) ans=max(ans,f[i][n]);
	cout<<ans<<endl;
}

此题可温故知新。

[USACO5.5]隐藏口令Hidden Password

题面：

Binny选择一个字符串S（由N个小写字母组成，5<=N<=5,000,000），然后他把S顺时针绕成一个圈，每次取一个做开头字母并顺时针依次取字母而组成一个字符串。这样将得到一些字符串，他把它们排序后取出第一个字符串。把这个字符串的第一个字母在原字符串中的位置-1做为口令。

思路：

以下思路是在学了一个叫”最小表示法”的东西之后，大家可以先去看看zy的论文，很清晰了。

或者您就简单听我讲一下此题的做法，可不用掌握那玩意：

首先取字典序最小的字符串，可以通过“最小表示法”的思路，构造两个字符串：一个是给定的原串，第二个是圈右移一个得到的新字符串，在样例中就是：

s1=anabana
s2=nabanaa

我们可以搞两个指针从头扫，比较当前字符是否匹配。当匹配K的时候发现不匹配了，由于我们要找最小的字符串，所以我们就把较大字符的指针往后挪一个$k+1$。

为啥是$K+1$？

假设$s1$的指针在$i$，$s2$的指针在$j$。假设当第k位发现$s1[i+k]>s2[j+k]$时，s1肯定不可能是最小表示了（s2比他小啊），所以我们就直接从$i+k+1$再重新找，仍可以保证能找到（s1一直找不到不就是当前的s2了吗）。

但是此题可能会出现$i+1==j$（就是在原串中重合）的情况，这时候如果不处理就会直接匹配完，但未必最小。这时候随便把一个指针++即可，因为如果当前是最小表示的话任意一个也满足条件。

遇到循环题最好倍个长。

代码：

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
#include <iostream>
using namespace std;

string s1,s2;
char c;
int n;

int zy()
{
	int i=0,j=0,k=0;
	while (i<n&&j<n)
	{
		k=0;
		if (i==j+1) j++;
		while (s1[i+k]==s2[j+k]&&k<=n) k++;
		if (k>n) return (i<j-1)?i:j-1; 
		if (s2[j+k]>s1[i+k]) j+=k+1;
		else i+=k+1;
	}
	return (i<j-1)?i:j-1;
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>c; if (c!='\n') s1+=c;
	}
	s1=s1+s1;
	s2=s1+s1[0]; s2.erase(0,1);
	cout<<zy()<<endl;	
}

[USACO5.5]矩形周长Picture

题面：求矩形凸包周长。

思路：

扫描线板子题，结果还是花了一天去学了那玩意。。

简单就是维护3个值$l,r,h,f$，分别代表当前线段的左端点，右端点，高度，以及上下边bool，下边就加上，上边就减去。

然后就是维护整个x轴区间，判断当前有多大范围被覆盖。线段树搞两个标记，一个村覆盖总长一个存当前区间是否覆盖，然后还要魔改一下pushup函数。

但是可能之前覆盖的边没有被删，导致重复计算，于是答案还要减去上一次搜到的答案。于是当前答案加一个$abs(tr[1]-last)$即可（这就是整个x轴区间的答案）。

这是竖边，横边重新存个图倒一下不就行了吗，为啥还要维护一些乱七八糟的东西啊。。。

讲的并不是很清楚，这种板子还是要自己去找博客学学的（暴露自己也没掌握透的事实）。。

代码（核心）：

1
2
3
4
5
6
7
8
9
10
11
12
for (int i=1;i<=st;i++){  //数据不保证y不等高。 

    int l=e[i].l,r=e[i].r,v=e[i].f;
    add(1,0,mx+1,l,r-1,v);
    while (e[i].h==e[i+1].h&&e[i].f==e[i+1].f)
    //先处理完所有的边长，减边的后面搞绝对值再干。
    {
        i++; l=e[i].l,r=e[i].r,v=e[i].f;
        add(1,0,mx+1,l,r-1,v);
    } 
    ans+=abs(tr1[1]-last); last=tr1[1];
}

[USACO5.5]贰五语言Two Five

题面：太长了。。

思路：

依然是DP，还是没想出来。。我觉得USACO的所有DP我就没有一道是写出来的。。

这是个类之前有个01串的做法，那题不是搞一个辅助DP，通过不断逼近求出最终答案得嘛。。

这道题问我们给定编号求第k小，还是可以把首位为A的方案数，首位为B的方案数…一直加，直到超过k为止，当前就是该为止的字符（因为这时候的方案数意味着自己可以达到的最大编号），然后再确定下一位继续从A搜（但要跳过已用字符）。

那么问题来了，怎么求首位是A的方案数（下文定义此操作叫排版）啊。

暴力！记忆化搜索！

但首先怎么设状态就不是很清楚啊。。

然后我们手膜了一下题面里的样例：

A C E P T

B D H Q U

F J M R W

G K N S X

I L O V Y

我们发现从A一直数到Y，他们时刻都是连通的！这里也有简单证明：由于我们填字符是从小到大填的，如果填的时候不连通跳着填，那中间必有空格没字母可填。

A C . . .

B . D . .

比如说这样，BD之间没有字母可用了。。

所以我们就设状态$f[a1][a2][a3][a4][a5]$ 是第i行占了i个空，按照当前排版可达的种类数。（好像还不是很明显）

我们转移的时候不妨保证先填了上面再填下面，这样就可以得到如下限制：

int dfs(int a,int b,int c,int d,int e,int sum)
//sum--> i have dfsed NO.sum letters
int now=0;
if (f[a][b][c][d][e]) return f[a][b][c][d][e];
if (a<5&&find(a,sum)) now+=dfs(a+1,b,c,d,e,sum+1);
if (b<a&&find(b+5,sum)) now+=dfs(a,b+1,c,d,e,sum+1);

if (c<b&&find(c+10,sum)) now+=dfs(a,b,c+1,d,e,sum+1);
if (d<c&&find(d+15,sum)) now+=dfs(a,b,c,d+1,e,sum+1);
if (e<d&&find(e+20,sum)) now+=dfs(a,b,c,d,e+1,sum+1);
return f[a][b][c][d][e]=now;

这个应该可以搞懂，但是我们如何按照自己的排版搞呢？

我们可以在判断的时候加一个find函数确定这个位置有没有被排版。

1
2
3
4
bool find(int x,int sum)
{
	return (!s[x]||(s[x]==(char)(sum+'A')));
}

其中$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
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstring>
using namespace std;

string str;
char c,s[10000],v[1000];
int num,f[6][6][6][6][6],ans;
//f[a1...a5]-->when NO.i line has ai number,the sum of sorts
//we can fix a letter during dfs

bool find(int x,int sum)
{
	return (!s[x]||(s[x]==(char)(sum+'A')));
}

int dfs(int a,int b,int c,int d,int e,int sum)
//sum--> i have dfsed sum letters
{
	int now=0;
	if (f[a][b][c][d][e]) return f[a][b][c][d][e];
	if (a<5&&find(a,sum)) now+=dfs(a+1,b,c,d,e,sum+1);
	if (b<a&&find(b+5,sum)) now+=dfs(a,b+1,c,d,e,sum+1);
	
	if (c<b&&find(c+10,sum)) now+=dfs(a,b,c+1,d,e,sum+1);
	if (d<c&&find(d+15,sum)) now+=dfs(a,b,c,d+1,e,sum+1);
	if (e<d&&find(e+20,sum)) now+=dfs(a,b,c,d,e+1,sum+1);
	return f[a][b][c][d][e]=now;
}

int main()
{
	cin>>c;
	if (c=='N') {
		cin>>num;
		for (int i=0;i<25;i++)
		for (s[i]='A';;s[i]++) 
		if (!v[s[i]]){
			v[s[i]]=1;
			memset(f,0,sizeof(f)); f[5][5][5][5][5]=1;
			int now=dfs(0,0,0,0,0,0);
			if (ans+now>=num) {
				 cout<<s[i]; break;
			}
			ans+=now; v[s[i]]=0;
			//需要找的编码肯定在它的后面，而查找无法直接找到前面的方案数 
		}
	}
	else{
		cin>>str;
		for (int i=0;i<25;i++)
			for (s[i]='A';s[i]<str[i];s[i]++) {//累加 
				memset(f,0,sizeof(f)); f[5][5][5][5][5]=1;
				ans+=dfs(0,0,0,0,0,0);
			}
			
		cout<<ans+1<<endl; 
	}
}

后续

总算按老师的想法刷完USACO，确实有很多好题也暴露了自己的短板，但想到自己省选的知识仍没有补完心里总是放不下心。

今后还是以学新知识为主了，脑子好昏想睡觉，不写了。