首页 > 代码库 > SHUOJ 1771 - 奇偶和(数位DP)

SHUOJ 1771 - 奇偶和(数位DP)

2024-07-11 13:03:33   213人阅读

http://202.121.199.212/JudgeOnline/problem.php?id=1771

夏季赛H题

Description

Input

第一行含有一个正整数 T，表示有 T 组测试数据。
每组数据只有一行，包含三个整数 L_i,R_i,m。
约定
    T≤200；
    0≤L≤R≤10^18；
    |m|≤100。

Output

对于每组测试用例，输出:
第一行：Case #: （# 要替换成对应的数字）。
输出两个整数，用一个空格分割。分别为在 [L_i,R_i ] 区间，有多少个数奇偶和等于 m，以及这些数的和（对和取模100000007后输出）。

Sample Input

31 10 210 20 410 30 -1

Sample Output

Case 1:1 2Case 2:0 0Case 3:2 33

HINT

[1,10] 之间奇偶和为2的是2；

[10,20] 之间没有奇偶和为4的；

[10,30] 之间奇偶和为 -1的有10 23。

 

解题报告:

邝神出的题,果然不好做..orz

这道题用数位DP来做, 算是第一次写..比赛时挂了10次..还算是最后过了

奇偶和的概念很简单, 就是所有数位上偶数的和减去奇数的和

思路如下:

首先将0~9, 0~99, 0~999, ...奇偶和为m的利用数位DP写出一个计算函数

然后对于一个任意数n 将它分割为 1~9..9 等

如 123 可以分为 1~99, 100~109, 110~119, 120, 121, 122, 123

然后对各部分使用数位dp计算结果 其中数字个数比较好处理, 而数字的和比较难处理, 注意算数字和的时候要先求模(因为这个挂了N次)

分解的计算个数为最多 18*10 次, 并不是一个大数字

数位dp的状态也最大只有 18*(18*9) 种

最后出答案的时候记住两个相减求模的时候会出现负数 要再+MOD 再求模

分解的部分(solve函数)在比赛的时候写麻烦了, 后来参照了邝神的标程, 改成了简单一些的代码.

代码如下

 

#include <iostream>#include <sstream>#include <ios>#include <iomanip>#include <functional>#include <algorithm>#include <vector>#include <string>#include <list>#include <queue>#include <deque>#include <stack>#include <set>#include <map>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <climits>#include <cctype>using namespace std;#define INF 0x3FFFFFFF#define MP(X,Y) make_pair(X,Y)#define PB(X) push_back(X)#define REP(X,N) for(int X=0;X<N;X++)#define REP2(X,L,R) for(int X=L;X<=R;X++)#define DEP(X,R,L) for(int X=R;X>=L;X--)#define CLR(A,X) memset(A,X,sizeof(A));#define IT iteratortypedef long long ll;typedef pair<ll,ll> PII;typedef vector<PII> VII;typedef vector<int> VI;#define X first#define Y second#define MOD 100000007int fsum(ll n){    ll r=0;    do{        ll t=n%10;        r-=t*((t&1)*2-1);        n/=10;    }while(n);    return r;}ll dp[20][2000];ll sum[20][2000];ll ten[19];PII dfs(int n, int m){    if(n<=0)    {        if(m==0) return MP(1,0);        return MP(0,0);    }    ll &dd = dp[n][m+1000];    ll &ds = sum[n][m+1000];    if(dd!=-1) return MP(dd,ds);    ll count=0, sum=0;    REP2(i,0,9)    {        PII r=dfs(n-1,m-fsum(i));        count+=r.X;        sum+=((i*(ten[n]%MOD)%MOD*(r.X%MOD))%MOD+r.Y);        sum%=MOD;    }    dd=count;    ds=sum;    return MP(count, sum);}PII solve(ll n, ll m){    if(n<0) return MP(0,0);    ll count=0, sum=0;    int x=0;    n++;	do{		REP(i,n%10)		{    		PII r=dfs(x, m-fsum(n-i-1));    		count+=r.X;			sum+=(((n-i-1)*ten[x+1])%MOD)*(r.X%MOD)%MOD+r.Y;			sum%=MOD;		}    	n/=10;    	x++;    }while(n);    return MP(count, sum);}    int main(){    ios::sync_with_stdio(false);    REP(i,19)    {        ten[i]=i>1?ten[i-1]*10:1;        ten[i]%=MOD;    }    ten[0]=0;    CLR(dp,-1);    int t,cs=1;    ll l,r,m;    cin>>t;    while(t--)    {        cout<<"Case "<<cs++<<":"<<endl;        cin>>l>>r>>m;        PII a=solve(l-1,m);        PII b=solve(r,m);        cout<<b.X-a.X<<‘ ‘<<((b.Y-a.Y)%MOD+MOD)%MOD<<endl;    }    return 0;}

 

 


联系
我们