标签归档:Java

hdu 5241 Friends(数学或者乱搞)

Problem Description
Mike has many friends. Here are nine of them: Alice, Bob, Carol, Dave, Eve, Frank, Gloria, Henry and Irene.

Mike is so skillful that he can master n languages (aka. programming languages).

His nine friends are all weaker than he. The sets they can master are all subsets of Mike’s languages.

But the relations between the nine friends is very complex. Here are some clues.

1. Alice is a nice girl, so her subset is a superset of Bob’s.
2. Bob is a naughty boy, so his subset is a superset of Carol’s.
3. Dave is a handsome boy, so his subset is a superset of Eve’s.
4. Eve is an evil girl, so her subset is a superset of Frank’s.
5. Gloria is a cute girl, so her subset is a superset of Henry’s.
6. Henry is a tall boy, so his subset is a superset of Irene’s.
7. Alice is a nice girl, so her subset is a superset of Eve’s.
8. Eve is an evil girl, so her subset is a superset of Carol’s.
9. Dave is a handsome boy, so his subset is a superset of Gloria’s.
10. Gloria is a cute girl, so her subset is a superset of Frank’s.
11. Gloria is a cute girl, so her subset is a superset of Bob’s.

Now Mike wants to know, how many situations there might be.

 

Input
The first line contains an integer T(T20) denoting the number of test cases.

For each test case, the first line contains an integer n(0n3000), denoting the number of languages.

 

Output
For each test case, output ”Case #t:” to represent this is the t-th case. And then output the answer.

 

Sample Input
2 0 2

 

Sample Output
Case #1: 1 Case #2: 1024

 

Source
我的一个naive的想法就是乱搞。因为对于某种语言来说,谁会谁不会的方案数是一定的。那么也就是说每种语言都可以独立看待,那么假设一种语言的方案数是x,那么答案就是x^n了。看样例发现是32^n了。
然后我就一直再算为啥是32。。。然后画了韦恩图出来把自己懵逼了。。
昨天在等cf的终测的时候,问了一下xpchf,他给我画了一个这样的图发现顿时清晰多了。
(图片来源xpchf)
他的计算方法是这样的:从下到上计算,对于每个点来说,如果他为1的话那么在他上方和他相连的点均为1,如果为0的话就把这个点删去不考虑。这样的话算出来就是32了。。。%%%%
跪xpchf。。。太强了。

 

BZOJ 2456: mode(乱搞,附java快速读入模板)

Description

给你一个n个数的数列,其中某个数出现了超过n div 2次即众数,请你找出那个数。

Input

第1行一个正整数n。
第2行n个正整数用空格隔开。

Output

    一行一个正整数表示那个众数。

Sample Input

5
3 2 3 1 3

Sample Output

3

HINT

100%的数据,n<=500000,数列中每个数<=maxlongint。

zju2132 The Most Frequent Number

浓浓的面试题既视感。如果全部存下来sort的话爆内存。

所以O(1)空间搞一个计数器,如果一个数出现了n/2次那么,它最后肯定可以使cnt>0.

但BZOJ上给java的内存限制很好,正好测试一下java快速读入。

 

Java 牛顿迭代法求大数开方

因为java大数没有sqrt函数,所以我们可以用牛顿迭代法求解平方根。

可以看成的一个正根。然后运用牛顿迭代法求解:。那么最后得到这个式子: