hdu 3064 twoNumber

时间：2023-03-08 20:22:23
hdu 3064 twoNumber

twoNumber

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 2048/1024 K (Java/Others)
Total Submission(s): 675    Accepted Submission(s): 210

Problem Description
小白请你帮个忙，在一大堆杂乱无章的数字中，找出两个丢失的数字。
这堆数字虽然杂乱无章，但是有一个特点，就是没有重复的数字，而且排序后可以首尾相连（不过丢失了两个）；
由于数字可能会比较多，所以有一部分数字已经被合并压缩：
1 2 3 4 5
可以表示为数字段[1,5]；
Input
输入一个n，表示有多少个数字段输入（0< n<1000000）
接下去输入两个数字，分别代表连续区间中最小的数字和最大的数字 (1<= st <= end <= 1000000)，当然这个数字可能已经丢失。
接下去输入n行，每行输入2个数字（St，End）(1<= st <= end <= 1000000)。
St代表数字区间的开始，End代表数字区间的末尾。
Output
输出缺少的两个数（小的先输出）
数据保证缺少且仅缺少两个不相同的数字。
Sample Input
4
1 15
1 3
7 9
4 6
11 14
Sample Output
10 15
Hint

HINT: be careful with the memory limit;

Source
思路：
 1：前n项和公式：1+2+3+...+n = n*(n+1)/2
2：前n项平方和公式：1^2+2^2+.........+n^2=n*（n＋1）*（2n＋1）/6
要求的两个数记为a，b；
有：
区间所有数的和可以算出来记为ans1，已给出的区间的和累加到sum1上，ans1-sum1即为要求的两个数的和；即a+b = ans1-sum1；
同理：
区间所有数的平方的和算出来记为ans2，已给出的区间的每一项的平方的和累加到sum2上，ans2-sum2即为要求的两个数的平方的和；则有a^2+b^2
= ans2-sum2;
然后解方程就可以了！
注意:
里面的数得用__int64位存，注意运算过程中的类型转换！
代码：
 #include "stdio.h"

 #include "math.h"

 int main()

 {

     int n;

     __int64 x,y;

     __int64 ans1,ans2;

     __int64 sum1,sum2;

     __int64 t1,t2;

     __int64 a,b;

     __int64 deta;

     while(scanf("%d",&n)!=-)

     {

         ans1 = ans2 = ;

         sum1 = sum2 = ;

         scanf("%I64d %I64d",&x,&y);

         ans1 = (x+y)*(y-x+)/;

         t1 = x*(x-)*(*x-)/;

         t2 = y*(y+)*(*y+)/;

         ans2 = t2-t1;

         while(n--)

         {

             scanf("%I64d %I64d",&x,&y);

             sum1 += (x+y)*(y-x+)/;

             t1 = x*(x-)*(*x-)/;

             t2 = y*(y+)*(*y+)/;

             sum2 += t2-t1;

         }

         ans1 -= sum1;

         ans2 -= sum2;

         a = ans1;

         b = ans2;

         deta = (__int64)sqrt((double)(*b-a*a));

         x = (a-deta)/;

         y = a - x;

         printf("%I64d %I64d\n",x,y);

     }

     return ;

 }

相关文章