问题 5315. -- 开灯-训练套题T3T1

5315: 开灯-训练套题T3T1

时间限制: 1 Sec  内存限制: 128 MB
献花: 865  解决: 382
[献花][花圈]

题目描述

1.        开灯(light.pas/c/cpp)

【问题描述】

  在一条无限长的路上,有一排无限长的路灯,编号为1,2,3,4......

  每一盏灯只有开或关两种状态,如果按一下某一盏的开关,那么这盏灯就会改变状态。刚开始时,所有灯都是关的。现做如下操作:

  每一次操作指定两个数a,t(a为实数,t为正整数)。将编号为[a],[2*a],[3*a],...[t*a]的灯的开关各按一次。其中[k]表示实数k的整数部分。

  在进行了n次操作后,只有一盏灯是开的,现在请计算这盏灯的编号。

【输入格式】

  第一行一个正整数n,表示n次操作;

  接下来n行,每行两个数,ai,ti,其中ai是实数,小数点后一定有6位,ti是正整数。

【输出格式】

  仅一个正整数,表示开着的那盏灯的编号。

【输入样例】

3

1.618034 13

2.618034 7

1.000000 21

【输出样例】

  20

【问题规模】

  记T=t1+t2+t3+...+tn

  对于30%的数据,满足T<=1000

对于80%的数据,满足T<=200000

对于100%的数据,满足T<=10000000

对于100%的数据,满足n<=5000,1<=ai<1000,1<=ti<=T

数据保证,在经过n次操作后,有且只有一盏灯是开的,不必判错。

输入

输出

提示


1.开灯



  【题目大意】



  给定T个数,如果将这T个数两两配对,最后恰好剩下一个数。问这个数是多少。



  【解法一】



  容易想到,先将这些数进行排序,然后从小到大进行配对。当出现有一个数无法配对的时候,这个数就是答案。    如果使用快速排序,时间复杂度为O(nlogn)。预计得分80--1 00



【解法二】



    这个解法不易想到。任何两个相同的数的异或和为0。所以求这T个数的异或和,所



有能配对上的数异或和为0,最后的结果就是那个“与众不同’’的数。 



 时间复杂度为0(n),而且程序比解法一还要简单。预计得分100  



【出题人的意图】



  这道题就是想考查能不能想到解法二。最开始设计此题的时候,是想从文件中直接



读入T个数,但是发现输入文件实在太大了,而且读入的时间也非常大。后来就想着能不



毫读入少一点,要用程序将这T个数算出来。于是就有了这道题。



  [a*t]的设计就不想让选手利用这T个数的规律从而计算出答案。笔者个人没有想到能利用此规律解题的办法,当然,如果你能想到,欢迎交流。



  本题是这次模拟赛的第1题,应该定位为送分题,所以如果你能写好一个快排,就能得到80分。本来想将T开到1000万,后来觉得还是鼓励写得好的快排,所以只开到了2 00万。笔者试过,快排也可以通过所有的测试点



    还有两个要注意的问题。第一,如果在求这T个数的过程中,没有用double,而用来float,会因为精度不足,失20分,第二,快排中没有使用随机,可能会退化成O(n^2),失



2 0分.

来源

[献花][花圈]