关于第十八期比赛

你那64位到底怎么用??
----------------解决方案--------------------------------------------------------
我都说了两种都可以啦



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
----------------解决方案--------------------------------------------------------
#define PB_ID bccn18_3
#include<stdio.h>
typedef long long int64;
bool flag[50009];
int main()
{
int64 n,m,sum;
int i,j,k;
while(scanf("%lld%lld",&n,&m)!=EOF) //你看一下你的64位输入用的是%lld还是%I64d。可能要做一下改动
{
if(n==-1&&m==-1) break ;
for(i=1;i<=n;i++) flag[i]=0;
k=1;
for(i=1;i<n;i++)
{
sum=(n-i)*(n-i-1)/2;
if(sum>=m)
{
for(;flag[k];k++);
printf("%d ",k);
flag[k]=1;
}
else
{
m=m-sum;
for(j=k;j<=n;j++)
{
if(flag[j]==0) m--;
if(m==0) break;
}
for(j++;flag[j];j++);
printf("%d ",j);
flag[j]=1;
i++;
break;
}
}
if(i<n)
{
for(j=n;j>=1&&i<n;j--)
{
if(!flag[j])
{
printf("%d ",j);
flag[j]=1;
i++;
}
}
}
for(i=1;i<=n;i++)
{
if(!flag[i])
{
printf("%d\n",i);
break;
}
}
}
return 0;
}

第三题LZ提供的标程，错哪？？



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
----------------解决方案--------------------------------------------------------
偶自己觉得错在这:
#define PB_ID bccn18_3
#include<stdio.h>
typedef long long int64;
bool flag[50009];
int main()
{
int64 n,m,sum;
int i,j,k;
while(scanf("%lld%lld",&n,&m)!=EOF)
----------------解决方案--------------------------------------------------------

发现世界杯,那个题目leeco写的比我好

----------------解决方案--------------------------------------------------------
我发现我第三题是个O(n)的.
里面的循环只循环一次就会跳出所以循环.最坏的情况是3*n
----------------解决方案--------------------------------------------------------

for(;flag[k];k++);

you are searching the first k such that flag[k] is not set from
whatever a lower bound:

for(k=lower_bound; flag[k]; k++)

or more readable:

for(k=lower_boud; ; k++)
{
if(flag[k]==0)
{
break;
}

}

This lower_bound is indeterminate and it is possible you have to
search O(n) times here.

[此贴子已经被作者于2007-9-16 13:57:26编辑过]

----------------解决方案--------------------------------------------------------
thanks, ACed at pku for 78ms.

I saw people got ACed for 0ms.

----------------解决方案--------------------------------------------------------
偶也只能到78
----------------解决方案--------------------------------------------------------

这个比我先前那个明显好很多.但是速度也就快10几.
#include<stdio.h>
int main()
{
unsigned long n,m,sum;
int i,j,k;
while(scanf("%u%u",&n,&m)!=EOF)
{
if(n==-1&&m==-1) break ;
k=1;
for(i=1;i<=n;i++)
{
sum=(n-i)*(n-i-1)/2;
if(sum>=m)
{
printf("%d ",i);
}
else
{
m=m-sum+i;
printf("%d ",m);
break;
}
}
for(j=n;j>=i;j--)
{
if(j==m) continue;
printf("%d ",j);
}
printf("\n");
}
return 0;
}

----------------解决方案--------------------------------------------------------