标签归档:Java

蒟蒻的自暴自弃的暑假生活(week3.5)

补了一下多校题目

hdu 5752  Sqrt Bo(水题)

暴力算出边界,用Java艹过,注意特判n=1的情况。

hdu 5753  Permutation Bo(期望计算)

计算期望。因为相邻三个数h1,h2,h3三个数(h1<h2<h3)的排列有6种,那么只有h1h3h2和h2h3h1两种可以选择c值,概率为1/3,其他的均是0的情况。对于边界,因为h0=hn+1=0,那么有1/2的概率选择c值。特判n=1的情况,因为这个WA了一次。

hdu 5754 Life Winner Bo(博弈)

可以看一下matrix67关于这个问题的一些神奇讲解.车和国王移动相对简单,因而画个图就看出来了。马的话就是对角线隔三个点会出现先手必败的情况,皇后则是威佐夫博弈,有关讲解可以直接看matrix67的博客。

hdu 5761 Rower Bo(物理,微积分,数学)

clearY大爷在比赛的时候就按照题解的思路积分出来啦,太神了,%%%…然后我尝试自己推倒了一次,写出来还是WA,原来存在a=0得情况,这时候不用判断无解直接输出0.。菜不成声QAQ

hdu 5762 Teacher Bo(抽屉原理)

直接暴力两两枚举,然后在一个dis数组里打标记,如果已有这个距离打上了标记,那么就输出yes。这样做为什么不会超时呢?因为最多只会有2*1e5个曼哈顿距离,所以就算你有很多个点,那么也只需要最多枚举这么多次就找到了。反之如果点很少,就可能出现no的情况。

hdu 5763 Another Meaning(kmp+dp)

字符串上的dp,知道思路后还是写挂了n次。。。首先我们可以用kmp预处理出来所有发现串匹配的位置,在那个位置(模式串的末尾位置打上一个标记1),再开始dp。dp[i]代表前面到i-1位置时的母串的含义数目,dp[0]=1,因为母串至少有一个含义。那么匹配到字符i时:如果没有之前预处理出来的标记,那么直接dp[i+1]=dp[i].如果有的话dp[i+1]=dp[i]+dp[i-lenB+1]。这就是状态转移方程了。

hdu 5774 Where Amazing Happens(map水题)

大水题

 

fzu 2036 Log Calculator(数学+Java大数)

Description

Input

The first line of the input contains an integer T(T≤100), indicating the number of test cases. Each test case contains two float numbers: a, b(-10^10000≤a,b≤10^10000), indicating and respectively.

Output

For each test case, print a line containing the test case number (beginning with 1) and the required result. Because of the result may be an irrational number, so you just need to print the result with 9 digits of precision, round half up.

Sample Input

2
1 1
0 0

Sample Output

Case 1: 2.000000000
Case 2: 1.000000000
思路:我们可以得到:2^a=x,2^b=y。所以ans=log2(2^a+2^b)。我们假设a比b小(其实无所谓,因为如果a大的话,我们交换一下即可),那么进一步化简得到ans=a+log2(1+2^(b-a))。然后根据数学极限的近似计算,ClearY证明在题目要求的精度范围内,b-a>34的情况下1+2^(b-a)近似等于2^(b-a)。然后就可做了。orz….
然后这道题还学到了一个知识点就是:
BigDecimal.setScale()方法可以格式化小数点的位置。
setScale(1)表示保留一位小数,默认用四舍五入方式。
setScale(1,BigDecimal.ROUND_DOWN)直接删除多余的小数位,如2.35会变成2.3
setScale(1,BigDecimal.ROUND_UP)进位处理,2.35变成2.4,直接进位
setScale(1,BigDecimal.ROUND_HALF_UP)四舍五入,2.35变成2.4
setScaler(1,BigDecimal.ROUND_HALF_DOWN)四舍五入,2.35变成2.3,如果是5则向下舍

 

sgu 111 Very simple problem(Java大数+二分)

Description

You are given natural number X. Find such maximum integer number that it square is not greater than X.

Input

Input file contains number X (1≤X≤101000).

Output

Write answer in output file.

Sample Input

Sample Output

水题,二分+Java艹过