loj#560. 「LibreOJ Round #9」Menci 的序列

链接：https://loj.ac/problem/560
由于这场比赛似乎有点毒。。就不打算把这套做完了
并不是很会做啊

首先，我们先得到一个数组，表示不考虑能表示出多少个$2^x$，设数组有值的最高位为n
显然，这是一段一段的
考虑一位一位确定
对于第$i$位，如果$n>=i$，那么显然，$i$是可以用$n$表示出来的
因为你可以拿掉几个$?$啊
然后你发现，其实你可以进位，但这个进位比较特殊，如果比2大就进位，换句话说，在保证这位还有数的情况下进位，这个并不影响可以表示出比n小的所有数,也不影响原来可以表示出的个数
考虑到$n$是一段一段的，因此，用$n$表示了$i$以后，别的就废了
否则，第i位不可以直接被表示出来，那么就把后面的全部加起来就完事了，显然不会超过范围，因为每一位最多是2啊
然后就做完了，时间复杂度是$O(n)$的
感觉很巧妙啊

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1000005;
int n,k;
char ss[N];
int a[N];
int ans[N];
int main()
{
    scanf("%d%d%s",&n,&k,ss+1);int now=0;for (int u=n;u>=1;u--){
    if (ss[u]=='*') now++;else a[now]++;}	n+=20;for (int u=0;u<=n;u++){
    a[u+1]=a[u+1]+(a[u]-1)/2;a[u]=a[u]-(a[u]-1)/2*2;}for (int u=k-1;u>=0;u--){
    while (n>=0&&a[n]==0) n--;if (n<0) break;if (n>=u) ans[u]=1;else{
    for (int i=0;i<=n;i++){
    a[i+1]=a[i+1]+a[i]/2;a[i]=a[i]%2;}for (int i=0;i<=u;i++) {
    ans[i]=a[i];}break;}n--;}now=k-1;while (now>=0&&ans[now]==0) now--;if (now<0) printf("0\n");else{
    for (int u=now;u>=0;u--) printf("%d",ans[u]);}return 0;
}