题解归档 - cf113E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf113E
• 本地来源：problems/cf113E/idea.md
• 题目链接：https://codeforces.com/contest/113/problem/E
• 原始标题：113E Sleeping

思路

113E Sleeping

题意

一天 h 小时、每小时 m 分钟；时钟用固定位宽十进制显示（小时宽 len(h-1)，分钟宽 len(m-1)，前导零）。

从 h1:m1 看到 h2:m2（含），统计分钟跳变 t → (t+1) mod (h·m) 时，显示串中至少 k 个数字位同时变化的次数。不包含离开 h2:m2 的那次跳变。

思路

把时间压成分钟编号 t = H·m + M。

小时内跳变（M < m-1）

分钟加 1，变化位数 = 1 + trailing9(M)（十进制进位链长度）。
统计 trailing9(M) ≥ k-1 的分钟数：在 [L,R] 内形如 x ≡ -1 (mod 10^t) 的个数为 ⌊(R+1)/10^t⌋ - ⌊L/10^t⌋。

整点跳变（M = m-1 → 0，小时 H → H+1 或日末回绕）

• 分钟段变化：diff(fmt(m-1), 00…0)，记常数 mc（固定位宽下非零位个数）。

• 小时段变化：

  • 若 H < h-1：1 + trailing9(H)；
  • 若 H = h-1（日末）：diff(fmt(h-1), 00…0)。
• 总变化 mc + hrchg(H) ≥ k 则计入。

区间

起点 s = h1·m+m1，终点 e = h2·m+m2。跳变起点 t ∈ [s, e-1]（不跨日）或跨日 [s, day-1] ∪ [0, e-1]。

按「首小时 / 完整小时块 / 尾小时」分解；完整小时块内分钟贡献相同，小时边界用 trailing9 批量计数，避免 O(h)。

验证

• 三组官方样例；
• Python 暴力对拍 5000 组小数据（含跨日）。

WA / TLE 修复

1. WA：badhr 未处理日末 H=h-1 回绕，改为 hourok（分钟固定贡献 + 小时增量/回绕）。
2. TLE：按小时 for 改为「首小时 / 完整小时块 / 尾小时」批量 cnt9r 计数，(O(\log)) 级。

结论

AC（submission 377706203）。无模板沉淀。

代码

来源：problems/cf113E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:13:48
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll h,m,k,h1,m1,h2,m2,lenh,lenm,day;
ll pw(ll a,ll b){
    ll zc=1,i;
    for(i=0;i<b;i++){
        if(zc>2000000000000000000LL/a) return 2000000000000000000LL;
        zc*=a;
    }
    return zc;
}
ll dig(ll x){
    ll zc=0;
    if(x==0) return 1;
    while(x){
        zc++;
        x/=10;
    }
    return zc;
}
ll cnt9(ll x,ll t){
    if(t<=0) return x+1;
    ll p=pw(10,t);
    if(p>2000000000000000000LL or x<p-1) return 0;
    return (x+1)/p;
}
ll cnt9r(ll l,ll r,ll t){
    if(l>r) return 0;
    return cnt9(r,t)-cnt9(l-1,t);
}
ll mpw(ll x,ll w){
    ll zc=1,i;
    for(i=0;i<w;i++) zc*=10;
    return zc;
}
ll difpair(ll x,ll y,ll w){
    ll p=mpw(10,w),zc=0,i,ax,ay;
    for(i=0;i<w;i++){
        ax=x%p/(p/10);
        ay=y%p/(p/10);
        if(ax!=ay) zc++;
        p/=10;
    }
    return zc;
}
ll minchg(){
    return difpair(m-1,0,lenm);
}
ll hourinc(ll H){
    return difpair(H,H+1,lenh);
}
ll hourwrap(){
    return difpair(h-1,0,lenh);
}
ll cmin(ll l,ll r){
    return cnt9r(l,r,k-1);
}
ll chour(ll l,ll r){
    if(l>r) return 0;
    ll mp,need,lim;
    mp=minchg();
    if(mp>=k) return r-l+1;
    need=k-mp;
    lim=min(r,h-2);
    ll ans=0;
    if(l<=lim) ans+=cnt9r(l,lim,need-1);
    if(l<=h-1 and h-1<=r and hourwrap()>=need) ans++;
    return ans;
}
ll hourok1(ll H){
    ll mp,need;
    mp=minchg();
    if(mp>=k) return 1;
    need=k-mp;
    if(H<h-1) return hourinc(H)>=need;
    return hourwrap()>=need;
}
ll solve(ll L,ll R){
    if(L>R) return 0;
    ll ans=0,hl,hr,ml,mr,full;
    hl=L/m;
    hr=R/m;
    if(hl==hr){
        ml=L%m;
        mr=R%m;
        if(ml<=min(mr,m-2)) ans+=cmin(ml,min(mr,m-2));
        if(mr==m-1 and L<=hl*m+(m-1) and hl*m+(m-1)<=R and hourok1(hl)) ans++;
        return ans;
    }
    ml=L%m;
    if(ml<=m-2) ans+=cmin(ml,m-2);
    if(L<=hl*m+(m-1) and hl*m+(m-1)<=R) ans+=chour(hl,hl);
    if(hr>hl+1){
        full=hr-hl-1;
        ans+=full*cmin(0,m-2);
        ans+=chour(hl+1,hr-1);
    }
    mr=R%m;
    if(m-2>=0) ans+=cmin(0,min(mr,m-2));
    if(mr==m-1 and L<=hr*m+(m-1) and hr*m+(m-1)<=R) ans+=chour(hr,hr);
    return ans;
}
ll calc(ll s,ll e){
    if(s==e) return 0;
    if(s<e) return solve(s,e-1);
    return solve(s,day-1)+solve(0,e-1);
}
int main(){
    cin>>h>>m>>k>>h1>>m1>>h2>>m2;
    lenh=dig(h-1);
    lenm=dig(m-1);
    day=h*m;
    ll s=h1*m+m1,e=h2*m+m2;
    cout<<calc(s,e)<<endl;
    return 0;
}