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\leq d\leq 8$,答案为 $n=d\times 10^x$;
- $d=9$,$n=\frac{8(10^x-1)}{9}+1$,就是一堆 $8$ 后面跟着一个 $9$;
- $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; }
近期评论