【BZOJ 2852】强大的区间

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2852
神犇题解:http://blog.csdn.net/rzo_kqp_orz/article/details/52497951

解题报告

设最终区间包含的数为$t$
那么我们就是要求解这个不等式:$ka \le t \le kb$
我们分两种情况讨论:

1. $\lfloor a \rfloor \ne \lfloor b \rfloor$

这样的话,显然答案为$k = 1$

2. $\lfloor a \rfloor = \lfloor b \rfloor$

这样的话,我们先可以刨开$a,b$的整数部分
于是答案变为这个不等式的解:$s \cdot \frac{1}{b – \lfloor a \rfloor} \le k \le s \cdot \frac{1}{a – \lfloor a \rfloor}$

我们发现最后的式子与原问题形式相同,于是可以递归求解
更进一步,我们每次将较大的数减去较小的数,然后交换位置,这是典型的类欧几里得算法
于是我们就可以在:$O(\log n)$的时间复杂度内递归求解原问题了

至于代码,显然需要用高精度
但我不会py QwQ

【BZOJ 1005】[HNOI2008] 明明的烦恼

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1005
数据生成器:http://paste.ubuntu.com/23338303/

这题和BZOJ_1211几乎一毛一样
唯一的区别:这题要写高精 qwq
于是果断弃疗,扔一份不带高精的代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000+9;
const int MX = 1000;

int C[N][N],res,n,emp;
LL vout=1; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void prework(){
	C[0][0] = C[1][1] = C[0][1] = 1;
	for (int j=1;j<=MX;j++) {
		C[0][j] = 1;
		for (int i=1;i<=j;i++) {
			C[i][j] = C[i][j-1] + C[i-1][j-1];
		}
	}
}

int main(){
	if ((n=read()) == 1) {
		if (!read()) puts("1");
		else puts("1");
	} else if (n == 2) {
		if (read() == 1 && read() == 1) puts("1");
		else puts("0");
	} else {
		prework(); emp = n - 2;
		for (int i=1,tmp;i<=n;i++) {
			if ((tmp=read()) == -1) {
				res++;
			} else {
				vout *= C[tmp-1][emp];
				emp -= tmp - 1;
			}
		}
		if (emp < 0) puts("0");
		else {
			for (int i=1;i<=emp;i++) {
				vout *= res;
			}
			cout<<vout;
		}
	}
	return 0;
}