「题解」「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;
}