首页 > 其他 > 详细

codeforces 1195D2-Submarine in the Rybinsk Sea

时间:2019-07-19 00:35:59      阅读:99      评论:0      收藏:0      [点我收藏+]

传送门:QAQQAQ

 

题意:自己看

 

思路:就是一个类似于数位DP的东西。。。

统计a[i]数位分解的数在每一位出现的个数,即分两种讨论:

1.位数小于当前j,则j会出现在q+i,而且计算顺序互换会计算两遍

2.位数大于等于当前j,则j会出现在j*2-1或j*2

(比赛时光D1就调老半天,D2又太谨慎,结果E没时间做了)

 

代码:

技术分享图片
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define m_k make_pair
const int inf=(int)(2e9);
const ll INF=(ll)(5e18);
const int N=100010;
const ll MOD=998244353;
 
ll a[N][12],d[N],ans=0;
int n,len[N],t[30];
ll dp[N][12][24];
 
int fd(ll x,int id)
{
    int ret=0;
    while(x) 
    {
        a[id][++ret]=x%10;
        x/=10;
    }
    return ret;
}
 
int main()
{
    memset(t,0,sizeof(t));
    memset(dp,0,sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&d[i]);
    }
    sort(d+1,d+n+1);
    for(int i=1;i<=n;i++)
    {
        len[i]=fd(d[i],i);
        t[len[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=len[i];j++)
        {
            ll now=0;
            for(int pre=1;pre<j;pre++)
            {
                dp[i][j][pre+j]+=t[pre]*2;//前后两种都要考虑 
                now+=t[pre];
            }
            ll sum=n-now;
            dp[i][j][j*2]+=sum;
            dp[i][j][j*2-1]+=sum;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=11;j++)
        {
            ll now=1;
            for(int k=1;k<=20;k++) 
            {
                if(k>1) now=now*10%MOD;
                ans=(ans+a[i][j]*dp[i][j][k]%MOD*now)%MOD;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
View Code

 

codeforces 1195D2-Submarine in the Rybinsk Sea

原文:https://www.cnblogs.com/Forever-666/p/11210507.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!