B http://acm.hust.edu.cn/vjudge/contest/view.action?cid=98759#problem/B
题意：瓶子侧躺在数轴上，瓶底在xlow，瓶口在xhigh，瓶身的曲线是多项式函数，给出a0--an是多项式系数，求瓶子的体积，和每增加 inc 体积的刻度值，最多输出8个。
解法：体积用积分求，刻度值用二分求。
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=1e5+;
double a[M];
double b[M];
double xlow,xhigh,inc;
vector<double> answer;
int n;
void init_b(){
for(int i=;i<=n<<;i++){
b[i]=;
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
b[i+j]+=a[i]*a[j];
}
}
}
double f(double x){
double sum=;
for(int i=;i<=n<<;i++){
sum+=b[i]*pow(x,i+)/(i+);
}
return sum*pi;
}
double get(double x2,double x1){
return f(x2)-f(x1);
}
double solve(){
init_b();
return get(xhigh,xlow);
}
void solve_two(){
answer.clear();
for(int i=;i<=;i++){
double L=xlow,R=xhigh;
if(get(R,L)<inc*i) return ;
while(L+eps<R){
double mid=(L+R)*0.5;
if(get(mid,xlow)<inc*i){
L=mid;
}
else{
R=mid;
}
}
answer.push_back(L-xlow);
}
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int cas=;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++){
scanf("%lf",&a[i]);
}
scanf("%lf%lf%lf",&xlow,&xhigh,&inc);
printf("Case %d: ",cas++);
double result=solve();
printf("%.2f\n",result);
if(result<inc){
puts("insufficient volume");
continue;
}
solve_two();
int len=answer.size();
for(int i=;i<len;i++){
printf("%.2f%c",answer[i],i==len-?'\n':' ');
}
}
return ;
}
D http://acm.hust.edu.cn/vjudge/contest/view.action?cid=98759#problem/D
题意：定义斐波那契字符串 f0=“0” ， f1=“1” ，fi = f i-1 + f i-2 。输入n和一个01串，问在第n个斐波那契字符串中出现了几次这个01串。
解法：对于比较小的串，可以把第n个斐波那契串直接处理出来，然后kmp。预处理到26个，就已经有190000长度了。对于大于26的串，答案有3部分，一部分等于fn-2中匹配成功的次数，一部分等于fn-1中匹配成功的次数，一部分等于fn-1的后缀加上fn-2的前缀在这个区间内匹配成功的次数。对于前两部分可以直接由之前的结果得到，对于中间的每次只保留len-1长度的前缀和后缀，这样不重不漏。
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=2e5+;
struct G {
int len;
char str[M];
} g[];
struct S{
char prefix[M],suffix[M];
}A,B,C;
char a[M];
char buffer[M];
int res[M];
LL dp[];
int n;
class KMP { ///模式匹配(kmp)O(ls+lp)
typedef char typec;///文本元素的类型
static const int MV=1e6+;///字符串的长度
int next[MV];
public:///匹配串长度ls，str 存待匹配文本,模式串长度lp,pat 存模式串
int kmp(int ls,typec str[],int lp,typec pat[],int res[]) { ///返回匹配次数,res 中
// - 31 -
// 存储每个匹配的初始位置
int i=,j=-,cnt=;
next[]=-;
while(i<lp) {
if(j==-||pat[i]==pat[j]) {
next[++i]=++j;
continue;
}
j=next[j];
}
i=j=;
while(i<ls) {
while(j!=lp&&str[i]==pat[j]) {
i++;
j++;
}
if(!j) {
i++;
continue;
}
if(j==lp) {
res[cnt++]=i-j;
}
j=next[j];
}
return cnt;
}
} gx;
void init() {
g[].len=;
strcpy(g[].str,"");
g[].len=;
strcpy(g[].str,"");
for(int i=; i<=; i++) {
g[i].len=g[i-].len+g[i-].len;
strcpy(g[i].str,g[i-].str);
strcat(g[i].str,g[i-].str);
}
}
int get_first_big_id(int len){
for(int i=;i<=;i++){
if(g[i].len>=len) return i;
}
}
void init_dp(int id,S &s){
int la=strlen(a);
dp[id]=gx.kmp(g[id].len,g[id].str,la,a,res);
for(int i=,j=g[id].len-la+;i<la-;i++,j++){
s.prefix[i]=g[id].str[i];
s.suffix[i]=g[id].str[j];
}
s.prefix[la-]=;
s.suffix[la-]=;
}
LL solve() {
int la=strlen(a);
if(n<=) {
return gx.kmp(g[n].len,g[n].str,la,a,res);
}
int id=get_first_big_id(la);
init_dp(id,A);
init_dp(id+,B);
id+=;
while(id<=n){
dp[id]=dp[id-]+dp[id-];
strcpy(buffer,B.suffix);
strcat(buffer,A.prefix);
dp[id]+=gx.kmp(strlen(buffer),buffer,la,a,res);
strcpy(C.prefix,B.prefix);
strcpy(C.suffix,A.suffix);
A=B;
B=C;
id++;
}
return dp[n];
}
int main() {
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
init();
int cas=;
while(~scanf("%d%s",&n,a)) {
printf("Case %d: %lld\n",cas++,solve());
}
return ;
}
end