USACO 3.2

  • 阶乘 Factorials
  • 01串 Stringsobits
  • 纺车的轮子 Spinning Wheels
  • 饲料调配 Feed Ratios
  • 魔板 Magic Squares
  • 香甜的黄油 Sweet Butter

p2726 阶乘 Factorials

10=25。
不难发现,2的个数一定比5的个数多。
其他数我们只需要尾数就好。
结果就是2^(2的个数-5的个数)
其他数%10。

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
/*
ID: ylx14271
PROG: fact4
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;//读入用
int sum;//存结果
int s;//存2的个数减去5的个数,即剩余2的个数
int i;//循环控制变量
int qiu(int k)
{
int kk=k;
while (kk%2==0)
{
kk/=2;
s++;
}//2的个数
while (kk%5==0)
{
kk/=5;
s--;
}//5的个数
return kk;
}
int main()
{
sum=1;//初始化
freopen("fact4.in","r",stdin);
freopen("fact4.out","w",stdout);
scanf("%d",&n);//读入
for (i=2;i<=n;i++) sum=(sum*qiu(i))%10;
for (i=1;i<=s;i++) sum=(sum*2)%10;
printf("%d\n",sum);
return 0;
}

p2727 01串 Stringsobits

于是我们先求出所有的方案数。
边界为f[i][0]=1; f[0][i]=1;
很容易发现,不论是哪一位,如果前面一样,那一位为1的话一定比那一位为0的大小大。
所以,如果k>f[i-1][j]的话,第i位一定为1,之后k减去f[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
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
/*
ID: ylx14271
PROG: kimbits
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;
long long n,m,k,i,j,l;
long long f[50][50];//f[i][j]表示i位数中有j个1的方案种数
int main()
{
freopen("kimbits.in","r",stdin);//抄题解者记得去掉
freopen("kimbits.out","w",stdout);
scanf("%l64d%l64d%l64d",&n,&m,&k);
for (i=0;i<=n;i++)//初始值
{
f[i][0]=1;
f[0][i]=1;
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
if (j<=i) f[i][j]=f[i-1][j-1]+f[i-1][j]; //dp求方案数
else f[i][j]=f[i][i];//再多的1只有那么多位所以方案数还是f[i][i]
}
}
i=n;j=m;
while (i!=0)
{
if (k>f[i-1][j]&&k!=0)
{
printf("1");
k=k-f[i-1][j];//余下的重复操作
i--;j--;//各减1继续搜
} else //第s+1位为1
{
printf("0");//输出0
i--;
}
}
printf("\n");
return 0;
}

p2728 纺车的轮子 Spinning Wheels

模拟题

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: ylx14274
PROG: spin
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 v[6];//速度
int s[6];//数量
int x[6][6],y[6][6];//5个轮子5个洞
int i,j,k,t;//循环控制变量
int a[361];
int b[6];
int main()
{
freopen("spin.in","r",stdin);
freopen("spin.out","w",stdout);
for (i=1;i<=5;i++)
{
scanf("%d%d",&v[i],&s[i]);//读入速度和洞的数量
for (j=1;j<=s[i];j++)//读入s[i]个洞
scanf("%d%d",&x[i][j],&y[i][j]);//读入洞的位置和宽度
} //读入完毕
//读进来了。要干嘛来着……
for (t=0;t<=360;t++)//可能一开始就有一个地方5个轮子在那都是洞
{
memset(a,0,sizeof(a));//a清0
for (i=1;i<=5;i++)//5个轮子
{
for (j=1;j<=s[i];j++)//s[i]个洞
{
for (k=x[i][j];k<=x[i][j]+y[i][j];k++)//标记到数组a
a[k%360]++;//标记。记得取模
x[i][j]=(x[i][j]+v[i])%360;//下一秒状态。记得取模
}
} //标记完成
for (i=0;i<=359;i++)
if (a[i]==5)//5个轮子在此处均为洞
{
printf("%d\n",t);//输出
return 0;
}
}
printf("none\n");
return 0;
}

p2729 饲料调配 Feed Ratios

直接枚举

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
/*
ID: ylx14274
PROG: ratios
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 f[4][4];
int aa,bb,cc;
int a,b,c;
int i,j,k,s;
int main()
{
scanf("%d%d%d",&aa,&bb,&cc);
for (i=1;i<=3;i++)//读入比例
{
scanf("%d%d%d",&f[i][1],&f[i][2],&f[i][3]);//读入饲料比例
}
for (i=0;i<=100;i++)//枚举每种饲料的份数
for (j=0;j<=100;j++)
for (k=0;k<=100;k++)
{
if (i==0&&j==0&&k==0) continue;
a=(f[1][1]*i)+(f[2][1]*j)+(f[3][1]*k);//大麦
b=(f[1][2]*i)+(f[2][2]*j)+(f[3][2]*k);//燕麦
c=(f[1][3]*i)+(f[2][3]*j)+(f[3][3]*k);//小麦
int ma=0,mb=0,mc=0;
int da=0,db=0,dc=0;
if (aa!=0)
{
ma=a%aa;
da=a/aa;
}
if (bb!=0)
{
mb=b%bb;
db=b/bb;
}
if (cc!=0)
{
mc=c%cc;
dc=c/cc;
}
if (ma==0&&mb==0&&mc==0)//能够整除
{
int ff=0;//标记用
if (bb==cc&&cc==0&&a!=0) ff=1;//只需饲料a
if (bb==aa&&aa==0&&b!=0) ff=1;//只需饲料c
if (aa==cc&&aa==0&&c!=0) ff=1;//只需饲料b
if (da==db&&db==dc&&da!=0) ff=1;
if (da==db&&cc==0&&da!=0) ff=1;
if (da==dc&&bb==0&&dc!=0) ff=1;
if (db==dc&&aa==0&&dc!=0) ff=1;
if (ff==1)
{
s=a/aa;//饲料份数
printf("%d %d %d %d\n",i,j,k,s);
return 0;
}
}
}
printf("NONE\n");
return 0;
}

p2730 魔板 Magic Squares

其实是普通的bfs。但是三种情况处理起来比较麻烦。
判重咱用的是map。
然后12345678是
1234 8765 然后存用12345678的话就比较麻烦,于是我存的话就是12348765,处理起来也方便一些。
读入的目标状态我们存的时候也做下处理,如样例:26845731,我们存的话是26841375。这样判断是否搜到的时候会比较方便。
三种情况的处理话自己推一下就出来了,见代码。

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
148
149
150
151
152
153
154

/*
ID: ylx14274
PROG: msquare
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;
map<int,bool> f;//判重用
int i,l,r;
int x,xx;
int fff=0;
struct haha
{
int pred;//存上一个在队列中的位置
char c;//存操作方式的
int n;//存当前状态的
int sum;//存当前操作的长度
} a[500000];
void digui(int k)
{
if (a[k].pred!=-1)digui(a[k].pred);
if (a[k].pred!=-1)printf("%c",a[k].c);
return;
}
void sc(int x)//输出
{
printf("%d\n",a[x].sum);
fff=1;
digui(x);
printf("\n");
return;
}
/**************************************************/
void aa(int k)//操作A
{
int an=k/10000;//第一行
int bn=k%10000;//第二行
int d=bn*10000+an;//第一行与第二行进行交换
if (f[d]==1) return;//去重
//printf("A:%d %d sum:%d\n",r+1,d,a[l].sum+1);
f[d]=1;//标记
r++;//入队
a[r].pred=l;//标记上一个
a[r].c='A';//标记为操作A
a[r].n=d;
a[r].sum=a[l].sum+1;//记操作次数
if (d==x) sc(r);//找到了就输出
return;
}

void bb(int k)//操作B
{
int an=k/10000;//第一行
int bn=k%10000;//第二行
an=(an%10)*1000+(an/10);//最后一列插入到第一列
bn=(bn%10)*1000+(bn/10);//最后一列插入到第一列
int d=an*10000+bn;
if (f[d]==1) return;//去重
//printf("B:%d %d sum:%d\n",r+1,d,a[l].sum+1);
f[d]=1;//标记
r++;//入队
a[r].pred=l;//标记上一个
a[r].c='B';//标记为操作B
a[r].n=d;
a[r].sum=a[l].sum+1;//记操作次数
if (d==x) sc(r);//找到了就输出
return;
}

void cc(int k)//操作C,好坑啊。
{
int an=k/10000;//第一行
int bn=k%10000;//第二行
int rr=an;//存an修改前的值
an=(an/1000*1000)/*第一位不变*/
+(bn/100%10*100)/*第二位来自第二行*/
+(an/100%10*10)/*第二位成第三位*/
+(an%10);/*最后一位不变*/
bn=(bn/1000*1000)/*第一位不变*/
+(bn%100/10*100)/*第三位变成第二位*/
+(rr%100/10*10)/*来自第一行的第三位*/
+(bn%10);/*最后一位不变*/
//这处理,我TM要炸了。
int d=an*10000+bn;
if (f[d]==1) return;//去重
//printf("C:%d %d sum:%d\n",r+1,d,a[l].sum+1);
f[d]=1;//标记
r++;//入队
a[r].pred=l;//标记上一个
a[r].c='C';//标记为操作B
a[r].n=d;
a[r].sum=a[l].sum+1;//记操作次数
if (d==x) sc(r);//找到了就输出
return;
}
/**************************************************/
int main()
{
int xxx=0;
for (i=1;i<=8;i++)
{
scanf("%d",&xx);//读入
xxx=xxx*10+xx;
}
x=xxx/10000;
xxx=xxx%10000;//保留最后四位
x=x*10000//前4位不变
+(xxx%10*1000)
+(xxx%100/10*100)
+(xxx/100%10*10)
+(xxx/1000);
if (x==12348765)//不需要变动
{
printf("0\n\n");
return 0;
}
//printf("x:%d\n",x);
f[12348765]=1;//标记
l=0;
r=1;
a[1].n=12348765;
a[1].pred=-1;

while (l!=r)
{
l++;
aa(a[l].n);//三种操作
if (fff==1) return 0;
bb(a[l].n);
if (fff==1) return 0;
cc(a[l].n);
if (fff==1) return 0;
}
return 0;
}

p1828 香甜的黄油 Sweet Butter

SPFA模板题。枚举放置糖果的位置。

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
/*
ID: ylx14274
PROG: butter
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,p,c;//n:奶牛数,p:牧场数,c:道路数
int x,a[801];//存每个点奶牛数量的
int ai,bi,ci,i;//读入用的和循环控制变量
int l,r,sum;//l:队首,r:队尾,sum:走的总距离
int d[801];//存最短路的。
int flag[801];//标记是否在队列中的
struct haha
{
int n;//存编号
int s;//存边权值
}f[801][800];
int s[801];//s[i]表示点i连的边的条数
int q[1600];
void in(int u,int v,int w)//插入
{
s[u]++;
s[v]++;
f[u][s[u]].n=v;//伪邻接表,将边存进去
f[u][s[u]].s=w;
f[v][s[v]].n=u;//双向边……
f[v][s[v]].s=w;
}
int main()
{
freopen("butter.in","r",stdin);
freopen("butter.out","w",stdout);
scanf("%d%d%d",&n,&p,&c);
for (i=1;i<=n;i++)
{
scanf("%d",&x);//读入牛的位置
a[x]++;//此位置的牛数量+1
}
for (i=1;i<=c;i++)
{
scanf("%d%d%d",&ai,&bi,&ci);//读入边
in(ai,bi,ci);//存起来
}
int Min=2333333;//min初始化
for (int ii=1;ii<=p;ii++)//枚举糖放置的位置
{
x=ii;//提出来
for (i=1;i<=p;i++)
{
d[i]=23333;
flag[i]=0;
}//初始化
d[x]=0;
l=0;//队列初始化
r=1;
q[r]=x;//x入队
flag[x]=1;//标记
while (l!=r)
{
l++;//出队
int xx=q[l];//挖出来
flag[xx]=0;//去标记
for (i=1;i<=s[xx];i++)//一个个点进行松弛操作
if (d[xx]+f[xx][i].s<d[f[xx][i].n])
{
d[f[xx][i].n]=d[xx]+f[xx][i].s;//更新
if (flag[f[xx][i].n]==0)//没在队列中
{
r++;//入队
q[r]=f[xx][i].n;
flag[f[xx][i].n]=1;//标记
}
}
}
sum=0;
for (i=1;i<=p;i++) sum=sum+a[i]*d[i];//求和
if (sum<Min) Min=sum;//比较
}
printf("%d\n",Min);//输出
return 0;
}