总结：今天去了NOIP模拟赛，其实是几道USACO的经典的题目，第一题和最后一题都有思路，第二题是我一开始写了个spfa，写了一半中途发现应该是矩阵乘法，然后没做完，然后就没有然后了！第二题的暴力都没码QAQ 现在我来写解题报告了，有点饿了QAQ、、
第一题
题目 1: 架设电话线 [Jeffrey Wang, 2007]
最近，Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务，于
是，她们要求FJ把那些老旧的电话线换成性能更好的新电话线。新的电话线架设
在已有的N(2 <= N <= 100,000)根电话线杆上，第i根电话线杆的高度为
height_i米(1 <= height_i <= 100)。电话线总是从一根电话线杆的顶端被引到
相邻的那根的顶端，如果这两根电话线杆的高度不同，那么FJ就必须为此支付
C*电话线杆高度差(1 <= C <= 100)的费用。当然，你不能移动电话线杆，只能
按原有的顺序在相邻杆间架设电话线。
Farmer John认为，加高某些电话线杆能减少架设电话线的总花费，尽管这
项工作也需要支出一定的费用。更准确地，如果他把一根电话线杆加高X米的话
，他得为此付出X^2的费用。
请你帮Farmer John计算一下，如果合理地进行这两种工作，他最少要在这
个电话线改造工程上花多少钱。
程序名: telewire
输入格式:
* 第1行: 2个用空格隔开的整数：N和C
* 第2..N+1行: 第i+1行仅有一个整数：height_i
输入样例 (telewire.in):
5 2
2
3
5
1
4
输入说明:
一共有5根电话线杆，在杆间拉电话线的费用是每米高度差$2。在改造之前
，电话线杆的高度依次为2，3，5，1，4米。
输出样例:
* 第1行: 输出Farmer John完成电话线改造工程所需要的最小花费
输出样例 (telewire.out):
15
输出说明:
最好的改造方法是：Farmer John把第一根电话线杆加高1米，把第四根加
高
2米，使得它们的高度依次为3，3，5，3，4米。这样花在加高电线杆上的钱是
$5
。此时，拉电话线的费用为$2*(0+2+2+1) = $10，总花费为$15。
题解
一开始考场上看到这题我惊喜做过的，然后发现呵呵，原来USACO有两题架设电话线，不过没关系感觉这道题DP能水一点分数，我就一开始顺手码了个暴力的DP，最后是90分，TLE了一个点。【P.S点我去，我回家i7四核都跑不出90分，这成绩真的没问题?】我暴力DP的思路就是f[i][j]表示第i个电线杆高度为j时，此电线杆和之前所有电线杆还有架线的最小花费。这样时间复杂度是O（nh^2）。从估计来看，欸?明明应该是水过啊！好吧，复杂度多了一个0，水过个P啊！好吧，来讲一讲正解，正解的复杂度是O（nh）的，这样刚好比超时少一个0.f[i][j]表示前i个，为j的个数，f[i][j]=f[i-1][p]+abs(p-j)*c+(j-a[i])*(j-a[i]);然后记录两个数组low,high，转移。
代码
/*ZZ*/
#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=;
const int Maxh=;
int n,c;
int hi[Maxn+];
int f[Maxn+][Maxh+];
inline int remin(int a,int b){
if (a<b) return a;
return b;
}
inline int abs(int x){
if (x<) return -x;
return x;
}
int main(){
freopen("telewire.in","r",stdin);
freopen("telewire.out","w",stdout);
scanf("%d%d",&n,&c);
for (int i=;i<=n;i++) scanf("%d",&hi[i]);
memset(f,,sizeof(f));
for (int i=hi[];i<=Maxh;i++) f[][i]=(i-hi[])*(i-hi[]);
for (int i=;i<=n;i++){
for (int h=hi[i];h<=Maxh;h++){
for (int k=Maxh;k>=;k--){
if (f[i-][k]==f[][]) break;
f[i][h]=remin(f[i][h],f[i-][k]+abs(k-h)*c+(h-hi[i])*(h-hi[i]));
}
}
}
int Ans=;
for (int h=hi[n];h<=Maxh;h++){
Ans=remin(Ans,f[n][h]);
}
printf("%d\n",Ans);
return ;
}
90分代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[];
int dp[];
int a[];
int low[];
int high[];
int c;
int n;
int p;
int ans=-;
int abs(int x)
{
if(x>)return x;
return -x;
}
int sum;
int main()
{
freopen("telewire.in","r",stdin);
freopen("telewire.out","w",stdout);
scanf("%d%d",&n,&c);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
p=max(p,a[i]);
if(i>)sum+=c*abs(a[i]-a[i-]);
}
sum=sum+;
for(int i=;i<a[];i++)
dp[i]=sum;
for(int i=a[];i<=p;i++)
dp[i]=(i-a[])*(i-a[]);
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
{
f[j]=dp[j];
dp[j]=low[j]=high[j]=sum;
}
low[]=f[];
for(int j=;j<=;j++)
{
low[j]=min(low[j-],f[j]-c*j);
}
high[]=f[]+*c;
for(int j=;j>=;j--)
{
high[j]=min(high[j+],f[j]+c*j);
}
for(int j=a[i];j<=;j++)
{
dp[j]=min(high[j]-c*j,low[j]+c*j)+(j-a[i])*(j-a[i]);
// cout<<i<<" "<<j<<" "<<dp[j]<<endl;
}
}
for(int i=a[n];i<=;i++)
if(ans==- || dp[i]<ans)ans=dp[i];
printf("%d\n",ans);
return ;
}
100分代码
第二题
题目 2: 奶牛接力 [Erik Bernhardsson, 2003]
FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目
。至于进行接力跑的地点，自然是在牧场中现有的T(2 <= T <= 100)条跑道
上。
农场上的跑道有一些交汇点，每条跑道都连结了两个不同的交汇点I1_i和
I2_i(1 <= I1_i <= 1,000; 1 <= I2_i <= 1,000)。每个交汇点都是至少两条跑
道的端点。奶牛们知道每条跑道的长度length_i(1 <= length_i <= 1,000)，以
及每条跑道连结的交汇点的编号。并且，没有哪两个交汇点由两条不同的跑道直
接相连。你可以认为这些交汇点和跑道构成了一张图。
为了完成一场接力跑，所有N头奶牛在跑步开始之前都要站在某个交汇点上
（有些交汇点上可能站着不只1头奶牛）。当然，她们的站位要保证她们能够将
接力棒顺次传递，并且最后持棒的奶牛要停在预设的终点。
你的任务是，写一个程序，计算在接力跑的起点(S)和终点(E)确定的情况下
，奶牛们跑步路径可能的最小总长度。显然，这条路径必须恰好经过N条跑道。
程序名: relays
输入格式:
* 第1行: 4个用空格隔开的整数：N，T，S，以及E
* 第2..T+1行: 第i+1为3个以空格隔开的整数：length_i，I1_i，以及I2_i，
描
述了第i条跑道。
输入样例 (relays.in):
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9
输出格式:
* 第1行: 输出1个正整数，表示起点为S、终点为E，并且恰好经过N条跑道的路
径的最小长度
输出样例 (relays.out):
10
题解
这道题我当时真的是一点思路都没有啊，感觉只能搜索，但是点那么多边只有100真的很可疑啊！我先写了一个spfa，然后感觉不太对，又写了矩阵乘法！其实应该是正解了，但是我没调完就结束了QAQ，我就再次贴上网上的一个矩阵乘法的思路：题目求i,j之间边数恰为N的最短路径（边可以重复走），我们知道线性代数中有：01邻接矩阵A的K次方C=A^K，C[i][j]表示i点到j点正好经过K条边的路径数。而floyd则是每次使用一个中间点k去更新i,j之间的距离，那么更新成功表示i,j之间恰有一个点k时的最短路，如果做N次floyd那么不就是i,j之间借助N个点时的最短路了？考虑当a[i][k]+a[k][j]<c[i][j]的时候，c[i][j]=a[i][k]+a[k][j]，这样c[i][j]保存了i,j之间有一个点的最短路，第二次将c[i][j]拷贝回到a[i][j]当中，并将c[i][j]重新置为INF，再做一次，则是在原来的基础上在i,j之间再用一个点k来松弛，这时候i,j之间实际上已经是两个点了，之后重复这么做就好了，可以利用二进制加速。其实，我们当时考试有人用暴力瞎搞搞也就弄出来了QAQ这、、、、、赫赫！
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std ;
typedef long long LL ;
const double eps(1e-) ;
const int inf(0x3f3f3f3f) ;
int n,t,s,e;
struct N{
int x,y,z;
}a[];
int to[];
set<int> S;
int siz;
int mul[][];
int map[][];
void p(int a[][],int b[][]){
static int c[][];
memset(c,0x3f,sizeof c);
for(int i=;i<=siz;i++){
for(int j=;j<=siz;j++){
for(int k=;k<=siz;k++){
c[i][j]=min(a[i][k]+b[k][j],c[i][j]);
}
}
}
memcpy(a,c,sizeof map);
}
int main(){
freopen("relays.in","r",stdin) ;
freopen("relays.out","w",stdout) ;
scanf("%d%d%d%d",&n,&t,&s,&e);
S.insert(s);S.insert(e);
for(int i=;i<t;i++){
scanf("%d%d%d",&a[i].z,&a[i].x,&a[i].y);
S.insert(a[i].x);S.insert(a[i].y);
}
for(set<int>::iterator it=S.begin();it!=S.end();++it){
to[*it]=++siz;
}
memset(map,0x3f,sizeof map);
for(int i=;i<t;i++){
map[to[a[i].y]][to[a[i].x]]=map[to[a[i].x]][to[a[i].y]]=min(map[to[a[i].x]][to[a[i].y]],a[i].z);
}
memcpy(mul,map,sizeof map);
int k=n-;
while(k){
if(k&) p(map,mul);
p(mul,mul);
k>>=;
}
printf("%d\n",map[to[s]][to[e]]);
return ;
}
矩阵乘法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[][];
struct node
{
int len;
int x;
int y;
}g[];
const int inf=2e9+;
struct srt
{
int val;
int id;
}sr[];
int cnt,used[];
int final[];
int main()
{
freopen("relays.in","r",stdin);
freopen("relays.out","w",stdout);
int n,m,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&g[i].len,&g[i].x,&g[i].y);
used[g[i].x]=;
used[g[i].y]=;
}
for(int i=;i<=;i++)
{
if(used[i])
{
sr[cnt].val=i;
sr[cnt].id=cnt;
cnt++;
}
}
for(int i=;i<=cnt;i++) final[sr[i].val]=sr[i].id;
for(int i=;i<=m;i++)
{
g[i].x=final[g[i].x]+;
g[i].y=final[g[i].y]+;
}
int cur=;
s=final[s]+;
t=final[t]+;
for(int i=;i<=m;i++) f[][i]=f[][i]=inf;
f[][s]=;
//离散化
for(int i=;i<=n;i++)
{
int pre=-cur;
for(int j=;j<=m;j++)
{
int start=g[j].x,end=g[j].y,dis=g[j].len;
if(f[pre][start]+dis<f[cur][end]) f[cur][end]=f[pre][start]+dis;
if(f[pre][end]+dis<f[cur][start]) f[cur][start]=f[pre][end]+dis;
}
cur=-cur;
for(int j=;j<=m;j++) f[pre][j]=inf;
}
printf("%d\n",f[-cur][t]);
//暴力
return ;
}
某暴力瞎搞搞
第三题
题目 3: 分配防晒霜 [Russ Cox, 2001]
奶牛们计划着去海滩上享受日光浴。为了避免皮肤被阳光灼伤，所有C(1 <=
C <= 2500)头奶牛必须在出门之前在身上抹防晒霜。第i头奶牛适合的最小和最
大的SPF值分别为minSPF_i和maxSPF_i(1 <= minSPF_i <= 1,000; minSPF_i <=
maxSPF_i <= 1,000)。如果某头奶牛涂的防晒霜的SPF值过小，那么阳光仍然能
把她的皮肤灼伤；如果防晒霜的SPF值过大，则会使日光浴与躺在屋里睡觉变得
几乎没有差别。
为此，奶牛们准备了一大篮子防晒霜，一共L(1 <= L <= 2500)瓶。第i瓶
防
晒霜的SPF值为SPF_i(1 <= SPF_i <= 1,000)。瓶子的大小也不一定相同，第i
瓶
防晒霜可供cover_i头奶牛使用。当然，每头奶牛只能涂某一个瓶子里的防晒霜
，而不能把若干个瓶里的混合着用。
请你计算一下，如果使用奶牛们准备的防晒霜，最多有多少奶牛能在不被灼
伤的前提下，享受到日光浴的效果？
程序名: tanning
输入格式:
* 第1行: 2个用空格隔开的整数：C和L
* 第2..C+1行: 第i+1行给出了适合第i头奶牛的SPF值的范围：minSPF_i以及
maxSPF_i
* 第C+2..C+L+1行: 第i+C+1行为了第i瓶防晒霜的参数：SPF_i和cover_i，两个
数间用空格隔开。
输入样例 (tanning.in):
3 2
3 10
2 5
1 5
6 2
4 1
输入说明:
一共有3头奶牛，2瓶防晒霜。3头奶牛适应的SPF值分别为3..10，2..5，以
及1..5。2瓶防晒霜的SPF值分别为6（可使用2次）和4（可使用1次）。可能的分
配方案为：奶牛1使用第1瓶防晒霜，奶牛2或奶牛3使用第2瓶防晒霜。显然，最
多只有2头奶牛的需求能被满足。
输出格式:
* 第1行: 输出1个整数，表示最多有多少头奶牛能享受到日光浴
输出样例 (tanning.out):
2
题解
这道题我用贪心A掉了，相对两个maxSPF一样的牛cow1与cow2，若cow1的minSPF<cow2的minSPF，那么对于一瓶cow1能用的防晒霜，cow2也能用，因为对于答案的贡献都是1，所以给谁都可以，但是若cow2能用的防晒霜cow1未必能用，所以cow1能用应优先给cow1.所以对于所有的牛maxSPF第一关键字升序，minSPF第二关键字降序，然后防晒霜升序，能给就给，贪心就好！考场里还有人用了别的做法->网络流，这个建图是十分显而易见的，复杂度也完全能过。【NOIP模拟赛你们确定要用网络流虐？】
代码
/*ZZ*/
#include<cstdio>
#include<algorithm>
using namespace std;
int n,l;
struct Crow{
int max;
int min;
};
Crow c[];
struct Spf{
int spf;
int num;
};
Spf s[];
inline bool cmp(Crow a,Crow b){
if (a.max<b.max) return true;
if (a.max==b.max && a.min>b.min) return true;
return false;
}
int main(){
freopen("tanning.in","r",stdin);
freopen("tanning.out","w",stdout);
scanf("%d%d",&n,&l);
for (int i=;i<=n;i++) scanf("%d%d",&c[i].min,&c[i].max);
for (int i=;i<=l;i++) scanf("%d%d",&s[i].spf,&s[i].num);
sort(c+,c+n+,cmp);
int index;
int Ans=;
for (int i=;i<=n;i++){
index=-;
for (int j=;j<=l;j++){
if (s[j].num> && c[i].min<=s[j].spf && s[j].spf<=c[i].max){
if (index==-){
index=j;
}else{
if (s[j].spf<s[index].spf) index=j;
}
}
}
if (index!=-){
Ans++;
s[index].num--;
}
}
printf("%d\n",Ans);
return ;
}
贪心做法
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define inf 19991231
using namespace std;
int n,l;
int s,t;
int ans=;
int res;
int f[];
int a[];
int b1[],b2[];
struct node
{
int val;
int opp;
int to;
};
vector <node> v[];
int d[];
void add(int x,int y,int val)
{
node tmp;
tmp.to=y;tmp.val=val;tmp.opp=v[y].size();
v[x].push_back(tmp);
tmp.to=x;tmp.val=;tmp.opp=v[x].size()-;
v[y].push_back(tmp);
}
bool make_level()
{
for(int i=;i<=t;i++)d[i]=-;
d[]=;
queue <int> q;
q.push();
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=;i<v[x].size();i++)
{
if(d[v[x][i].to]==- && v[x][i].val>)
{
d[v[x][i].to]=d[x]+;
q.push(v[x][i].to);
}
}
}
return d[t]!=-;
}
int dfs(int x,int cap)
{
if(x==t)return cap;
int r=;
for(int i=;i<v[x].size();i++)
{
if(d[v[x][i].to]==d[x]+ && v[x][i].val>)
{
int what=min(v[x][i].val,cap-r);
what=dfs(v[x][i].to,what);
r+=what;
v[x][i].val-=what;
v[v[x][i].to][v[x][i].opp].val+=what;
}
}
if(!r)d[x]=-;
return r;
}
int main()
{
freopen("tanning.in","r",stdin);
freopen("tanning.out","w",stdout);
scanf("%d%d",&n,&l);
s=;
t=n+l+;
for(int i=;i<=n;i++)
{
scanf("%d%d",&b1[i],&b2[i]);
add(l+i,t,);
}
for(int i=;i<=l;i++)
{
int x;
scanf("%d%d",&a[i],&x);
add(s,i,x);
}
for(int i=;i<=l;i++)
{
for(int j=;j<=n;j++)
{
if(a[i]>=b1[j] && a[i]<=b2[j])
{
add(i,j+l,);
}
}
}
while(make_level())
{
ans+=dfs(s,inf);
}
printf("%d\n",ans);
return ;
}
网络流做法