关于一个运算优化的问题

skyivben · 发表于 2009-3-17 21:44:12

我使用分治法，解这道题的运行时间是 0.406 秒。完整的 C# 源程序请参见： Timus 1318. Logarithm

wayne · 发表于 2009-3-17 23:26:46

http://acm.timus.ru/很好的网站啊，我收藏了

shshsh_0510 · 发表于 2009-3-18 09:36:48

我按73# 方法，105#的数据写了一下，是0.109

无心人 · 发表于 2009-3-18 09:54:25

要看提交到上面的成绩现在俺不相信上面的数据了肯定是可以针对其数据作假的

wayne · 发表于 2009-3-18 11:40:46

134楼的那个小朋友很像我的侄女，一样精灵可爱，呵呵

无心人 · 发表于 2009-3-18 11:45:23

你的头像足够精灵可爱的了

shshsh_0510 · 发表于 2009-3-18 11:48:15

谢谢夸奖

我只在前面加了个排序，按理说时间应该变长，结果却出乎意料的由0.109变为0.093 看来还和测试机器的缓存相关！

litaoye · 发表于 2009-3-18 11:55:32

呵呵,离0.062越来越近了!我觉得这样下去破纪录是早晚的事儿! 我感觉可以到0.04左右,可以试试我说的方法,应该是个n*logN的方法,虽然常数稍微有些大!

原帖由 shshsh_0510 于 2009-3-18 11:48 发表谢谢夸奖我只在前面加了个排序，按理说时间应该变长，结果却出乎意料的由0.109变为0.093 看来还和测试机器的缓存相关！

shshsh_0510 · 发表于 2009-3-18 12:04:36

呵呵，不玩了，把正事都耽误了，估计也许真的可以在当前测试系统中达到0.067 把代码贴上，谁有兴趣就试一下看。总结一下：按73# 方法倒着比较，对随机数据在平均复杂性意义下，基本上就是最快的程序了。在该系统中，也能达到0.4 接下来，其实就不是看算法了，而在猜测试数据

其数据中，异或后小于 2^32的很多，所以先判断一下前3个异或值是不是0立刻可以到达0.109 我还试着调节调用scanf的次数，但看起来没什么差别。对每个判断逻辑进行一些手工优化，但并不比编译器好。一个令我出乎意料的是，在前面加了一个sort,居然变为0.093 拍完序当然还可以分治一下什么的，但归根结底还是猜测试数据的样子，有点像是黑客了

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int compare( const void *arg1, const void *arg2 )
{
//return _stricmp( * ( char** ) arg1, * ( char** ) arg2 );
if(*((unsigned int *)arg1) !=*((unsigned int *)arg2))
return *(unsigned int *)arg1>* ( unsigned int *)arg2;
if(* (( unsigned int*)arg1+1)!=* (( unsigned int*)arg2+1))
return * (( unsigned int*)arg1+1)>* (( unsigned int*)arg2+1);
if(* (( unsigned int*)arg1+2)!=* (( unsigned int*)arg2+2))
return * (( unsigned int*)arg1+2)>* (( unsigned int*)arg2+2);
return * (( unsigned int*)arg1+3)>* (( unsigned int*)arg2+3);
}
int main(int argc, char* argv[])
{
unsigned int * tmp3;
int count,result,i,j,tmp2,tmp;
unsigned int data[4*5000];
unsigned int d1,d2,d3,d4;
scanf("%d",&count);
result=0;
tmp=0;
tmp2=count*4;
while (tmp<tmp2) {
tmp3=data+tmp;
scanf("%u",data+tmp);
tmp++;
// scanf("%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u%u",
// tmp3,tmp3+1,tmp3+2,tmp3+3,tmp3+4,tmp3+5,tmp3+6,tmp3+7,tmp3+8,tmp3+9,tmp3+10,tmp3+11,tmp3+12,tmp3+13,tmp3+14,tmp3+15);
// tmp+=16;
}
qsort( (void *)data, (size_t)count, 16, compare );
/////////////////////////////////////////////////////
// if ( count &0x1) {
// for (i=0;i<(count-1)/2;i++)
// {
// tmp=i*8;
// scanf("%u %u %u %u %u %u %u %u",
// &(data[tmp]),&(data[tmp+1]),&(data[tmp+2]),&(data[tmp+3]),
// &(data[tmp+4]),&(data[tmp+5]),&(data[tmp+6]),&(data[tmp+7]));
// }
// scanf("%u %u %u %u",&(data[tmp+8]),&(data[tmp+9]),&(data[tmp+10]),&(data[tmp+11]));
// }else {
// for (i=0;i<count/2;i++)
// {
// tmp=i*8;
// scanf("%u %u %u %u %u %u %u %u",
// &(data[tmp]),&(data[tmp+1]),&(data[tmp+2]),&(data[tmp+3]),
// &(data[tmp+4]),&(data[tmp+5]),&(data[tmp+6]),&(data[tmp+7]));
// }
// }
////////////////////////////////////////////////////
// for (i=0;i<count*4;i++)
// {
// scanf("%u",&(data[i]));
// }
////////////////////////////////////////////////////
// for (i=0;i<count;i++)
// {
// tmp=i*4;
// scanf("%u %u %u %u",&(data[tmp]),&(data[tmp+1]),&(data[tmp+2]),&(data[tmp+3]));
// }
for (i=0;i<count;i++){
for (j=i+1;j<count;j++){
tmp=i*4;
tmp2=j*4;
d1=data[tmp]^data[tmp2];
d2=data[tmp+1]^data[tmp2+1];
d3=data[tmp+2]^data[tmp2+2];
d4=data[tmp+3]^data[tmp2+3];
if(d1==0 && d2==0 && d3==0) { goto C1;} //0.218
//(0,160047680,1518781562,1262177448)
// if ( (d1>1262177448) ||
// (d1==1262177448 && d2 >1518781562) ||
// (d1==1262177448 && d2 ==1518781562 && d3 >160047680 ) ||
// (d1==1262177448 && d2 ==1518781562 && d3 ==160047680 ) )
if ( (d1>1262177448) || ( d1==1262177448 && (d2 >1518781562 || (d2 ==1518781562 && d3 >=160047680))))
{result+=38;continue;}
//(0,16004768,3587851993,126217744),
// if ( (d1>126217744) ||
// (d1==126217744 && d2 >3587851993) ||
// (d1==126217744 && d2 ==3587851993 && d3 >16004768 ) ||
// (d1==126217744 && d2 ==3587851993 && d3 ==16004768 ) )
if ( (d1>126217744) || ( d1==126217744 && (d2 >3587851993 || (d2 ==3587851993 && d3 >=16004768))))
{result+=37;continue;}
//(0,3008077584,2076772117,12621774),
if ( (d1>12621774) ||
(d1==12621774 && d2 >2076772117) ||
(d1==12621774 && d2 ==2076772117 && d3 >3008077584 ) ||
(d1==12621774 && d2 ==2076772117 && d3 ==3008077584) )
{result+=36;continue;}
//(0,730304488,1925664130,1262177),
if ( (d1>1262177) ||
(d1==1262177 && d2 >1925664130) ||
(d1==1262177 && d2 ==1925664130 && d3 >730304488 ) ||
(d1==1262177 && d2 ==1925664130 && d3 ==730304488 ) )
{result+=35;continue;}
//(0,932023908,3199043520,126217),
if ( (d1>126217) ||
(d1==126217 && d2 >3199043520) ||
(d1==126217 && d2 ==3199043520 && d3 >932023908 ) ||
(d1==126217 && d2 ==3199043520 && d3 ==932023908 ) )
{result+=34;continue;}
//(0,952195850,3326381459,12621),
if ( (d1>12621) ||
(d1==12621 && d2 >3326381459) ||
(d1==12621 && d2 ==3326381459 && d3 >952195850 ) ||
(d1==12621 && d2 ==3326381459 && d3 ==952195850 ) )
{result+=33;continue;}
//(0,2242703233,762134875,1262),
if ( (d1>1262) ||
(d1==1262 && d2 >762134875) ||
(d1==1262 && d2 ==762134875 && d3 >2242703233 ) ||
(d1==1262 && d2 ==762134875 && d3 ==2242703233 ) )
{result+=32;continue;}
//(2147483648,3230747430,935206946,126),
if ( (d1>126) ||
(d1==126 && d2 >935206946) ||
(d1==126 && d2 ==935206946 && d3 >3230747430 ) ||
(d1==126 && d2 ==935206946 && d3 ==3230747430 && d4> 2147483647) )
{result+=31;continue;}
//(1073741824,1182068202,2670501072,12),
if ( (d1>12) ||
(d1==12 && d2 >2670501072) ||
(d1==12 && d2 ==2670501072 && d3 >1182068202 ) ||
(d1==12 && d2 ==2670501072 && d3 ==1182068202 && d4> 1073741823) )
{result+=30;continue;}
//(2684354560,1836193738,1126043566,1),
if ( (d1>1) ||
(d1==1 && d2 >1126043566) ||
(d1==1 && d2 ==1126043566 && d3 >1836193738 ) ||
(d1==1 && d2 ==1126043566 && d3 ==1836193738 && d4> 2684354559) )
{result+=29;continue;}
//(268435456,1042612833,542101086,0),
if ( (d1>0) ||
(d1==0 && d2 >542101086) ||
(d1==0 && d2 ==542101086 && d3 >1042612833 ) ||
(d1==0 && d2 ==542101086 && d3 ==1042612833 && d4> 268435455) )
{result+=28;continue;}
//(3892314112,2681241660,54210108,0),
if ((d2 >54210108) ||
(d2 ==54210108 && d3 >2681241660 ) ||
(d2 ==54210108 && d3 ==2681241660 && d4> 3892314111) )
{result+=27;continue;}
//(3825205248,3704098002,5421010,0),
if ((d2 >5421010) ||
(d2 ==5421010 && d3 >3704098002 ) ||
(d2 ==5421010 && d3 ==3704098002 && d4> 3825205247) )
{result+=26;continue;}
// ,(1241513984,370409800,542101,0)
if ((d2 >542101) ||
(d2 ==542101 && d3 >370409800 ) ||
(d2 ==542101 && d3 ==370409800 && d4> 1241513983) )
{result+=25;continue;}
// ,(2701131776,466537709,54210,0)
if ((d2 >54210) ||
(d2 ==54210 && d3 >466537709 ) ||
(d2 ==54210 && d3 ==466537709 && d4> 2701131775) )
{result+=24;continue;}
// ,(4135583744,46653770,5421,0)
if ((d2 >5421) ||
(d2 ==5421 && d3 >46653770 ) ||
(d2 ==5421 && d3 ==46653770 && d4> 4135583743) )
{result+=23;continue;}
// ,(2990538752,434162106,542,0)
if ((d2 >542) ||
(d2 ==542 && d3 >434162106 ) ||
(d2 ==542 && d3 ==434162106 && d4> 2990538751) )
{result+=22;continue;}
// ,(3735027712,902409669,54,0)
if ((d2 >54) ||
(d2 ==54 && d3 >902409669 ) ||
(d2 ==54 && d3 ==902409669 && d4> 3735027711) )
{result+=21;continue;}
// ,(1661992960,1808227885,5,0)
if ((d2 >5) ||
(d2 ==5 && d3 >1808227885 ) ||
(d2 ==5 && d3 ==1808227885 && d4> 1661992959) )
{result+=20;continue;}
// ,(2313682944,2328306436,0,0)
if ((d2 >0) ||
(d2 ==0 && d3 >2328306436 ) ||
(d2 ==0 && d3 ==2328306436 && d4> 2328306435) )
{result+=19;continue;}
// ,(2808348672,232830643,0,0)
if ((d3 >232830643 ) ||
(d3 ==232830643 && d4> 2808348671) )
{result+=18;continue;}
// ,(1569325056,23283064,0,0)
if ((d3 >23283064 ) ||
(d3 ==23283064 && d4> 1569325055) )
{result+=17;continue;}
// ,(1874919424,2328306,0,0)
if ((d3 >2328306 ) ||
(d3 ==2328306 && d4> 1874919423) )
{result+=16;continue;}
// ,(2764472320,232830,0,0)
if ((d3 >232830 ) ||
(d3 ==232830 && d4> 2764472319) )
{result+=15;continue;}
// ,(276447232,23283,0,0)
if ((d3 >23283 ) ||
(d3 ==23283 && d4> 276447231) )
{result+=14;continue;}
// ,(1316134912,2328,0,0)
if ((d3 >2328 ) ||
(d3 ==2328 && d4> 1316134911) )
{result+=13;continue;}
// ,(3567587328,232,0,0)
if ((d3 >232 ) ||
(d3 ==232 && d4> 3567587327) )
{result+=12;continue;}
// ,(1215752192,23,0,0)
if ((d3 >23 ) ||
(d3 ==23 && d4> 1215752191) )
{result+=11;continue;}
// ,(1410065408,2,0,0)
if ((d3 >2 ) ||
(d3 ==2 && d4> 1410065407) )
{result+=10;continue;}
//(1000000000,0,0,0),
C1:
if ((d3 >0 ) ||
(d3 ==0 && d4> 999999999) )
{result+=9;continue;}
//(100000000,0,0,0),
if (d4> 99999999) {result+=8;continue;}
if (d4> 9999999) {result+=7;continue;}
if (d4> 999999) {result+=6;continue;}
if (d4> 99999) {result+=5;continue;}
if (d4> 9999) {result+=4;continue;}
if (d4> 999) {result+=3;continue;}
if (d4> 99) {result+=2;continue;}
if (d4> 9) {result+=1;continue;}
}
}
printf("%u",result*2);
return 0;
}

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[求助] 关于一个运算优化的问题

回复 136# wayne 的帖子

评分