HDU6040 Hints of sd0061 分治排序

http://acm.hdu.edu.cn/showproblem.php?pid=6040

Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

Sample Input

Sample Output

Source

题意

给一个随机程序,生成一个长度为n的数组$a_i$,再给m次寻问$b_i$,询问数组$a_i$排序后,排名为$b_i+1$的数是多少。

思路

将询问的$b_i$数组排序,对$a_i$数组进行分治,类似于快排,选取参考点,交换数据后,在$b_i$数组中二分查找mid的范围,那么此时$b_i=mid$的询问都做出来了,此时$a_i$$b_i$数组都分成了左右两部分,直接递归处理这两部分即可。

 

 

PowerOJ 尔尔序的神奇计数问题 暴力or容斥


尔尔序的神奇计数问题

Time Limit: 8000 MS Memory Limit: 2097152 KB

Description

    现在有$4$个集合,分别为$A,B,C,D$,且每一个集合的大小都是$n$。尔尔序想求解一个问题,现在他把$A,B,C$的交集的大小、$A,B,D$的交集的大小,$A,C,D$的交集的大小,$B,C,D$的交集的大小之和记为$X$,同时把$A,B$的交集的大小、$A,C$的交集的大小、$A,D$的交集的大小、$B,C$的交集的大小、$B,D$的交集的大小之和记为$Y$,求解$|X-Y|$的值。

Input

第一行输入一个整数$n$ ($1 \leq n \leq 5 \times 10^4$)代表这$4$个集合的大小。 第二行输入$n$整数$A_i$ ($1 \leq A_i \leq 10^{18}$),代表集合$A$中的数。 第三行输入$n$整数$B_i$ ($1 \leq B_i \leq 10^{18}$),代表集合$B$中的数。 第四行输入$n$整数$C_i$ ($1 \leq C_i \leq 10^{18}$),代表集合$C$中的数。 第五行输入$n$整数$D_i$ ($1 \leq D_i \leq 10^{18}$),代表集合$D$中的数。 保证在同一集合内没有重复的数。

Output

输出$|X-Y|$的值。

Sample Input

Sample Output

题解

数据量比较小,对每个集合排序后,用set_intersection求交集即可。使用容斥原理可以发现,最后的答案其实是|size(A+B+C+D) + size(CD) + size(ABCD) – 4*n|

C++代码

Java代码

 

 

 

 

HDU5943 Kingdom of Obsession 暴力判质数+二分匹配

http://acm.hdu.edu.cn/showproblem.php?pid=5943


Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there are $n$ people with their id continuous $(s+1, s+2, \cdots, s+n)$ standing in a line in arbitrary order, be more obsessively, people with id $x$ wants to stand at $y^{th}$ position which satisfy
$$x \mod y = 0$$
Is there any way to satisfy everyone's requirement?

Input

First line contains an integer $T$, which indicates the number of test cases.
Every test case contains one line with two integers $n$, $s$.
Limits
$1 \leq T \leq 100$.
$1 \leq n \leq 10^9$.
$0 \leq s \leq 10^9$.

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.
If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.

Sample Input

2
5 14
4 11

Sample Output

Case #1: No
Case #2: Yes

Source

 

题意:

有n个人,分别id为s+1,s+2,……s+n,现在让这n个人排队,要求每个位置的人的id要能被位置号整除,问是否可行。

思路:

考虑到id为质数的人,只能被放到第一个位置,或者放到位置号和他id相同的位置。当s+1……s+n区间内出现2个质数以上质数的时候,一定要将后部分放到前面去。因为数据范围为$1 \leq n \leq 10^9$.$0 \leq s \leq 10^9$.这个范围下相邻的两个质数都靠的比较近,可以暴力从s+n开始往前,验证区间的质数是否大于等于2。

如果区间内的质数小于2个,则将s+1到s+n的数与1到n进行二分匹配。

如果区间内的质数大于等于2个,则将后s个数与1到s进行二分匹配。

如果完全匹配上就是可行的。

 

 

Codeforces 709A Juicer 水题

A. Juicer

time limit per test

1 second

memory limit per test

256 megabytes

 

Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

Input

The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

Output

Print one integer — the number of times Kolya will have to empty the waste section.

Examples

input

output

input

output

input

output

input

output

Note

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

题意

按顺序给了N个橘子,按顺序放进榨汁机进行榨汁,如果某个橘子的体积超过了b,直接扔掉,如果装进榨汁机的橘子的总体积超过了d,进行一次废渣清除。问需要进行多少次废渣清除操作。

题解

按照题意说的模拟就行了!

 

HDU5840 Special Tetrahedron 暴力计算几何

http://acm.hdu.edu.cn/showproblem.php?pid=5839

Special Tetrahedro

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Given n points which are in three-dimensional space(without repetition).

Please find out how many distinct Special Tetrahedron among them. A tetrahedron is called Special Tetrahedron if it has two following characters.

1. At least four edges have the same length.

2. If it has exactly four edges of the same length, the other two edges are not adjacent.

Input

Intput contains multiple test cases.

The first line is an integer T,1≤T≤20, the number of test cases.

Each case begins with an integer n(n≤200), indicating the number of the points.

The next n lines contains three integers xi,yi,zi, (−2000≤xi,yi,zi≤2000), representing the coordinates of the ith point.

Output

For each test case,output a line which contains"Case #x: y",x represents the xth test(starting from one),y is the number of Special Tetrahedron.

Sample Input

2
4
0 0 0
0 1 1
1 0 1
1 1 0
9
0 0 0
0 0 2
1 1 1
-1 -1 1
1 -1 1
-1 1 1
1 1 0
1 0 1
0 1 1

Sample Output

Case #1: 1
Case #2: 6

Author

UESTC

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

题意

在三维空间中,给出N个点(N<=200),定义特殊四面体为四个边等长且不等长的两边不相邻的四面体,或者六条边都相等的四面体。求特殊四面体的个数。

思路

枚举每一条线段,作为空间四边形的一条对角线,再枚举每一个点,如果这个点到上述的对角线的两个端点距离相等,将其加入这个对角线下属的集合。对于每条对角线下属的集合,枚举集合中的任意两个点C,D,现假设对角线的端点A,B,在C、D加入集合的时候,就保证了AC=AD,BC=BD 了,现在判断,如果ABCD四个点不共面并且AC=AD,这就是一个特殊四面体了。

考虑到这样枚举会让六条边都相同的四面体计数6次,其他的合法四面体会计数2次,所以我们将上述两种情况分别计数,最后算答案的时候,前者的数目除以6+后者的数目/2就是特殊四面体的个数。