4
18
2015
0

A(j)H(s)OI2015day1简要题意

跪lzz大爷
day1:
 
A:
 
有个集合S:{1,2,,,,,n},用S的子集排成一个k*k三角形
对于第i行第j列的集合(j<=i),它是第i行第j-1列的集合的子集(当j!=1时),也是第i-1行第j列的集合的子集(当i!=1时)。
集合可以为空。
求方案数(mod 1e9+7)。
 
30% n<=10,k<=10
 
60% n<=1e9,k<=10
 
100% n<=1e9,k<=1e9
 
1s,512mb
 
B:
 
给定L、R、k和一个长度为n的数列a。
 
一段区间[l,r]的权值为(max ai (l<=i<=r) - min aj (l<=j<=r))/(r-l+k)
 
求权值最大的区间的权值,满足区间长度在L到R之间。
 
多组数据(至多10组)
 
20% n<=1000
 
另10% k=0,L=2,R=n
 
另10% k=1
 
100% n<=1e5,n>=R>=L>=2,ai<=1e8,答案<=1e3
 
5s,512mb
 
C:
 
给一棵n个节点的树,每条边有一个字符串。
 
每次询问点u到v的路径中,有多少条边上的字符串有一个前缀s(s为每次询问给定的字符串)
 
n<=100000,m<=100000,所有字符串长<=10
 
2s,512mb
 
Category: My Oi,My Life | Tags: 逗比 AHOI | Read Count: 654

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com