USACO 精选试题 水题大杂烩

USACO 精选试题解题报告……
水题不再另开文章,有意义的题目还是要另开的

第1题 利润 (Profits, USACO 2011 Jan)
(没在Bzoj上找到这题)
解法:DP最大子段和
复杂度:$O(n)$
代码:略


第2题 购买饲料二 (Buying Feed II, USACO 2010 Jan)
解法:DP(还有时间复杂度更优秀的贪心,但是DP也能过,贪心是把每个店的单价都硬求)
设$dp(i,j)$为走了$i$公里,买了$j$吨饲料的最小费用,转移分该坐标有没有商店来做,注意这样做有一个坑一个点上有很多商店,所以复杂度多加一个$n$
复杂度:$O(EK^2N)$
代码:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int k, e, n;
struct data {
int x, c, f;
}d[105];
LL dp[355][105];
void clean() {
ms(dp, 127);
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &d[i].x, &d[i].f, &d[i].c);
}
dp[0][0] = 0;
for (int i = 1; i <= e; i++) {
for (int j = 0; j <= k; j++) {
int flag = false;
for (int oo = 1; oo <= n; oo++)
if (d[oo].x == i) {
flag = true;
for (int orz = 0; orz <= min(j, d[oo].f); orz++) dp[i][j] = min(dp[i][j], dp[i - 1][j - orz] + d[oo].c * orz + j - orz);
} else if (!flag) dp[i][j] = dp[i - 1][j] + j;
}
}
printf("%lld\n", dp[e][k]);
}
int main() {
scanf("%d%d%d", &k, &e, &n), solve();
return 0;
}

第3题 奶牛杂技 (Cow Acrobats, USACO 2006 Nov)
解法:贪心,排序比较函数为$w+s$
复杂度:$O(nlogn)$
代码:略


第4题 抓苹果 (Apple Catching, USACO 2004 Nov)
解法:DP
代码:略


第5题 抢购干草 (Hay For Sale, USACO 2008 Dec)
解法:裸背包DP
代码:略


第6题 建造栅栏 (Building A Fence, USACO 2008 Oct)
解法:DP,四边形三边之和大于第四边
代码:略


第7题 建造道路 (Building Roads, USACO 2007 Dec)
解法:裸最小生成树
代码:略


第8题 青铜莲花池 (Bronze Lilypad Pond, USACO 2007 Feb)
解法:基础BFS
代码:略


第9题 滑雪课程 (Ski Lessons, USACO 2009 Open)
解法:DP
代码:略


第10题 奶牛飞盘队 (Cow Frisbee Team, USACO 2009 Mar)
解法:DP
设$dp(i,j)​$为前$i​$个物品,组成和模$f​$的方案数
$dp(i,j)+=dp(i-1,j), dp(i,(j+a_i)\%f) +=dp(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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 2000 + 5, MAXF = 1000 + 5, MO = 1e8;
int n, f, dp[MAXN][MAXF], a[MAXN];
void clean() {
ms(dp, 0);
}
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
dp[i][a[i] % f] = 1;
for (int j = 0; j < f; j++) {
dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MO;
dp[i][(j + a[i]) % f] = (dp[i][(j + a[i]) % f] + dp[i - 1][j]) % MO;
}
}
printf("%d\n", dp[n][0]);
}
int main() {
scanf("%d%d", &n, &f), solve();
return 0;
}


第11题 奶牛博览会 (Cow Exhibition, USACO 2003 Fall)
解法:背包DP,最好用一维数组
代码:略


第12题 最近回文 (Cheapest Palindrome, USACO 2007 Open)
解法:区间DP
设$dp(i,j)$为把区间$[i,j]$变为回文串的最小花费。
观察到删除一个数和加上一个数是等价操作,因为要构成回文串,不是将对应的字母补上,就是将这个字母删掉,所以取$cst_i=min(addv, delv)$,即转移方程:
当$s_i==s_j$时,$dp(i,j)=min(dp(i+1,j-1))$
否则$dp(i,j)=min(dp(i+1,j)+cst_{s_i}, dp(i,j-1)+cst_{s_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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXM = 2000 + 5, INF = 1000000000;
int n, m, cst[30], f[MAXM][MAXM];
char s[MAXM];
char getc() {
char ch = getchar();
while (!('a' <= ch && ch <= 'z')) ch = getchar();
return ch;
}
int dp(int l, int r) {
if (f[l][r] >= 0) return f[l][r];
if (l >= r) return f[l][r] = 0;
int tmp = INF;
if (s[l] == s[r]) tmp = min(tmp, dp(l + 1, r - 1));
tmp = min(tmp, dp(l + 1, r) + cst[s[l] - 'a']);
tmp = min(tmp, dp(l, r - 1) + cst[s[r] - 'a']);
return f[l][r] = tmp;
}
void clean() {
ms(f, -1);
}
void solve() {
clean();
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
int x = getc() - 'a';
int a, b; scanf("%d%d", &a, &b);
cst[x] = min(a, b);
}
printf("%d\n", dp(1, m));
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}


第13题 安慰奶牛 (Cheering up the Cows, USACO 2008 Nov)
解法:最小生成树,边权改为两端节点权+边权$\times 2$,然后最后答案还要加上起点,在$n$个点里找一个最小的即可。
代码:略


第14题 玉米迷宫 (Corn Maze, USACO 2011 Open)
解法:裸Bfs
代码:略


第15题 奶牛集会 (MooFest, USACO 2004 Open)
解法:Bzoj 3378
代码:Bzoj 3378


第16题 奶牛文字 (Cowlphabet, USACO 2011 Feb)
解法:DP
设$dp(i,j,k)$为小写$i$个,大写$j$个的方案数
初值$dp(1,0,k)=1$,$k$是小写字母,$dp(0,1,k)=1$,$k$是大写字母
$dp(i,j,k)=\sum dp(i-1,j,s)(k$是小写字母)
$dp(i,j,k)=\sum dp(i,j-1,s)(k$是大写字母)
然后注意细节打就是了
代码:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MO = 97654321;
vector<int> G[60];
int u, l, p;
LL f[255][255][60];
int getIDfromChar(char ch) {
if ('a' <= ch && ch <= 'z') return ch - 'a';
if ('A' <= ch && ch <= 'Z') return ch - 'A' + 26;
}
char getc() {
char ch = getchar();
while (!('a' <= ch && ch <= 'z') && !('A' <= ch && ch <= 'Z')) ch = getchar();
return getIDfromChar(ch);
}
int dp(int i, int j, int k) {
if (i < 0 || j < 0) return 0;
if (f[i][j][k] >= 0) return f[i][j][k];
int tmp = 0;
for (int orz = 0; orz < G[k].size(); orz++) {
int s = G[k][orz];
if (k < 26) tmp = (tmp + dp(i - 1, j, s)) % MO; else tmp = (tmp + dp(i, j - 1, s)) % MO;
}
return f[i][j][k] = tmp;
}
void clean() {
for (int i = 0; i < 60; i++) G[i].clear();
ms(f, -1);
}
void solve() {
clean();
for (int i = 1; i <= p; i++) {
int a = getc(), b = getc();
G[a].push_back(b);
}
for (int i = 0; i < 26; i++) f[1][0][i] = 1;
for (int i = 26; i < 52; i++) f[0][1][i] = 1;
LL ans = 0;
for (int i = 0; i < 52; i++) ans = (ans + dp(l, u, i)) % MO;
printf("%lld\n", ans);
}
int main() {
scanf("%d%d%d", &u, &l, &p), solve();
return 0;
}


第17题 奶牛跨栏 (Cow Hurdles, USACO 2007 Nov)
解法:Bzoj 1641
代码:Bzoj 1641


第18题 工作安排 (Work Scheduling, USACO 2009 Open)
解法:贪心+堆
和有题射兔子的差不多,但是效仿那个做法复杂度不对,这里时间戳$10^9$,只有75分
我们考虑把工作按结束时间从小到大排序,然后分别把每个工作都放进一个小根堆里,如果堆满了,考虑把当前工作和堆顶比较替换
代码:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1e5 + 5;
struct data {
int d, p;
bool operator < (const data &b) const {
return p > b.p;
}
}jb[MAXN];
bool cmp(const data &a, const data &b) {
return a.d < b.d;
}
int n;
void clean() {
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%d%d", &jb[i].d, &jb[i].p);
}
sort(jb + 1, jb + 1 + n, cmp);
LL ans = 0;
priority_queue<data> pq;
pq.push(jb[1]), ans += jb[1].p;
for (int i = 2; i <= n; i++) {
if (pq.size() >= jb[i].d) {
if (jb[i].p > pq.top().p) {
ans += jb[i].p - pq.top().p, pq.pop(), pq.push(jb[i]);
}
} else pq.push(jb[i]), ans += jb[i].p;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d", &n), solve();
return 0;
}


第19题 手机网络 (Cell Phone Network, USACO 2008 Jan)
解法:Bzoj 1596
代码:Bzoj 1596


第20题 提交作业 (Turning in Homework, USACO 2004 Open)
//暂放


第21题 滑雪缆车 (Ski Lift, USACO 2006 Mar)
//暂放


第22题 派发巧克力 (Chocolate Giving, USACO 2010 Feb)
解法:SPFA
代码:略


第23题 赞助学费 (Financial Aid, USACO 2004 Mar)
解法:堆+贪心
先把原数组按照$C$排序,然后用堆维护前$k$小的值的和,求出每个数的左右两边$n/2$个数的最小费用$ls, rs$,然后枚举一下答案,可以二分,但是并无多大用处,注意这题$n$和$c$,之前就把$c$的范围搞错了
代码:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXC = 200000 + 5;
struct data {
LL ci, fi;
bool operator < (const data &b) const {
return ci < b.ci;
}
}cow[MAXC];
int n, c, f, ws;
LL ls[MAXC], rs[MAXC];
priority_queue<int> pq;
void clean() {
ms(ls, 127), ms(rs, 127);
}
void solve() {
clean();
ws = n / 2;
for (int i = 1; i <= c; i++) scanf("%lld%lld", &cow[i].ci, &cow[i].fi);
sort(cow + 1, cow + 1 + c);
while (!pq.empty()) pq.pop();
int s = 0;
for (int i = 1; i <= ws; i++) pq.push(cow[i].fi), s += cow[i].fi;
for (int i = ws + 1; i <= c; i++) {
ls[i] = s;
if (cow[i].fi < pq.top()) {
s -= pq.top(), s += cow[i].fi;
pq.pop(), pq.push(cow[i].fi);
}
}
while (!pq.empty()) pq.pop();
s = 0;
for (int i = c - ws + 1; i <= c; i++) pq.push(cow[i].fi), s += cow[i].fi;
for (int i = c - ws; i > 0; i--) {
rs[i] = s;
if (cow[i].fi < pq.top()) {
s -= pq.top(), s += cow[i].fi;
pq.pop(), pq.push(cow[i].fi);
}
}
LL ans = -1;
/*int l = 1, r = c + 1;
while (l < r) {
int mid = (l + r) / 2;
if (ls[mid] + cow[mid].fi + rs[mid] <= f) {
ans = max(ans, cow[mid].ci);
l = mid + 1;
} else r = mid;
}*/
for (int i = c; i > 0; i--) {
if (ls[i] + cow[i].fi + rs[i] <= f) {
ans = max(ans, cow[i].ci);
break;
}
}
printf("%lld\n", ans);
}
int main() {
while (scanf("%d%d%d", &n, &c, &f) == 3) solve();
return 0;
}


第24题 白银莲花池 (Silver Lilypad Pond, USACO 2007 Feb)
//暂放


第25题 地震 (Earthquake, USACO 2001 Open)
//到处都找不到这题,先暂放


第26题 股票市场 (Stock Market, USACO 2009 Feb)
解法:
代码:


第27题 奶牛赛车 (Cow Cycling, USACO Feb 2002)
解法:
代码:


第28题 奶牛观光 (Sightseeing Cows, USACO 2007 Dec)
解法:Bzoj 1960
代码:Bzoj 1960


第29题 道路重建 (Rebuilding Roads, USACO Feb 2002)
解法:Poj 1947
代码:Poj 1947

------ 本文结束 ------