树上问题类

[NOI2015]软件包管理器

题解

对于树上每个点,0表示未安装,1表示已安装。 安装一个软件$x$,把$path_{0,x}$全部赋1即可,卸载同样操作。 每次取已安装软件总数绝对值作为答案即可。

细节

注意大众写法应该将编号整体+1,避免对编号为0的点进行操作。

[NOIP2016]天天爱跑步

题解

树上差分变种。

首先对于每个询问来更新一些点的答案是不现实的,所以可以对于每个观察者(点)计算哪些询问(路线)有贡献。我们发现对于每个j,能对它的答案产生贡献的点分两类:它的子树中的$s_i$和$LCA(s_i,t_i)$为其祖先且$s_i$不在j-LCA链上且$t_i$在j子树中的$s_i$。

最开始我想到了dp,用dp[i][j]表示i的子树中depth为j的s的个数,但数组显然开不下,且难以维护。好像有一种线段树合并的维护方法,好麻烦。后来想到tarjan算法中记录dfn作为当前递归层的栈底,我们也可以对于dfs遍历树时每个节点记录进入时的cnt[depth[j]+w[j]],然后遍历完子树后统计答案时用此时的cnt减去进入时的cnt,得到当前节点子树中的cnt,类似于一个差分。此方法是可行的,因为每个节点要用的cnt值只有一个,空间时间复杂度均很优秀。

细节

LCA处的处理我没有想得很透彻。首先当遍历来到某个询问的LCA后其子树中存在有s,t对上方的节点是不会产生贡献的(不会经过上方节点),所以要在LCA处减去对应的s对cnt(一些节点的答案)的贡献。其次LCA处可能会将同一跑步路线中的s按照上述两类都计算一遍贡献(形象说就是LCA在路径中没有过顶点又过了顶点),因此需要减去重复计算的贡献,此类情况下一定有depth[si]==depth[LCA]+w[LCA]

代码

#include<bits/stdc++.h>
#define Side(x) for(int i=p[x];i;i=nt[i])
using namespace std;
const int N=300020;
int tot,e[N<<1],nt[N<<1],p[N];
void _add(int x,int y){e[++tot]=y,nt[tot]=p[x],p[x]=tot;}
inline void add(int x,int y){_add(x,y),_add(y,x);}
int n,m,o[N],depth[N],f[N][22],cnt_base[N*2],cnt_base1[N*2],start[N],ans[N];
int *cnt=&cnt_base[N],*cnt1=&cnt_base1[N];
vector<int>player[N],lca[N],lca1[N];
char ch;
void read(int &v)
{
	v=0,ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))v=(v<<1)+(v<<3)+ch-'0',ch=getchar();
}
void dfs(int x)
{
    for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
    Side(x)
    {
        if(!f[e[i]][0])
        {
            f[e[i]][0]=x,depth[e[i]]=depth[x]+1;
            dfs(e[i]);
        }
    }
}
int LCA(int x,int y)
{
    if(depth[x]>depth[y])swap(x,y);
    int d=depth[y]-depth[x];
    for(int i=0;d;i++,d>>=1)if(d&1)y=f[y][i];
    for(int i=20;i>-1;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return x==y?x:f[x][0];
}
void dfs2(int x)
{
    int tmp=cnt[o[x]+depth[x]],tmp1=cnt1[depth[x]-o[x]];
    cnt[depth[x]]+=start[x];
    for(vector<int>::iterator iter=player[x].begin();iter!=player[x].end();iter++)
        cnt1[*iter]++;
    Side(x)
        if(e[i]!=f[x][0])dfs2(e[i]);
    ans[x]+=cnt[o[x]+depth[x]]-tmp,ans[x]+=cnt1[depth[x]-o[x]]-tmp1;
    for(auto iter=lca[x].begin();iter!=lca[x].end();iter++)cnt1[*iter]--;
    for(auto iter=lca1[x].begin();iter!=lca1[x].end();iter++)cnt[*iter]--;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,xi,yi;i<n;i++)
        scanf("%d%d",&xi,&yi),add(xi,yi);
    f[1][0]=1,depth[1]=1,dfs(1);
    for(int i=1;i<=n;i++)read(o[i]);
    for(int i=1,si,ti;i<=m;i++)
    {
        read(si),read(ti);
        int l=LCA(si,ti);
        //cerr<<"LCA:"<<si<<' '<<ti<<':'<<l<<endl;
        start[si]++,ans[l]-=(bool)(depth[si]==depth[l]+o[l]);//,start[ti]++;
        player[ti].push_back((depth[l]*2)-depth[si]),lca[l].push_back((depth[l]*2)-depth[si]),lca1[l].push_back(depth[si]);
        //player[ti].push_back((depth[l]<<2)-depth[ti]);
    }
    dfs2(1);
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}

 

期望与概率DP类

WJMZBMR打osu! / Easy

题解

我又是看了题解才做出来的,菜爆了! 首先设第$i$个位置时combo长度为$a_i$,得分为$f_i=a^2$,此处先不考虑不确定性和期望,则假设连续正确输入第$i+1$个位置的得分为$f_{i+1}=(a_i+1)^2=a_i^2+2\cdot a_i+1$并且长度为$a_{i+1}=a_i+1$。 因此我们可以将整体得分表示为$$\sum_{i=1}^{i<=n}{(a_i\cdot 2+1)}$$

由此我们再来考虑概率的影响。可以发现根据上式,得分的期望与$a_i$的期望呈线性相关,由此可以直接处理combo长度的期望值$a_i$并在计算时对$f_i$进行转移。

这里对$f_i,a_i$的转移进行分类讨论

然后据此打出来就可以了。因为题目没有给出n的范围,且此转移只和上一个状态相关,因此可以采用边读边算的方法或者乱混n大小的方法

[国家集训队]单选错位

题解

看题解系列,没救了!

首先题面说得有点意思,给了一段数据生成的程序,很有意思并没什么用。

然后我们来分析一下问题,首先是手动模拟这个概率计算。沿用题面里的$a_i$表示第i道题的选项个数,若第i-1道题对了则对于第i题的每个选项$j,~j\le a_{i-1}$,有$\frac{1}{a_{i-1}}$的可能性错位后选择的是这个选项(上一题的答案是j),而对于每个$k,~k\le a_i$有$\frac{1}{a_i}$的可能是正确答案,会产生$\frac{1}{a_{i-1}}\cdot \frac{1}{a_i}\cdot1$的期望值。由于要求选项一一对应,只有$j=k$时才对分数有贡献。

所以对于每题,期望分值为$\sum_{i=1}^{i\le\min (a_i,a_{i-1})}\frac{1}{a_{i-1}\cdot a_i}=\frac{\min(a_{i-1},a_i)}{a_{i-1}\cdot a_i}$

然后读入完之后直接$O(n)$顺着扫一遍就得到答案了。

数据结构类

mex

题意

给出一个长n的序列a和q次询问$(n,q \in [1,~2\times10^5],a\in [1,10^9])$,每次询问数列中$[l,r]$内最小没出现的自然数。

题解

看题解x2,自己准备滚了!

偶然看到此题,以前用莫队水过,但是感觉$O(n\sqrt n)$的算法很不优秀,遂搜索,知有主席树做法,匆忙瞟过,yy了一种不可做方法纯暴力,然后去膜正解了。

参考

  1. WerKeyTom_FTD的题解
  2. Candy?的题解

先离线询问(按右端点升序排列),离散化a数列,再建值域线段树,维护每个值出现的最右端位置$mx_i$的最小值,查询时找到最小的pos使得$mx_{pos}\le l$即得到所求最小自然数。

该方法非常神仙,在此$Orz_{Orz_{Orz}}$一波WerKeyTom_FTD神仙。

细节处,离散化时先排序,然后扫一遍,若$a_i+1=a_{i+1}$说明比$a_i$大1的自然数(可能取到为答案)在序列里,否则同时向去重后的数组加入$a_i+1$。

离散化线段树代码较主席树方法短,常数小,进了第一面(lydsy)

代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline T chkmn(T x,T y){return x<y?x:y;}
template<typename T>inline T read(T &x)
{
    x=0;T f=1;char ch=getchar();
    while(!isdigit(ch))f=ch=='-'?-1:1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x;
}
const int N=200020;
const int INF=2147483647;
int n,m,cnt,num,a[N],b[N],c[N],ans[N];
struct node{int l,r,mx;}t[N<<2];
struct quiry
{
    int l,r,*ans;
    bool operator < (const quiry& x) const{return r<x.r;}
}q[N];
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r)return ;
    int m=l+r>>1;
    build(p<<1,l,m),build(p<<1|1,m+1,r);
}
void update(int p,int pos,int v)
{
    if(t[p].l==t[p].r)
        {t[p].mx=v;return ;}
    int m=t[p].l+t[p].r>>1;
    if(pos<=m)update(p<<1,pos,v);
    else update(p<<1|1,pos,v);
    t[p].mx=chkmn(t[p<<1].mx,t[p<<1|1].mx);
}
int query(int p,int pos)
{
    if(t[p].l==t[p].r)return t[p].l;
    if(t[p<<1].mx<pos)return query(p<<1,pos);
    else return query(p<<1|1,pos);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        b[i]=read(a[i]);
    sort(b+1,b+1+n);
    int cnt=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=cnt;i++)
    {
        if(b[i]+1!=b[i+1])c[++num]=b[i]+1;
        c[++num]=b[i];
    }
    sort(c+1,c+1+num);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(c+1,c+1+num,a[i])-c;
    for(int i=1;i<=m;i++)
        read(q[i].l),read(q[i].r),q[i].ans=&ans[i];
    sort(q+1,q+1+m);
    build(1,1,num);
    for(int i=1;i<=m;i++)
    {
        for(int j=q[i-1].r+1;j<=q[i].r;j++)update(1,a[j],j);
        *q[i].ans=query(1,q[i].l);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",c[ans[i]]);
}

 

斜率优化DP类

说明

如果递推式可以变成形如 $dp[i]=s[i]+min(f[j]−k[i]\cdot t[j])$,且t[j]和k[i]是单调的,就可以采用斜率优化维护凸壳的方式来取答案,大大降低复杂度。

[HNOI2008]玩具装箱TOY

题解

不加优化

复杂度$O(n^2)$,动规方程为$$dp_i=min(dp_j+[sum_i-sum_j+(i-j-1)-L]^2)$$。

我们可以先进行一下简化:令$C=L+1,g_i=sum_i+i$,原方程变形为$dp_i=min(dp_j+(g_i-g_j-C)^2)$。

斜率优化

复杂度可变为$O(n)$?假的吧

将简化的式子展开,变为$dp_i=g_i^2−2\cdot C\cdot g_i+min(2\cdot C\cdot g_j+g_j^2+C^2−2\cdot g_i\cdot g_j)$ 。

然而没什么用。

直接列不等式求解,假设i前面有j、k两状态,j<k且j优于k,则有$dp_j+(g_i-g_j-C)^2 \le dp_k+(g_i-g_k-C)^2​$解得抄答案得$$\frac{(dp_j+(g_j+C)^2)-(dp_k+(g_k+C)^2)}{2\cdot(g_j-g_k)}\ge g_i​$$

发现左边形似斜率式,我们就令Slope(x,y)=左式。

然后我们可以证明两个单调队列维护要用到的结论:

1.若$Slope(q[l],q[l+1])\le f[i]$,则q[l]没有q[l+1]优,则删除q[l] 

2.若$Slope(q[r-1],q[r])\ge Slope(q[r],i)$,则删除q[r]

这里证明一下两个策略:

  1. 策略1比较显然,对于当前更新到的i当然要选择最优的来进行更新,当前l不比l+1优($slope(l,l+1)\le g_i$),而$g_i$是单增序列,则一定有$slope(l,l+1)\le g_{i+1}$,因此之后l也不比l+1优。
  2. 对于策略2,我们整个用单调队列维护的更新过程是从队首取出较优的状态,需要保证队首l与次队首l+1的斜率小于等于次队首l+1与之后l+2的斜率,否则弹出队首l之后后面的斜率$slope(l+1,l+2)$比队首更小,则l不可能成为新的更优状态,也就一定是无用状态了。因此我们需要满足单调队列中两两间的斜率是单增的。
  3. 另外对于队首后面的所有点,因为两两间斜率单增,所以l和l+2,l+3,l+4...的斜率也是单增的(不懂就画个图),即比后面的都优,因此整个队列中队首最优且优秀程度单增。

代码

#include<bits/stdc++.h>
#define pow(x) ((x)*(long long)(x))
using namespace std;
const int N=200020;
int n,L,g[N],q[N],l,r;
long long dp[N];
double calc(int k,int j)
{return (dp[j]-dp[k]+(long long)(g[j]+L)*(g[j]+L)-(long long)(g[k]+L)*(g[k]+L))/(2.0*(double)(g[j]-g[k]));}
int main()
{
    scanf("%d%d",&n,&L);L++;
    l=r=1;
    for(int i=1,ai;i<=n;i++)
    {
        scanf("%d",&g[i]);
        g[i]+=g[i-1]+1;
        while(l<r&&calc(q[l],q[l+1])<=g[i])l++;
        int w=q[l];
        dp[i]=dp[w]+(long long)(g[i]-g[w]-L)*(g[i]-g[w]-L);
        //cerr<<dp[i]<<endl;
        while(l<r&&calc(q[r],i)<calc(q[r-1],q[r]))r--;
        q[++r]=i;
    }
    printf("%lld",dp[n]);
    return 0;
}