题目限制一览
| 题目 |
时间限制 |
空间限制 |
| 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最小是多少呢？
第一行两个实数 h、x0,表示身高和目的地横坐标。 接下来七行每行两个实数 xi、ri,表示七座半圆形彩虹的圆心和半径。
Output
输出最小的 r,四舍五入保留 2 位小数。
1
2
3
4
5
6
7
8
| 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
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #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 天教室个数的方差。
第一行包括两个正整数 n 和 m ，其中 n 为借教室的天数，m 为操作次数。
接下来一行，共包含 n 个整数，第i 个整数表示第 i 天剩余教室数目为 ai 个。
接下来 m 行，每行的第一个整数为操作编号（只能为 1 或 2 或 3），接下来：
包含两个正整数 l 和 r，若操作编号为 1，则接下来再包含一个正整数 d。
Output
对于每个操作 2 和操作 3，输出一个既约分数（分子与分母互质）表示询问的答案（详见样例）。若答案为 0，请输出“0/1”（不含引号）
1
2
3
4
5
6
| 5 4
1 2 3 4 5
1 1 2 3
2 2 4
3 2 4
3 1 5
|
Sample Output
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(xi-2x_i\overline{x}+\overline{x}^2)=\sum{i=1}^nxi^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}^nxi$，可以设 $S=\sum{i=1}^nxi^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+2xiv+v^2)=\sum{i=1}^nxi^2+2v\sum{i=1}^nx_i+nv^2$
上述式子表明新的区间平方和可以由 现在的区间平方和和现在的区间和 维护而来（此处注意应该是先更新区间平方和再更新区间和）,那么线段树就可以圆满解决这个题了
至于输出既约分数，就是分子分母同时除以它们的最大公约数
Codes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #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);
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;
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。
一行三个数n,k,l。表示机房有n个神牛，选出队员能力值和为k，每个神牛的能力最大值<=L且>=0。
Output
输出一个数，表示方案数，方案满足选出若干选手使能力和为k。因为答案比较大，最后模10^9+7。
Sample Output
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #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;
}
|
