「题解」「BalticOI2014」序列 Sequence

BalticOI2014 Day 1 T3，一道毒瘤题目。

题目链接：LibreOJ 2824/BZOJ 3917/BalticOI2014 D1T3。

题目

题目描述

原题 pdf

传送门。

题意翻译

给定一个长度为 $k$，公差为 $1$ 的等差数列，数列首项为 $n$。你只知道数列的每一项的某一位，求出数列首项至少是多少。

数据范围

子任务	分值	数据范围	附加限制
$1$	$9$	$1\leq K\leq 1000$	答案不超过 $1000$
$2$	$33$		无
$3$	$25$	$1\leq K\leq 10^5$	给定数列中所有元素均相等
$4$	$33$	$1\leq K\leq 10^5$	无

时空限制

题解

本题有部分分做法。

解法 A（9 分）

注意到对于 $9$ 分的数据，满足答案 $n\leq 10^3$。

所以我们可以枚举答案 $n$，暴力验证是否为答案。

时间复杂度为 $\Theta(n+K)$。

代码

略。

解法 B（25 分）

注意到对于 $25$ 分的数据，序列的元素不变。

所以我们不难发现，答案比较接近 $10^x$ 次方（因为要进位），假设这个元素为 $d$，我们不难发现：

1. $1\leq d\leq 8$，答案为 $n=d\times 10^x$；
2. $d=9$，$n=\frac{8(10^x-1)}{9}+1$，就是一堆 $8$ 后面跟着一个 $9$；
3. $d=0$，$n=10^x$。

上面的 $x$ 与 $k$ 有关，可以简单算一下。

时间复杂度为 $\Theta(1)$。

代码

略。

解法 C（100 分）

我们先考虑一个复杂点的问题。

设给出的数列的元素为 $a _ i$，$a _ i$ 是序列元素必须具有的数字序列。

为了简化表达，我们定义 $(x)y$ 表示 $10x+y$。

假设 $n=10x+y$，即 $(x)y$，其中 $y=n \bmod 10$，即 $y$ 是最后一位数字，$x=\lfloor\frac{n}{10}\rfloor$。

枚举 $y\in[0,9]$，确定 $y$ 值后，我们的序列如下所示
$$\begin{bmatrix}&(x)y,&(x)y+1,&\cdots,&(x)8,&(x)9,\\&(x+1)0,&(x+1)1,&\cdots,&(x+1)8,&(x+1)9,\\&(x+2)0,&\cdots\end{bmatrix}$$

删除最后一位数字后，我们得到序列
$$x,\cdots,x+1,x+2,\cdots$$

$(x)y$ 具有 $a _ 1$，因此 $x$ 必须具有 $a _ 1y$。$(x)(y+1)$ 具有 $a _ 2$，因此 $x$ 必须具有 $a _ 2y+1$ 等。

通过合并这些子问题，我们可以获得一系列新的集合 $B _ 1,B _ 2,\cdots$。
其中 $B _ 1$ 包含 $X$。$B _ 2$ 包含 $(x+1)$ 等所需的数字。

我们对新序列重复相同的步骤。每次新序列的长度都不会大于 $\frac{x}{10}+1$，$x$ 为原长度。

因此，在 $\log _ {10}k$ 步之后，我们的序列长度为 $1$ 或 $2$，即到达了递归边界，直接贪心求解即可。

时间复杂度为 $\Theta(k\log _ {10}k)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F3F3F3F3Fll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

inline ll Solve(vector<int> V,reg bool flag){
    if(V.size()==1){
        reg int t=V[0];
        ll res=0;
        for(reg int i=1;i<=9;++i)
            if(t>>i&1){
                res=res*10+i;
                t^=(1<<i);
                if(t&1)
                    res*=10,t^=1;
            }
        if(t&1)
            res=10;
        if(flag)
            res=max(res,1ll);
        return res;
    }
    ll res=INF;
    for(reg int x=0;x<=9;++x){
        if(V.size()==2&&(~V[0]>>9&1)&&(~V[1]&1)&&!flag&&x==9)
            continue;
        vector<int> New;
        int y=x-1,z=0;
        for(reg int i=0,size=V.size();i<size;++i){
            ++y;
            z|=V[i]&(~(1<<y));
            if(y==9||i==size-1)
                New.push_back(z),y=-1,z=0;
        }
        res=min(res,Solve(New,(x==0)&&(V[0]&1))*10+x);
    }
    return res;
}

int n;

int main(void){
    n=read();
    vector<int> V(n);
    for(reg int i=0;i<n;++i){
        static int x;
        x=read();
        V[i]=(1<<x);
    }
    printf("%lld\n",Solve(V,1));
    return 0;
}