USACO 2.1

  • 城堡 The Castle
  • 顺序的分数 Ordered Fractions
  • 三值的排序 Sorting a Three-Valued Sequence
  • 健康的荷斯坦奶牛 Healthy Holsteins
  • 海明码 Hamming Codes

P1457 城堡 The Castle

暴力出奇迹
读入有点坑
第一,二问:
简单的floodfill。
第三,四问:
暴力枚举
“有多解时选(重心)最靠西的(仍然有多解时选这些里面(重心)最靠南的)。” 请注意重心二字! 北墙的重心比东墙的要靠西啊~~所以拆墙顺序是西墙,南墙,北墙,东墙。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int f[51][51][5];//存墙,f[i][j][0]存所属标号
int n,m,i,j,ii,jj;
int p=0;//连通块的个数
int a[2501];//存每个连通块的大小?
int ff[5][3]={{0,0,0},
{3,0,1},//右
{4,1,0},//下
{1,0,-1},//左
{2,-1,0}};//上,晕了~~~~(>_<)~~~~
//上下左右四个方向,f[i][0]存到达那需穿过的墙的方向
void dfs(int x,int y,int id)//dfs求连通块,id是标记的编号
{
if (x<=0||x>n||y<=0||y>m) return;//越界辣~\(≧▽≦)/~
if (f[x][y][0]!=0) return;//被搜过辣,当然这种情况是不会出现的
f[x][y][0]=id;//存编号
a[id]++;
for (int ii=1;ii<=4;ii++)//四种情况去搜
if ((f[x+ff[ii][1]][y+ff[ii][2]][0]==0)/*没被搜过*/
&&(f[x][y][ff[ii][0]]==0)/*过去没墙*/)
dfs(x+ff[ii][1],y+ff[ii][2],id);//往下搜
}
int main()
{
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
scanf("%d%d",&m,&n);//读入;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
int hehe;
scanf("%d",&hehe);//读入墙的数字和
if (hehe>=8)
{
hehe-=8;
f[i][j][4]=1;//标记南方有墙
}
if (hehe>=4)
{
hehe-=4;
f[i][j][3]=1;//标记东方有墙
}
if (hehe>=2)
{
hehe-=2;
f[i][j][2]=1;//标记北方有墙
}
if (hehe>=1)
{
hehe-=1;
f[i][j][1]=1;//标记西方有墙
}
//终于标记完了╮(╯▽╰)╭
//这种方法好巧啊。
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
if (f[i][j][0]==0)/*目前不属于任何一个连通块*/
{
p++;
dfs(i,j,p);//++p是目前搜的这个连通块的标记
}
}
printf("%d\n",p);//成功灭掉第一问
int maxx=a[1];//初始化
for (i=1;i<=p;i++) if (a[i]>maxx) maxx=a[i];
printf("%d\n",maxx); //成功灭掉第二问
//由题可知,移去的墙相对于某一个位置来说一定是东面或者北面
char k;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) //枚举 挖走动墙
{
if (i!=1&&f[i][j][2]==1&&f[i][j][0]!=f[i-1][j][0])
//第一行的北墙不能挖走,而且要有墙
//而且没有在同一个连通块
{
int hehe=a[f[i][j][0]]+a[f[i-1][j][0]];//合并后连通块大小
if (hehe>maxx)
{
maxx=hehe;
ii=i;
jj=j;//标记
k='N';//标记
}
if (hehe==maxx)
{
if ((j<jj)/*更西*/||(i>ii&&j<=jj)/*更南且不会更东*/)
{
ii=i;
jj=j;//标记
k='N';//标记
}
}
}
if (j!=m&&f[i][j][3]==1&&f[i][j][0]!=f[i][j+1][0])
//最后一列的东墙不能挖走 ,而且要有墙
//而且没有在同一个连通块
{
int hehe=a[f[i][j][0]]+a[f[i][j+1][0]];//合并后连通块大小
if (hehe>maxx)
{
maxx=hehe;
ii=i;
jj=j;//标记
k='E';//标记
}
if (hehe==maxx)
{
if ((j<jj)||(i>ii&&j<=jj))//更西方,更南方且不会更东方
{
ii=i;
jj=j;//标记
k='E';//标记
}
}
}
}
printf("%d\n",maxx);//第三问完成
printf("%d %d %c\n",ii,jj,k);//终于完成了
return 0;
}

P1458 顺序的分数 Ordered Fractions

枚举每一种方案,去掉未化简的,单独输出0/1,然后对其他的进行排序,用sort排序。见代码。

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

/*

ID: ylx14271

PROG: frac1

LANG: C++

*/

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
struct ha
{
int x,y;
}a[25700];
int n,i,j,p;
int gcd(int aa,int bb)
{
if (aa%bb==0) return bb;
return gcd(bb,aa%bb);
}
int cmp(ha aa,ha bb)//排序,先按照行,行相同的情况下按照列
{//ad-bc,aa.x bb.y aa.y bb.x
if ((aa.x*bb.y-aa.y*bb.x)>0)//aa比bb大
//通分后是(ad-bc)/bd,因为分母一定>0所以只要判断分子了
return 0;
else return 1;
}
int main()
{
freopen("frac1.in","r",stdin);
freopen("frac1.out","w",stdout);
scanf("%d",&n);
printf("0/1\n");
for (i=1;i<=n;i++)
for (j=i;j<=n;j++)
if (gcd(i,j)==1)//互质
{
p++;
a[p].x=i;a[p].y=j; //存起来
}
sort(a+1,a+p+1,cmp);//排序
for (i=1;i<=p;i++)
printf("%d/%d\n",a[i].x,a[i].y);//输出
return 0;
}

P1459 三值的排序 Sorting a Three-Valued Sequence

为了使交换次数最小,我们想到了以下贪心策略:
① 能不交换就不交换;
② 如果能只用一次交换就完成归位,就不用两次交换。
由于排序之后是11……1122……2233……33的形式,我们不妨按照排序之后的结果对原数据分区。令w(i,j)表示数字i在j区的数量。例如122 312 13中w(2,1)=2。
按照①的说法,在一区的1、二区的2、三区的3就不应该再被交换了。
按照②的说法,在一区的2应该和二区的1进行交换,1和3、2和3类似。
设这一次交换的步数为A,则
A=min{w(1,2)+w(2,1)}+min{w(1,3)+w(3,1)}+min{w(2,3)+w(3,2)}
接下来已经不能一步恢复两个数字了,就像312一样。这时只有先让一个数字归位,然后再交换另外两个。这样,每三个数字需要用两步完成。
设这一次交换的步数为B,则
B=(S-2A)÷3×2
其中S表示需交换的数字的总个数,即S=w(1,2)+w(2,1)+w(2,3)+w(3,2)+w(1,3)+w(3,1)。
最后将A和B相加,即最终结果。

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<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n;
int i,j,sum;
int a[1010],b[4]={0},c[4][4];//c[i][j]在区间段i内j的个数
int main()
{
freopen("sort3.in","r",stdin);
freopen("sort3.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);//读入
b[a[i]]++;//统计个数
}
for (j=1;j<=b[1];j++)//数字1所在的区间段
c[1][a[j]]++;//统计
for (j=b[1]+1;j<=b[1]+b[2];j++)//数字2所在的区间段
c[2][a[j]]++;//统计
for (j=b[1]+b[2]+1;j<=b[1]+b[2]+b[3];j++)//数字3所在的区间段
c[3][a[j]]++;//统计
int haha=min(c[1][2],c[2][1]);
sum=min(c[1][2],c[2][1]);//printf("%d ",sum);
//交换次数,先2这个区间段的1和1这个区间段的2交换
c[1][2]-=haha;
c[2][1]-=haha;
sum+=min(c[2][3],c[3][2]);// printf("%d ",sum);
//交换在2这个区间段的3,和在3这个区间段的2。
haha=min(c[2][3],c[3][2]);
c[2][3]-=haha;
c[3][2]-=haha;
sum+=min(c[1][3],c[3][1]);//printf("%d ====",sum);
//交换在1这个区间段的3,和在3这个区间段的1。
haha=min(c[1][3],c[3][1]);
c[1][3]-=haha;
c[3][1]-=haha;
sum=sum+(c[1][2]+c[2][1]+c[2][3]+c[3][2]+c[1][3]+c[3][1])*2/3;
cout<<sum<<endl;
return 0;
}

P1460 健康的荷斯坦奶牛 Healthy Holsteins

这道题我开始纠结了很久是用dfs还是用bfs呢,但是由于结果要求如果有多种情况,就输出字典序最小的,这样子dfs就会比较方便,就会省很多判断。总的来说这是简单的搜索。

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
88
89
90
91
92
93
94
95
96
97
98
99
/*

ID: ylx14274

PROG: holstein

LANG: C++

*/

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int vv;//维他命种类
int v[26];//每种所需数量
int n;//喂牛的饲料种类数
int a[16][26];//每种饲料每种维他命含量
int w[26];//存最小需要饲料的方案
int p,mm,he;//存需吃的种类的数量
int c[26];//c[i]标记吃不吃第i种饲料,1为吃
int pd()
{
for (int i=1;i<=vv;i++)
if (v[i]>0) return 0;//不符合条件
return 1;
}
int pr()
{
if (p<mm)//这种方案需要的饲料种类更少
//由于搜索保证了先搜到的字典序会小,所以不需比较p=min的情况
{
he=0;
mm=p;
for (int i=1;i<=n;i++)
if (c[i]==1)
{
he++;
w[he]=i;
}
}
}
void dfs(int t)
{
if (pd()==1)//牛吃这些能满足所需维他命的最小量
{pr();return;}
if (t>n)//每种饲料都选过了
{return;}
////吃第t种饲料
for (int i=1;i<=vv;i++)
{
v[i]-=a[t][i];//标记
}
c[t]=1;//标记吃第t种饲料
p++;
dfs(t+1);
for (int i=1;i<=vv;i++)
{
v[i]+=a[t][i];//还原标记
}
c[t]=0;//还原标记
p--;
////不吃第t种饲料
dfs(t+1);
}
int main()
{
mm=23333;
freopen("holstein.in","r",stdin);
freopen("holstein.out","w",stdout);
scanf("%d",&vv);//读入需要的维他命总数
for (int i=1;i<=vv;i++) scanf("%d",&v[i]);//读入牛所需的维他命量
scanf("%d",&n);//读入喂牛的饲料种数
for (int i=1;i<=n;i++)//读入编号i所包含的各种维他命量
for (int j=1;j<=vv;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("%d",mm);
for (int i=1;i<=mm;i++)
printf(" %d",w[i]);
printf("\n");
return 0;
}

P1461 海明码 Hamming Codes

其实就是枚举。我开始不知道b干嘛用的后来才发现b是用来限制枚举范围的?其实自己可以开一个很大的数。当然这题也可以用dfs,不过没必要。

题目2大坑点;

1.两两编码之间至少有 D 个单位,意思是海明距可以>=D,而不仅仅是==D

2.输出十个就要换行,而且每一行的第一个之前不能加空格。

海明距的话有两种方式判断,第一种是用位运算,不会位运算之类的自行百度,也就是我的这种方法,比较简洁,还有一种是楼下的方法,用字符串,比较容易理解,但是写起来不太方便。

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
#include<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n;//n:要求的个数
int d,b;//d距离,b位
int k;//存目前编码个数
int i,j;//循环控制变量
int a[65];//存结果
int find(int x,int y)//寻找距离,用位运算
{
int g=x^y;//相同位不同则为1,相同则为0。
int s=0;//存1的个数
while (g!=0)//找1的个数
{
if (g%2==1) s++;//统计
g/=2;
}
return s;
}
int main()
{
freopen("hamming.in","r",stdin);
freopen("hamming.out","w",stdout);
scanf("%d%d%d",&n,&b,&d);
k=1;
a[k]=0;
int hehe=1<<b;
while (k<n)
for (i=a[k]+1/*一定要比上一个数大*/;i<=hehe;i++)
{
if (find(a[k],i)>=d)//满足条件
{
int he=1;//标记用
for (j=1;j<=k-1;j++)//用a[k]与之前的都判断一次
if (find(a[j],i)<d)
{
he=0;//标记该数不符合条件
break;
}
if (he==1)//符合条件
{
k++;//计数
a[k]=i;//储存
break;
}//符合条件的话跳出

}
}
printf("%d",a[1]);
for (int ii=2;ii<=n;ii++)
{
if (ii%10!=1)printf(" %d",a[ii]);else printf("%d",a[ii]);
if (ii%10==0) printf("\n");
}
if (n%10!=0) printf("\n");
return 0;
}