首页 > ACM题库 > HDU-杭电 > hdu 2073 无限的路-递推-[解题报告]C++
2013
12-29

hdu 2073 无限的路-递推-[解题报告]C++

无限的路

问题描述 :

甜甜从小就喜欢画图画,最近他买了一支智能画笔,由于刚刚接触,所以甜甜只会用它来画直线,于是他就在平面直角坐标系中画出如下的图形:

甜甜的好朋友蜜蜜发现上面的图还是有点规则的,于是他问甜甜:在你画的图中,我给你两个点,请你算一算连接两点的折线长度(即沿折线走的路线长度)吧。

输入:

第一个数是正整数N(≤100)。代表数据的组数。
每组数据由四个非负整数组成x1,y1,x2,y2;所有的数都不会大于100。

输出:

第一个数是正整数N(≤100)。代表数据的组数。
每组数据由四个非负整数组成x1,y1,x2,y2;所有的数都不会大于100。

样例输入:

5
0 0 0 1
0 0 1 0
2 3 3 1
99 99 9 9
5 5 5 5

样例输出:

1.000
2.414
10.646
54985.047
0.000

点击打开链接

分析:这个线段距离原点的长可分为两部分。第一部分是无点的线段,长度依次为√(0^2+1^2)、√(1^2+2^2)、√(2^2+3^2)……√((n-1)^2+n^2)这个n的值刚好为这一点的横纵坐标之和;第二部分是有点的线段,这个很容易发现长度依次为√2、2√2、3√2、……(m-1)√2 ,第m条有点线段长度是这一点横坐标乘以√2.并且这个m的值与n相等.

      综上,只需要求出两个点距离原点的距离,相减求绝对值即可。

#include"stdio.h"
#include"math.h"
double fun(double x,double y)
{
	double ans;
	double m=(double)sqrt(2);
	int n,i;
	n=x+y;
	ans=0.0;
	for(i=1;i<n;i++)
		ans+=i*m;
	ans+=x*m;//这里注意
	for(i=0;i<n;i++)
		ans+=sqrt(i*i+(i+1)*(i+1));
	return ans;
}
int main()
{
	int t;
	int n;
	int x1,x2,y1,y2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%.3f\n",fabs(fun(x1,y1)-fun(x2,y2)));
	}
	return 0;
}

解题转自:http://blog.csdn.net/yangyafeiac/article/details/7828435


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。