COCI 2015/2016 部分题目题解3

修改

2026年9月7日 · 阅读需 11 分钟

laieahoy

管理员

PAROVI

题意转化

这道题其实将题意转化过来就很清晰了，其实就是选一些区间让它们完全覆盖 $[1,N]$ 的大区间。

DP 推导

看到这样的问题，很自然地会想到 DP，我们先设 $f[j]$ 表示完全覆盖到 $j$ 时，有多少种可能的情况，那么转移式子也很好推：

f[max(j,a[i].r)]=\sum_{j\ge a[i].l}f[j]

因为只有 $j\ge a[i].l$ 时才可能完全覆盖，那么我们会惊奇地发现，这道题已经做完了。

一些实现上的小细节

在我们转移 $f[max(j,a[i].r)]$ 时，因为正在转移的状态是 $max(j,a[i].r)$ ，所以 $f[j]$ 可能被多次转移，所以常用的倒序转移规避重复转移的技巧不能用，需要专门记录一个数组来转移。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=130,M=25,mod=1e9;
int n,cnt;
struct node{
    int l,r;
}a[N];
int dp[M],now[M];

bool cmp(node a,node b)
{
    return a.l==b.l?a.r<b.r:a.l<b.l;
}

int main()
{
    cin>>n;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(__gcd(i,j)==1){
                a[++cnt]={j,i};
            }
        }
    }
    sort(a+1,a+1+cnt,cmp);
    dp[1]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=n;j++) now[j]=dp[j];
        for(int j=1;j<=n;j++){
            if(!dp[j]) continue;
            if(j>=a[i].l){
                int nj=max(j,a[i].r);
                now[nj]+=dp[j];
                if(now[nj]>=mod) now[nj]-=mod;
            }
        }
        for(int j=1;j<=n;j++) dp[j]=now[j];
    }
    cout<<dp[n]<<"\n";

    return 0;
}

SAN

题目大意

有一张表，第 i 行从数字 i 开始，后面的数字按照下面的规则生成：

x -> x+rev(x)

例如第 12 行是：

现在给出若干个询问，每次给出一个区间 [L,R]，要求统计整张表中，位于这个区间内的数字总共出现了多少次。

第一列是：

1,2,3,4,...

如果直接枚举第一列的每个数字，再模拟它后面的变化，肯定无法通过。因为 R 最大可以达到 1e10，第一列就已经有一百亿个数字了。

所以需要观察一次变换 x+rev(x) 的结构，而不是去枚举每一行。

先看一次加法

假设一个数字是：

abcde

它翻转后是：

edcba

相加时，最外侧的两位会互相配对，第二外侧的两位也会互相配对：

a+b
b+d
c+c
d+b
e+a

这里暂时不考虑进位，而是把每一位看成一个系数。可以发现，得到的系数一定是对称的。

例如一个三位数相加后，系数一定是：

p,q,p

五位数则一定是：

p,q,r,q,p

每个系数都来自两个数字之和，因此范围是 0 到 18。

这给出了一个重要的限制：第二列中可能出现的数字并不是任意数字，而是由一组对称的系数构成的。我们可以按照这个结构进行 DFS，而不是枚举所有第一列数字。

统计一种系数对应多少个数字

假设某一对位置的系数是 p，那么原数字对应的两位需要满足：

a+b=p

其中 a 和 b 都在 0 到 9 之间。

比如 p=3 时有：

0+3
1+2
2+1
3+0

所以普通位置有 4 种可能。

代码中的 ways[p] 就是普通位置的方案数，计算方式是：

p<=9 时为 p+1
p>=10 时为 19-p

不过最外面的一对位置包含原数字的最高位，最高位不能是 0。

所以最高位要单独统计。还是以 p=3 为例，0+3 不能使用，只剩下三种方案。

代码中的 lead[p] 表示最高位的方案数，并且：

lead[0]=0;

这样就不会把最高位为 0 的情况算进去。

中间位置需要特殊处理

如果原数字的位数是奇数，就会有一个中间位置。

这个位置翻转后仍然对应自己，因此它的系数一定是：

a+a

所以中间位置只能取偶数：

0,2,4,...,18

而且每个偶数只有一种来源。

比如系数为 8 时，只能由：

4+4

产生。

当数字长度为 1 时，这个中间位置同时也是最高位。此时不能选择 0+0，因此从 2 开始枚举。

用 DFS 枚举第二列

对于一个固定的数字长度，DFS 从最低位开始处理。

当前处理的位置是 dep，和它对称的位置是：

other=len-dep-1;

如果这一对位置选择系数 i，那么它对最终数字的贡献是：

(pw[dep]+pw[other])*i

同时，产生这种系数的方案数也要乘进去：

最外侧位置乘 lead[i]；
其他位置乘 ways[i]；
中间位置只有偶数系数，并且每个系数对应一种方案。

DFS 结束时，就得到一个第二列数字 sum，以及产生它的第一列数字数量 cnt：

a[++tot]={sum,cnt};

这里的 cnt 很重要。它不是某个数字在整张表中的最终出现次数，而是这个数字作为第二列数字时，由多少个第一列数字产生。

为什么需要排序合并

同一个数字可能通过不同的系数组合得到。

例如某个数字既可能由一组普通系数表示，也可能由于进位关系由另一组系数表示。DFS 会把这些情况分别记录下来，因此数组中可能出现多条相同的 val。

这些记录需要合并：

相同数字的出现次数相加

具体做法很直接：

按 val 从小到大排序；
扫描排序后的数组；
相同的数字放到同一个位置；
将它们的 cnt 相加。

这里不用 map，是因为候选数字数量比较多，而 map 的节点还要额外保存指针和管理信息，空间开销比较大。直接使用数组排序，能够满足空间限制。

处理第二列之后的数字

现在假设数字 x 已经知道出现了多少次。

它的下一个数字是：

x+reverse(x)

因此，x 出现多少次，它的后继就要增加多少次：

a[pos].cnt+=a[i].cnt;

为什么可以直接从小到大处理？

因为对于正整数来说，reverse(x) 也是非负数，而且 x+reverse(x) 一定比 x 大。所以所有转移都是从较小的数字转向较大的数字。

处理到当前数字时，它能收到的贡献已经来自更小的数字，后面只需要把当前贡献继续传给它的后继即可。

后继数字可以直接查找

DFS 枚举出的第二列数字都有对称系数结构。

将这样的数字翻转，系数顺序会反过来，但因为原本就是对称的，所以翻转后仍然满足相同的结构。

因此，一个候选数字的后继也一定属于候选数字集合。

候选数字排序后，就可以用二分查找后继的位置，而不需要再开新的哈希表或平衡树。

从第一列开始统计

第一列中的数字非常简单：

1,2,3,...,x

所以不超过 x 的第一列数字一共有 x 个。

对于第二列及以后，我们把每个候选数字的出现次数转移完成后，再对这些次数做前缀和。

于是，不超过 x 的总出现次数就是：

第一列贡献+第二列及以后贡献

代码中对应：

return x+a[pos].cnt;

设这个函数为 calc(x)，那么询问 [L,R] 的答案就是：

calc(R)-calc(L-1)

为什么只枚举十位数字

题目中的上限是 1e10。

虽然 1e10 本身有 11 位，但它的后继是：

1e10+1

已经超过上限了，所以它不会对第二列及以后产生有效贡献。

因此，第二列只需要由最多十位的第一列数字产生。代码中枚举：

for(int len=1;len<=10;len++)

第一列的数量则直接通过前缀函数中的 x 统计，不需要把第一列全部建出来。

小数处理

两条轨迹的相交位置可能是半整数，所以答案也可能出现 .5。

代码中统一把所有距离乘以 2：

向右走的变色龙贡献 2*(L-d)；
向左走的变色龙贡献 2*d。

这样所有计算都变成整数，最后输出时：

如果答案是偶数，输出 .0；
如果答案是奇数，输出 .5。

复杂度分析

设 DFS 生成的记录数量为 K。

预处理时需要排序、合并，并为每个数字查找一次后继，复杂度为：

O(K log K)

每次询问只需要二分查找，复杂度为：

O(log K)

总复杂度为：

O(K log K+Q log K)

空间复杂度为：

O(K)

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=4e6+5;
const ll MAXV=1e10;
struct node{
    ll val,cnt;
}a[N];
int tot;
ll pw[11];
int ways[19],lead[19];

bool cmp(node x,node y)
{
    return x.val<y.val;
}

ll rev(ll x)
{
    ll ret=0;
    while(x){
        ret=ret*10+x%10;
        x/=10;
    }
    return ret;
}

int find(ll x)
{
    int l=1,r=tot;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid].val<=x) l=mid+1;
        else r=mid-1;
    }
    return r;
}

void dfs(int len,int dep,ll sum,ll cnt)
{
    if(sum>MAXV) return;
    if(dep>(len-1)/2){
        a[++tot]={sum,cnt};
        return;
    }
    int other=len-dep-1;
    if(dep==other){
        int st=(dep==0?2:0);
        for(int i=st;i<=18;i+=2){
            dfs(len,dep+1,sum+pw[dep]*i,cnt);
        }
        return;
    }
    int st=(dep==0?1:0);
    for(int i=st;i<=18;i++){
        ll nsum=sum+(pw[dep]+pw[other])*i;
        ll ncnt=cnt;
        if(dep==0) ncnt*=lead[i];
        else ncnt*=ways[i];
        if(ncnt==0) continue;
        dfs(len,dep+1,nsum,ncnt);
    }
}

void init()
{
    pw[0]=1;
    for(int i=1;i<=10;i++) pw[i]=pw[i-1]*10ll;
    for(int i=0;i<=18;i++){
        if(i<=9){
            ways[i]=i+1;
            lead[i]=i;
        }
        else{
            ways[i]=19-i;
            lead[i]=19-i;
        }
    }
    lead[0]=0;
    for(int len=1;len<=10;len++) dfs(len,0,0,1);
    sort(a+1,a+1+tot,cmp);
    int now=0;
    for(int i=1;i<=tot;i++){
        if(now==0||a[now].val!=a[i].val){
            a[++now]=a[i];
        }
        else{
            a[now].cnt+=a[i].cnt;
        }
    }
    tot=now;
    for(int i=1;i<=tot;i++){
        ll nxt=a[i].val+rev(a[i].val);
        if(nxt>MAXV) continue;
        int pos=find(nxt);
        if(pos>=1&&a[pos].val==nxt){
            a[pos].cnt+=a[i].cnt;
        }
    }
    for(int i=1;i<=tot;i++){
        a[i].cnt+=a[i-1].cnt;
    }
}

ll calc(ll x)
{
    if(x<=0) return 0;
    int pos=find(x);
    return x+a[pos].cnt;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int Q;
    cin>>Q;
    while(Q--){
        ll L,R;
        cin>>L>>R;
        cout<<calc(R)-calc(L-1)<<"\n";
    }

    return 0;
}

PAROVI​

题意转化​

DP 推导​

一些实现上的小细节​

SAN​

题目大意​

先看一次加法​

统计一种系数对应多少个数字​

中间位置需要特殊处理​

用 DFS 枚举第二列​

为什么需要排序合并​

处理第二列之后的数字​

后继数字可以直接查找​

从第一列开始统计​

为什么只枚举十位数字​

小数处理​

复杂度分析​