【如花的忧郁男子】

题目描述

MinGW 是指只用自由软件来生成纯粹的 Win32 可执行文件的编译环境,它是 Minimalist GNU on Windows 的略称,可它尚未纯爷们,所以在这个需要百分百纯爷们的环境中总是会出现不和谐的一朵如花的忧郁男子——jsn1993!
事实上,那一朵忧郁的男子总是那么特立独行。在 22 世纪的,MinGW 星球有 62 亿人,假设光棍占 1/3,那么已婚男子和女子一共 2/3,所以一共有约 42 亿个男子,为了方便考虑,就假设一共有 232 个男子,编号从 1~232。引入一个概念“国家”,每个国家拥有的人是由三个参数 A,B,C 确定的,i 号国家拥有的人是 Ai,Ai+Ci,Ai+2Ci,…,Ai+kCi(Ai+kCi≤Bi)。但是由于 22 世纪是一个开放的年代,人人都拥有双重国籍,一部份人还拥有偶数重国籍,尽管有些人无国可籍。那不和谐的一朵如花的忧郁男子便是唯一一个只有奇数重国籍的人!现在给你这个星球,让你求出这一朵男子的编号与他拥有的国籍数。

输入格式

第一行一个数 N 表示国家数。
接下来 N 行,每行 3 个整数 Ai、Bi、Ci,描述这个国家。

输出格式

第一行一个数表示他的编号。
第二行一个数表示他拥有的国籍数。
如果没有如花的忧郁男子,输出  “Spring Brother Save Me!”。数据保证不会有多个如花的忧郁男子。

样例数据 1

输入

2
1 10 1
2 10 1

输出

1
1

备注

【数据范围】
10%的数据,N<5,Bi≤ 10。
50%的数据,N<20,Bi≤ 100 000。
100%的数据,N≤20000;Ai,Bi,C< 231

逗比的题目,逗比的数据……膜拜一下LLX大神

暴力+排序+离散+输出  “Spring Brother Save Me!”能拿80分……正解是如果某一个区间有奇数,那那个区间的翅膀总个数就是奇数,于是很明显就转化为一个二分问题了。

之后问题就是计算某个区间的翅膀个数了,其实这个也很容易,对于区间[L,R]计算一下用b[i]从1分别一直加到L和R的次数,再相减就是了,直接看代码比较容易明白:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*