usaco 4.2.4 cowcycle
这题数据不是很BT,用简单的dfs就可以过,不过还是有几点要注意的.我就是死在其中的某点上.
1.我一开始自作聪明的加了个剪枝,可是结果是越剪时间用的越多,我的剪枝方法是,确定前轮之后[我先确定前轮,因为我觉得这样比先确定后轮时间要少一点]然后再用那个3倍关系确定后轮的范围,这样时间用的更多.真是画蛇添足了
2.我用的排序时qsort,由于一直用c写acm的代码,排序基本是qsort,一般是没问题的,可是这次就死在这里.后来自己写的冒泡就过了,才知道qsort其实不是非常快,尤其是小数据的时候.
其他的应该只要读懂题意,然后照着题目的要求算方差就OK了,千万别搞错了differences的个数
代码如下:
/
ID:qcx97811
LANG:C
TASK:cowcycle
/
#include
#include
#include
#include
int F,R,F1,F2,R1,R2
int amax,bmax,amin,bmin//amax amin是前轮的最小和最大值 bmin和bmax是后轮的最小和最大值
int a[10],b[12],aa[10],bb[12];//a记录本次的前轮数据 b本次的后轮数据 aa和bb是最优的前轮和
后轮数据
double diff[56],mean,var,best//diff和题中的有点不同
void dfsb(int now,int beg)
{
int i,j
double k
if(R == now)//后轮选完了
{
if(a[0]3b[0] > a[F-1]b[R-1])//the 3X rule
return ;
for(i = 0i < F;i++)
{
for(j = 0j < R;j++)
{//calc the diff
diff[Ri+j] = a[i]1.0/(b[j]
1.0);
}
}
for(i = 0i < FR-1;i++)
{//冒泡排序
for(j = FR-1j >; i;j–)
{
if(diff[j] > diff[j-1])
{
k = diff[j];
diff[j] = diff[j-1];
diff[j-1] = k
}
}
}
mean = (diff[0] - diff[RF-1])/(RF-1);//the num of the
differences is RF-1 计算平均值
var = 0
j = RF-1
for(i = 0i < j;i++)
{
var += (diff[i]-diff[i+1]-mean)(diff[i]-diff
[i+1]-mean);
}
var = var1.0/(RF-1);//计算方差
if(-1 == aa[0])//如果是第一次的话
{
for(i = 0i < F;i++)
aa[i] = a[i];
for(j = 0j < R;j++)
bb[i] = b[i];
best = var
}
else
{
if(var < best)
{//如果更优的话
best = var
for(i = 0i < F;i++)
aa[i] = a[i];
for(i = 0i < R;i++)
bb[i] = b[i];
}
}
return ;
}
if(beg > bmax)
return ;//没后轮选了
for(i = begi <= bmax;i++)
{//选下一个后轮
b[now] = i
dfsb(now+1,i+1);
}
}
void dfsa(int now,int beg)
{
int i,j,k,kk
if(F == now)
{//前轮选完了
if(a[0]3R1 > a[F-1]R2)
return//3x规则
dfsb(0,R1);//开始选后轮
return ;
}
if(beg > amax)
return ;//没前轮选了
for(i = begi <= amax;i++)
{//测试当前的前轮 然后开始选下一个前轮
a[now] = i
dfsa(now+1,i+1);
}
}
int main(void)
{
freopen(“cowcycle.in”,“r”,stdin);
freopen(“cowcycle.out”,“w”,stdout);
int i,j
scanf(“%d%d”,F,&R);
scanf(“%d%d%d%d”,F1,&F2,&R1,&R2);
amin = F1
amax = F2
bmax = R2
bmin = R1
aa[0] = -1//标记
dfsa(0,amin);//开始搜索
printf(“%d”,aa[0]);
//下面是输出
for(i = 1i < F;i++)
printf(“ %d”,aa[i]);
printf(“\n%d”,bb[0]);
for(i = 1i < R;i++)
printf(“ %d”,bb[i]);
printf(“\n“);
return 0
}
ID:qcx97811
LANG:C
TASK:cowcycle
/
#include
#include
#include
#include
int F,R,F1,F2,R1,R2
int amax,bmax,amin,bmin//amax amin是前轮的最小和最大值 bmin和bmax是后轮的最小和最大值
int a[10],b[12],aa[10],bb[12];//a记录本次的前轮数据 b本次的后轮数据 aa和bb是最优的前轮和
后轮数据
double diff[56],mean,var,best//diff和题中的有点不同
void dfsb(int now,int beg)
{
int i,j
double k
if(R == now)//后轮选完了
{
if(a[0]3b[0] > a[F-1]b[R-1])//the 3X rule
return ;
for(i = 0i < F;i++)
{
for(j = 0j < R;j++)
{//calc the diff
diff[Ri+j] = a[i]1.0/(b[j]
1.0);
}
}
for(i = 0i < FR-1;i++)
{//冒泡排序
for(j = FR-1j >; i;j–)
{
if(diff[j] > diff[j-1])
{
k = diff[j];
diff[j] = diff[j-1];
diff[j-1] = k
}
}
}
mean = (diff[0] - diff[RF-1])/(RF-1);//the num of the
differences is RF-1 计算平均值
var = 0
j = RF-1
for(i = 0i < j;i++)
{
var += (diff[i]-diff[i+1]-mean)(diff[i]-diff
[i+1]-mean);
}
var = var1.0/(RF-1);//计算方差
if(-1 == aa[0])//如果是第一次的话
{
for(i = 0i < F;i++)
aa[i] = a[i];
for(j = 0j < R;j++)
bb[i] = b[i];
best = var
}
else
{
if(var < best)
{//如果更优的话
best = var
for(i = 0i < F;i++)
aa[i] = a[i];
for(i = 0i < R;i++)
bb[i] = b[i];
}
}
return ;
}
if(beg > bmax)
return ;//没后轮选了
for(i = begi <= bmax;i++)
{//选下一个后轮
b[now] = i
dfsb(now+1,i+1);
}
}
void dfsa(int now,int beg)
{
int i,j,k,kk
if(F == now)
{//前轮选完了
if(a[0]3R1 > a[F-1]R2)
return//3x规则
dfsb(0,R1);//开始选后轮
return ;
}
if(beg > amax)
return ;//没前轮选了
for(i = begi <= amax;i++)
{//测试当前的前轮 然后开始选下一个前轮
a[now] = i
dfsa(now+1,i+1);
}
}
int main(void)
{
freopen(“cowcycle.in”,“r”,stdin);
freopen(“cowcycle.out”,“w”,stdout);
int i,j
scanf(“%d%d”,F,&R);
scanf(“%d%d%d%d”,F1,&F2,&R1,&R2);
amin = F1
amax = F2
bmax = R2
bmin = R1
aa[0] = -1//标记
dfsa(0,amin);//开始搜索
printf(“%d”,aa[0]);
//下面是输出
for(i = 1i < F;i++)
printf(“ %d”,aa[i]);
printf(“\n%d”,bb[0]);
for(i = 1i < R;i++)
printf(“ %d”,bb[i]);
printf(“\n“);
return 0
}
