比赛结果:感觉还是有很多再做的.贴子都顶到7页了.能看到这么多人在做我就很高兴了.对不对并不重要.说不定我数据搞错了.
leeco做两个.hjin也过了一个

先说一下基础的三个吧.
扇形面积:原来题目是:http://acm.jlu.edu.cn/joj/showproblem.php?pid=2437
原题:背景是圈地运动.告诉你你的马一天能走的距离.然后你早上出发走到晚上停止.那么你圈的地就是你的出发点到结束点这条直线和你跑出来的路线所围成的面积..
本来应该算的是一个弓形.结果那天弄了半天样例都没有过.结果才发祥题目出了问题.他算的是扇形面积.所以过了这个题目的可以把自己的程序改一下精度直接去那上面提交...

已知弦长和弧长可以列出这样的方程sin(k)-2*x*k/l=0(k是弧度所对应的半角度).如果是个优弧的话方程要变一下.
这个方程是没有公式的.但是只要你用笔话一下可以发现 y=sin(k),和y=2*x*k/l是只有一个交点的.所以就满足了二分的要求.当然你还可以发现y=sin(k)/(2*x*k/l)是单调的.所以你也可以用更快的牛顿切线或者迭代.

世界杯:http://acm.tju.edu.cn/toj/showp2865.html

大家看一下题目就发现那个输出太恶了.所以就把字符串给去掉了.这个题目大家过不去可能是忘记了高中数学里的概率的和积关系了.
比如第一个队伍得冠的应该是这么算的:当第1对进入决赛.那他面对的应该是8--16.那么:
P=p8*A[1,8]/100+p9*A[1,9]/100.0+....+; pi代表的是第i队进入决赛的概率..依次类推到进入前4强和前8强.

逆序数:(太失败了.提供的程序出了点问题..向大家道歉)
大家可以把程序直接到这里去提交: http://acm.pku.edu.cn/JudgeOnline/problem?id=2085

一定要发现一个重要的规律.其实在描述里就已经给了.那就是n个数字的全排列最大的逆序数是n*(n-1)/2
那么怎么样保证给你一个逆序数你输出最小的全排列呢? 很明显要全排列最小也就是第一个数字小.第一个数字小当然就是后面的逆序数大.
假设你排到第k个
当m>k*(k-1)/2 输出第m-k*(k-1)/2大的数.然后把没有输出的从大到小输出就可以了
当m<k*(k-1)/2 输出最小的就可以了.接下来继续试探第k+1个数字
当m=k*(k-1)/2 从大到小输出所有的
所以整体上应该是个O(n)

提高题目:
做的最好的毫无疑问的是ACking.第二个题目经过他的提示catlan数算是明白.第一个题目他是过了..我还是没过..
这两个题目就不说了...大家继续讨论..

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

不是最快过了那两个题目吗?
可惜这次cwande和eastsun没有能及时来.两个题目被ACKing做的也没有什么讨论的余地了.
不过第一个应该还有能讨论的地方.继续去改我那个烂的可以的程序.知道TLE或者RE为止

逆序数:
#include<stdio.h>
typedef __int64 int64;
bool flag[50009];
int main()
{
int64 n,m,sum;
int i,j,k;
while(scanf("%I64d%I64d",&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;
}

世界杯
#include<stdio.h>
#include<string.h>
double b[4][17];
int a[17][17];
void dfs(int x,int y,int deep)
{
int i,j;
if(y-x==1) b[deep][x]=a[x][y]/100.0,b[deep][y]=a[y][x]/100.0;
else
{
dfs(x,(y+x)/2,deep+1);
dfs((y+x)/2+1,y,deep+1);
for(i=x;i<=(y+x)/2;i++)
{
b[deep][i]=0.0;
for(j=(y+x)/2+1;j<=y;j++)
{
b[deep][i]+=b[deep+1][i]*b[deep+1][j]*a[i][j]/100.0;
}
}
for(i=(y+x)/2+1;i<=y;i++)
{
b[deep][i]=0.0;
for(j=x;j<=(x+y)/2;j++)
{
b[deep][i]+=b[deep+1][i]*b[deep+1][j]*a[i][j]/100.0;
}
}
}
}
int main()
{

int i,j,n,m,l;
int t,k;
scanf("%d",&t);
k=1;
while(k<=t)
{
for(i=1;i<=16;i++)
{
for(j=1;j<=16;j++) scanf("%d",&a[i][j]);
}
dfs(1,16,0);
printf("Scenario #%d:\n",k);
for(i=1;i<=16;i++)
{
printf("%.2f\n",b[0][i]*100);
}
printf("\n");
k++;
}
return 0;

}
扇形面积:
#include<stdio.h>
#include<math.h>
#define inf 1e-10
double l,x;
double pi;
double f(double k)
{
return sin(k)-2*x*k/l;
}
double g(double k)
{
return sin(k)-2*x*(pi-k)/l;
}
int main()
{

double mid,max,min,r,ans;
pi=acos(-1);
while(scanf("%lf%lf",&x,&l)!=EOF)
{
x/=2.0;
if (fabs(pi * x - l) < inf)
{
printf("%lf\n",pi * x * x);
}
if(l<pi*x)
{
min=0;
max=pi;
while(max-min>inf)
{
mid=(min+max)/2;
if(f(mid)>=0)
{
min=mid;
}
else max=mid;
}
mid = (max + min) / 2;
r=x/sin(mid);
ans=r*r*mid;
}
else
{
min=0;
max=pi;
while(max-min>inf)
{
mid=(min+max)/2;
if(g(mid)>0) max=mid;
else min=mid;
}
r=x/sin(min);
ans=r*r*(pi-min);
}
printf("%.2lf\n",ans);
}
return 0;

}

大家多想想.
每个题目应该都能写的比我快

哪个地方?

我给你的程序只有
typedef __int64 int64;
和这个:
scanf("%I64d%I64d",&n,&m)!=EOF
不同啊!.

我前面贴的程序在VC上没有错误啊?
可能你的G++也是用%I64d把..你改一下给大家rejudge一下...
就是那个64位出了问题

把大家给害了.可怜的leeco,hjin

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

第三个到这里去提交吧:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2085

题目是完全一样的

恩.
你改一下到PKU上去提交.我在那也只能70多MS

你那64位到底怎么用??