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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

2015.10.09月赛题解(数学&数论专场)  

2015-10-10 00:10:52|  分类: ACM-bjfu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:http://acm.bjfu.edu.cn/acmhome/contest.do?&method=contestDetail&contestId=87
A:
矩阵快速幂。
本来是一道复杂的矩阵快速幂题,后来考虑到大家对这个不是很熟悉,找个了裸题,主要帮助大家学习矩阵快速幂。
很容易可以得到递推公式:f(n)=2*(f(n-1)+f(n-2))
有很多方法可以得出这个递推公式,这里介绍下用dp的思想来推导:
dp[i][0]表示以字符'A'或'C'为结尾的字符串个数,
dp[i][1]表示以字符'M'为结尾的字符串个数。
我们先来求dp[i][0],前面可以跟任意一个字符,另外当前字符可以是字符'A'或'C'两种情况,所以有
dp[i][0]=2*(dp[i-1][0]+dp[i-1][1]);
然后我们再来求dp[i][1],前面只能跟字符'A'或'C',所以有dp[i][1]=dp[i-1][0].
f(i)=dp[i][0]+dp[i][1],表示长度i能表示的字符串个数,
dp[i][0]=2*(dp[i-1][0]+dp[i-1][1])=2*f(i-1);
dp[i][1]=dp[i-1][0]=2*(dp[i-2][0]+dp[i-2][1])=2*f(i-2);
于是我们就得到了递推公式:f(n)=2*(f(n-1)+f(n-2))。
接下来用矩阵快速幂套套模板就可以了(网上有很多矩阵快速幂资料可以学习,这里就不多说了,建议先学习用矩阵快速幂求Fib数)

B:
YY。
我们可以发现,有些数可以从N展开至1,有些不能,只能展开到a,考虑一般情况,问题就变成了求区间[a,N]所有数的二进制数上1的个数和。如果我们能算出1到p之间所有数的二进制数上1的个数和,那么区间的也就可以算了,等于1到N的结果减1到a-1的结果。求1到p这部分就比较简单了,按数的位数来做,可以发现有规律,细节再处理处理就可以了,具体见代码:

LL n,k,a;
LL fun(LL t){
LL nn=t+1,c=0;
while(t){
c++;
t>>=1;
}
LL len,s=0;
for(LL i=0;i<c;i++){
len=(LL)1<<i;
LL yu=nn%(len<<(LL)1);
s=s+nn/(len<<(LL)1)*len;
s=s+Max((LL)0,yu-len);
}
return s;
}

int main(){
while(cin >> n >> k){
if(k >= 16000000){
a=1;
}else{
if(n > (2*k+1)*(2*k+1))
a=n-(2*k+1)*(2*k+1)+1;
else
a=1;
}
cout << fun(n)-fun(a-1) << endl;
}
return 0;
}


C:
dfs构造或者打表。
这题数据没出好,打表也可以过,毕竟结果没多少种……
这里介绍下dfs构造的姿势,稍加思考,我们可以发现这么几条规律:
回文素数的位数只能是奇数(除了11);
回文素数的第一个数字只能是1 3 7 9;
既然是回文,如果我们知道了数的前半部分,就可以构造出整个数了。
这么算下来,已经剪了不少枝,满足条件的状态也没多少了,可以进行dfs构造了。
贴个核心代码:

void dfs(int pos,int s,int length){//pos表示当前第几位,s表示当前构造的数,length表示数的总长
if(pos*2 >= length){
int t=fun(s,length); //s为t的前半部分,length为t的位数
if(jud(t)) //判断t是否为素数
pf(t);
return;
}
for(int i=0;i<10;i++){
if(jud1(s*10+i,length)) //剪枝:判断当前构造的数在不在区间[a,b]内,如果不在则不用考虑。例如区间为[5,15000],此时s为17,length为5,则这种情况肯定不符合,因为17#71>15000
dfs(pos+1,s*10+i,length);
}
}



D:
dfs构造。
枚举K范围内的所有质数,然后用这些质数构造小于N的数。这题代码可以很短,可以在10行内搞定。具体看代码:

LL N,K,a,f[30]={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,110};
void dfs(LL t,int r){
a++;
for(int i=r;f[i]<=K && t*f[i]<=N;i++)
dfs(t*f[i],i);
}
int main(){
while(sf264(N,K)!=EOF){
a=0;
dfs(1,0);
pf64(a);
}
return 0;
}



E:
质因数分解+二分。
详细题解看这里:
http://fudq.blog.163.com/blog/static/191350238201581603337624/

F:
签到题。
任意姿势都可以过。可以总结规律O(1)过,也可以遍历一遍O(n)过。
  评论这张
 
阅读(75)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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