完整的 C# 源程序请参见：
Timus 1318. Logarithm :victory:
http://acm.timus.ru/很好的网站啊，我收藏了 我按73# 方法，105#的数据写了一下，是0.109 要看提交到上面的成绩
现在俺不相信上面的数据了
肯定是可以针对其数据作假的 134楼的那个小朋友很像我的侄女，一样精灵可爱，呵呵 :)
你的头像足够精灵可爱的了
回复 136# wayne 的帖子
谢谢夸奖:)我只在前面加了个排序，按理说时间应该变长，结果却出乎意料的由0.109变为0.093
看来还和测试机器的缓存相关！ 呵呵,离0.062越来越近了!我觉得这样下去破纪录是早晚的事儿!
我感觉可以到0.04左右,可以试试我说的方法,应该是个n*logN的方法,虽然常数稍微有些大!
原帖由 shshsh_0510 于 2009-3-18 11:48 发表 http://bbs.emath.ac.cn/images/common/back.gif
谢谢夸奖:)
我只在前面加了个排序，按理说时间应该变长，结果却出乎意料的由0.109变为0.093
看来还和测试机器的缓存相关！ 呵呵，不玩了，把正事都耽误了，估计也许真的可以在当前测试系统中达到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;
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),&(data),&(data),&(data),
// &(data),&(data),&(data),&(data));
// }
// scanf("%u %u %u %u",&(data),&(data),&(data),&(data));
//}else {
// for (i=0;i<count/2;i++)
// {
// tmp=i*8;
// scanf("%u %u %u %u %u %u %u %u",
// &(data),&(data),&(data),&(data),
// &(data),&(data),&(data),&(data));
// }
//}
////////////////////////////////////////////////////
//for (i=0;i<count*4;i++)
//{
// scanf("%u",&(data));
//}
////////////////////////////////////////////////////
//for (i=0;i<count;i++)
//{
// tmp=i*4;
// scanf("%u %u %u %u",&(data),&(data),&(data),&(data));
//}
for (i=0;i<count;i++){
for (j=i+1;j<count;j++){
tmp=i*4;
tmp2=j*4;
d1=data^data;
d2=data^data;
d3=data^data;
d4=data^data;
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;
}