首页 > ACM题库 > HDU-杭电 > hdu 2624 Thanks for your love-数学相关-[解题报告]C++
2014
02-12

hdu 2624 Thanks for your love-数学相关-[解题报告]C++

Thanks for your love

问题描述 :

Thanks for your love——Do not ask me how many people ever I loved,you do not know how deep my injury. Did not dare, do not want to, should not be, thank you for your love again. I had to exist like a dust or will bring you harm. Did not dare, do not want to, should not be, thank you for your love again. I had to exist in your future.
This is my most fear that brought to your harm Forever.

Zty have N friends, most friends in his feeling were the same but exactly one (while all other people are equal in his felling). In order to detect which is the people that he has different feeling, he ask himself a lot of questions. With this question , your task is to determine the identifier of the friend who he has different feeling about using the results of these questions. We assigning each friend of him a unique integer identifier from 1 to N.

输入:

The first line of the input file contains two integers N and M, separated by spaces, where N is the number of friends Zty has (2<=N<=10000 ) and M is the number of questions fulfilled (1<=M<=100). The following 2M lines describe all questions. Two consecutive lines describe each question. The first of them starts with a number Ti (1 <= Ti <= N/2), representing the number of friends placed in the left group and in the right group, followed by Ti identifiers of friends placed in the left group and Ti identifiers of friends placed in the right group. All numbers are separated by spaces. The second line contains one of the following characters: ‘<’, ‘>’, or ‘=’.
It represents the result of the sum feelings:
‘<’ means that the sum of all the feeling in the left group is less than the sum of all the feeling in the right group.
‘>’ means that the sum of all the feeling in the left group is greater than the sum of all the feeling in the right group,
‘=’ means that the sum of all the feeling in the left group is equal to the sum of all the feeling in the right group.

输出:

The first line of the input file contains two integers N and M, separated by spaces, where N is the number of friends Zty has (2<=N<=10000 ) and M is the number of questions fulfilled (1<=M<=100). The following 2M lines describe all questions. Two consecutive lines describe each question. The first of them starts with a number Ti (1 <= Ti <= N/2), representing the number of friends placed in the left group and in the right group, followed by Ti identifiers of friends placed in the left group and Ti identifiers of friends placed in the right group. All numbers are separated by spaces. The second line contains one of the following characters: ‘<’, ‘>’, or ‘=’.
It represents the result of the sum feelings:
‘<’ means that the sum of all the feeling in the left group is less than the sum of all the feeling in the right group.
‘>’ means that the sum of all the feeling in the left group is greater than the sum of all the feeling in the right group,
‘=’ means that the sum of all the feeling in the left group is equal to the sum of all the feeling in the right group.

样例输入:

5 3
1 1 2
=
1 3 4
>
1 4 5
=

样例输出:

3



 HOJ1624 Triplets
这体本身思想就不是太好想,利用高中数轴的思想得出一结论

   
Max(A,B,C)-Min(A,B,C)=(|A-B|+|B-C|+|C-A|)/2,

 想到此点就像脑筋急转弯的感觉,也是数学意识的体现。



  该题 Ta = (Ia, Ja, Ka) and Tb = (Ib, Jb,
Kb),

D(Ta, Tb) = max {Ia-Ib, Ja-Jb,
Ka-Kb}-min{Ia-Ib,Ja-Jb,Ka-Kb},最后让你求给



一定数量的T_vector,求任意两个T的D值的总和。

 
直接计算会超时,要想想特殊数学方法,真的有时想来到一定时候时数学始终在作怪,数学功底不行啊,嘿嘿。

 

 
任意两个T_vector的差计算耗时,而且任意两个T_vector间具有耦合性,要是将问题划分为独立的子问题较好。

  转化思维: 

 D(Ta,Tb)=(|(Ia-Ib)-(Ja-Jb)|+|(Ja-Jb)-(Ka-Kb)|+|(Ka-Kb)-(Ia-Ib)|)/2;

转化为D(Ta,Tb)=(|(Ia-Ja)-(Ib-Jb)|+|(Ja-Ka)-(Jb-Kb)|+|(Ka-Ia)-(Kb-Ib)|)/2;

 
这样即可将耦合问题转化为独立问题了。

 

  Ux=(Ix-Jx) Vx=(Jx-Kx) Wx=(Kx-Ix);

  D(Tx,Ty)=(|Ux-Uy|+|Vx-Vy|+|Wx-Wy|)/2;

 
首先将U,V,W按照从小到大顺序排序,U0<U1<…<Un-1

  然后分析Ui
,可知其当被减数时次数为t,作减数时次数为(n-1-t)

 
故Ui在其算式中累加结果为Ui*(2*t-n+1);



  代码如下:

#include <iostream>

#include <algorithm>

using namespace  std;

#define M 200005



int a[M],b[M],c[M];

int main(void)

{

    int
n,x,y,z,i;

    long long
sum;

   

   
while((scanf(“%d”,&n))==1&&n!=0)

    {

   
    sum=0;

   
   
for(i=0;i<n;i++)

   
    {

   
   
   
cin>>x>>y>>z;

   
   
    a[i]=x-y;
b[i]=y-z;c[i]=x-z;

   
    }

   
   

   
   
sort(a,a+n);

   
   
sort(b,b+n);

   
   
sort(c,c+n);

   
   
for(i=0;i<n;i++)

   
   
   
sum+=(a[i]+b[i]+c[i])*(2*i-n+1);

   
   
sum/=2;

   
   
cout<<sum<<endl;

    }



    return
0;

}

 
终于感受到数学的巨大作用了,当你走投无路时,来想想数学的思维,真的是绝啊。

 

 

 

解题转自:http://blog.sina.com.cn/s/blog_4d3c6319010097vz.html