关于一个运算优化的问题

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 的帖子

评分