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
大家看一下题目就发现那个输出太恶了.所以就把字符串给去掉了.这个题目大家过不去可能是忘记了高中数学里的概率的和积关系了.
比如第一个队伍得冠的应该是这么算的:当第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编辑过]
----------------解决方案--------------------------------------------------------
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/
----------------解决方案--------------------------------------------------------
----------------解决方案--------------------------------------------------------
不是最快过了那两个题目吗?
可惜这次cwande和eastsun没有能及时来.两个题目被ACKing做的也没有什么讨论的余地了.
不过第一个应该还有能讨论的地方.继续去改我那个烂的可以的程序.知道TLE或者RE为止
----------------解决方案--------------------------------------------------------
飞燕MM``又换造型```我还是喜欢上一个```
衣服很宽松滴露到肩膀```要是往下面拉一下.........
----------------解决方案--------------------------------------------------------
飞燕MM``又换造型```我还是喜欢上一个```
衣服很宽松滴露到肩膀```要是往下面拉一下.........
。。。。。。。。。。。。。。。。。。。
楼上走题了。。。
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/
[此贴子已经被作者于2007-9-15 23:00:12编辑过]
----------------解决方案--------------------------------------------------------
飞燕MM``又换造型```我还是喜欢上一个```
衣服很宽松滴露到肩膀```要是往下面拉一下.........
言辞请慎重~~~~~~~
----------------解决方案--------------------------------------------------------
还是楼上好啊。。。。。么~~~~
楼主发你的标程出来吧~~~
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/
----------------解决方案--------------------------------------------------------
逆序数:
#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;
}
----------------解决方案--------------------------------------------------------
大家多想想.
每个题目应该都能写的比我快
----------------解决方案--------------------------------------------------------