星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

玄学算法/精彩DS总结 I

posted on 2018-03-26 22:04:45 | under Summary |

$0.Preface$

第一次认真写一大篇博文,主要是因为模拟退火这玩意儿很多东西都太玄学,有必要自己总结一下提升印象。

大部分代码都在luogu/loj的提交记录里面,可以随时找到。
时光流逝太多了,转眼间总结都写了九篇,甚至有很多内容因为写不下我自己单独开了 $slide$ 。自己比起以前虽然进步了很多,但智商越来越低,体力也越来越差。这时就能够体会到, $OI$ 确实是一门竞赛。

$1.Simulated\ Annealing$

简单来说,模拟退火是一种模拟现实世界退火过程进行随机贪心的算法。
它主要进行如下的步骤:

  1. 选取初始温度、温度下降率和温度下界。这通常决定你算法的效率、同时也决定了算法的正确概率。
  2. 随机选取一个当前解的扰动范围中的新解,比较两者的答案。选择过程中可以根据步长调整随机。当新解答案更优时,直接选取新解答案;当原解答案更优时,根据 $Metropolis$ 准则选取答案。
  3. 重复以上过程,直至温度降低到下界为止
    其中, $Metropolis$ 准则是指当概率 $p=\exp(\frac{-(Ans_i-Ans_j)}{T})>rd$ 时,选取新解,否则选取原解。
    $i$ 表示原解, $j$ 表示新解。公式中 $Ans_i-Ans_j$ 当且仅当 $Ans_i<Ans_j$ 时 $Ans_j$ 为更优解时。否则为 $Ans_j-Ans_i$ 。
    $rd$ 为 $[0,1)$ 的随机浮点数。

    然而实际在应用中,一般用 $\rm rand()\%10000<=T$ 代替 $Metropolis$ 准则。这样开始接受新解的概率很高,而后期会趋向于接受原解。

  4. 多次重复退火,选取最优答案

    此外一定要注意的是:

    1.在实际应用中,有时候你在退火前会对数组进行处理,退火后继续处理(如 $\rm HNOI2011$ 任务调度),此时请务必重新复制一个数组放入退火过程;

    2.务必注意你的随机过程中有没有 $\%0$ 或 $\div0$ 。


[HAOI2006]均分数据

此题退火第二步为随机选取一个元素将其放到另一组内。初始化时已经随机分组。
顺带一提,一大波大佬的博客都是把 $Metropolis$ 改成一个神奇的随机,但正确率貌似比 $Metropolis$ 还高。把 $\rm19260817$ 换成 $\rm19491001$ 才过。

[HNOI2011]任务调度

这题其实可以用各种随机算法艹过去。写退火练练手。
贪心地进行检测就好。 调参比较费劲,考场上记得对拍。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring> 
#define neko 1010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
using std::sort;
static int n,pa,pb,stk,suma,sumb,ans=2e9;
typedef int arr[neko];
static arr salp,sbet,alp,bet,s;
struct node
{
    int opt,a,b;
}q[neko];
bool cmpa(int x,int y)
{
    if(q[x].b==q[y].b)return q[x].a<q[y].a;
    return q[x].b>q[y].b;
}
bool cmpb(int x,int y)
{
    if(q[x].a==q[y].a)return q[x].b<q[y].b;
    return q[x].a>q[y].a; 
}
int greedy()
{
    int ansa=suma,ansb=0,sum;
    //assume q[alp].b time < q[bet].a time
    f(i,1,pb)
    {
        ansb+=q[bet[i]].b;
        if(ansb<ansa)ansa+=q[bet[i]].a;
        else ansa=ansb+q[bet[i]].a;
    }sum=chkmax(ansa,ansb);
    //opposite
    ansb=sumb,ansa=0;
    f(i,1,pa)
    {
        ansa+=q[alp[i]].a;
        if(ansa<ansb)ansb+=q[alp[i]].b;
        else ansb=ansa+q[alp[i]].b;
    }sum=chkmax(sum,chkmax(ansa,ansb));//pick the maximum
    return sum;
}
void Swap(int &a,int &b)
{int t=a;a=b;b=t;}
int solve()
{
    int nowa=0,swapa=0,nowb=0,swapb=0,preans,nowans,minus;
    double T=100000;
    preans=greedy();
    while(T>0.1)
    {
        T*=0.99;
        if(pa)nowa=rand()%pa+1,swapa=rand()%pa+1;
        if(pb)nowb=rand()%pb+1,swapb=rand()%pb+1;
        //printf("%d %d %d %d\n",nowa,nowb,swapa,swapb);
        if((nowa==swapa)&&(nowb==swapb))continue;
        Swap(alp[nowa],alp[swapa]),Swap(bet[nowb],bet[swapb]);
        minus=preans-(nowans=greedy());
        if(minus<0&&(rand()%10000>T))Swap(alp[nowa],alp[swapa]),Swap(bet[nowb],bet[swapb]);//do not accept the new solution
        else preans=nowans;//accept the solution,so update the answer
        //printf("%d %d\n",preans,nowans);
    }return preans;
}
int SA()
{
    int SAans=2e9;suma=sumb=0;
    memcpy(alp,salp,sizeof(salp));
    memcpy(bet,sbet,sizeof(sbet));
    f(i,1,pa)suma+=q[alp[i]].a;
    f(i,1,pb)sumb+=q[bet[i]].b;
    sort(alp+1,alp+pa+1,cmpa),sort(bet+1,bet+pb+1,cmpb);
    f(i,1,100)SAans=chkmin(SAans,solve());
    return SAans;
}
void dfs(int step)
{
    if(step>stk){ans=chkmin(ans,SA());return;}
    salp[++pa]=s[step];
    if(rand()%40000<30000)dfs(step+1);
    --pa;
    sbet[++pb]=s[step];
    if(rand()%40000<30000)dfs(step+1);
    --pb;
}
int main()
{
    srand(19491001+19260817);
    scanf("%d",&n);
    f(i,1,n)
    {
        scanf("%d%d%d",&q[i].opt,&q[i].a,&q[i].b);
        if(q[i].opt==1)salp[++pa]=i;
        else if(q[i].opt==2)sbet[++pb]=i;
        else s[++stk]=i;
    }dfs(1),printf("%d\n",ans);
    return 0;
}

$2.Linear\ Basis$

这坑目前是填不掉了。虽然写了几个板子,HAOI2017的那道题没用线段树分治也拿到了60分其实是70分但是WA了一个点,但是感觉还是没有理解线性基。之后问一下几位大佬。
注意:以下内容为未完全理解线性基时写的内容,完整版本请看 $slide$ 。 还是写一点东西吧。
线性基是一个大小为 $\log$ 的子集合,集合内的所有元素可以异或出原集合的所有数。

构造、求异或最大值

都是从大到小贪心,复杂度为 $\Theta(\log)$ 。
$UPD:$ 实际上是 $O($ 消元复杂度 $\times$ 基元素个数(也就是向量维数) $)$ 。

合并

复杂度是 $\Theta(\log^2)$ 。

求异或最小值

直接看最低的哪一位有值。

此外可以 $\Theta(\log^2)$ 的重构线性基来使每一位相互独立:

如果 $j<i$ 且 $bas_i\&(1<<j)$ ,那么 $bas_i\wedge=bas_j$ 。 注意:这被称为真线性基,即满足线性无关的线性基其实是长这样的。
这可以用来解决求异或第k小的问题:res=0,如果k第i位为1,res异或线性基中第i个元素,最终res就是第k小。

[SCOI2016]幸运数字

树链剖分维护线性基异或最大值。对于每条链都暴力合并,复杂度是十分正确的 $\Theta(\log^2)$ 。但是我常数太大了qwq

// luogu-judger-enable-o2
#include<cstdio>
#include<bitset>
#define neko 30010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);++i)
#define rf(i,a,b) for(register int i=(a);i>=(b);--i)
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
using namespace std;
static int maxbit;
typedef int arr[neko];
static arr dep,siz,fa,son,w,ord,top,head;
typedef long long ll;
static ll a[neko],A[neko];
struct Basis
{
    ll x[62]={0};
}bas[neko<<2];
namespace Linear_Basis
{
    void insert(int root,ll alp)
    {
        rf(i,maxbit,0)
        {
            if(!bas[root].x[i]){bas[root].x[i]=alp;break;}
            else alp^=bas[root].x[i];
        }
    }
    Basis merge(Basis l,Basis r)
    {
        f(i,0,maxbit)
        {
            if(r.x[i])
            {
                rf(j,maxbit,0)
                {
                    if(r.x[i]&(1ll<<j))
                    {
                        if(!l.x[j]){l.x[j]=r.x[i];break;}
                        else r.x[i]^=l.x[j];
                    }
                }
            }
        }return l;
    }
    ll greedy(Basis alp)
    {
        ll ans=0;
        rf(i,maxbit,0)if((ans^alp.x[i])>ans)ans^=alp.x[i];
        return ans;
    }
}
namespace Seg_Tree
{
    #define mid ((l+r)>>1)
    #define lson root<<1,l,mid
    #define rson root<<1|1,mid+1,r
    #define ori tagl,tagr
    using namespace Linear_Basis;
    void build(int root,int l,int r)
    {
        if(l==r){insert(root,A[ord[l]]);return;}
        build(lson);
        build(rson);
        bas[root]=merge(bas[root<<1],bas[root<<1|1]);
    }
    Basis query(int root,int l,int r,int tagl,int tagr)
    {
        if(l>=tagl&&r<=tagr)return bas[root];
        Basis tmp;bool flag=0;
        if(tagl<=mid)tmp=query(lson,ori),flag=1;
        if(tagr>mid)tmp=merge(tmp,query(rson,ori));
        return tmp;
    }
}
int root,n,q,t,cnt;
struct node
{
    int v,next;
}e[neko<<1];
namespace Siz_Subdivision
{
    using namespace Seg_Tree;
    void swap(int &x,int &y)
    {int t=x;x=y,y=t;}
    void add(int x,int y)
    {
        e[++t].v=y;
        e[t].next=head[x];
        head[x]=t;
    }   
    void dfs(int u)
    {
        dep[u]=dep[fa[u]]+1;
        siz[u]=1;
        travel(i,u,v)
        {
            if(v!=fa[u])
            {
                fa[v]=u;
                dfs(v);
                siz[u]+=siz[v];
                if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
            }
        }
    }
    void dfs2(int u)
    {
        w[u]=++cnt;
        ord[cnt]=u;
        if(son[fa[u]]==u)top[u]=top[fa[u]];
        else top[u]=u;
        if(son[u])dfs2(son[u]);
        travel(i,u,v)if(v!=fa[u]&&v!=son[u])dfs2(v);
    }
    ll pathq(int l,int r)
    {
        Basis now;
        while(top[l]!=top[r])
        {
            if(dep[top[l]]<dep[top[r]])swap(l,r);
            now=merge(now,query(1,1,n,w[top[l]],w[l]));
            l=fa[top[l]];
        }if(dep[l]>dep[r])swap(l,r);
        now=merge(now,query(1,1,n,w[l],w[r]));
        return Linear_Basis::greedy(now);
    }
}
void print(ll x)
{
    char num[110];int p=0;
    while(x)
    {
        num[++p]=x%10;
        x/=10;
    }rf(i,p,1)putchar(num[i]+'0');
    putchar('\n');
}
int main()
{
    using namespace Siz_Subdivision;
    int x,y;
    scanf("%d%d",&n,&q);
    f(i,1,n)scanf("%lld",&a[i]),A[i]=a[i];
    f(i,1,n)
    {
        x=0;
        while(a[i])a[i]>>=1,++x;
        maxbit=chkmax(x,maxbit);
    }
    f(i,1,n-1)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }root=1;
    dfs(root),dfs2(root);
    Seg_Tree::build(1,1,n);
    f(i,1,q)scanf("%d%d",&x,&y),print(pathq(x,y));
}

$3.Persistent\ Weight\ Segment\ Tree$

可持久化线段树由其只需变动修改 $\log n$ 个区间而节省空间。
可持久化权值线段树通常利用前缀和的思想和PST的基本操作来完成。
需要注意的一点是:在查询时,你导入的参数为两个根,而这两个根需要随遍历往下。还要注意向右遍历时,需要用rank-tmp。可改成非递归。

注意:luogu上的板子是错的,查rank的时候root为空、rank为0要return 0,当前和小于rank也要return 0。某些题目区间内数没有区间大小那么多的话就凉了。

注意:Others 里有不少补充。

$4.Persistent\ Balanced\ Tree$

洛谷上的模板是个卡常SB题,根只能开500000个,不然直接MLE并显示RE。
可持久化平衡树是一个类似于PST的东西,写法也有许多相似之处。只是调试仍然和普通平衡树一样恶心
当然, $\rm\ fhq\ treap$ 是一个相当好用且暴力的数据结构,但 $\rm split$ 和 $\rm merge$ 操作有许多值得注意的细节。

  1. 两个操作都需要新建节点,并利用新的节点进行递归操作(包括 $\rm pushup$ )。
  2. 除了求第k大,其他操作都需要 $\&root$ ,以便于随时的 $\rm split$ 和 $\rm merge$ 。
  3. 与原来的平衡树一样,注意前驱后继的边界。
  4. 考场上谨慎把握码力。

$5.Static\ Node\ Dividing\&Conquering\ Tree$

此坑终于可以开始填了。
静态点分树是指一般点分树的题型,这类题型通常不会要求你更改树的形态,因此点分树结构只需要预处理就可得出。 点分树是一个巧妙的暴力数据结构, 为了不用ST表求两点距离减少常数,一般地,我们会将一个点的所有点分树上的祖先信息存在vector里,这样只消耗了 $O(n\log n)$ 的时空复杂度且减少了常数。
此外,若用vector自带的lower_bound和upper_bound,一般可以方便地二分出一个左闭右开的区间,所以我们可以使用后缀和方便统计答案。 此内容的详细部分可以见slide。

$6.Segment\ Tree\ Merging$

线段树合并在树上询问子树答案时具有优异的性质和较小的复杂度(时空均 $O(n\log n)$ )。当然其他地方也可以用,可以参考fjzzq的博客和任轩笛的国家队论文。

    int merge(int x,int y,int l,int r)
    {
        if((!x)||(!y))return x|y;
        if(l==r){/*把xy两点信息合并*/ return x;}
        /*时间线段树合并有时需要直接在这里统计答案,其他的目前没看到;一般只有左边的修改对右边的答案有影响*/
        /*(Fix[L[x]]&Qry[R[y]])+(Fix[L[y]]&Qry[R[x]])*/
        /*此处 & + 均为信息合并,上式成立仅当不同子树贡献算在当前点上*/
        L[x]=merge(L[x],L[y],l,mid);
        R[x]=merge(R[x],R[y],mid+1,r);
        pushup(x);
        return x;
    }
    void dfs(int u,int fa)
    {
        for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v)if(v^fa)dfs(v,u),now=0,rt[u]=merge(rt[u],rt[v],0,m),ans[u]+=now;
    }//这是树上线段树合并的dfs形式

$ $

    int merge(int x,int y)
    {
        if((!x)||(!y))return x|y;
        //如果有强制在线或者不能在merge时回答询问 可以在这里newnode 可持久化一下
        L[x]=merge(L[x],L[y]);
        R[x]=merge(R[x],R[y]);
        //此处把y的信息合并到x上 这种写法当且仅当任意信息可直接加 注意根据题目使用
        //如Sum[x]+=Sum[y];
        return x;
    }

$newnode$ 的空间复杂度也是 $O(n\log n)$ 的,因为原来构建了 $O(n\log n)$ (题目不同有差异)个点,而 $merge$ 遇到的总点数就是那么多,所以没有问题。但应该要开 $\sout{8\log}$ 空间的啊,做题开 $\sout{4\log}$ 似乎就没有问题了,不知道为啥qwq
需要注意因为非可持久化的线段树合并后儿子信息会改变(但普通动态开点线段树的根是不会改变的),因为如果你运用了一个儿子的结点上来,那么接下来你对这个点进行修改的时候对应的儿子结点也会修改,所以当前答案只能在当前统计
还有一个 $Interesting\ Fact$ ,就是“可持久化”线段树合并和“可持久化线段树”合并还是有点区别的。