7.2总结

淩亂°似流年 2021-11-11 00:48 221阅读 0赞

# 7.2总结 #

## 得分情况： ##

估分：100+30+100=230

实际：100+10+90=200

Rank5

海星，没有欺诈题了。

## T1 ##

一眼就是线段树啦。

等等，为甚么\$n\\leq7\*10^6\$这么大？

不管了先打着。

(30min later)打完一看，极限数据1100ms

这题该不会是要我打树状数组吧，虽然是\$log^2\$级别的，但是常数小啊

码码码…

(20min later)树状数组极限数据4000ms…

先不管了，反正也有90分。

（剩20分钟）来改一改第一题吧

诶，这一段打的这么丑

int find(int k,int l,int r,int x,int y)
    {
        if ((l<=y)&&(r>=x))
        {
            int mid=(l+r)/2;
            if ((l>=x)&&(r<=y))
            {
                if (tree[k].sum>=z)
                {
                    if (l==r) return l;
                    if (tree[k*2].sum>=z) return find(k*2,l,mid,x,y);
                    else
                    {
                        z-=tree[k*2].sum;
                        return find(k*2+1,mid+1,r,x,y);
                    }
                }
                else
                {
                    z-=tree[k].sum;
                    return 0;
                }
            }
            int tt=find(k*2,l,mid,x,y);
            if (tt!=0) return tt;
            else
            {
                tt=find(k*2+1,mid+1,r,x,y);
                return tt;
            }
        }
        else
        return 0;
    }

改成这样

int find(int k,int l,int r,int z)
    {
        int mid=(l+r)/2;
        if (l==r) return l;
        if (tree[k*2]>=z) return find(k*2,l,mid,z);
        else
        {
            return find(k*2+1,mid+1,r,z-tree[k*2]);
        }
    }

就切掉了…

后来发现还有两个地方可以优化…

我的代码怎么这么丑

## T2 ##

想了很久，差点就想到正解了

我比赛的时候想到了状压dp,但是没有想到怎么转移。

### 正解 ###

首先，对于n>21的情况是无解的。

原因不明

对于n$\\le$21的情况，我们设f\[s\]表示集合s中的字符已经有了全排列的最前位置。

设next\[i\]\[ch\]表示位置i之后第一个出现字符ch的位置

方程就是\$f\[s\]=max(next\[f\[s-2^\{x\_i\}\]\]\[x\_i\])\$