USACO 1 合集

USACO 1.1

  • [USACO1.1]你的飞碟在这儿Your Ride Is Here
  • [USACO1.1]贪婪的送礼者Greedy Gift Givers
  • [USACO1.1]黑色星期五Friday the Thirteenth
  • [USACO1.1]坏掉的项链Broken Necklace

[USACO1.1]你的飞碟在这儿Your Ride Is Here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var s1,s2:string;
ss1,ss2,i,len1,len2:longint;
begin
readln(s1);
readln(s2);
len1:=length(s1);
len2:=length(s2);
ss1:=1;ss2:=1;
for i:=1 to len1 do
begin upcase(s1[i]);ss1:=ss1*(ord(s1[i])-64); end;
for i:=1 to len2 do
begin upcase(s2[i]);ss2:=ss2*(ord(s2[i])-64); end;
if ss1 mod 47=ss2 mod 47 then write('GO') else write('STAY')
end.

[USACO1.1]贪婪的送礼者Greedy Gift Givers

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
/*
ID: ylx14274
PROG: gift1
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 main()
{
map<string,int> f;//存编号用
int a[20]={0};//存结果用
string s[20],ss;//存名字用
int i,j,n,m,r;//循环控制变量,n:人数,m:钱数,r:发的人数
//freopen("gift1.in","r",stdin);
//freopen("gift1.out","w",stdout);
cin>>n;//读入人数
for (i=1;i<=n;i++)//读入人名
{
cin>>s[i];
f[s[i]]=i;//存进去
}
for (i=1;i<=n;i++)//读入每个人给别人发的钱,人数
{
cin>>ss;
cin>>m>>r;
if (r!=0)
{
int haha=m/r;//存给每个人的钱。
a[f[ss]]-=m/r*r;//自己的钱减去给的钱
for (j=1;j<=r;j++)
{
string sss;
cin>>sss;
a[f[sss]]+=haha;//加上别人给的钱;
}
}
}
for (i=1;i<=n;i++)
cout<<s[i]<<" "<<a[i]<<endl;
return 0;
}

[USACO1.1]黑色星期五Friday the Thirteenth

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
var n,i,j,k,d:longint;
a,b:array [0..10000] of longint;
begin
read(n);
a[1]:=31;
a[3]:=31;
a[5]:=31;
a[7]:=31;
a[8]:=31;
a[10]:=31;
a[12]:=31;
a[4]:=30;
a[6]:=30;
a[9]:=30;
a[11]:=30;
for i:=1900 to 1900+n-1 do
begin
if ((i mod 4=0)and(i mod 100<>0))or(i mod 400=0) then a[2]:=29 else a[2]:=28;
for j:=1 to 12 do
for k:=1 to a[j] do
begin
inc(d);
if d=8 then d:=1;
if k=13 then inc(b[d]);
end;
end;
write(b[6],' ',b[7],' ');
for i:=1 to 5 do write(b[i],' ');
end.

[USACO1.1]坏掉的项链Broken Necklace

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

/*
ID: ylx14274
PROG: beads
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
int n,i,j,maxx;
long long ll,rr,o;
char s[4000],l,r;
using namespace std;
int main()
{
//freopen("beads.in","r",stdin);
//freopen("beads.out","w",stdout);
cin>>n;
cin>>s;//rbw
for (i=0;i<=n-1;i++)
{
s[n+i]=s[i];
} //拉直-------------
for (i=1;i<=n;i++)//枚举每个切断的位置
{
l='a';r='a';//初始化
ll=0;rr=0;
for (j=i-1;j>=1;j--)//往左边取珠子
{
if (s[j]=='w') {ll++;}//如果是白色就任意
else//否则
{
if (l=='a')//这是第一个非白的珠子
{
l=s[j];//标记
ll++;//计数
} else//否则
{
if (s[j]==l)//是相同颜色的珠子
{ll++;} //计数
else break;//否则退出。
}
}
}
for (j=i;j<=i+n;j++)//往右边取珠子
{
if (s[j]=='w') rr++;//如果是白色就任意
else//否则
{
if (r=='a')//这是第一个非白的珠子
{
r=s[j];//标记
rr++;//计数
} else//否则
{
if (s[j]==r)//是相同颜色的珠子
rr++; //计数
else break;//否则退出。
}
}
}
if (ll+rr>n)
{
ll=n;
rr=0;
}
if ((ll+rr)>maxx) o=i;
maxx=(ll+rr)>maxx?ll+rr:maxx;
}
cout<<maxx;
return 0;
}

USACO 1.2

  • [USACO1.2]挤牛奶Milking Cows
  • [USACO1.2]方块转换 Transformations
  • [USACO1.2]回文平方数 Palindromic Squares
  • [USACO1.2]双重回文数 Dual Palindromes
  • [USACO1.2]命名那个数字 Name That Number

[USACO1.2]挤牛奶Milking Cows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var a:array[1..10000000] of integer;
n,x,y,i,max,min,j,s,ss,mm,hh:longint;
begin
read(n);
hh:=maxlongint;
for i:=1 to n do
begin
read(x,y);
for j:=x to y-1 do
a[j]:=1;
if y-1>mm then mm:=y-1;
if x<hh then hh:=x;
end;
for i:=hh to mm do
begin
if a[i]=1 then inc(max) else max:=0;if max>s then s:=max;
if a[i]=0 then inc(min) else min:=0;if min>ss then ss:=min;
end;
write(s,' ',ss);
end.

[USACO1.2]方块转换 Transformations

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
142
143
144
145
146
147
/*
ID: ylx14271
PROG: transform
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;
char a[11][11],b[11][11],c[11][11],d[11][11];
//a存原本的,b存要求的的,c存变换后的结果,d用来玩的
int n,i,j;
void xz()//旋转90°过程
{
for (i=1;i<=n;i++)//将d数组复制成c数组
{
for (j=0;j<n;j++)
{
d[i][j]=c[i][j];
}
}
for (i=1;i<=n;i++)//旋转D数组(也就是原本的c数组)将结果存入c数组
{
for (j=0;j<=n-1;j++)
{
c[i][j]=d[n-j][i-1];//顺时针旋转90°
}
}
return;
}
void fs()//反射
{
for (i=1;i<=n;i++)//将d数组复制成c数组
for (j=0;j<=n-1;j++)
{
d[i][j]=c[i][j];//复制一遍
}
for (i=1;i<=n;i++)
for (j=0;j<=n-1;j++)
{
c[i][j]=d[i][n-j-1];//翻转过程,第j列到了第n-j+1列
}
}
int pd()//判断经过处理后的图案是否与要求的图案一致
{
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (c[i][j]!=b[i][j])//如果这个字符对不上
return 1;//返回1
}
return 0;
}
int main()
{
cin>>n;
for (i=1;i<=n;i++)//读入原本的图案
{
cin>>a[i];
}
for (i=1;i<=n;i++)//读入要转换成的图案
{
cin>>b[i];
}
////////////////////////////////////////////华丽的分割线-90°////////////////
for (i=1;i<=n;i++)//将c数组复制成a数组
{
for (j=0;j<n;j++)
{
c[i][j]=a[i][j];
}
}
xz();//顺时针旋转90°
if (pd()==0)//如果与要求的图案相等
{
cout<<1<<endl;
return 0;
}
////////////////////////////////////////////华丽的分割线-180°//////////////
xz();//c在原本的90°的基础上直接转。
if (pd()==0)//如果与要求的图案相等
{
cout<<2<<endl;//输出
return 0;//结束
}
////////////////////////////////////////////华丽的分割线-270°//////////////
xz();//c在原本的90°的基础上直接转。
if (pd()==0)//如果与要求的图案相等
{
cout<<3<<endl;//输出
return 0;//结束
}
////////////////////////////////////////////华丽的分割线-反射//////////////
for (i=1;i<=n;i++)//将c数组复制成a数组
{
for (j=0;j<n;j++)
{
c[i][j]=a[i][j];
}
}
fs();//反射
if (pd()==0)//判断。
{
cout<<4<<endl;
return 0;
}
////////////////////////////////////////////华丽的分割线-组合//////////////
//介于反射过了,所以c数组直接旋转吧。
xz();//c在原本的90°的基础上直接转。90°
if (pd()==0){cout<<5<<endl; return 0;}//判断
xz();//c在原本的90°的基础上直接转。180°
if (pd()==0){cout<<5<<endl; return 0;}//判断
xz();//c在原本的90°的基础上直接转。270°
if (pd()==0){cout<<5<<endl; return 0;}//判断 \
////////////////////////////////////////////华丽的分割线-原图//////////////
int biaoji=0;//标记
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (a[i][j]!=b[i][j])//如果这个字符对不上
biaoji=1; //标记
}
if (biaoji==0)//如果每个数组都对得上
{
cout<<6<<endl;//输出
return 0;//结束
}
/////////////////////////////////////////////华丽的分割线-无//////////////
cout<<7<<endl;//否则就无法变换成为要求的图形
return 0;
}

[USACO1.2]命名那个数字 Name That Number

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: ylx14274
PROG: namenum
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 a[256];
int i,j;
char ss[13],n[13];
int main()
{
set<string> set1;
a[65]=a[66]=a[67]=2;//简单粗暴的初始化
a[68]=a[69]=a[70]=3;//q很难判断来着
a[71]=a[72]=a[73]=4;
a[74]=a[75]=a[76]=5;
a[77]=a[78]=a[79]=6;
a[80]=a[82]=a[83]=7;
a[84]=a[85]=a[86]=8;
a[87]=a[88]=a[89]=9;
freopen("namenum.in","r",stdin);
freopen("namenum.out","w",stdout);
freopen("dict.txt", "r", stderr);
fscanf(stdin,"%s",n);
int l=strlen(n);//存n的长度
int ll;//存
int ylx=0;//存有没有结果
for (i=1;i<=4734;i++)
{
fscanf(stderr,"%s",ss);//读入
ll=strlen(ss);//求出数的长度
if (l==ll)
{
bool he=true;//判断这个串是否符合条件
for (j=0;j<=l-1;j++)//一个一个判断
{
int cc,c;
cc=int(ss[j]);
c=int(n[j])-48;
if (a[cc]!=c) he=false;//一个不满足就标记
}
if (he) {cout<<ss<<endl;ylx=1;}//符合条件就输出,标记有结果
}
}
if (ylx==0) cout<<"NONE"<<endl;
return 0;
}

[USACO1.2]回文平方数 Palindromic Squares

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

/*
ID: ylx14274
PROG: palsquare
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 a[30];//存n进制数转的结果,
int b[30];//各种用途
int i,j,n,k,kk;//n存进制
int nf,ny;
void he(int nn)//转成n进制
{
int ha,yu,shang;
for(j=1;j<=29;j++)
a[j]=0;
k=0;
shang=nn;
while (true)
{
yu=shang%n;
shang=shang/n;
++k;
a[k]=yu;
if (shang==0) break;
}
}
void haa(int nn)//转成n进制
{
int ha,yu,shang;
for(j=1;j<=29;j++)
b[j]=0;
kk=0;
shang=nn;
while (true)
{
yu=shang%n;
shang=shang/n;
++kk;
b[kk]=yu;
if (shang==0) break;
}
}
int main()
{
freopen("palsquare.in","r",stdin);
freopen("palsquare.out","w",stdout);
cin>>n;
for (i=1;i<=300;i++)//枚举
{
int biaoji=1;//标记用
he(i);//转成n进制
{
nf=i*i;
haa(nf);//转成n进制
for (j=1;j<=kk;j++)//判断回文数
{
if (b[j]!=b[kk-j+1])
{
biaoji=0;
break;
}
}
}
//因为是回文数,就算是倒着存的但是输出也不影响,
if (biaoji==1)
{
for (j=k;j>=1;j--)
{
if (a[j]<10) printf("%d",a[j]);
else{
char cha=char(a[j]-10+65);
printf("%c",cha);
}
}
cout<<" ";
for (j=1;j<=kk;j++)
if (b[j]<10) printf("%d",b[j]);
else{
char cha=char(b[j]-10+65);
printf("%c",cha);
}
cout<<endl;
}
//cout<<"华丽的分隔线 \n";
}
return 0;
}

[USACO1.2]双重回文数 Dual Palindromes

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
/*
ID: ylx14274
PROG: dualpal
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
int a[30];//存转换后的数,这里10并没有变成A
int n,s,sum=0,i,j,k;//sum:统计已经输出的数的个数。
using namespace std;
void he(int nn,int n1)//nn转成n1进制,存入a数组zhong
{
int ha,yu,shang;
for(j=1;j<=29;j++)//初始化
a[j]=0;
k=0;
shang=nn;
while (true)//进制转换
{
yu=shang%n1;
shang=shang/n1;
++k;//统计a的位数的
a[k]=yu;
if (shang==0) break;//没了就退出2
}
}
int main()
{
cin>>n>>s;
s+=1;
for (;sum<=n;s++)//枚举
{
int f=0,biaoji;//标记用,f存在几种进制下是回文数
for (i=2;i<=10;i++)//不需要搞一个数组存10进制,因为i=10的时候算了
{//而且是最后算,所以值还在a数组里,最后输出就输出这个
biaoji=1;//初始化,存是否为回文数
he(s,i);//将s转成i进制数存到a数组里
for (j=1;j<=k;j++)//判断s是否为回文数
{
if (a[j]!=a[k-j+1])//如果其中一位不满足就标记。
{
biaoji=0;//标记这个数不是回文数
break;//跳出循环
}
}
if (biaoji==1)//在i进制下这个数是回文数
f++;//计数
}
if (f>=2)
{
for (j=k;j>=1;j--)
printf("%d",a[j]);//10进制数就直接输出233
printf("\n");
sum++;//记得标记!
}
if (sum>=n) break;
}
return 0;
}

USACO 1.3

  • [USACO1.3]混合牛奶 Mixing Milk
  • [USACO1.3]修理牛棚 Barn Repair
  • [USACO1.3]牛式 Prime Cryptarithm
  • [USACO1.3]虫洞wormhole
  • [USACO1.3]滑雪课程设计Ski Course Design
  • [USACO1.3]号码锁 Combination Lock

[USACO1.3]混合牛奶 Mixing Milk

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
var n,m,i,s:longint;
a:array[1..2,1..5000] of longint;
//a[1]存牛奶的单价,a[2]存农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量
procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[1,(l+r) div 2];
repeat
while a[1,i]<x do
inc(i);
while x<a[1,j] do
dec(j);
if not(i>j) then
begin
y:=a[1,i];
a[1,i]:=a[1,j];
a[1,j]:=y;
y:=a[2,i];
a[2,i]:=a[2,j];
a[2,j]:=y;
inc(i);
dec(j)
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
read(n,m);
s:=0;
for i:=1 to m do
read(a[1,i],a[2,i]);
sort(1,m);
for i:=1 to m do
begin
if n-a[2,i]>=0 then
begin
n:=n-a[2,i];
inc(s,a[2,i]*a[1,i]);
end else if n>0 then
begin
inc(s,n*a[1,i]);
n:=0;
end;
end;
write(s);
end.

[USACO1.3]修理牛棚 Barn Repair

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
/*
ID: ylx14274
PROG: barn1
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 m,s,c,i,sum;
int a[201],b[201];//存编号
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
scanf("%d%d%d",&m,&s,&c);//最大的数目m,牛棚的总数s牛棚里牛的总数c
for (i=1;i<=c;i++) scanf("%d",&a[i]);//读入
if (m>=c)//如果可以放的板子足够多,那就一间牛棚一个吧
{
cout<<c<<endl;
return 0;
}
sort(a+1,a+c+1);//a数组从小到大排序
sum=a[c]-a[1]+1;//最长的覆盖长度,所有的放在一个板子下
for (i=1;i<c;i++)//求间隙大小
b[i]=a[i+1]-a[i];//b[i]为a[i]和a[i+1]之间的间隙
sort(b+1,b+c,cmp);//从大到小排序
for (i=1;i<m;i++)//本来就有一块,i是切的块数
{
sum=sum-b[i]+1;
}
cout<<sum<<endl;
return 0;
}

[USACO1.3]牛式 Prime Cryptarithm

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
/*
ID: ylx14274
PROG: crypt1
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 n,haa;/*读入用*/
int aa[10]={0},bb[10]={0},i,j,k,f,sum=0;
//aa存可以用的数字,bb存这种情况,i,j,k循环控制变量
void biaoji(int bj)//标记此牛式的此部分用了哪些数字
{
int a[10],hh,bbjj=bj;
while (true)
{
hh=bbjj%10;//取出目前最后一位
bb[hh]=1;//标记这一位
bbjj=bbjj/10;//删除目前最后一位
if (bbjj==0) return;//如过没了就退出
}
}
int main()
{
scanf("%d",&n);//读入n
for (i=1;i<=n;i++)//读入n个数,存起来。
{
scanf("%d",&haa);//读入
aa[haa]=1;//标记
}
for (i=100;i<999;i++)//疯狂的枚举
for (j=10;j<=99;j++)
{
f=1;//初始化
if (i*j>10000) continue;//如过结果不是4位就拉倒
if (((i*(j%10))<100)||((i*(j%10))>=1000)) continue;
//如果i*j的个位不是三位数也拉倒
if (((i*(j/10))<100)||((i*(j/10))>=1000)) continue;
//如果i*j的十位不是三位数也拉倒
for (k=0;k<10;k++){bb[k]=0;}//bb数组初始化
biaoji(i);//标记第一个因数
biaoji(j);//标记第二个因数
biaoji(i*(j%10));//标记i*j的个位反正j是两位数
biaoji(i*(j/10));//标记i*j的十位
biaoji(i*j);//标记i*j的集,终于都标记了
for (k=0;k<10;k++)//然后就是判断了
{
if (bb[k]==1)//牛式中出现了这个数字
{
if (aa[k]!=1)//然而并没有允许使用这个数字
f=0;
}
}
if (f==1)//如过牛式中有的都是可以用的数字,那么就统计
sum++;
}
cout<<sum<<endl;
return 0;
}

[USACO1.3]虫洞wormhole //que

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
/*
ID: ylx14271
PROG: wormhole
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
int read(){
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){k=k*10+(s-'0');s=getchar();}
return k*base;
}
void write(int x){
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}

int n;
struct node
{
int x;
int y;
} a[30];
int b[30];
int ans;

bool cmp(node aa,node bb)
{
if (aa.y==bb.y) return aa.x<bb.x;
return aa.y<bb.y;
}

int f(int num,int d,int begin,int p1)
{
if (num>n+10) return 0;
//cout<<num<<" "<<d<<" "<<begin<<" "<<p1<<endl;
if (num!=1&&d==begin&&p1==1) return 1; else
if (p1==0)
{
if (a[d].y==a[d+1].y) return f(num+1,d+1,begin,1);
else return 0;
} else
if (p1==1)
{
return f(num+1,b[d],begin,0);
}//b[i]=x;b[x]=i;
}

bool check()
{
//cout<<"\n peidui";
//for (int j=1;j<=n;j++) cout<<b[j]<<" ";
//cout<<" -------"<<endl;
for (int j=1;j<=n;j++)
if (f(1,j,j,1)==1) return 1;
return 0;
}

void dfs(int x)//配对
{
//cout<<x<<endl;
if (x==n+1) {if (check()==1) ans++;return;}
if (b[x]==0)
{
for (int i=x+1;i<=n;i++)
if (b[i]==0)
{
//
//,b[d]cb[d]cout<<" --"<<x<<":"<<i<<endl;
b[i]=x;b[x]=i;
//printf("x:%d i:%d b[i]:%d b[x]:%d\n",x,i,b[i],b[x]);
dfs(x+1);
b[i]=0;b[x]=0;
}

}
if (b[x]!=0) dfs(x+1);
return;
}
int main()
{

//freopen("wormhole.in","r",stdin);
//freopen("wormhole.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
//cout<<n<<" 233333333333333333333333333 \n";
sort(a+1,a+n+1,cmp);
//for (int i=1;i<=n;i++) printf("%d %d\n",a[i].x,a[i].y);
dfs(1);
printf("%d\n",ans);
return 0;
}

[USACO1.3]滑雪课程设计Ski Course Design

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
#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 a[1010];//存没做山峰的海拔高度
int w;//每次枚举时修改山峰高度的花费
int m;//需要的最小的花费
int i,j;//循环控制变量
int main()
{
scanf("%d",&n);//读入山峰数量
m=200000000;
for (i=1;i<=n;i++)//读入每个山峰的高度
scanf("%d",&a[i]);
for (i=0;i<=84;i++)//枚举,因为所有山峰高度都在100一下所以只需搜到84
{//山峰高度修改后范围:i<a[j]<i+17
w=0;//w一定要清零
for (j=1;j<=n;j++)//统计
{
if (a[j]<i)//如果山峰j高度小于i
w+=(i-a[j])*(i-a[j]);//加上改这座山所需的费用
if (a[j]>i+17)//如果这座山房高度大于i+17
w+=(a[j]-(i+17))*(a[j]-(i+17));
}
if (w<m) m=w;//如果所需费用小于min
}
cout<<m<<endl;
return 0;
}

[USACO1.3]号码锁 Combination Lock

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
/*
ID: ylx14274
PROG: combo
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 a[7];//存密码,1~3约翰的号码组合,4~6预设号码组合
int n,i,j,k,sum=0;
int pd (int nn,int bb)//判断是否位置差在2个之间
{
int hehe=abs(a[bb]-nn);//记得加绝对值
if ((hehe<=2)||(hehe)>=n-2)//如果与号码组合的这一位位置差在2个以内
return 1;//返回1
return 0;
}
int main()
{
scanf("%d",&n);//读锁的数字个数
if (n<=5)//此时所有位置离正确的数字位置相差不会超过2。
{
cout<<n*n*n<<endl;//输出n的三次方
return 0;//退出
}
for (i=1;i<=6;i++)
scanf("%d",&a[i]);//读密码
for (i=1;i<=n;i++)//疯狂的枚举
for (j=1;j<=n;j++)
for (k=1;k<=n;k++)
{
if (((pd(i,1)==1)&&(pd(j,2)==1)&&(pd(k,3)==1))
//如果三个数字和约翰的号码组合位置差在2个以内
||/*或者*/((pd(i,4)==1)&&(pd(j,5)==1)&&(pd(k,6)==1)))
//如果三个数字和设号码组合位置差在2个以内
sum++;//计数
}
cout<<sum<<endl;
return 0;
}

USACO1.4

  • [USACO1.4]等差数列 Arithmetic Progressions
  • [USACO1.4]母亲的牛奶 Mother’s Milk

[USACO1.4]等差数列 Arithmetic Progressions

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
#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 hhh
{
int a,b;
}a[100010];
int cmp(const hhh &a,const hhh &b)//先按a排序再按b排序
{
if(a.b<b.b) return 1;
if(a.b>b.b) return 0;
if(a.a<b.a) return 1;
if(a.a>b.a) return 0;
return 1;
}
int m,n,p,q,i,j,aa;
int f[100000];
int c[100000];
int cc;//存双平方数的个数
int fff=0;
int ff;//ff标记是否越界&&是否符合条件。fff标记符合条件的等差数列的个数。
int main()
{
/////////////////////////////////////////////////////////////////
scanf("%d%d",&n,&m);//n等差数列长度,m搜索双平方数的上界
for (p=0;p<=m;p++)//把能表示成p的平方 + q的平方的数标记
for (q=p;q<=m;q++)
{
if (f[p*p+q*q]==0)//如果这个数之前没标记过就再标记
{
cc++;//个数+1
c[cc]=p*p+q*q;//存起来
f[p*p+q*q]=1; //标记
}
}
////////////////////////////////////////////////////////////
sort(c+1,c+cc+1);//c数组从小到大排序
i=0;
for (i=1;i<=cc-n+1;i++)//因为后面有n个双平方数所以最多到cc-n+1
{
aa=c[i];//存结果中的a
j=i;//初始化
int flag;
do
{
j++;
ff=0;//初始化
flag=0;
int b=c[j]-c[i];//等差数列的差。
if (j>cc-n+2)//后面没那么多个数
{
flag=1;// 标记
break;//跳出当前循环
}
if (aa+b*(n-1)>c[cc])//如果最大的那个大于符合条件的最大的双平方数
{
flag=1;// 标记
break;//跳出当前循环
}
for (int k=2;k<=n-1;k++)//把后面的也给枚举+判断
{
if (f[aa+k*b]!=1)//如果这个不满足条件后面也不要算了
{
ff=1;// 标记
break;//跳出当前循环
}
}
if (ff==0)//如果符合条件
{
fff=fff+1;;//存个数的
a[fff].a=aa;
a[fff].b=b;
}
}while (flag==0);
}
sort(a+1,a+fff+1,cmp);
///////////////////////////////////////////////////////////////////////
{
printf("%d %d\n",a[i].a,a[i].b);
}
if (fff==0)
printf("NONE");
return 0;
}

[USACO1.4]母亲的牛奶 Mother’s Milk

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
/*
ID: ylx14271
PROG: milk3
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int a[4];//存现有牛奶
int b[4];//存容积
int i,j,s,ff;
int c[21][21]={0};//判重,由a和c的牛奶量就可以推出b的牛奶量\
所以只需判断a和c
int t[30];//c牛奶剩余可能,1:可能出现
void dfs(int aa,int cc)
{
int bb=b[3]-aa-cc;
if (c[aa][cc]==1) return;//判重
c[aa][cc]=1;//标记
//下面一点小小的优化:如过a/b/c桶是空的,则不需向别的桶子倒牛奶\
如果接收牛奶的一方没有容积了,也不需要给它倒牛奶\
因为倒了跟没到是一个效果
if ((bb<=b[2])&&(aa!=0))
{
dfs(aa-min(aa/*a的牛奶量*/,b[2]-bb/*b的剩余容积*/),cc);//a→b
}
if ((cc<=b[3])&&(aa!=0))
{
dfs(aa-min(aa/*a的牛奶量*/,b[3]-cc/*c的剩余容积*/),cc+min(aa,b[3]-cc));
//a→c
}
if ((aa<=b[1])&&(bb!=0))
{
dfs(aa+min(bb/*b的牛奶量*/,b[1]-aa/*a的剩余容积*/),cc);//b→a
}
if ((cc<=b[3])&&(bb!=0))
{
dfs(aa,cc+min(bb,b[3]-cc));//b→c
}
if ((aa<=b[1])&&(cc!=0))
{
dfs(aa+min(cc,b[1]-aa),cc-min(cc,b[1]-aa));//c→a
}
if ((bb<=b[2])&&(cc!=0))
cout<<"c→b,min(cc,b[2]-bb): "<<min(cc,b[2]-bb)<<" cc-min(cc,b[2]-bb):
"<<cc-min(cc,b[2]-bb)<<endl;
dfs(aa,cc-min(cc,b[2]-bb));//c→b
}
int main()
{

scanf("%d%d%d",&b[1],&b[2],&b[3]);//读入容积

a[3]=b[3];//c桶此时牛奶是满的,牛奶量即容积
dfs(0,a[3]);//深搜

for (i=0;i<=b[3];i++)//c的牛奶量不可能大于它的容积
if ((c[0][i]==1)&&(ff==1)) printf(" %d",i);
else if (c[0][i]==1)
{
printf("%d",i);
ff=1;
}
printf("\n");
return 0;
}

USACO 1.5

  • [USACO1.5]数字三角形 Number Triangles
  • [USACO1.5]回文质数 Prime Palindromes
  • [USACO1.5]特殊的质数肋骨 Superprime Rib

[USACO1.5]数字三角形 Number Triangles

1
2
3
4
5
6
7
8
9
10
11
12
13
var n,i,j:longint;
b,a:array[1..1000,1..1000]of longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to i do read(a[i,j]);
b:=a;
for i:=n-1 downto 1 do
for j:=1 to i do
if b[i+1,j]>b[i+1,j+1] then b[i,j]:=b[i,j]+b[i+1,j]
else b[i,j]:=b[i+1,j+1]++b[i,j];
writeln(b[1,1]);
end.

[USACO1.5]回文质数 Prime Palindromes

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
var aa:array[1..779] of longint
=(5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,
10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,
15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,
30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,
35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,
71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,
77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,
94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,
98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,
1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,
1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,
1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,
1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,
1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,
1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,
1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,
1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,
1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,
1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,
1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,
1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,
1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,
1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,
1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,
1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,
1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,
1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,
1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,
3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,
3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,
3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,
3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,
3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,
3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,
3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,
3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,
3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,
3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,
3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,
3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,
3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,
3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,
3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,
3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,
3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,
7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,
7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,
7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,
7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,
7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,
7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,
7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,
7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,
7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,
7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,
7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,
7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,
7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,
7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,
7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,
9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,
9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,
9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,
9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,
9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,
9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,
9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,
9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,
9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,
9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,
9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,
9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,
9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,
9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,
9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899);
a,b,i:longint;
begin
read(a,b);
for i:=1 to 779 do
if (aa[i]<=b)and(aa[i]>=a) then writeln(aa[i])
end.

[USACO1.5]特殊的质数肋骨 Superprime Rib

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
/*
ID: ylx14271
PROG: sprime
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#define LL unsigned long long
int n;
int a[9];
using namespace std;
int pd(int xx)//判断质数
{
if (xx==1) return 0;//1不是质数
for (int i=2;i<=sqrt(xx);i++)
if (xx%i==0)//能整除
return 0;//0代表不是质数
return 1;//否则就是质数
}
void dfs(int nn,int t)
{
if (t==n)//如果搜完了
{
cout<<nn<<endl;//不需要再判断是否为质数
//因为在搜索过程中已经判断过了
return;//退出
}
int nnn=nn*10+1;
if (pd(nnn)==1)//如果这个数是质数的话就继续往下搜
dfs(nnn,t+1);
nnn=nn*10+3;
if (pd(nnn)==1)//如果这个数是质数的话就继续往下搜
dfs(nnn,t+1);
nnn=nn*10+7;
if (pd(nnn)==1)//如果这个数是质数的话就继续往下搜
dfs(nnn,t+1);
nnn=nn*10+9;
if (pd(nnn)==1)//如果这个数是质数的话就继续往下搜
dfs(nnn,t+1);
}
int main()
{
scanf("%d",&n);
if (n==1) printf("2\n3\n5\n7\n");//1的话直接打表就好了
dfs(2,1);dfs(3,1);dfs(5,1);dfs(7,1);//深搜
return 0;
}