这次的题目好难好BT啊囧。。。
30：这题是水题。。
50：个人感觉是二进制位数-最后一位位置+1不知道为什么错了一个点
70：模拟题，我好像模拟烂了。。只有49分囧。。
100：给空间中n个点，定义距离为三个纬度中最短的差，求最小生成树，想了半天想了个很复杂的算法，算法度很难估计，只好上暴力，居然有50分晕。。
120：这题我看到题目中说有60%的数据n,m<=300，于是对于每个点先枚举斜着走的方向，再分别统计，是n*m*(n+m)的。。得了60分。。
150：去死吧。。根本不会。一开始我想是不是用随机化骗点分。。但是太困了编不下去了囧。。。
最后得了234分。。太菜了。。悲剧。。
哎。。买了台HD2。。真是帅呆了。。实际上WM也不错啊。。
不过还是暑假的时候去把这个刷成Android吧。。
PS。。最近好像什么OJ都挂了。。VIJOS，八中OJ，连PKU都不能上了囧。。

acmicpc-live-archive.uva.es/nuevoportal/
题目在UVA上。。。
这道题首先可以列个Dp方程出来
设F[n]为还有n次就要以a价格卖出的最大期望收入，那么
F[n]=Max{ (p-F[n-1])/(1+(p-a)^b) }+F[n-1]…p为大于a的整数。。
由于决策有无限个。。一般的Dp都悲剧了。。
一开始我用微积分算出这个式子关于p的导数，然后想直接用数学方法求出最大值，失败了。。
不过我根据数学观察发现这个导数是单调递减的，也就是说这个函数是单峰的，
于是就可以二分搜索出最大值囧。。。
额。。看来前段时间苦学数学也是有好处的囧。。。
Code：
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=100+1,inf=~0U>>2;
int n,a;double b,F[maxn];
int main()
{
//freopen("in","r",stdin);
for(int num=1;;num++)
{
cin>>n>>a>>b;if(!n)break;
F[0]=a;n–;
for(int i=1;i<=n;i++)
{
int l=a+1,r=inf;
#define get(p) (p-F[i-1])/(1+pow(p-a,b))
while(l+1<r)
{
int m=(l+r)/2;
if(get(m+1)-get(m)>=0)
l=m;
else
r=m;
}
F[i]=max(get(l),get(r))+F[i-1];
}
printf("Case %d: %0.2lfn",num,F[n]);
}
}

题目在UVA上。http://acm.uva.es/archive/nuevoportal/
一开始我的想法是搜索。。然后写了N个剪枝。。搞的累死。。结果却发现根本不行。。
我测了一下发现一组数据差不多0.2s。。但这玩意数据多的吓人。。TLE。。。
后来我感觉应该从这么多数据中找共同点。就是预处理一下。。
由于棋盘是一样的，所以能放的状态是有限的，
所有状态可以用它能分别放B-Y的个数和其需要的布数来表示，
只有步数最小的才予以考虑，那么只要开个4维数组记录所有状态就可以了。。、
由于没有剪枝，暴力搜出所有状态需要4s+。。但之后只要枚举4种颜色的个数就OK了。。
所以程序飞快，AC了(*^__^*) 嘻嘻
Code：
#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1;using namespace std;int D[10][10][10][10]={0};int w[4],W,cnt=0;int a[4]={0};int M[3][3]={0};bool check[4];const int di[]={0,1,0,-1},dj[]={1,0,-1,0};inline bool Legal(int i,int j){ return i>=0&&i<3&&j>=0&&j<3;}void Fill(int p,int i,int j,int s){ //cout<<p<<" "<<i<<" "<<j<<" "<<s<<endl; if(p==4) { int&x=D[a[0]][a[1]][a[2]][a[3]]; if(!x||x>s)x=s;cnt++; return; } if(i==3) { Fill(p+1,0,0,s); return; } int ii,jj; memset(check,0,sizeof(check)); rep(d,4) { ii=di[d]+i;jj=dj[d]+j; if(Legal(ii,jj)&&M[ii][jj]) check[M[ii][jj]-1]=true; } if(j==2)ii=i+1,jj=0; else ii=i,jj=j+1;bool c=true; rep(x,p)if(!check[x])c=false; Fill(p,ii,jj,s);if(!c)return; int om=M[i][j]; M[i][j]=p+1; a[p]++;if(om)a[om-1]–; Fill(p,ii,jj,s+1); a[p]–;if(om)a[om-1]++; M[i][j]=om;}int main(){ //freopen("in","r",stdin); Fill(0,0,0,0); for(int num=1;;num++) { rep(i,4)cin>>w[i];if(!w[0])break; cin>>W; int ans=100,s=0; for(int a=0;a<=9;a++) { s+=a*w[0]; for(int b=0;a+b<=9;b++) { s+=b*w[1]; for(int c=0;a+b+c<=9;c++) { s+=c*w[2]; for(int d=0;a+b+c+d<=9;d++) { s+=d*w[3];int x=D[a][b][d]; //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<s<<" "<<x<<endl; if(x&&s>=W)ans<?=x; s-=d*w[3]; } s-=c*w[2]; } s-=b*w[1]; } s-=a*w[0]; } cout<<"Case "<<num<<": "; if(ans==100)cout<<"Impossible"<<endl; else cout<<ans<<endl; }}

看了看WF 2010的题目。。发现好难啊天哪。。我真是太弱菜啦悲剧。。。
Problem A:
烦的跟鬼一样的模拟题，而且情况很多。。我好不容易搞懂了题目已经半疯了。。

Problem C：
离散化一下。。然后倒过来求出能到达终点的面积就OK了。。

Problem E：
这到题是裸的带连通性的状态压缩问题啊，直接上状态压缩Dp。。为了重建路径干脆把路径保存在状态里面好了。反正空间够的。。

Problem G:
还算简单的动归题。。。

Problem I:
有点意思饿。。就是一个n*m的图，给你三个点以及它们必须在那个次序到达，让你统计满足这个条件的从左上角到左下角的路径数。。说白了还是带连通性的状态压缩问题。。关键是要记录一些附加的量，然后转移的时候小心一点就可以了。。。

Problem J:
这道题说的是给你一个X*Y的矩阵，然后让你用切割的办法（每次必须一刀或横或竖切成两块）分成N块，面积分别为你的N个朋友的要求面积。。
1<=X,Y<=100,N<=15。。很显然要Dp。。状态就是当前矩形的长宽，还有当前矩形要切出的子集。。但是这样的话状态会很多。。实际上不多，因为当前矩形的面积一定等于当前子集的和。所以开个Map保存所有状态就OK了。。

[Usaco2008Nov]安慰奶牛cheer

Time Limit:10000MS Memory Limit:165536K
Total Submit:18 Accepted:15
Case Time Limit:1000MS

Description

Farmer John变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接N
(5 <= N <= 10,000)个牧场, 牧场被连续地编号为1..N. 每一个牧场都是一个奶牛的家.
FJ计划除去P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间
的连通性. 你首先要决定那些道路是需要保留的N-1条道路.

第j条双向道路连接了牧场S_j和E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j),
而且走完它需要L_j (0 <= L_j <= 1,000)的时间. 没有两个牧场是被一条以上的道路所连接.

奶牛们非常伤心, 因为她们的交通系统被削减了. 你需要到每一个奶牛的住处去安慰她们. 每次
你到达第i个牧场的时候(即使你已经到过), 你必须花去C_i (1 <= C_i <= 1,000)的
时间和奶牛交谈.

你每个晚上都会在同一个牧场(这是供你选择的)过夜, 直到奶牛们都从悲伤中缓过神来. 在早上
起来和晚上回去睡觉的时候, 你都需要和在你睡觉的牧场的奶牛交谈一次. 这样你才能完成你的
交谈任务.

假设Farmer John采纳了你的建议, 请计算出使所有奶牛都被安慰的最少时间.

对于你前10次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.

程序名: cheer

Input

* 第 1 行: 用空格隔开的两个整数N和P
* 第 2..N+1 行: 第i+1行包含了一个整数: C_i
* 第 N+2..N+P+1 行: 第 N+j+1 行包含用空格隔开的三个整数: S_j, E_j 和 L_j

Output

第 1 行: 一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间).

Sample Input

Sample Output

Source
饿..这道题还是有点意思的…首先要我们求一个生成树..那么尝试着转化成最小生成树问题,对于每条边,如果选的话,则要耗去来回一趟和访问2个端点的时间,重加一下权就可以了,最后选择最小的哪个节点当出发点就行了。..
Code:

#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000;int n,m;struct uf{ int F[maxn]; uf(){rep(i,n)F[i]=i;} int Find(int i) { return i==F[i]?i:(F[i]=Find(F[i])); } bool Find(int i,int j) { i=Find(i);j=Find(j); return F[i]=j,i!=j; }};struct Edge{ int s,t,c; Edge(int _s,int _t,int _c):s(_s),t(_t),c(_c){} bool operator<(const Edge&o)const { return c>o.c; }};priority_queue<Edge> PQ;int C[maxn];int main(){ //freopen("in","r",stdin); cin>>n>>m;int s,t,c,ans=~0U>>1; rep(i,n)scanf("%d",C+i),ans<?=C[i]; rep(i,m)scanf("%d%d%D",&s,&t,&c),–s,–t,PQ.push(Edge(s,t,c*2+C[s]+C[t])); uf U; while(n>1) { Edge e=PQ.top();PQ.pop(); if(U.Find(e.s,e.t)) ans+=e.c,n–; } cout<<ans<<endl;}176输出解释:保持这些路径: 1-(5)-2-(5)-3 5 / (12) /(12) *4——+从牧场4起床, 然后按照 4, 5, 4, 2, 3, 2, 1, 2, 4 的顺序来访问奶牛们, 总共需要176个单位的时间.5 71010206301 2 52 3 52 4 123 4 172 5 153 5 64 5 12输入解释: +-(15)-+ / / 1-(5)-2-(5)-3-(6)–5 /(17) / (12) / /(12) 4——+

[HNOI2003]激光炸弹

Time Limit:10000MS  Memory Limit:165536K
Total Submit:49 Accepted:20
Case Time Limit:1000MS

Description

一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标，用整数Xi,Yi(其值在 [0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的 正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。 0

Input

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示

Output

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

Sample Input

2 1
0 0 1
1 1 1

Sample Output

1
这道题本来应该是用扫描线+线段树做的，但我很无耻的直接暴力枚举正方形。。也是能过的囧
。。。
Code：
#include <vector>
#include <cstdio>
const int maxc=5002;
using namespace std;
int T[maxc][maxc]={0},n,r;
int main()
{
scanf("%d %d",&n,&r);
int x,y,c,a,ans=0;
while(n–)scanf("%d%d%d",&x,&y,&c),T[x+1][y+1]=c;
for(int i=1;i<maxc;i++)
for(int j=1;j<maxc;j++)
T[i][j]+=T[i-1][j]+T[i][j-1]-T[i-1][j-1];
for(int i=0;i+r<maxc;i++)
for(int j=0;j+r<maxc;j++)
if((a=T[i+r][j+r]+T[i][j]-T[i+r][j]-T[i][j+r])>ans)
ans=a;
printf("%dn",ans);
}

Source

额啊。。太悲剧了。。上个星期天我去参加的数学竞赛。。比赛的时候我脑子小了，犯了一堆SB错误。。
球体体积公式记成pi*r^3晕。。
C（a，b）的公式算错了。。
解答题最后一题是一道超级恶心的难题，我做的半死也没做出来，然后对附加题绝望了没去看，结果附加题都很水晕。。。哎。。附加题两题一共50分啊。。
哎。。200分的试卷就考了100分。。我智商真是太低了。。撞死。。
哎。。那天我见到了李恕，莫非我中了吸商光环啊悲剧。。。

[HNOI2009]最小圈

Time Limit:10000MS  Memory Limit:65536K
Total Submit:93 Accepted:37
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

Source
这道题是最最基本的二分判定+查找负环的问题了。。直接上Dfs查找负环就OK了(*^__^*) 。。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(eit i=x.begin();i!=x.end();i++)
const int inf=~0U>>1,maxn=3000;
using namespace std;
int n,m;
struct Edge
{
int t;
double c,oc;
Edge(int _t,double _c):t(_t),oc(_c){}
};
typedef vector<Edge>::iterator eit;
vector<Edge> E[maxn];
double D;
bool vis[maxn]={0},Find;
double Dist[maxn];
void dfs(int x)
{
vis[x]=true;double cost=Dist[x],ncost;
tr(e,E[x])if((ncost=cost+e->c)>Dist[e->t])
{
if(!vis[e->t]){Dist[e->t]=ncost;dfs(e->t);}
else Find=true;
if(Find)break;
}
vis[x]=false;
}
bool Check(double _D)
{
D=_D;
rep(i,n)tr(e,E[i])e->c=D-e->oc;
Find=false;
rep(i,n)Dist[i]=0;
rep(i,n){dfs(i);if(Find)return true;}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;
int s,t;double c;
rep(i,m)scanf("%d %d %lf",&s,&t,&c),–s,–t,E[s].pb(Edge(t,c));
double r=1e7,l=-r;
while(r-l>1e-9)
{
double m=(l+r)/2;
if(Check(m))r=m;
else l=m;
}
printf("%0.8lfn",l);
}

[Usaco2007 Feb]The Cow Lexicon

Time Limit:5000MS  Memory Limit:65536K
Total Submit:8 Accepted:7
Case Time Limit:1000MS

Description

没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她 说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音.

奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词 的一个排列).

Input

第1行:两个用空格隔开的整数,W和L.
第2行:一个长度为L的字符串,表示收到的信息.
第3行至第W+2行:奶牛的字典,每行一个词.

Output

唯一一行:一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer

Sample Output

2

Source

一般来说对付这种字符串匹配的问题都是要用Dp的。。
这道题用Dp（i,s,p）表示当前第匹配到第i个字符，最末是第s个单词的长为p的前缀。。
然后对于每个字符开个vector记录出现过的位置，同时用MaxEnd记录当时可以开新串的位置的Dp最大值（用于转移串的第一个顶点）。。注意vector要排个序以防止后效性。。
就可以了。。具体看Code吧(*^__^*) 嘻嘻。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxw=600,maxn=300,maxl=26;
using namespace std;
string S[maxw],A;
int w,l;
int Dp[maxw][maxl]={0};
struct state
{
int s,p;
state(int _s,int _p):s(_s),p(_p){}
bool operator<(const state&o)const
{return p>o.p;}
};
vector<state> P[maxl];
int main()
{
//freopen("in","r",stdin);
cin>>w>>l;
cin>>A;
rep(i,w)
{
cin>>S[i];
rep(j,S[i].size())
{
P[S[i][j]-‘a’].pb(state(i,j));
Dp[i][j]=-inf;
}
}
rep(i,26)sort(P[i].begin(),P[i].end());
int MaxEnd=0;
rep(t,l)
{
int c=A[t]-‘a’;int nextMaxEnd=MaxEnd;
for(vector<state>::iterator i=P.begin();i!=P.end();i++)
{
if(!i->p)Dp[i->s][i->p]=MaxEnd+1;
else Dp[i->s][i->p]>?=Dp[i->s][i->p-1]+1;
if(i->p==S[i->s].size()-1)nextMaxEnd>?=Dp[i->s][i->p];
}
MaxEnd=nextMaxEnd;
}
cout<<l-MaxEnd<<endl;
}

以前最大流我都是写sap啊。dinic啊之类的复杂算法。。感觉很不爽。。但是暴力dfs又经常超时，而EK算法反而更难写。。于是我很纠结。。
今天我看到了一种很帅的算法。。就是每次只增广容量在K以上的增广路，找不到了将k除2。。
代码很简单，时间我测了一下在稀疏图上是sap的3倍左右。。
哎。。花了4000买了台HTC HD2。。再是山寨的我只能撞死了晕。。
我无聊又进行了一些测试，发现在边权比较参差不齐的时候效果还是很好的，但在单位边图上就退化成暴力dfs了囧。。但可以加个高度函数优化，速度就几乎跟SAP一样了。。不过没意义。。
Code：
#include<iostream>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
int n,m;
const int V=5000;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[V]={0};
int vs,vt,v;
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int k=0;
bool vis[V]={0};
bool dfs(int no)
{
if(no==vt)return true;
vis[no]=true;
for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c>=k&&dfs(e->t))
{
e->c-=k;e->op->c+=k;return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;v=n;int s,t,c;
vs=0;vt=n-1;
while(m–)
{
cin>>s>>t>>c;–s;–t;
AddEdge(s,t,c);
k=c>k?c:k;
}
long long ans=0;
while(k)
{
while(memset(vis,0,sizeof(vis)),dfs(vs))ans+=k;
k>>=1;
}
cout<<ans<<endl;
}