[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;
}

acm.sgu.ru/problem.php
这道题看上去很唬人：给你一个图和一堆顶点，找一条最短路包含所有的顶点。。其实很水。。。
随便找一个需要包含的点中的一个点，找出这个距这点最短路最远的点，那么那个点必然是这段路的起点或终点(为什么自己体会吧(*^__^*) 嘻嘻)。。所以再从找出的这个点出发Dijstra一下。。再找出最远点。。那么这俩点之间必然有一条最短路包含所有的点！。。所以Dp一下然后重建路径就可以了。。
Code：
www.ideone.com/3DzNn

就是一个无向图找vs到vt的第K长简单路。。
这个实际上直接二分+剪枝就可以了。。关键是题目一模一样的SCOI 2007 的kshort(这个的数据范围反而小晕。。)反而A不掉。。囧啊囧。。。。
二分K短路的长度，然后dfs判断是否存在K条小于这个长度的路径，这样就可以知道K长路的长度，然后生成所有这些路，排个序就可以了晕。。
Code：
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
#include<cstring>
#define pb push_back
using namespace std;
const int maxn=100,inf=~0U>>2;
int n,m,k,vs,vt;
struct Edge
{
    int t,c;
    Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void AddEdge(int s,int t,int c)
{
    E[s].pb(Edge(t,c));
    E[t].pb(Edge(s,c));
}
int Dist[maxn];
void Spfa(int vs,vector<Edge> E[maxn])
{
    bool inq[maxn]={0};queue<int> Q;
    for(int i=0;i<n;i++) Dist[i]=inf;
    Dist[vs]=0;inq[vs]=true;Q.push(vs);
    while(Q.size())
    {
        int t=Q.front();Q.pop();inq[t]=false;
        int cost=Dist[t],ncost;
        for(eit e=E[t].begin();e!=E[t].end();++e)
            if((ncost=cost+e->c)<Dist[e->t])
            { Dist[e->t]=ncost;
                if(!inq[e->t])
                    inq[e->t]=true,Q.push(e->t);
            }
    }
}
bool vis[maxn]={0};
int Limit,Num;
void dfs(int no,int gone)
{
    vis[no]=true;
    if(Num>=k)goto end;
    if(gone+Dist[no]>Limit) goto end;
    if(no==vt){Num++;goto end;}
    for(eit e=E[no].begin();e!=E[no].end();++e)if(!vis[e->t])
    {
        dfs(e->t,gone+e->c);
        if(Num>=k) goto end;
    }
    end:
    vis[no]=false;
}
int Now[maxn];
struct Route
{
    int*A;
    int n,Len;
    Route(int _n,int _Len)
    {
        n=_n;Len=_Len;
        A=new int[n];
        memcpy(A,Now,sizeof(int)*n);
    }
    bool operator<(const Route&o)const
    {
        return Len<o.Len;
    }
    void show()const
    {
        cout<<Len<<" "<<n<<endl;
        for(int i=0;i<n-1;i++)
            cout<<A[i]+1<<" ";
        cout<<A[n-1]+1<<endl;
    }
};
vector<Route> Rs;
void Sdfs(int no,int gone,int d)
{
    vis[no]=true;
    Now[d-1]=no;
    if(gone+Dist[no]>Limit) goto end;
    if(no==vt)
    {
        Rs.pb(Route(d,gone));
        goto end;
    }
    for(eit e=E[no].begin();e!=E[no].end();++e)if(!vis[e->t])
    {
        Sdfs(e->t,gone+e->c,d+1);
    }
    end:
    vis[no]=false;
}
bool Check(int _Limit)
{
    Num=0;
    Limit=_Limit;
    dfs(vs,0);
    return Num>=k;
}
void Get(int _Limit)
{
    Limit=_Limit;
    Sdfs(vs,0,1);
    sort(Rs.begin(),Rs.end());
    Rs[k-1].show();
}
void Init()
{
    cin>>n>>m>>k;
    int s,t,c;
    while(m–)
    {
        cin>>s>>t>>c;s–;t–;
        AddEdge(s,t,c);
    }
    cin>>vs>>vt;vs–;vt–;
}
void Work()
{
    Spfa(vt,E);
    int l=0,r=inf;
    if(!Check(r))
    {
        cout<<"No"<<endl;
        return;
    }
    while(l+1<r)
    {
        int m=l+r>>1;
        if(Check(m))
            r=m;
        else
            l=m;
    }
    Get(r);
}
int main()
{
    //freopen("in","r",stdin);
    Init();
    Work();
}

[BeijingWc2008]雷涛的小猫

Time Limit:50000MS Memory Limit:165536K
Total Submit:22 Accepted:15
Case Time Limit:10000MS

Description

Input

Output

Sample Input

Sample Output

Hint

Source
这题算是水题了。。从低到高转移，并且记录每行的最大值，就可以了囧。。
Code：

#include<cstdio>#include<iostream>using namespace std;const int maxn=2000+10;int n,h,d;int N[maxn][maxn]={0};void Init(){ scanf("%d %d %d",&n,&h,&d); for(int i=0;i<n;i++) { int s,x;scanf("%d",&s); while(s–)scanf("%d",&x),N[i][x]++; }}int Best[maxn]={0};int Dp[maxn]={0};void Work(){ for(int i=1;i<=h;i++) for(int j=0;j<n;j++) { if(i-d>=0)Dp[j]>?=Best[i-d]; Dp[j]+=N[j][i]; Best[i]>?=Dp[j]; } printf("%dn",Best[h]);}int main(){ //freopen("in","r",stdin); Init(); Work();}8

[HNOI2007]神奇游乐园

Time Limit:10000MS Memory Limit:165536K
Total Submit:60 Accepted:28
Case Time Limit:1000MS

Description

经历了一段艰辛的旅程后，主人公小P乘坐飞艇返回。在返回的途中，小P发现在漫无边际的沙漠中，有一块狭长的绿地特别显眼。往下仔细一看，才发现这是一个游乐场，专为旅途中疲惫的人设计。娱乐场可以看成是一块大小为n×m的区域，且这个n×m的区域被分成n×m个小格子，每个小格子中就有一个娱乐项目。然而，小P并不喜欢其中的所有娱乐项目，于是，他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目，值越大表示越喜欢。为负时表示他不喜欢，这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。小P决定将飞艇停在某个小格中，然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径，从飞艇所在格出发，最后又回到这个格子。小P有一个习惯，从不喜欢浪费时间。因此，他希望经过每个格子都是有意义的：他到一个地方后，就一定要感受以下那里的惊险和刺激，不管自己是不是喜欢那里的娱乐项目。而且，除了飞艇所在格，其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。
在满足这些条件的情况下，小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗？

Input

输入文件中的第一行为两个正整数n和m，表示游乐场的大小为n×m。因为这个娱乐场很狭窄，所以n和m满足：2<=n<=100，2<=m<=6。
接下来的n行，每行有m个整数，第i行第j列表示游乐场的第i行第j列的小格子中的娱乐项目的满意度，这个满意度的范围是[-1000，1000]。同一行的两个整数之间用空格隔开。

Output

输出文件中仅一行为一个整数，表示最高的满意度之和。

Sample Input

Sample Output

Hint

大家测下这个数据
5 5
1 1 -100 3 3
1 1 -100 3 3
1 1 -100 3 3
1 1 -100 3 3
1 1 -100 3 3
结果是30?

Source
饿。。跟Formual 1差不多。。直接上连通性状态压缩Dp就可以了。还要考虑不选当前格子的情况(*^__^*) 嘻嘻……。。

Code还是只能放在ideone上。。。哎。。开始钻研这种Dp了。。这玩意真是NB啊囧。。
http://www.ideone.com/Oh0E1

40004 4100 300 -400 400-100 1000 1000 1000-100 -100 -100 -100-100 -100 -100 1000

这道题目算法就不说了。。关键是我这个实现方法还是很有意思的。。
我直接用一个类来表示状态。。大大简化了代码(*^__^*) 。。
const int maxn=20;
typedef unsigned long long ull;
int n,m;
struct State
{
    ull s;
    State(ull _s=0):s(_s){}
    int get(int i){return s>>(3*i)&7;}
    int operator[](int i){return get(i);}
    void set(int i,int x){s&=~(7ULL<<(3*i));s|=ull(x)<<(3*i);}
    bool operator<(const State&o)const
    {return s<o.s;}
    void normal()
    {
        static int tmp[10],cnt;
        memset(tmp,0,sizeof(tmp));
        cnt=0;
        for(int i=0;i<=m;i++)
        {
            int t=get(i);
            if(!t)continue;
            if(!tmp[t]) tmp[t]=++cnt;
            set(i,tmp[t]);
        }
    }
    void Merge(int a,int b)
    {
        for(int i=0;i<=m;i++)
            if(get(i)==b)
                set(i,a);
        normal();
    }
    bool LegalAsEnd()const
    {
        return s==0;
    }
    void NextRow()
    {
        s<<=3;
    }
    void Show()
    {
        for(int i=0;i<=m;i++)
            cout<<get(i)<<" ";
        cout<<endl;
    }
};
完整的代码在ideone上。。百度放不下囧。。。
http://www.ideone.com/0mrgG

我很无聊的钻研了vector的实现代码，发现这个玩意非常NB，但在很多情况下没有必要减小表的大小，那么vector的速度就成问题了。。
我自己写了个Vector类，只支持加一个元素这个操作，不过速度比vector快了很多囧。。
比如说边表之类的就可以加速了。。
Code：
#include <cstring>
#include <iostream>
#include <ctime>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1;
using namespace std;
template<class T>
struct Vector
{
typedef T* it;
it Mem,End,MemEnd;
void Grow()
{
int s=MemEnd-Mem;
it NewMem=new T[s*2];
memcpy(NewMem,Mem,sizeof(T)*s);
delete[] Mem;Mem=NewMem;
MemEnd=Mem+s*2;
End=Mem+s;
}
Vector()
{
Mem=new T[1];
MemEnd=Mem+1;
End=Mem;
}
void Add(const T&a)
{
if(End==MemEnd)Grow();
*(End++)=a;
}
it begin(){return Mem;}
it end(){return End;}
};
int main()
{
int time=clock();
Vector<int> V;
rep(i,10000000) V.Add(i);
cout<<clock()-time<<endl;time=clock();
vector<int> A;
rep(i,10000000) A.push_back(i);
cout<<clock()-time<<endl;time=clock();
}

[SCOI2009]生日快乐

Time Limit:1000MS  Memory Limit:165536K
Total Submit:50 Accepted:41

Description

windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。
现在包括windy，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。
windy主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。
这样，要切成 N 块蛋糕，windy必须切 N-1 次。
为了使得每块蛋糕看起来漂亮，我们要求 N 块蛋糕的长边与短边的比值的最大值最小。
你能帮助windy求出这个比值么？

Input

包含三个整数，X Y N。

Output

包含一个浮点数，保留6位小数。

Sample Input

5 5 5

Sample Output

1.800000

Hint

【数据规模和约定】
100%的数据，满足 1 <= X,Y <= 10000 ； 1 <= N <= 10 。

Source

Day1

晕。。实际上是水题啊。。直接搜索就可以了囧。。以前我还以为是神牛题晕。。
天啊。。后天就要数学竞赛了我居然在拼命搞OI囧。。。
Code：

#include <algorithm>
#include <cstdio>
using namespace std;
double dfs(double x,double y,int c)
{
if(x>y)swap(x,y);
if(c==1)return y/x;double ret=1e20,r=1.0/c;
for(int i=1;i<c;i++)
ret<?=max(dfs(x*r*i,y,i),dfs(x-x*r*i,y,c-i)),
ret<?=max(dfs(x,y*r*i,i),dfs(x,y-y*r*i,c-i));
return ret;
}
int main()
{
double x,y;int n;
scanf("%lf %lf %d",&x,&y,&n);
printf("%0.6fn",dfs(x,y,n));
}