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)$
代码：
#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)$
代码：
#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})$
代码：
#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$是大写字母)
然后注意细节打就是了
代码：
#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分
我们考虑把工作按结束时间从小到大排序，然后分别把每个工作都放进一个小根堆里，如果堆满了，考虑把当前工作和堆顶比较替换
代码：
#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$的范围搞错了
代码：
#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
