C程序最大间隙问题 金币列阵问题 最多约数问题等

最大间隙问题#include<iostream>

usingnamespacestd;constintMAX=200001;

doublenum[MAX]；boolrun()

{

intn;

if(scanf("%d",&n)==EOF)returnfalse;

inti;

doublemax=0.0,min=INT_MAX;

for(i=0;i<n;i++)

{

scanf("%lf",&num[i]);

if(num[i]>max)max=num[i];

if(num[i]<min)min=num[i];

}

int*cnt=newint[n];

double*low=newdouble[n];

double*high=newdouble[n];

for(i=0;i<n;i++)

{

cnt[i]=0;

low[i]=max;

high[i]=min;

}

doubleave=(max-min)/(n-1);

for(i=0;i<n;i++)

{

inttmp=(int)((num[i]-min)/ave);

cnt[tmp]++;

if(num[i]>high[tmp])high[tmp]=num[i];

if(num[i]<low[tmp])low[tmp]=num[i];

}

doublet=high[0],res=0.0;

for(i=1;i<n;i++)

{

if(cnt[i]>0)

{

doubletmp=low[i]-t;

if(tmp>res)

res=tmp;

t=high[i];

}

}

cout<<res<<endl;

returntrue;

}intmain()

{

while(run());

return0;

}金币列阵问题#include<fstream>

#include<iostream>

usingnamespacestd;

constintsize=100;

intk,n,m,ccount,best;

intb0[size+1][size+1],b1[size+1][size+1],b[size+1][size+1];

boolfound;

voidprint()

{

for(inti=1;i<=n;i++)

{

for(intj=1;j<=m;j++)

cout<<b1[i][j]<<"";

cout<<endl;

}

}voidtrans1(intx)

//行翻转

{

for(inti=1;i<=m;i++)

b1[x][i]=b1[x][i]^1;

ccount++;

}

voidtrans2(intx,inty)

//列交换

{

for(inti=1;i<=n;i++)

swap(b1[i][x],b1[i][y]);

if(x!=y)ccount++;

}

boolsame(intx,inty)

{

for(inti=1;i<=n;i++)

if(b0[i][x]!=b1[i][y])

returnfalse;

returntrue;

}

voidacpy(inta[size+1][size+1],intb[size+1][size+1])

{

for(inti=1;i<=n;i++)

for(intj=1;j<=m;j++)

a[i][j]=b[i][j];

}

voidanswer()

{

intx,y,j,p;

cin>>k;

for(inti=1;i<=k;i++)

{

cin>>n>>m;

//原状态

b0

for(x=1;x<=n;x++)

for(y=1;y<=m;y++)

cin>>b0[x][y];

//目标状态

b1

for(x=1;x<=n;x++)

for(inty=1;y<=m;y++)

cin>>b1[x][y];

acpy(b,b1);

best=m+n+1;

for(j=1;j<=m;j++)

{

acpy(b1,b);

ccount=0;

trans2(1,j);//列变换

intp;

for(p=1;p<=n;p++)

if(b0[p][1]!=b1[p][1])

trans1(p);//行变换

for(p=1;p<=m;p++)

//找列相等的（b1的q列和b0的p列相等）

{

found=false;

for(intq=p;q<=m;q++)

if(same(p,q))

{

trans2(p,q);

found=true;

break;

}

if(!found)break;

}

if(found&&ccount<best)

best=ccount;

}

if(best<m+n+1)

cout<<best<<endl;

else

cout<<-1<<endl;

}

}

intmain()

{

answer();

return0;}最多约数问题#include<iostream>

usingnamespacestd;

#definemaxMax

constlongMAXP=100000;

longprim[MAXP];

longmax,numb,PCOUNT;

voidprimes();

voidsearch(longfrom,longtot,longnum,longlow,longup);

intmain()

{

primes();

longl,u;

cin>>l>>u;

if((l==1)&&(u==1))

{

max=1;

numb=1;

}

else

{

max=2;

numb=l;

search(1,1,1,l,u);

}

cout<<max<<endl;

return0;

}voidprimes()

{

boolget[MAXP+1];

longi;

for(i=2;i<=MAXP;i++)

get[i]=true;

for(i=2;i<=MAXP;i++)

if(get[i])

{

longj=i+i;

while(j<=MAXP)

{

get[j]=false;

j+=i;

}

}

longii,j;

for(ii=2,j=0;ii<=MAXP;ii++)

if(get[ii])prim[++j]=ii;

PCOUNT=j;

}voidsearch(longfrom,longtot,longnum,longlow,longup)

{

if(num>=1)

if((tot>max)||((tot==max)&&(num<numb)))

{

max=tot;

numb=num;

}

if((low==up)&&(low>num))search(from,tot*2,num*low,1,1);

for(longi=from;i<=PCOUNT;i++)

{

if(prim[i]>up)return;

else

{

longj=prim[i],x=low-1,y=up,n=num,t=tot,m=1;

while(true)

{

m++;

t+=tot;

x/=j;

y/=j;

if(x==y)break;

n*=j;

search(i+1,t,n,x+1,y);

}

m=1<<m;

if(tot<max/m)return;

}

}

}字典序问题#include<iostream>usingnamespacestd;#include<string>intf[26][20]={0};intg[20]={0};intsolve(stringst){stringfrom,to;to=st;intindex=0;intlen=to.length();if(len==1)returnto[0]-'a'+1;for(intj=0;j<len;j++)index+=g[j];for(inti=0;i<to[0]-'a';i++)index+=f[i][len-1];intk=1;while(k<len){if(to[k]<=to[k-1])return0;if(k+1==len){index++;} for(intp=to[k-1]-'a'+1;p<to[k]-'a';p++)index+=f[p][to.length()-k-1];k++;}returnindex;}voidrecord(intlen){g[0]=0;g[1]=26;for(inti=0;i<26;i++){f[i][0]=1;}for(intj=1;j<len;j++){for(inti=0;i<26