解题报告 P2822 组合数问题

题目内容

P2822

大意:给定 tkt 次给出 nm,询问所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right ) 有多少对 (i,j) 满足 k|\binom{i}{j}

解题思路

因为数据范围中 n,m\leq 2000,所以不能直接把组合数存储起来,而注意到一个数据点中 k 是固定的,因此可以定义 f_{i,j} 为对于所有的 x\in[0,i]y\in[0,\min(j,x)] 中满足 k|\binom x y\binom x y 的个数。

可以使用递推法预处理所有的 \binom i j\bmod k,然后使用二维前缀和来处理 f_{i,j},每次 O(1) 回答询问。

c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];//下面解释
    }

上面是处理 f 的部分。每次求出组合数直接取模方便判断是否能被 k 整除。二维前缀和的递推都很容易看懂,但是对于最后的 f[i][i+1]=f[i][i]; 的理解是:由于每次 f[i][j] 都要加上 f[i-1][j],而不处理最后的 f[i][i+1] 的话会造成处理下一排时 f[i-1][j] 为 0,所以要进行这样的处理。

还有就是数据中可能有 n,这时候要进行特判

完整代码:

#include <cstdio>
#include <cctype>

//快读

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];
    }
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m>n?n:m]);
    }
    return 0;
}

当然还有另一种方法就不需要特判,如下:

#include <cstdio>
#include <cctype>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k;
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=2000;j++)
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(i>=j && c[i][j]==0);
    //这里和上面一样,但是一定要注意判断这里的c[i][j]有没有意义,否则会抱灵
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m]);
    }
    return 0;
}

解题报告 P2858 [USACO06FEB]Treats for the Cows G/S

题目内容

P2858

大意:n 个元素的序列,每次可以从头或者尾去掉一个元素,获得的收益是这个元素的权值乘上该次去除的次数,求最大收益。

解题思路

不难发现,这题由于去除元素的顺序对最终的结果是有影响的,所以不能直接贪心,考虑使用 dp。

这题一眼看上去像是一个区间 dp,那我们先开始寻找如何定义状态。考虑我们已经去除了 [i,j] 以外的所有元素,可以发现外面元素去除的顺序已经不重要了,满足无后效性,说明可以这样定义状态:f_{i,j} 表示还剩 [i,j] 时可以达到的最大收益。

转移:当我们达到 [i,j] 时,要么是去掉了第 i-1 个元素,要么是去掉了第 j+1 个元素,设当前的天数为 d,第 i 个元素为 v_i,则有状态转移方程

f_{i,j}=\max(f_{i-1,j}+dv_{i-1},f_{i,j+1}+dv_{j+1})

那么枚举区间长度的时候就必须从大到小枚举,为了方便可以在枚举区间长度的同时枚举天数

最后统计答案的时候答案为 ans=\displaystyle\max_{i=1}^n\lbrace f_{i,i}+nv_i\rbrace,输出即可。

#include <cstdio>
#include <cctype>

//快读

//max

const int maxn=2005;
int v[maxn],f[maxn][maxn];

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int len=n-1,day=1;len>=1;len--,day++)//从n-1开始枚举区间长度
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            f[i][j]=max(f[i][j+1]+v[j+1]*day,f[i-1][j]+v[i-1]*day);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][i]+n*v[i]);
    printf("%d\n",ans);
    return 0;
}

当然,这题正序枚举区间长度也是可以的,只是倒序的更好理解我太菜不会

解题报告 P1119 灾后重建

题目内容

P1119

大意:给定编号从 1n-1 的村庄,每个村庄都被一定程度上损毁,而公路正常,在 t_i 时间前 i 号村庄不能通过,询问在 t 时间时 x 号和 y 号村庄能不能通车,如果能,最短路径是多少。

解题思路

这题思路真的很妙,让我们对 Floyd 的本质有了更深的理解,至少本蒟蒻是这样觉得的。

回归 Floyd 算法的本质:

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

实际上,Floyd 是通过枚举中转点 k 来求得每个点之间的最短路,本质上是一种 dp。

然后,注意到本题中,每个村庄的恢复时间是递增的,且给出的询问的时间也是递增的。而题目让我们求任意两点的最短路,那么也可以抽象成 Floyd。具体的方法就是,由于时间是递增的,所以每到一个村庄恢复的时间点我们就可以让这个村庄成为那个可以用来中转的 k 来更新这一时间的所有最短路。

在这题中,就是使用时间戳,保证回答被询问的时间前信息被更新过即可。注意村庄编号从 0 开始

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

const int maxn=205;
int n,m,t[maxn],f[maxn][maxn],q;

inline void floyd(int k)//更新信息的,通过给定可以中转的中转点来进行更新
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    return;
}

int main()
{
    n=read(),m=read();
    memset(f,0x3f,sizeof(f));//初始赋极大值 0x3f 不至于加起来爆int
    for(int i=0;i<n;i++)
        t[i]=read(),f[i][i]=0;
    while(m--)
    {
        int x=read(),y=read(),w=read();
        f[x][y]=f[y][x]=w;//双向边
    }
    q=read();
    int now=0;
    while(q--)
    {
        int x=read(),y=read(),s=read();
        while(t[now]<=s && now<n)//将这一时间前的所有时间信息更新
            floyd(now++);
        if(t[x]>s || t[y]>s || f[x][y]>=0x3f3f3f3f)//如果这一时间时村庄未修复,或者无路线
            printf("-1\n");//输出 -1
        else
            printf("%d\n",f[x][y]);//否则输出最短路即可
    }
    return 0;
}

解题报告 P2901 [USACO08MAR]Cow Jogging G

题目内容

P2901

给定一有向带权图,求从 n 到 1 的前 k 短路的长度

解题思路

求 k 短路的一个常用的方法是使用 A*,怎么求呢?

首先,预处理出所有点到 1 的最短距离(使用反向图跑最短路),然后从 n 开始进行广搜,只不过队列改为优先队列,估价方式为 f+dis[now] 小的先出队,其中 f 为已经走过的路,dis[now]now 到 1 的最短距离,这样子进行估价可以使估的价一定小于等于实际代价。然后 A* 会根据估价从小到大依次进行扩展,最先进入到 1 号的就是最短路,随后次短路,第三短路。。。会依次进入到 1 号点,每次输出走过路径长即可。

#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <utility>
#include <cstring>

typedef long long ll;
using namespace std;

const int maxn=1e3+5;

struct node
{
    ll pos,f;
    node(){}
    node(int _p,int _f)
    {
        pos=_p;
        f=_f;
    }
};

struct edge
{
    ll from,to,dist;
    edge(){}
    edge(ll u,ll v,ll w)
    {
        from=u;
        to=v;
        dist=w;
    }
};

//快读省略

vector<edge> g1[maxn],g2[maxn];//g1存正向图,g2存反向图
ll dis[maxn],n,m,k;
bool vis[maxn];

bool operator<(const node &_a,const node &_b)
{
    return _a.f+dis[_a.pos]>_b.f+dis[_b.pos];
}

void dijsktra()//反向跑dij获取每个点的距离
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    memset(dis,0x3f,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g2[now])
            {
                if(dis[e.to]>dis[now]+e.dist)
                {
                    dis[e.to]=dis[now]+e.dist;
                    q.push(make_pair(dis[e.to],e.to));
                }
            }
        }
    }
    return;
}

void astar()//开始A*
{
    priority_queue<node> q;
    q.push(node(n,0));
    while(!q.empty())
    {
        ll now=q.top().pos,f=q.top().f;
        q.pop();
        if(now==1)//如果到终点了
        {
            printf("%lld\n",f);//直接输出
            if(!(--k))//如果已经求完前k短路,结束
                return;
        }
        else
            for(auto i:g1[now])//然后就是扩展
                q.push(node(i.to,i.dist+f));
    }
    while(k--)//如果还有没搞完的
        printf("-1\n");
    return;
}

inline void ins(ll u,ll v,ll w)
{
    g1[u].push_back(edge(u,v,w));
    g2[v].push_back(edge(v,u,w));
    return;
}

int main()
{
    n=read(),m=read(),k=read();
    ll u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        ins(u,v,w);
    }
    dijsktra();
    astar();
    return 0;
}

解题报告 P4198 楼房重建

题目内容

P4198

大意:维护一串序列,单点修改,在线查询 LIS

解题思路

首先这题要注意精度问题,有可能会出现玄学的精度错误

分析题意:考虑看到的楼房最高点 (i,H_i),不难发现能看到的楼房的最高点的斜率都是递增的,即 k_i=i/H_i 满足单调递增(这应该很好想)。发现大区间的信息可以由小区间合并而来,可以使用线段树。这里的单点修改很简单,主要的难点在于如何在 pushup 时合并子区间的信息。

l_k 维护线段树下标为 k 代表的区间中能被看见的楼房的个数(就是单纯只考虑这个区间),m_k 维护 k 区间中楼房的最大斜率。

考虑我们正在处理一个区间,线段树对应的下标为 k ,已经递归处理完他的左半边 L 和右半边 R,现在在进行合并。m_k=\max(m_L,m_R),这个是非常好想的,k 区间的最大斜率就是左右两半边取 max。问题就是 l_k 怎么合并,他不能单纯的等于 l_L+l_R,因为可能会出现右区间中的楼房被左区间的楼房挡住的情况,因此不能直接加起来。

很明显,我们需要在 R 区间中寻找有多少楼房不会被左边挡住。令 f(mk,k) 为在区间 k 中第一个不被 mk 斜率挡住的楼房及此楼房后面看得到的楼房的总数。返回之前的合并过程,有 l_k=l_L+f(m_L,R),因为 L 区间的贡献是无论如何都会产生的。故要在 R 中查找以第一个不会被左区间挡到的楼房开始的能看见的最多的楼房数。

现在考虑正在处理 f ,进入了 R 区间,而 R 区间又由两个小的区间 R_1R_2 构成。以下分三种情况:

  • 如果 m_R,说明左区间会把右区间全部挡完,返回 0
  • 如果 R 区间长度为 1,则看这栋楼是否会被挡,如果不会,返回 1,反之返回 0
  • 如果 m_{R_1},即右区间的左子区间会被挡完,那么就不管左区间了,递归查询右区间即 f(mk,R_2)
  • 如果 m_{R_1} > mk,即左子区间不会被挡完,那么显然右子区间产生的贡献即为 m_{R}-m_{R_2},即右区间的总个数(是已经处理完了的)减去左区间的贡献。然后还要递归查询左区间,因为不知道挡了多少,即 f(mk,R_1)

上述 pushup 过程的核心代码如下(f2 为上文的 mf1 为上文的 l):

int pushup(double mk,int i,int j,int k)
{
    if(f2[k]<=mk)//挡完
        return 0;
    if(a[i]>mk)//如果第一栋楼都能被看见
        return f1[k];//说明可以直接返回这个区间计算过的答案
    if(i==j)//区间长度为1的情况
        return f2[k]>mk;
    if(f2[L]<=mk)//如果左区间挡完
        return pushup(mk,M+1,j,R);//递归查询右区间
    return pushup(mk,i,M,L)+f1[k]-f1[L];//否则递归查询左区间再加上右区间的贡献
}

void change(int i,int j,int x,double d,int k)
{
    // balabala
    f2[k]=max(f2[L],f2[R]);
    f1[k]=f1[L]+pushup(f2[L],M+1,j,R);//左的全部贡献加上右还没被挡完的部分
    return;
}

了解了以上要点之后,不难发现每一次 pushup 的操作都为 O(\log n),故总复杂度为 O(m\log^2n)

代码:

#include <cstdio>
#include <cctype>
#include <algorithm>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)

using std::max;

const int maxn=1e5+5;

int f1[maxn<<2],n,m;
double f2[maxn<<2];//维护最大斜率的线段树
double a[maxn];//存储每栋楼的斜率

//快读省略

int pushup(double mk,int i,int j,int k)
{
    if(f2[k]<=mk)
        return 0;
    if(a[i]>mk)
        return f1[k];
    if(i==j)
        return f2[k]>mk;
    if(f2[L]<=mk)
        return pushup(mk,M+1,j,R);
    return pushup(mk,i,M,L)+f1[k]-f1[L];
}


void modify(int i,int j,int x,double d,int k)
{
    if(i==j&&i==x)
    {
        f1[k]=1;
        f2[k]=d;
        return;
    }
    if(x<=M)
        modify(i,M,x,d,L);
    if(x>M)
        modify(M+1,j,x,d,R);
    f2[k]=max(f2[L],f2[R]);
    f1[k]=f1[L]+pushup(f2[L],M+1,j,R);
    return;
}

int main()
{
    n=read(),m=read();
    int x,y;
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read();
        a[x]=(double)y/(double)x;
        modify(1,n,x,a[x],1);
        printf("%d\n",f1[1]);
    }
    return 0;
}

解题报告 P2782 友好城市

题目内容

一条河,两岸有 n 对友好城市,分别给出坐标,友好城市之间需要开通航线,然而航线不可以两两交叉,求最多能开行的航线条数。

解题思路

首先将每对友好城市按照北岸坐标从小到大排序,不难发现,设已开通的航线的南北坐标分别为 S_1N_1,则如果另一条从 N_2S_2 的航线发生冲突,则会有 N_1>N_2S_1。所以我们如果将所有北岸坐标排好序之后,要使所有的航线不冲突,就让要选出来的南岸的城市坐标满足单调上升,这样才会不交叉。

所以排好序之后找南岸坐标的最长上升子序列就可以了。由于题目里面 n\le2\times 10^5,所以 O(n^2) 的算法无法通过,需要使用 O(n\log n)

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using std::sort;
using std::lower_bound;

struct city
{
    int n,s;
    bool operator<(const city &b)//按照北岸排序
    {
        return n<b.n;
    }
}a[(int)2e5+5];


int f[(int)2e5+5];

//快读省略

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        a[i].n=read(),
        a[i].s=read();
    sort(a+1,a+n+1);//按照北岸排序
    memset(f,0x7f,sizeof(f));
    int len=1;
    f[1]=a[1].s;
    for(int i=2;i<=n;i++)//找 LIS
    {
        if(a[i].s>=f[len])
            f[++len]=a[i].s;
        else
        {
            int p=lower_bound(f+1,f+len+1,a[i].s)-f;
            f[p]=a[i].s;
        }
    }
    printf("%d\n",len);
    return 0;
}

解题报告 P1396 营救

题目内容

一张带权图,求从 st 经过的边中的最大边权的最小值

解题思路

要使最大边权最小,说明是瓶颈生成树,而最小生成树即为瓶颈生成树。故跑一遍 Kruskal,由于 Kruskal 是从小到大枚举边,因此如果当加了某条边后 st 联通了,那么这条边的边权就是最终要的结果了。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

//快读省略

//并查集省略

//边的结构体省略

bool cmp(edge a,edge b)
{
    return a.dist<b.dist;
}

vector<edge> q;
int n,m,s,t;

int kruskal()
{
    sort(q.begin(),q.end(),cmp);
    for(auto &e:q)
    {
        int from=e.from,to=e.to,dist=e.dist;
        if(!u.query(from,to))
            u.uni(from,to);
        if(u.query(s,t))//如果刚好加了这条边之后s和t联通了
            return dist;//说明当前边一定就是最大的了
    }
}

int main()
{
    n=read(),m=read(),s=read(),t=read();
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        q.push_back(edge(u,v,w));
    }
    printf("%d\n",kruskal());
    return 0;
}

解题报告 P3574 [POI2014]FAR-FarmCraft

题目内容

P3574

大意:村庄是一棵树,住在 1 号的管理要给每个房子送电脑,通过每个房子之间的道路需要 1 分钟,每个村民需要不同的时间安装电脑,而当管理把电脑送到村民后,村民会立即开始安装,最后管理会回到自己家给自己装电脑,求从管理出发到最后一个人装好电脑花费的时间。

解题思路

可以考虑每一个子树需要安装的最短时间。设住在 i 处的村民需要 c_i 的时间安装电脑, f_i 表示以 i 为根的子树全部安装好需要的最短时间,g_i 表示开车遍历以 i 为根的子树需要的最短时间,则有如下的方程:

f_i=\max(c_i,f_j+g_i+1)\
g_i\leftarrow g_i+g_j+2

其中 ji 的子节点,且 g_i 是动态更新的,就是遍历 j 之前的所有子树需要花的总时间。意思就是,对于一个 i 为根的子树,显然,第一次到 i 点的时候就让这里的村民开始装电脑得到的肯定更优,用这个时间与后面遍历下面节点的时间相比,总花费的时间是两者中间取最大的。而 f_j+g_i+1 的意义为,遍历过 j 节点之前的所有子节点需要的时间和 g_i 加上 j 节点需要的最短时间 f_j,至于 +1 就是从 i 节点走到 j 节点的花费。

而至于为什么是 +1 而不是 +2,是因为 \forall i:f_i-g_i\ge1,即等待的时间必然大于等于 1,所以只需要考虑从 i 进入 j 的时间,即为 1,而返回来的 1 的时间是被 f_j 覆盖掉的

不难发现,遍历的顺序会影响最终的结果,所以考虑贪心:可以发现,f_i-g_i 这段时间就是拿来等待的,做过接水问题的都知道要先处理等待时间大的,于是在转移前将子节点按照 f_i-g_i 排序即可。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn=500010;
int n,c[maxn],f[maxn],g[maxn],tmp[maxn];
vector<int> G[maxn];

inline void ins(int a,int b)
{
    G[a].push_back(b);
    G[b].push_back(a);
    return;
}

inline bool cmp(int x,int y)
{
    return f[x]-g[x] > f[y]-g[y];
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(now!=1)//管理员的电脑最后装
        f[now]=c[now];
    int cnt=0;
    for(auto i:G[now])
        if(i!=fa)
            dfs(i,now);
    //一定要先遍历后记录儿子节点,不然会被下面的节点覆盖掉
    for(auto i:G[now])
        if(i!=fa)
            tmp[++cnt]=i;
    sort(tmp+1,tmp+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        f[now]=max(f[now],f[tmp[i]]+g[now]+1),
        g[now]+=g[tmp[i]]+2;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    int a,b;
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        ins(a,b);
    }
    dfs(1,0);
    printf("%d\n",max(c[1]+g[1],f[1]));//在最后也要注意
    return 0;
}

解题报告 P6082 [JSOI2015]salesman

题目内容

P6082

大意:给定一棵 n 个点的树,有点权,从 1 号点开始一次旅行,最后回到 1 号点。每到达一个点,就能获得等于该点点权的收益。每个点都有进入该点的次数限制,且每个点的收益只获得一次。求最大收益以及方案是否唯一。

解题思路

不难发现,这道题满足最优子结构,一棵子树的答案可由这棵子树的子树合并而来。

注意到进入限制这个性质,到达这个点进入了一次,去到每一棵子树再回来又是进入这个点一次,所以实际上我们只能访问这个点的 限制次数减一 棵子树。

而为了保证最优,需要使用贪心思想,当将一个节点的所有子树的信息处理完之后,将其从大到小排序,取前面的限制次数减一个并加起来(当然如果加到负数就肯定不加了)。

至于解的唯一性,注意到如果一个子树下的某个子树的解不唯一,那么这个子树的解肯定也不唯一。以及如果对于他的一棵子树,这个子树的答案为 0,则走与不走这个子树的效果是相同的,答案就会不唯一。还有,如果最后一个选的子树 a 的答案与下一个待选子树 b 的答案相同,说明可以选 a 也可以选 b,效果都是一样的,也会产生多解。

代码如下:

#include <utility>
#include <cstdio>
#include <cctype>
#include <queue>

using std::priority_queue;
using std::make_pair;
using std::vector;
using std::pair;

const int maxn=1e5+5;
int n,money[maxn],stop[maxn];
int f[maxn][2];

vector<int> g[maxn];

inline void ins(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
    return;
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(g[now].size()==1)//这是判断是否为叶子节点的
    {
        f[now][0]=money[now];
        return;
    }
    priority_queue<pair<int,int> > q;//排序用
    for(int i=0;i<g[now].size();i++)//访问下面的节点
    {
        if(g[now][i]!=fa)
        {
            dfs(g[now][i],now);//继续递归
            q.push(make_pair(f[g[now][i]][0],g[now][i]));//并且加入队列
        }
    }
    int lastChosen;
    for(int i=1; (!q.empty()) && (now==1 ? 1 : i<stop[now]);i++)
    {
        int to=q.top().second,val=q.top().first;
        if(val<0)//如果现在这棵子树已经小于 0 了,说明会产生负贡献,直接舍弃
            break;
        if(val==0)//有多解
            f[now][1]=1;
        f[now][0] += val;
        lastChosen=val;
        f[now][1] |= f[to][1];//下面的答案有多解的话也会产生多解
        q.pop();
    }
    f[now][0]+=money[now];
    if(q.size() && q.top().first==lastChosen)//如果下一个备选答案与上一个的相同,则有多解
        f[now][1]=1;
    return;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
        money[i+1]=read();
    for(int i=1;i<n;i++)
        stop[i+1]=read();
    int from,to;
    for(int i=1;i<n;i++)
    {
        from=read(),to=read();
        ins(from,to);
    }
    dfs(1,0);
    printf("%d\n",f[1][0]);
    if(f[1][1])
        printf("solution is not unique\n");
    else
        printf("solution is unique\n");
    return 0;
}

解题报告 P4231 三步必杀

题目内容

P4231

大意:区间加等差,最后询问整个序列的异或和以及最大值

解题思路

区间加等差其实就是差分序列区间加常数,两端特殊修改。

但是注意到这里的数据范围是 1e7,线段树卡不过去,而且询问是在最后询问的,因此可以直接上二阶差分。

模拟一段区间加等差的过程:给 [3,6] 加上首项为 3,末项为 9 的等差数列:

0  0  0  0  0  0  0  0  这是原数列
0  0  3  5  7  9  0  0  这是加了等差数列之后的
0  0  3  2  2  2 -9  0  这是一阶差分
0  0  3 -1  0  0  -11 9 这是二阶差分

可见,我们如果要进行区间加等差的操作的话,需要在二阶差分上动 4 个点,分别是

d2[l]+=s;
d2[l+1]+=d-s;
d2[r+1]-=e+d;
d2[r+2]+=e;

其中 d 为公差,s 为首项,e 为末项。错误常发生于以为 d2[l+1]d2[r+1] 是不用修改的,但是实际上由于 s 可能不等于 d,故二阶差分的 l+1 处要进行处理。

最后,两次前缀和就可以还原出原序列,在还原的过程中可以顺便进行最大值查询和异或和操作。

总的复杂度 O(n+m),可以卡过去,如果是线段树的话是 O(m\log n+n),会被卡掉

要开 long long

#include <cstdio>
#include <cctype>
typedef long long ll;

const int maxn=1e7+5;
ll a[maxn],d1[maxn],d2[maxn];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    int n=read(),m=read();
    ll l,r,s,e;
    while(m--)
    {
        l=read(),r=read(),s=read(),e=read();
        int d=(e-s)/(r-l);//得到公差
        d2[l]+=s;
        d2[l+1]+=d-s;
        d2[r+1]-=e+d;
        d2[r+2]+=e;
    }
    ll maxans=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        d1[i]=d1[i-1]+d2[i],a[i]=a[i-1]+d1[i];//还原
        maxans=maxans<a[i]?a[i]:maxans;
        ans^=a[i];
    }
    printf("%lld %lld\n",ans,maxans);
    return 0;
}