月度归档:2017年02月

Codeforces 395B. On Sum of Fractions(数学,素数间隔)

Let’s assume that

  • v(n) is the largest prime number, that does not exceed n;
  • u(n) is the smallest prime number strictly greater than n.

Find .

Input

The first line contains integer t (1 ≤ t ≤ 500) — the number of testscases.

Each of the following t lines of the input contains integer n (2 ≤ n ≤ 109).

Output

Print t lines: the i-th of them must contain the answer to the i-th test as an irreducible fraction “p/q“, where p, q are integers, q > 0.

Examples
input

output

看到式子后展开了一下,1/(2*3)+2/(3*5)+…..大概长这样,发现貌似很好消。。假如说n处于自己的u(n)和v(n)之间的话,大概化简了一下式子。现在我们就是求v(n)和u(n)的问题了。。其实这个暴力就可以了,因为1e9范围内相邻素数间隔不超过800左右。

 

Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)做题记录

终于把这套题补完了,get到了不少已经忘了的和新的姿势。。。

A. Oath of the Night’s Watch

题意:找寻一个数组内比最小元素大而且比最大元素小的元素有多少个。

排序扫一下就好了。

B. Code For 1

题意:给出一个数字n,一次操作可以把一个数字变成x/2,x%2,x/2这样的一个序列。操作若干次直到把所有数字变为了1或者0。给出L和R统计这个区间有多少个1。0<=R-L<=1e5,n<=2^50。

我们可以先递归的找出n最后会化成一个多长的序列。设长度为len。然后区间长度才1e5,可以对每个位置都递归一下判断是0还是1。时间复杂度O(1e5*log(n))就好了。。。

C. Jon Snow and his Favourite Number

题意:略。

随机了一些数据,发现找不超过十几次就可以出现一个循环节,循环节长度没超过5。(随机的,不怎么靠谱)。然后就这么暴力的找循环节,hash一下序列就可以了。

 

D. Jon and Orbs

题意:给出k种球,每天等概率的产生一种球,现在想知道让每种球都至少有一件的概率大于等于p/2000至少需要多少天.一共k次询问。k,p,q均小于1000。

概率dp,设dp[i][j]为到第i天产生j种球的概率。那么dp[i][j]=dp[i-1][j-1]*(k-j+1)/k+dp[i-1][j]*j/k。dp[0][0]=1.

然后就这么dp就可以了。但是天数的上限并不是k。而估计天数的限制又去学习了一波。。。

假设我们现在有i种球了,那么我们获得下一种新球的概率就是p=(n-i)/n。那么获得i+1种球的期望抽取次数也就是:

那么就是一个期望的线性相加的过程了。从1-k进行求和,,这个和项是一个调和级数,大概是一个log(k)。那么我们天数开到k*log(k)就好了。当然需要预处理dp数组。

E. Game of Stones

题意:给出n堆石子,和nim游戏类似的规则,但是假如一堆石子已经在之前被拿走了x个石子,那么之后任何人都不能再拿这么多个石子了。每堆石子不超过60个。

暴力求sg函数了。sg[0]=0。dfs(n,mask)代表当前有n个石头,mask是当前不能选的数字的集合。然后求出来sg函数值即可。。。可以本地打表,但是我直接交了dfs也给过了。可能状态数少吧。。

F. Barrels and boxes

题意:给出f个食物和w瓶酒,一种东西可以放到一个stack里,要求相同种类的stack不能连续的放。而且w的各个stack必须要大于给出的H才可以。求合法的概率p/q。输出p*q对于1e9+7的逆元。

一共有w个酒,那么酒可以分成的堆数就是w种。我们枚举酒被分成的堆数,假设现在被分成了i堆(每堆都不为空)。那么由插板法可知w个物品分成i堆的方案数C(w-1,i-1)。那么考虑这i堆相当于隔板把f个物品又分组。因为可能把f分成i组或者i+1组或者i-1组相当于是在f+1个空位里放。所以就是C(f+1,i)。两个相乘就是不考虑h的方案数。

考虑h的时候需要减去个i*h就可以了。

 

Codeforces Beta Round #3做题记录

A. Shortest path of the king

题意:在一个8*8的棋盘上给你起始点和终止点坐标,求最短移动次数的操作序列。

因为是个空的棋盘,那么肯定就是两个点之间的曼哈顿距离是最短移动次数了。至于向左向右向上向下和终点比一下就好了。。

B. Lorry

题意:给出n件物品(n<=1e5),和容量为v的背包(v<=1e9),有两种物品:一种体积为1一种体积为2.求最多可以得到的价值。

算是一个超大背包的问题了吧。。一开始写了两个贪心都wa掉了。。。然后询问了一下韩司机。

其实按照性价比来排序是很显然的,但是关键是会出现这样的情况:9/1和11/2。这时候假设v=2,因为我们提前选择了9/1导致了11/2无法被选择,但是选择9/1的原因是当有两件这样的物品时肯定这么做是没错的。所以说最后的几个选择1类型的物品可能可以被替换成2类型。只需要记录两个最后选择的1类型物品即可。因为和最优解产生的偏差,只在于一个2类型物品。然后与剩余的性价比最高的2类型物品判断一下。

C. Tic-tac-toe

题意:略。

模拟,细节题吧。。。

D. Least Cost Bracket Sequence

题意:给出一个由(,),?组成的序列,每个?都可以转换成(和)中的一个。第i个?转换成(的花费为a[i],转成)的花费为b[i]。求出一个合法的括号序列,而且花费要最小。。。

一开始以为要区间dp,但是前面的括号选择会影响到后面的情况。不是很好做。贪心的话,就是先把整个序列的?全部变成),这样的话在维护一个cnt,遇到(加1,遇到)减1,当cnt为负数的时候,就意味着我们需要从前面选一个a[i]-b[i]最小的位置变成(。这个可以用一个小根堆来维护。

因为判断无解WA了好几发,当cnt最后不为0就无解了。。。我一开始智障的写了cnt>0.。。。

又算是一道带修改的贪心?