动态规划 | 线段树 | 二分 | 模拟 | 20190824考试解题报告

题目限制一览

题目 时间限制 空间限制
1. agent 1000 MS 512 MB
2. earth 1000 MS 512 MB
3. aurora 1000 MS 512 MB

1. 彩虹(rainbow.cpp)

Description

探险队员们跟随两位护法来到了七色虹前。七色虹,就是平面直角坐标系中赤橙黄绿青蓝紫七个半圆,第i座(1<=i<=7)半圆形彩虹的圆心是(xi,0),半径是ri,半圆上所有点的纵坐标均为非负数。探险队员可以看做一条竖直的、长度等于身高的线段,线段的底端纵坐标为0,最高的一位探险队员的身高为h。

现在探险队员们要从(0,0)到达(x0,0),穿越彩虹的过程中,探险队员的整个身体必须始终在至少一个半圆形彩虹的内部。由于彩虹的半径ri可能太小了,不足以满足这个条件,因此两位护法决定帮助他们把所有彩虹的半径都增大一个非负实数r。探险队员们想知道,r最小是多少呢?

Input

第一行两个实数 h、x0,表示身高和目的地横坐标。 接下来七行每行两个实数 xi、ri,表示七座半圆形彩虹的圆心和半径。

Output

输出最小的 r,四舍五入保留 2 位小数。

Sample Input

4.0 36.0
0.0 4.0
6.0 4.0
12.0 4.0
18.0 4.0
24.0 4.0
30.0 4.0
36.0 4.0

Sample Output

1.00

Hint

对于 100% 的数据,满足 0<=xi,x0<=10000,0<h<100。

分析

类似于 喷水池问题 的解法,即 二分 + 区间覆盖问题

对于每个彩虹半圆,探险队能安全走过的空间就是半圆与 $y=h$ 这一条直线的两个交点之间的矩形部分,而这两个交点很好求出

对于一个圆心为 $(x_0,0)$,半径为 $r$ 的半圆,有 $h^2+dx^2=r^2$,那么 $dx=\sqrt{r^2-h^2}$ ,两点横坐标分别为 $x_0-dx$ 和 $x_0+dx$,对于和 $y=h$ 直线有交点的半圆,把这些交点保存为区间,然后判断这些区间能不能覆盖 $[0,x_0]$,然后实数域上二分猜答案即可

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define mid ((L+R)/2.0)
using namespace std;
typedef pair<double,double> pr;
const double inf=2147483647.00;
const double eps=1e-8;
struct node{
	double x,r;
	bool operator <(const node &o)const{
		if(x!=o.x) return x<o.x;
		else return r<o.r;
	}
}s[9];double h,x0;
pr getseq(double cx,double cr,double py){
	double dx=sqrt(pow(cr,2)-pow(py,2));
	return make_pair(cx-dx,cx+dx);
}
bool check(double d){
	pr dots[9];int cnt=0;
	for(int i=1;i<=7;i++){
		if(s[i].r+d>=h) dots[++cnt]=getseq(s[i].x,s[i].r+d,h);
	} sort(dots+1,dots+cnt+1);
	if(dots[1].first>0) return false;
	double cover=dots[1].second;
	for(int i=2;i<=cnt;i++){
		if(cover>=x0) return true;
		if(dots[i].first>cover) return false;
		cover=max(cover,dots[i].second);
	} return cover>=x0;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("rainbow.in","r",stdin);
	freopen("rainbow.out","w",stdout);
	#endif
	scanf("%lf%lf",&h,&x0);
	for(int i=1;i<=7;i++) scanf("%lf%lf",&s[i].x,&s[i].r);
	sort(s+1,s+7+1);double L=0.0,R=100000.0,ans;
	check(52.71);
	while(R-L>eps){
		if(check(mid)) R=mid,ans=mid;
		else L=mid;
	} printf("%.2lf",ans);
	return 0;
}

2. 还教室(classroom.cpp)

Description

还记得 NOIP 2012 提高组 Day2 中的借教室吗?时光飞逝,光阴荏苒,两年过去了,曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。

在接受借教室请求的 n 天中,第 ii 天剩余的教室为 ai 个。作为大学借教室服

务的负责人,你需要完成如下三种操作共 mm 次:

① 第 l 天到第 r 天,每天被归还 d 个教室。

② 询问第 l 天到第 r 天教室个数的平均数。

③ 询问第 l 天到第 r 天教室个数的方差。

Input

第一行包括两个正整数 n 和 m ,其中 n 为借教室的天数,m 为操作次数。

接下来一行,共包含 n 个整数,第i 个整数表示第 i 天剩余教室数目为 ai 个。

接下来 m 行,每行的第一个整数为操作编号(只能为 1 或 2 或 3),接下来:

包含两个正整数 l 和 r,若操作编号为 1,则接下来再包含一个正整数 d。

Output

对于每个操作 2 和操作 3,输出一个既约分数(分子与分母互质)表示询问的答案(详见样例)。若答案为 0,请输出“0/1”(不含引号)

Sample Input

5 4
1 2 3 4 5
1 1 2 3
2 2 4
3 2 4
3 1 5

Sample Output

4/1
2/3
14/25

Hint

全部数据满足:$1\leq l,r \leq 10^5$,$n,m \leq 10^5$,$0\leq a_i \leq 10$,$1\leq d\leq 3$,操作 1 的数量不超过 10%

注意:$a_i$ 和 $d$ 的操作范围很小以及操作 1 的数量很少是为了保证答案的分子分母不会超过 Int64 的范围,与题目的做法本身并无关系

分析

看到区间更新和区间查询,很容易想到线段树,问题 1 就是区间更新板子,问题 2 直接区间求和后除以区间长度即可,关键在于维护问题 3 的答案信息

显然我们不能直接维护方差,且不能通过实数的方式算出方差然后试图得出分数形式,因为这样会有精度损失

那么我们要维护的也就是方差的右边部分,也就是 $\sum_{i=1}^n(x_i-\overline{x})^2$ ,之后像平均数那样除以区间长度即可

然而我们还是不能直接维护上述的一坨式子,把它展开得到:

$\sum_{i=1}^n(x_i-\overline{x})^2=\sum_{i=1}^n(x_i-2x_i\overline{x}+\overline{x}^2)=\sum_{i=1}^nx_i^2+n\times \overline{x}^2-2\times \sum_{i=1}^nx_i\overline{x}$

$\sum_{i=1}^nx_i^2+n\times \overline{x}^2-2\overline{x}\times \sum_{i=1}^nx_i$,可以设 $S=\sum_{i=1}^nx_i^2$,$T=\sum_{i=1}^nx_i$,则 $\overline{x}=\frac{T}{n}$,化简式子:

$\sum_{i=1}^nx_i^2+n\times \overline{x}^2-2\overline{x}\times \sum_{i=1}^nx_i=S+n\times \frac{T^2}{n^2}-2\times \frac{T}{n}\times T=S+\frac{T^2}{n}-2\times\frac{T^2}{n}=S-\frac{T^2}{n}$

上述式子表明维护方差需要维护 区间平方和区间和(区间长度 $n$ 可以直接得出)

区间和的线段树写过板子,那么区间平方和呢?其实转化之后也可以由区间和得出:

$\sum_{i=1}^n(x_i+v)^2=\sum_{i=1}^n(x^2+2x_iv+v^2)=\sum_{i=1}^nx_i^2+2v\sum_{i=1}^nx_i+nv^2$

上述式子表明新的区间平方和可以由 现在的区间平方和和现在的区间和 维护而来(此处注意应该是先更新区间平方和再更新区间和),那么线段树就可以圆满解决这个题了

至于输出既约分数,就是分子分母同时除以它们的最大公约数

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 100005
#define mid ((L+R)>>1)
using namespace std;
typedef long long ll;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
struct node{
	int LC,RC;
	ll V,PV,TAG;
	#define lc(x) T[x].LC
	#define rc(x) T[x].RC
	#define val(x) T[x].V
	#define pval(x) T[x].PV
	#define tag(x) T[x].TAG
}T[maxn<<2];int newp,Tr[maxn];
inline void pushup(int k){
	val(k)=val(lc(k))+val(rc(k));
	pval(k)=pval(lc(k))+pval(rc(k));
}
int build(int L,int R){
	int p=++newp;
	if(L==R){
		val(p)=Tr[L];
		pval(p)=val(p)*val(p);
		return p;
	} 
	lc(p)=build(L,mid);rc(p)=build(mid+1,R);
	pushup(p);
	return p;
}
inline void spr(int k,int L,int R,int d){
	tag(k)+=d;
	pval(k)=pval(k)+(1ll*2*d*val(k)+1ll*(R-L+1)*d*d);
    // 式子开头乘上 1ll,会自动将式子中的所有变量看做 long long 参与运算
    // 可以防止中途因为 int 爆掉
	val(k)+=(R-L+1)*d;
}
inline void pushdown(int k,int L,int R){
	if(tag(k)==0) return;
	spr(lc(k),L,mid,tag(k));
	spr(rc(k),mid+1,R,tag(k));
	tag(k)=0;
}
inline void updata(int k,int L,int R,int x,int y,int d){
	if(x<=L && R<=y) return spr(k,L,R,d);
	pushdown(k,L,R);
	if(mid>=x) updata(lc(k),L,mid,x,y,d);
	if(mid<y) updata(rc(k),mid+1,R,x,y,d);
	pushup(k);
} 
ll sum(int k,int L,int R,int x,int y){
	if(x<=L && R<=y) return val(k); pushdown(k,L,R);
	ll ans=0;
	if(mid>=x) ans+=sum(lc(k),L,mid,x,y);
	if(mid<y) ans+=sum(rc(k),mid+1,R,x,y);
	return ans;
}
ll psum(int k,int L,int R,int x,int y){
	if(x<=L && R<=y) return pval(k); pushdown(k,L,R);
	ll ans=0;
	if(mid>=x) ans+=psum(lc(k),L,mid,x,y);
	if(mid<y) ans+=psum(rc(k),mid+1,R,x,y);
	return ans;
}
int n,m;
ll gcd(ll a,ll b){
	if(a<b) swap(a,b);
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("classroom.in","r",stdin);
	freopen("classroom.out","w",stdout);
	#endif
	fcin(n);fcin(m);for(int i=1;i<=n;i++) fcin(Tr[i]);
	build(1,n);int op,x,y,z; 
	ll summ,divm,psumm,xsumm,ysumm;
	ll newx,newy,tsumm;
	while(m--){
		fcin(op);fcin(x);fcin(y);
		if(op==1) fcin(z),updata(1,1,n,x,y,z);
		else if(op==2){
			summ=sum(1,1,n,x,y);
			divm=gcd(summ,(ll)(y-x+1));
			printf("%lld/%lld\n",summ/divm,(ll)(y-x+1)/divm);
		}else{
			summ=sum(1,1,n,x,y);
			psumm=psum(1,1,n,x,y);
			newx=(ll)(y-x+1)*psumm-summ*summ; if(newx<0) return 1; // debug
			newy=(ll)(y-x+1)*(ll)(y-x+1);
			divm=gcd(newx,newy);printf("%lld/%lld\n",newx/divm,newy/divm);
		}
	}
	return 0;
}

2. 篮球比赛(basketball.cpp)

Description

由于Czhou举行了众多NOIP模拟赛,也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进,并且球技不断精进。这引起了体育老师彩哥的注意,为了给校篮球队找到势均力敌的对手,彩哥找到了Czhou神,想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子,决定派出配合默契又不至于吊打校篮球队的阵容。

而机房神牛的能力值受到游戏时长,训练时长,个人基础值得影响,可能会不断变化。所以Czhou想根据神牛当天状态从中选出若干名选手,使他们的能力值和等于k。

Input

一行三个数n,k,l。表示机房有n个神牛,选出队员能力值和为k,每个神牛的能力最大值<=L且>=0。

Output

输出一个数,表示方案数,方案满足选出若干选手使能力和为k。因为答案比较大,最后模10^9+7。

Sample Input

2 2 2

Sample Output

6

Hint

样例说明:神牛的能力值可能为(0,2)(1,2)(1,1)(2,0)(2,1)(2,2),这样都可以选出一些数字使他们的能力值和为2。

对于(0,2)表示第一只牛能力值为0,第二只牛能力为2

类似的:

对于(1,2)选出2即满足要求。

对于(1,1)选出全部选手即满足要求。

所以(0,2)(1,1)都是满足要求的方案。

数据范围:

n,k<=20

0<=L<=10^9.

分析

做法一:爆搜 + 背包(20分)

没什么好说的……暴力枚举每个神牛的能力值然后检验是否能刚好达到 K,因为数据规模的原因只能过 2 个点

做法二:状压 DP(100分)

从提示的数据范围来看,$n$,$k$ 都是非常小的整数,所以可以用状压 DP 表示 $[0,k]$ 中每一个能力值能不能取得到,所以 $f[i][j]$ ($i\in[1,n]$,$j\in[1,2^{min(l,k)}-1]$) 表示考虑完前 $i$ 个神牛,且满足状态 $j$ 表示的能力值的方案数

也就是说其中若能力值 $x$ 取到,$j$ 化成二进制的第 $x$ 位为 1,题目的 $l$ 可能很大,但我们只需讨论 $k$ 以内的情况

这个状压 DP 的方程也不难想到,新增一位神牛时,除了当前状态中能取到的能力值不变,还会增加一些新的能取到的能力值

故由 $f[i][j]$ 转移到 $f[i+1][j’]$ 时,若新神牛的能力值为 $x$,对应的 $j’=j \;\lvert\; (j«x) \;\lvert\; 1«(x-1)$,转移方程为:

$f[i+1][j’]=(f[i+1][j’]+f[i][j])\mod (1e9+7)$ ,其中 $x\in[0,min(l,k)]$

而如果新神牛的能力值 $x\geq k$,那么原来的方案数显然不会改变,但是这仍然是一种取神牛的方式,所以:

$f[i+1][j]=(f[i][j]\times (l-k) \mod (1e9+7)) \mod (1e9+7)$ ($When\; l\geq k$)

统计时,判断当前状态 $i$ 下能力值 $k$ 能否被取到,用 $i\; \& \; 1«(k-1)$

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 25 
#define maxs 1<<21
using namespace std;
typedef long long ll;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
const ll mod=(ll)1e9+7; 
ll f[maxn][maxs];int n,m,k,l;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("basketball.in","r",stdin);
	freopen("basketball.out","w",stdout);
	#endif
	fcin(n);fcin(k);fcin(l);m=(1<<k)-1;
	for(int i=1;i<=min(l,k);i++) f[1][1<<(i-1)]=1;
	int nxts;
	if(l>=k) f[1][0]=(l-k+1); // 特判 
	for(int i=1;i<n;i++){
		if(!f[i][0]) f[i][0]=1;
		for(int j=0;j<=m;j++)
			if(f[i][j]){
				for(int h=0;h<=min(l,k);h++){
					nxts=(j|(j<<h)|(1<<(h-1)))&m;
					(f[i+1][nxts]+=f[i][j])%=mod;
				}
				if(l>=k) (f[i+1][j]+=(f[i][j]*(ll)(l-k)%mod))%=mod; 
			}
	} ll ans=0;
	for(int i=0;i<=m;i++)
		if(i&(1<<(k-1))) (ans+=f[n][i])%=mod;
	printf("%lld",ans);
	return 0;
}