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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1799][Ahoi2009]self 同类分布  

2015-03-14 08:55:11|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1799: [Ahoi2009]self 同类分布

啊啊啊啊啊啊啊又被坑死了!!!!
我到网上找了两个所谓A掉的程序全是错的!!!!
然后最后又被GTY的程序坑了!!!
BZOJ的数据是有多弱啊啊啊啊
题解在代码下方

#include <cstdio>
#include <cstdlib>
#include <iostream>
typedef long long ll;
using namespace std;
const int MA = 9*18+1;
const int N = 20;
int n,m,MOD,T,list[20];
int v[N][MA][MA][2];
ll f[N][MA][MA][2];
void update(short i,short j,short k,short t,ll val){
if(k > MOD)return;
int &vn = v[i][j][k][t];ll &fn = f[i][j][k][t];
if(vn!=T)vn=T,fn=0;
fn += val;
}
ll solve(ll lim,int x){
if(!x)return 0;T++;
short i,j1,j2,k;MOD = x;
for(list[0]=0;lim;lim/=10)list[++list[0]] = lim%10;
//for(i=1;i*2<=list[0];i++)swap(list[i],list[list[0]-i+1]);
n = list[0];
f[n+1][0][0][0] = 1;
v[n+1][0][0][0] = T;
for(i=n+1;i>1;i--)
for(j1=0;j1<MOD;j1++)
for(j2=0;j2<=MOD;j2++)
if(v[i][j1][j2][0]==T||v[i][j1][j2][1]==T){
update(i,j1,j2,0,0);update(i,j1,j2,1,0);
if(f[i][j1][j2][0]==0 && f[i][j1][j2][1]==0)continue;
for(k=0;k<=9;k++){
//0
if(f[i][j1][j2][0]){
if(k<list[i-1]){
update(i-1,(j1*10+k)%MOD,j2+k,1,f[i][j1][j2][0]);
//printf("%d\n",f[i-1][(j1*10+k)%MOD][j2+k][1]);
}else if(k==list[i-1]){
update(i-1,(j1*10+k)%MOD,j2+k,0,f[i][j1][j2][0]);
}
}
//1
if(f[i][j1][j2][1])
update(i-1,(j1*10+k)%MOD,j2+k,1,f[i][j1][j2][1]);
}
}
update(1,0,MOD,0,0); update(1,0,MOD,1,0);
return f[1][0][MOD][0] + f[1][0][MOD][1];
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
ll a,b,ans=0;
cin >> a>> b;
for(i=1;i<MA;i++){
ll tmp = solve(b,i)-solve(a-1,i);
printf("%d %lld\n",i,tmp);
ans += tmp;
}
cout << ans << endl;
return 0;
}

题解:
首先显然是个数位DP……
f[i][j][k]表示填到了第i位,%MOD=J,数位和=K的数字数
但是由于模数不确定使得题目非常蛋疼,所以我们枚举模数,一共只有9*18个可能模数(注意不是9*17……)
  评论这张
 
阅读(239)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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