Archive

Archive for August, 2009

USACO 3.1.3 Humble Numbers

August 31, 2009 Leave a comment

这道题我脑袋一时短路看了题解..

下面是nocow上的官方题解译文

我们在数组hum中计算出前n个丑数。为了实现起来更简单,我们把1也作为一个丑数,算法也要因此略微调整一下。

当我们已知前k个丑数,想得到第k+1个,我们可以这样做:

对于每个质数p
	寻找最小的丑数h
	  使得 h * p 比上一个丑数大

取我们找到的 h * p 中最小的一个:它就是下一个丑数

为了使搜索更快,我们可以为每个质数维护一个索引“pindex”表示每个质数已经乘到了哪个丑数,每次都从那里开始,而不是再从头再来。

代码:

/*
ID: dementr1
PROG: humble
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“humble.in”);
ofstream fout(“humble.out”);
int humble[100001]={},p[101]={},pnow[101]={};
int K,N;
void init()
{
int i;
fin>>K>>N;
for(i=1;i<=K;i++) fin>>p[i];
fin.close();
}
void work()
{
int i,j,min,minj[100],tmp,counter=0;
humble[0]=1;
for(i=1;i<=N;i++)
{
min=2000000000;
for(j=1;j<=K;j++)
{
tmp=p[j]*humble[pnow[j]];
while(tmp<=humble[i-1])
{
tmp*=p[j];
}
if(tmp<min)
{
min=tmp;
counter=0;
minj[counter++]=j;
}
else if(tmp==min)
{
minj[counter++]=j;
}
}
humble[i]=min;
for(j=0;j<counter;j++) pnow[minj[j]]++;
}
fout<<humble[N]<<endl;
}
int main()
{
init();
work();
return 0;
}

Advertisements
Categories: Old Blog Posts

USACO 3.1.2 Score Inflation

August 31, 2009 Leave a comment

一道典型的完全背包的题目

详细讲解可以参见dd_engi的背包九讲

我只简单地说一下

两重循环

外层循环物品,一个一个地装

内层循环是分值数

基本方程为f[j]=max(f[j],f[j-times[i]]+score[i]),状态的含义为用前i道题,总时间为j的最大值

此外这个dp还可以剪枝,在内层循环之前,判断若score[i]<=f[times[i]]可以直接跳过,用这个物品也是浪费

这个优化的力度比较大

代码:

/*
ID: dementr1
PROG: inflate
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“inflate.in”);
ofstream fout(“inflate.out”);
int M,N,score[10000]={},times[10000]={},f[10001]={};
void init()
{
int i;
fin>>M>>N;
for(i=0;i<N;i++)
fin>>score[i]>>times[i];
fin.close();
}
void work()
{
int i,j;
for(i=0;i<N;i++)
if(score[i]>f[times[i]])
for(j=0;j<=M;j++)
if(j-times[i]>=0)
f[j]=max(f[j],f[j-times[i]]+score[i]);
fout<<f[M]<<endl;
fout.close();
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts

USACO 3.1.1 Agri-Net

August 31, 2009 Leave a comment

一道标准的最小生成树,裸的模型,选择自己喜欢的算法来编吧。

代码:

/*
ID: dementr1
PROG: agrinet
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“agrinet.in”);
ofstream fout(“agrinet.out”);
int N,length=0,a[100][100]={};
void init()
{
int i,j;
fin>>N;
for(i=0;i<N;i++)
for(j=0;j<N;j++) fin>>a[i][j];
fin.close();
}
void work()
{
int time,num,i,j,min,minj;
bool used[100]={false};
used[0]=true;
num=0;
for(time=1;time<N;time++)
{
min=99999999;
for(i=0;i<N;i++)
if(used[i])
{
for(j=0;j<N;j++)
if(i!=j&&!used[j]&&a[i][j]<min)
{
min=a[i][j];
minj=j;
}
}
used[minj]=true;
length+=min;
}
fout<<length<<endl;
fout.close();
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts

USACO 2.4.5 Fractions to Decimals

August 31, 2009 Leave a comment

模拟手算长除法,其实就是一道高精度计算题,判重可以用一个布尔数组实现。

代码:

/*
ID: dementr1
PROG: fracdec
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
ifstream fin(“fracdec.in”);
ofstream fout(“fracdec.out”);
int y[100001]={},s[100001]={},ynum=0,snum=0,r=0;
struct link
{
bool appear;
int dis;
} data[100001];
string ss;
void divide(int a, int b)
{
int i;
bool print=false;
y[0]=a%b;
s[0]=a/b;
int start;
while(1)
{
snum++;
s[snum]=(y[ynum]*10)/b;
y[ynum+1]=(y[ynum]*10)%b;
ynum++;
if(data[y[ynum]].appear)
{
print=true;
break;
}
data[y[ynum]].appear=true;
data[y[ynum]].dis=snum;
}
int forstart,forcmp;
start=data[y[ynum]].dis;
if(s[start]==s[snum])
{
forstart=snum-1;
forcmp=start;
}
else
{
forstart=snum;
forcmp=start+1;
}
if(forstart==forcmp) print=false;
int t[10],tmp=0;
if(s[0]==0) ss+=’0′;
while(s[0]>0)
{
t[tmp++]=s[0]%10;
s[0]/=10;
}
for(i=tmp-1;i>=0;i–) ss+=(t[i]+’0′);
ss+=”.”;
bool another=false;
for(i=1;i<=forstart;i++)
{
if(i==forcmp&&i!=forstart&&print)
{
ss+=”(“;
}
if(!(i==forcmp&&i==forstart&&s[i]==0))
{
ss+=(s[i]+’0′);
another=true;
}
}
if(print) ss+=”)”;
if(!another) ss+=”0″;
for(i=0;i<ss.length();i++)
{
fout<<ss[i];
if(i%76==75) fout<<endl;
}
if(ss.length()%76!=0) fout<<endl;
}
int main()
{
int a,b,i;
fin>>a>>b;
for(i=0;i<=100000;i++) data[i].appear=false;
divide(a,b);
fin.close();
fout.close();
return 0;
}

Categories: Old Blog Posts

USACO 2.4.4 Bessie Come Home

August 31, 2009 Leave a comment

数据范围这么小,不用floyd算法用什么?

代码:

/*
ID: dementr1
PROG: comehome
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“comehome.in”);
ofstream fout(“comehome.out”);
int dis[100][100]={},P;
void init()
{
int i,j,tmp;
char a,b;
for(i=0;i<52;i++)
for(j=0;j<52;j++)
dis[i][j]=100000;
fin>>P;
for(i=0;i<P;i++)
{
fin>>a>>b;
if(‘a'<=a&&a<=’z’) a=a-‘a’;
else if(‘A'<=a&&a<=’Z’) a=a-‘A’+26;
if(‘a'<=b&&b<=’z’) b=b-‘a’;
else if(‘A'<=b&&b<=’Z’) b=b-‘A’+26;
fin>>tmp;
if(tmp<dis[a][b]) dis[a][b]=dis[b][a]=tmp;
}
}
void floyd()
{
int k,i,j,min=10000000,mini;
for(k=0;k<52;k++)
for(i=0;i<52;i++)
for(j=0;j<52;j++)
if(i!=k&&k!=j&&i!=j&&dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
for(i=26;i<51;i++)
if(dis[51][i]<min)
{
min=dis[51][i];
mini=i;
}
fout<<(char)(mini+’A’-26)<<” “<<min<<endl;
}
int main()
{
init();
floyd();
return 0;
}

Categories: Old Blog Posts

USACO 2.4.3 Cow Tours

August 31, 2009 Leave a comment

先用floyd过一遍,取任两个牧区中的点i,j,maxx[i]为从i点出发的最远距离,maxl为maxx中的最大值,则直径为 max(maxx[i]+maxx[j]+dis(i,j),maxl),但在实现上可先求出最短的maxx[i]+maxx[j]+dis(i,j),再和 maxl比较取最大值为答案。

代码:

/*
ID: dementr1
PROG: cowtour
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<stdio.h>
#include”math.h”
using namespace std;
struct xy
{
long double x,y;
}  pix[200];
long double dis[200][200],a[200][200];
int N;
long double ptdist(xy a, xy b)
{
return sqrt((long double)(b.x-a.x)*(b.x-a.x)+(long double)(b.y-a.y)*(b.y-a.y));
}
void init()
{
string s;
int i,j;
ifstream fin(“cowtour.in”);
fin>>N;
for(i=0;i<N;i++)
fin>>pix[i].x>>pix[i].y;
for(i=0;i<N;i++)
{
fin>>s;
for(j=0;j<N;j++)
{
if(s[j]-‘0’==1)
a[i][j]=ptdist(pix[i],pix[j]);
else a[i][j]=100000;
}
}
fin.close();
}
void floyd()
{
int i,j,k;
double mx[200]={},maxx=0,min=100000;
for(k=0;k<N;k++)
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if((i!=k&&i!=j&&k!=j)&&(a[i][k]+a[k][j]<a[i][j])) a[i][j]=a[i][k]+a[k][j];
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if(a[i][j]!=100000&&a[i][j]>mx[i]) mx[i]=a[i][j];
if(mx[i]>maxx) maxx=mx[i];
}
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i!=j&&a[i][j]==100000)
if(mx[i]+mx[j]+ptdist(pix[i],pix[j])<min) min=mx[i]+mx[j]+ptdist(pix[i],pix[j]);
FILE *fout=fopen(“cowtour.out”,”w”);
fprintf(fout,”%lf\n”,max(maxx,min));
}
int main()
{
init();
floyd();
return 0;
}

Categories: Old Blog Posts

USACO 2.4.2 Overfencing

August 31, 2009 Leave a comment

比castle的算法容易,但比castle的输入更加猥琐。

代码:

/*
ID: dementr1
PROG: maze1
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ofstream fout(“maze1.out”);
int a[3000][80]={},step[3000][80]={},H,W;
int startx[2],starty[2];
int move1[4][2]={{2,0},{-2,0},{0,2},{0,-2}},move2[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int xmax,ymax;
struct pix
{
int x,y;
} list[300000];
void init()
{
int i,j,counter=0,s=0;
char tmp;
FILE *fp=fopen(“maze1.in”,”r”);
fscanf(fp,”%d”,&W);
fscanf(fp,”%d”,&H);
xmax=W*2+1;
ymax=H*2+1;
while(fscanf(fp,”%c”,&tmp)!=EOF)
{
if(tmp==’\n’) continue;
i=counter/(xmax);
j=counter%(xmax);
if(tmp==’ ‘) a[i][j]=0;
else a[i][j]=1;
step[i][j]=-1;

if((j==0||j==W*2||i==0||i==H*2)&&tmp==’ ‘)
{
startx[s]=i;
starty[s]=j;
s++;
step[i][j]=0;
}
counter++;
}
}
void bfs()
{
int open,closed,px,py,i,j;
open=1;
closed=-1;
list[0].x=startx[0];
list[0].y=starty[0];
list[1].x=startx[1];
list[1].y=starty[1];
while(closed<open)
{
closed++;
if(closed<=1)
{
for(i=0;i<4;i++)
{
px=list[closed].x+move2[i][0];
py=list[closed].y+move2[i][1];
if(0<=px&&px<=ymax
&&0<=py&&py<=xmax
&&a[px][py]==0&&(step[px][py]>step[list[closed].x][list[closed].y]+1||step[px][py]==-1))
{
open++;
list[open].x=px;
list[open].y=py;
step[px][py]=step[list[closed].x][list[closed].y]+1;
}
}
}
else
{
for(i=0;i<4;i++)
{
px=list[closed].x+move1[i][0];
py=list[closed].y+move1[i][1];
if(0<=px&&px<=ymax
&&0<=py&&py<=xmax
&&a[px-move2[i][0]][py-move2[i][1]]==0&&(step[px][py]>step[list[closed].x][list[closed].y]+1||step[px][py]==-1))
{
open++;
list[open].x=px;
list[open].y=py;
step[px][py]=step[list[closed].x][list[closed].y]+1;
}
}
}
}
int max=-1;
for(i=0;i<ymax;i++)
for(j=0;j<xmax;j++)
if(step[i][j]>max) max=step[i][j];
fout<<max<<endl;
}
int main()
{
init();
bfs();
return 0;
}

Categories: Old Blog Posts