PKU 2008 Individual Practice 1 (2)

3615 Problem D Cow Hurdles

大意:

N(1<=300)个顶点的图,有T(<=40000)个询问,

每次询问从s到e的所有路径中,最大边最小是多少。。

分析:

很明显N很小T很大暴力不可行。。

于是想到floyd。。发现扩展一下没有问题,不过是改成了。。

D[i,j]=min(D[i,j],max(D[i,k],D[k,j]) );而已

启示:

很多时候floyd是很有用的。。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300,inf=~0U>>1;
int d[maxn][maxn];
int n,m,ti;
int main()
{
freopen("in","r",stdin);
cin>>n>>m>>ti;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=inf;
int s,t,c;
while(m–)
{
scanf("%d %d %d",&s,&t,&c);s–;t–;
d[s][t]=min(d[s][t],c);
}
for(int k=n-1;k>=0;k–)
for(int i=n-1;i>=0;i–)if(i!=k&&d[i][k]!=inf)
for(int j=n-1;j>=0;j–)
d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
while(ti–)
{
scanf("%d %d",&s,&t);s–;t–;
printf("%dn",(d[s][t]==inf?-1:d[s][t]));
}
}

3616 Problem E Milking Time

大意:M个区间,每个有个效率值,取一些区间,让所有区间不重叠并前相邻的两个中空开R格以上。。

分析:设P[n]为最后一个区间在n结束时最大效率和,则P[n]=max(P[k])(k<=n-R)。。

那么用数状数组维护一下就OK了。。

启示:

区间问题如果长度不是太大的化鬼才离散化。。。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#define low(x) (x&(-x))
#define Renew(x,c) x=max(x,c)
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,int> inter;
const int maxn=1000000+100,maxm=1000+100,inf=~0U>>2;
int N,M,R,A[maxn];
int Max(int l)
{
int ans=0;
for(;l>0;l-=low(l))
Renew(ans,A[l]);
return ans;
}
void Change(int l,int d)
{
for(;l<=N;l+=low(l))
Renew(A[l],d);
}
inter I[maxm];
void init()
{
cin>>N>>M>>R;N++;
for(int i=1;i<=N;i++) A[i]=-inf;
int s,t,e;
for(int i=0;i<M;i++)
{
scanf("%d %d %d",&s,&t,&e);
I[i]=inter(pi(s,t),e);
}
sort(I,I+M);
}
void solve()
{
int ans=-inf,get;
for(inter*i=I;i!=I+M;i++)
{
get=Max(i->first.first-R);
get+=i->second;
Change(i->first.second,get);
}
ans=Max(N);
cout<<ans<<endl;
}
int main()
{
init();
solve();
}

3617 Problem F Best Cow Line

大意:

长度为N的一串字符,每次从两端取一个,放入新的字符串尾部,那么N次后字符串序最小的字符串是什么?

分析:

如果两端不一样的话就取小点的。。如果一样的话可以忽略看再里面一个么?

不是很清楚为什么。。不过A掉了。。就是说如果字符串正过来看比较小,就选左边的,如果倒过来看比较小,就选右边的。。

启示:

直觉阿。。不证明。。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;
typedef string::iterator it;
typedef string::reverse_iterator rit;
const int maxn=2000;
int n,limit=5000000;
string a,ans;
bool cmp(it a,it b,rit c,rit d)
{
for(;a!=b;a++,c++)
{
if(*a<*c) return true;
if(*a>*c) return false;
}
return false;
}
int main()
{
scanf("%d",&n);char c;
for(int i=0;i<n;i++)
scanf("n%c",&c),a+=c;
it l=a.begin(),r=a.end();
rit rl=a.rbegin(),rr=a.rend();
while(l!=r)
{
if(cmp(l,r,rl,rr))
{
ans+=*l;
l++;rr–;
}
else
{
r–;rl++;
ans+=*r;
}
}
int now=0;
for(int i=0;i<n;i++)
{
now++;
printf("%c",ans[i]);
if(now==80) printf("n"),now=0;
}
if(now) printf("n");
}

3618 Problem G Exploration

水题。。不分析。。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;
const int maxn=50000;
typedef pair<int,int> pi;
inline int abs(int x){return x>0?x:-x;}
int t,n,x;
pi X[maxn];
int main()
{
cin>>t>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
X[i]=pi(abs(x),x);
}
sort(X,X+n);int last=0;
for(int i=0;i<n;i++)
{
t-=abs(last-X[i].second);
if(t<0){cout<<i<<endl;return 0;}
last=X[i].second;
}
cout<<n<<endl;
}

3619 Problem H Speed Reading

水题。。直接数学计算。。

Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
using namespace std;
const int maxk=1000;
int n,k;
int time(int s,int t,int r)
{
int p=n/(s*t),ans;
if(p*s*t==n)
return (p-1)*(t+r)+t;
ans=p*(t+r);
int e=n-p*s*t;
ans+=((e-1)/s)+1;
return ans;
}
int main()
{
cin>>n>>k;
int s,t,r;
while(k–)
{
cin>>s>>t>>r;
cout<<time(s,t,r)<<endl;
}
}

3620 Problem I Avoid The Lakes

一个网格。。求最大的连续空格块的大小

直接DFS。。。

Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>
#define Renew(x,c) x=max(x,c)
using namespace std;
const int maxn=100+10;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
bool map[maxn][maxn]={0};
int n,m,k;
int dfs(int i,int j)
{
map[i][j]=false;int ans=1;
for(int ii,jj,d=0;d<4;d++)
{
ii=i+di[d];jj=j+dj[d];
if(map[ii][jj])
ans+=dfs(ii,jj);
}
return ans;
}
int main()
{
freopen("in","r",stdin);
cin>>n>>m>>k;int s,t;
while(k–)
{
cin>>s>>t;
map[s][t]=true;
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j])
Renew(ans,dfs(i,j));
cout<<ans<<endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>