注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

zjoi2013 day2题解  

2013-06-17 13:57:36|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实这是我们学校的考试题
题目暂时还看不到,等以后bzoj上能看到吧

抛硬币:
先求KMP,通过fail数组来计算F[i][0],F[i][1]表示i这个点走0/1后走到的状态
那么从i-1这个状态点走到n的期望g(i)是什么呢?
g(i)=1+p[0]*g(F[i][0])+p[1]*g(F[i][1])
注意到F[i][0],F[i][1]至少一个为i+1,不妨设F[i][t]=i+1
g(i+1)=(g(i)-1-p[t^1]*g(F[i][t^1]))/p[t];
接下来有一步非常神奇
设g(i)=k[i]*g(1)-b[i],那么显然k[1]=1,b[1]=0,然后递推得到k[i+1],b[i+1],最后得到k[n],b[n]
k[i+1]*g(i+1)-b[i+1]=(k[i]*g(0)-b[i]-1-p[t^1]*(k[F[i][t^1]]*g(0)-b[F[i][t^1]]))/p[t]
k[i+1]=(k[i]-p[t^1]*k[F[i][t^1]])/p[t]
b[i+1]=(b[i]+1-p[t^1]*b[F[i][t^1]])/p[t]
然后就行了
约分的话,由于分母的质因子不大于100,所以gcd的质因子也不大于100,所以我们只要打一个1~100的素数表然后一个个试就行了。避免了高精度gcd与高精度除法
但是我一直有个问题不理解就是k,b的计算为什么不会出现负数?
这一步暂时不明

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 1010
#define mod 1000000000
using namespace std;
typedef long long LL;
char str[maxn];
int n;
const int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
const int nPrime=25;
const int MAX_LEN=200;
struct bign
{
int digit[MAX_LEN],n;
bign()
{
n=1;
memset(digit,0,sizeof(digit));
}
friend bign operator + (const bign &a,const bign &b)
{
bign c;
int jinwei=0;
c.n=max(a.n,b.n);
for(int i=1;i<=c.n;i++)
{
c.digit[i]=a.digit[i]+b.digit[i]+jinwei;
jinwei=c.digit[i]/mod;
c.digit[i]%=mod;
}
if(jinwei)
c.digit[++c.n]=jinwei;
return c;
}
friend bign operator - (const bign &a,const bign &b)
{
bign c;
int tuiwei=0;
for(int i=1;i<=a.n;i++)
{
c.digit[i]=a.digit[i]+mod-b.digit[i]-tuiwei;
tuiwei=(c.digit[i]/mod)^1;
c.digit[i]%=mod;
}
for(c.n=a.n;c.n>1&&c.digit[c.n]==0;c.n--);
return c;
}
friend bign operator * (const bign &a,const bign &b)
{
bign c;
LL temp;
for(int i=1;i<=a.n;i++)
{
int jinwei=0;
for(int j=1;j<=b.n;j++)
{
temp=(LL)a.digit[i]*b.digit[j]+c.digit[i+j-1]+jinwei;
jinwei=temp/mod;
c.digit[i+j-1]=temp%mod;
}
if(jinwei)
c.digit[i+b.n]+=jinwei;
}
for(c.n=a.n+b.n;c.n>1&&c.digit[c.n]==0;c.n--);
return c;
}
friend bign operator * (const bign &a,int p)
{
bign c;
LL temp;
c.n=a.n;
int jinwei=0;
for(int i=1;i<=a.n;i++)
{
temp=(LL)a.digit[i]*p+jinwei;
jinwei=temp/mod;
c.digit[i]=temp%mod;
}
if(jinwei)
c.digit[++c.n]=jinwei;
return c;
}
void operator /= (int p)
{
LL temp,rem=0;
for(int i=n;i>=1;i--)
temp=digit[i],digit[i]=(rem*mod+temp)/p,rem=(rem*mod+temp)%p;
for(;n>1&&digit[n]==0;n--);
}
int operator % (int p)
{
LL temp,rem=0;
for(int i=n;i>=1;i--)
temp=digit[i],rem=(rem*mod+temp)%p;
return rem;
}
void print()
{
printf("%d",digit[n]);
for(int i=n-1;i>=1;i--)
printf("%09d",digit[i]);
}
};
struct Fraction
{
bign a,b;
/* a是分子,b是分母 */
void Reduction()
{
for(int i=0;i<nPrime;i++)
while(b%prime[i]==0&&a%prime[i]==0)
a/=prime[i],b/=prime[i];
}
Fraction() {}
Fraction(bign a,bign b): a(a),b(b){}
friend Fraction operator + (const Fraction &a,int p)
{
return Fraction(a.a+a.b*p,a.b);
}
friend Fraction operator + (const Fraction &a,const Fraction &b)
{
bign c=a.a*b.b+a.b*b.a,d=a.b*b.b;
return Fraction(c,d);
}
friend Fraction operator - (const Fraction &a,const Fraction &b)
{
bign c=a.a*b.b-a.b*b.a,d=a.b*b.b;
return Fraction(c,d);
}
friend Fraction operator * (const Fraction &a,const Fraction &b)
{
return Fraction(a.a*b.a,a.b*b.b);
}
friend Fraction operator / (const Fraction &a,const Fraction &b)
{
return Fraction(a.a*b.b,a.b*b.a);
}
}p[2];
int F[maxn][2];//0 is 'T',1 is 'H'
void read()
{
int a,b;
scanf("%d %d %s",&a,&b,str+1);
p[0].a.digit[1]=a,p[0].b.digit[1]=b;
p[1].a.digit[1]=b-a,p[1].b.digit[1]=b;
p[0].Reduction(),p[1].Reduction();
n=strlen(str+1);
static int fail[maxn];
fail[1]=1,fail[2]=1;
for(int i=2,j=0;i<n;i++)
{
for(j=fail[i];j!=1&&str[j]!=str[i];j=fail[j]);
fail[i+1]=j+(str[j]==str[i]);
}
int p=str[1]=='T';
F[1][p]=2,F[1][p^1]=1;
for(int i=2;i<=n;i++)
{
bool type=str[i]=='T';
F[i][type]=i+1,F[i][type^1]=F[fail[i]][type^1];
}
}
void Dp()
{
/*
p[t]*g(i+1)+p[t^1]*g(f[i][t^1])+1=g(i)
g(i+1)=(g[i]-p[t^1]*g(f[i][t^1])-1)/p[t]
g(n)=0
设g(i)=k[i]*g(0)-b[i](这一步好神)
g(i+1)=(k[i]*g(0)-b[i]-p[t^1]*(k[f[i][t^1]]*g(0)-b[f[i][t^1]])-1)/p[t]
=((k[i]-p[t^1]*k[f[i][t^1]])*g(0)-(b[i]-p[t^1]*b[f[i][t^1]]+1))/p[t]
*/
static Fraction k[maxn],b[maxn];
k[1].a.digit[1]=1;
k[1].b.digit[1]=1;
b[1].a.digit[1]=0;
b[1].b.digit[1]=1;
for(int i=1;i<=n;i++)
{
int t=F[i][1]==i+1;
k[i+1]=(k[i]-p[t^1]*k[F[i][t^1]])/p[t];
b[i+1]=(b[i]+1-p[t^1]*b[F[i][t^1]])/p[t];
k[i+1].Reduction(),b[i+1].Reduction();
}
Fraction ans=b[n+1]/k[n+1];
ans.Reduction();
ans.a.print();
printf("/");
ans.b.print();
printf("\n");
}
int main()
{
read();
Dp();
return 0;
}


丽洁体:
大水题
A,C串显然贪心即可
B串爆枚,这样是n^2的
不过我们只要从t[i]==b[1]的i位枚举即可
这样就是500*n的了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define maxn 500010
using namespace std;
map<int,int> hash;
int a[maxn],b[maxn],c[maxn],t[maxn],lt,la,lb,lc;
void work(char b[],int lb,int a[],int &la)
{
int tot=0;
for(int i=1;i<=lb;)
{
if(b[i]<'a'||b[i]>'z')
i++;
else
{
int s=0;
while(b[i]>='a'&&b[i]<='z')
s=s*26+b[i]-'a',i++;
if(!hash.count(s))
hash[s]=++tot;
a[++la]=hash[s];
}
}
}
void read()
{
static char t1[maxn],a1[maxn],b1[maxn],c1[maxn];
int lt1,la1,lb1,lc1;
gets(t1+1);
gets(a1+1);
gets(b1+1);
gets(c1+1);
lt1=strlen(t1+1),la1=strlen(a1+1),lb1=strlen(b1+1),lc1=strlen(c1+1);
work(t1,lt1,t,lt),work(a1,la1,a,la),work(b1,lb1,b,lb),work(c1,lc1,c,lc);
}

int work()
{
int sum=0,ida=0,idc=lt+1;
for(int k=1;k<=la;k++)
for(ida=ida+1;ida<=lt&&t[ida]!=a[k];ida++)
sum++;
for(int k=lc;k>=1;k--)
for(idc=idc-1;idc>=1&&t[idc]!=c[k];idc--)
sum++;
int ans=sum+idc-ida-1;
for(int i=ida+1;i<=idc-1;i++)
if(t[i]==b[1])
{
int idb=i-1,s=sum;
bool mark=true;
for(int k=1;k<=lb&&mark;k++)
for(idb=idb+1;idb<=idc-1&&t[idb]!=b[k]&&mark;idb++)
{
s++;
if(s>=ans)
mark=false;
}
if(mark&&idb<=idc-1)
ans=s;
}
return ans;
}
int main()
{
read();
printf("%d\n",work());
return 0;
}


话旧:
若k=0,答案是2^((n-2)/2)
设F[i][0],F[i][1]分别表示到了第i个必经点,下一步往下走还是往上走
对于两个相邻的必经点,我们分一些情况讨论:
都向下,这是最好算的,利用k=0的答案的公式即可
左往上右往下,我们会发现右边是固定的;左边是2^((n-2)/2)+2^((n-4)/2)……加下去。答案其实并不是2^n-1,而是2^n。因为n=0时也是1
左往下右往上,同理
左往上右往上,利用左往上右往下的结论,其实就是2^n+2^(n-1)+……于是最后就是2^(n+1)-1了
但是还有很多非常恶心的特殊情况
比如两点间就是斜率为1的直线啊
比如都往上的情况还要讨论他们撞在一起就不用跑到坐标轴上去的情况啊
比如这些情况是否合法啊
写的想砍人了
不过总算还是自己写出来了,有N多if

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod 19940417
#define maxm 1000010
using namespace std;
typedef long long LL;
pair<int,int> Point[maxm];
int nPoint;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
int n,m;
Read(n),Read(m);
Point[++nPoint]=make_pair(0,0),Point[++nPoint]=make_pair(n,0);
for(int i=1,a,b;i<=m;i++)
{
Read(a),Read(b);
Point[++nPoint]=make_pair(a,b);
}
sort(Point+1,Point+nPoint+1);
nPoint=unique(Point+1,Point+nPoint+1)-Point-1;
}
LL power(LL p,LL n)
{
LL ans=1;
for(LL i=n;i;i>>=1,p=p*p%mod)
if(i&1)
ans=ans*p%mod;
return ans;
}
void Dp()
{
int maxh=0;
bool flag[maxm][2];
static LL F[maxm][2];
F[1][1]=1,flag[1][1]=true;
for(int i=2;i<=nPoint;i++)
{
int go=Point[i].second==0;
if(Point[i].first-Point[i-1].first==Point[i].second-Point[i-1].second)
{
F[i][1]=F[i][0]=F[i-1][1],maxh=max(maxh,Point[i].second);
flag[i][1]|=flag[i-1][1];
flag[i][0]|=flag[i-1][1];
}
else if(Point[i].first-Point[i-1].first==Point[i-1].second-Point[i].second)
{
F[i][go]=F[i-1][0];
flag[i][go]|=flag[i-1][0];
}
else if(Point[i].first-Point[i-1].first==2)
{
F[i][go]=F[i-1][1];
flag[i][go]|=flag[i-1][1];
if(flag[i-1][1])
maxh=max(maxh,Point[i].second+1);
if(Point[i].second==1)
{
F[i][1]=(F[i][1]+F[i-1][0])%mod;
F[i][0]=(F[i][0]+F[i-1][0])%mod;
flag[i][1]|=flag[i-1][0],flag[i][0]|=flag[i-1][0];
}
}
else
{
maxh=max(maxh,Point[i].second);
if(flag[i-1][1])
maxh=max(maxh,Point[i-1].second+(Point[i].second+Point[i].first-Point[i-1].second-Point[i-1].first)/2);
int n=Point[i].first-Point[i-1].first-Point[i].second-Point[i-1].second;
LL cnt=power(2,max(0,n/2-1));
if(go==0&&n>=0)
{
F[i][1]=F[i][0]=(F[i][1]+F[i-1][0]*cnt)%mod;//i-1向右下,i向左下
flag[i][1]|=flag[i-1][0],flag[i][0]|=flag[i-1][0];
if(n!=0)
{
F[i][1]=F[i][0]=(F[i][1]+F[i-1][1]*cnt)%mod;//i-1向右上,i向左下
flag[i][1]|=flag[i-1][1],flag[i][0]|=flag[i-1][1];
}
}
if(n>0)
{
F[i][go]=(F[i][go]+F[i-1][0]*cnt)%mod;//i-1向右下,i向左上
flag[i][go]|=flag[i-1][0];
}
if(n==4)
F[i][go]=(F[i][go]+F[i-1][1])%mod;//i-1向右上,i向左上,不相撞
else if(n>4)
F[i][go]=(F[i][go]+F[i-1][1]*(cnt-1))%mod;//i-1向右上,i向左上,不相撞
F[i][go]=(F[i][go]+F[i-1][1])%mod;//i-1向右上,i向左上,相撞
flag[i][go]|=flag[i-1][1];
}
}
printf("%lld %d\n",F[nPoint][1],maxh);
}
int main()
{
read();
Dp();
return 0;
}


  评论这张
 
阅读(1554)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017