玄学算法/精彩DS总结 I
teafrogsf
2018-03-26 22:04:45
## $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]任务调度
这题其实可以用各种随机算法艹过去。写退火练练手。
贪心地进行检测就好。
调参比较费劲，考场上记得对拍。
```cpp
#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
```cpp
// 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的博客和任轩笛的国家队论文。
```cpp
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形式
```
$ $
```cpp
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$，就是“可持久化”线段树合并和“可持久化线段树”合并还是有点区别的。