USACO 3.1

  • 最短网络 Agri-Net
  • 总分 Score Inflation
  • 丑数 Humble Numbers
  • 联系 Contact
  • 邮票 Stamps

P1546 最短网络 Agri-Net

prim

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
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

int g[310][310];
bool pd[310]={false};//0 is false;
int Min[310];
int Mst=0;
int main()
{
int n,m;
cin>>n;
for(int i=0;i<=300;i++)//将邻接矩阵赋初值
for(int j=1;j<=300;j++)
g[i][j]=2000000000;
for (int i=1;i<=n;i++)


for (int j=1;j<=n;j++)
scanf("%d",&g[i][j]);
for(int i=1;i<=309;i++)//最小权值数组赋初值
Min[i]=g[1][i];
pd[1]=1;
for(int i=1;i<n;i++)
{
int j;
int zuixiao=2000000000;
int zui;//zui存最小值的
for(j=1;j<=n;j++)//擂台比较找最小的
{
if(pd[j]==0)
if(zuixiao>Min[j])
{zuixiao=Min[j];zui=j;}
}
pd[zui]=1;//标记
Mst+=zuixiao;
for(int k=1;k<=n;k++)//更新
{
if(g[zui][k]<Min[k]&&pd[k]==0)
Min[k]=g[zui][k];
}

}
cout<<Mst;
}

P2722 总分 Score Inflation

裸的01背包,不不不,这道题其实是裸的完全背包,n是题目种类又不是题目数量,一种题可以有很多道的。

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
/*
ID: ylx14271
PROG: inflate
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,n,i,j;
int s,t,f[100000];
int main()
{
freopen("inflate.in","r",stdin);
freopen("inflate.out","w",stdout);
scanf("%d%d",&m,&n);
f[0]=0;
for (i=1;i<=n;i++)//s分数t耗时
{
scanf("%d %d",&s,&t);//读入
for (j=t;j<=m;j++)
if (f[j-t]+s>f[j]) f[j]=f[j-t]+s;//比较
}
printf("%d\n",f[m]);//输出
return 0;
}

P2723 丑数 Humble Numbers

听说暴力出奇迹?于是redbag打算找出很多个丑数然后排序输出第n个。然后看到n的数据范围惊呆了。
直接TLE啊。
由题可知,当前产生的第I个丑数f[i],是之前的某个丑数a[j],
某个丑数
a[j]需要>f[i-1],而且要尽可能的小。
于是我们就可以枚举j,然后找到最小的一个丑数使那个丑数a[j]>f[i-1];
三重循环还是会爆的样子。
但是,很容易发现满足条件的丑数x
a[j]>f[i-1],一定满足条件,xa[j]>f[i-2];于是我们就可以从满足xa[j]>f[i-2]的丑数x的位置往后枚举,找到满足条件x*a[j]>f[i-1]的丑数。
然后和min比较。
就可以把结果存进去输出了。

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
/*
ID: ylx14271
PROG: humble
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,i,j,m,k;
long long a[123],s[100011],f[100011];
int main()
{
freopen("humble.in","r",stdin);
freopen("humble.out","w",stdout);
scanf("%d%d",&k,&n);
for (i=1;i<=k;i++)
scanf("%d",&a[i]);//读入
f[0]=1;//假设1是丑数
for (i=1;i<=n;i++)//枚举n个丑数
{
m=2000000000;//赋初值,随便赋就好,赋大些
for (j=1;j<=k;j++)
{
//s[j]存的是a[j]至少与第几小丑数相乘才能得到一个比f[i-1]大的丑数
while (a[j]*f[s[j]]<=f[i-1]) s[j]++;//找到符合条件的最小的s[j];
if (a[j]*f[s[j]]<m) m=a[j]*f[s[j]];//比较
}
f[i]=m; //存起来
}
printf("%d\n",f[n]);
return 0;
}

P2724 联系 Contact

百度了很多题解,都有写到输出很坑。
然而我想说的是
输出太坑了。
usaco对格式要求太严格了。
输出完频率要换行。
输出6个序列要换行。
输出完序列要换行。
如果该频率的序列刚好是6个的话只要换一次行。
每行第一个序列之前不能有空格。
每行最后一个序列之后不能有空格。
关于排序
频率高的在前。
频率一样时,位数少的在前。
位数也一样时,字典序小的在前。
存的话用map来存每个序列对应的编号。
x[i/i为标号/].s存这个序列,x[i].a存频率。
然后才能不愉快的AC。

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: ylx14271
PROG: contact
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<string,int> s;
int a,b,n,i,j,k,len,ls,xx;
char ch;
char c[5000000];
struct haha
{
string s;
int a;
}x[100100];
int cmp(haha aa,haha bb)
{
if (aa.a>bb.a) return 1;//频率从小到大排序
if (aa.a==bb.a)//频率相等
{
if (aa.s.size()<bb.s.size())return 1;//长度短的在前
if (aa.s.size()==bb.s.size()&&aa.s<bb.s)return 1;//字典序小的在前
return 0;
}
return 0;
}
int main()
{
freopen("contact.in","r",stdin);
freopen("contact.out","w",stdout);
scanf("%d %d %d\n",&a,&b,&n);
while ((ch=getchar())!=EOF)//读入
{
if (ch=='1'||ch=='0')
{
len++;//len:统计位数的
c[len]=ch;//存起来
//len作为某个串的结尾,枚举开头
string ss="";
int B=max(len+1-b,1);//一定要比1大
for (i=len;i>=B;i--)
{
ss=c[i]+ss;//要加在前面,我就不用substr
if (len-i+1>=a)//长度>=a
{
if (s[ss]==0)//从未出现
{
ls++;
s[ss]=ls;//标记
x[s[ss]].s=ss;//储存
}
x[s[ss]].a++;//统计
}
}
}
}//尼玛要怎么输出啊 (╯▽╰),好坑
sort(x+1,x+ls+1,cmp);//从大到小排序
for (i=1;i<=ls;i++)
{//N个频率最高的序列要全部输出完才能退出
if (n==0&&x[i].a!=x[i-1].a) break;
if (x[i].a==x[i-1].a)//和上一个出现次数一样
{
if (xx%6==0) cout<<x[i].s;//每一行的开头不要加空格
else cout<<" "<<x[i].s;//否则就要加空格
xx++;
if (xx%6==0) printf("\n");//6个一换行
}
else
{
n--;//又输出了一个出现频率
if (i!=1&&xx%6!=0) printf("\n");
//出现之前那个频率的串,如果是6的倍数,结尾就换行了,在此就不用再换行了。
printf("%d\n",x[i].a);//输出完频率之后换行
cout<<x[i].s;//再输出串
xx=1;//重新统计
}
}
if (xx%6!=0) printf("\n");//如果最后一个数有6个的话,
return 0;
}

P2725 邮票 Stamps

完全背包,然后从头搜就可以了,

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
/*
ID: redbag
PROG: stamps
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 k,n,i,j,s,a;//k:总共消耗的邮票数
int f[2000000];//f[i]表示构成面值为i至少需要的邮票数
int main()
{
scanf("%d%d",&k,&n);
for (i=1;i<=2000000;i++) f[i]=2333;//标记
f[0]=0;//赋初值 ,用0张邮票可以构成0
for (i=1;i<=n;i++)
{
scanf("%d",&a);//读入
for (j=a;j<=2000000;j++)
if (f[j-a]+1<=k)//用的邮票数目在范围内
f[j]=min(f[j],f[j-a]+1);//取较小的
}
s=0;
for (i=1;i<=2000000;i++)//找从1开始 连续 的能取的集合的最后一个。
if (f[i]==2333)//凑不出了
{
s=i-1;//记录
break;//退出
}
printf("%d\n",s);//输出
return 0;
}