自动搬运

查看原文

来自洛谷，原作者为

	yingxilin Qian·JX の joker

搬运于2025-08-24 23:07:07，当前版本为作者最后更新于2024-12-23 13:12:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P11411 兰奇的卡牌游戏

今天来讲一个超级缝合题目，所以要先讲一些前置。

前置知识——单调栈

[USACO06NOV] Bad Hair Day S

题目入口。

思路

单调栈板子，保证栈顶最大，从前往后遍历，栈顶比当前小的就删掉。并在每次入栈后将栈中剩余统计入答案。

code

#include<bits/stdc++.h>
using namespace std;
const int N=8e4+5;
int n;
int st[N];
int h[N];
int cur;
int ans;
int main(){
//    freopen("test.in","r",stdin);
//    freopen("test.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++){
        while(cur&&h[i]>=st[cur]) cur--;
        // if(cur==0||h[i]>st[cur]) st[++cur]=h[i];
        ans+=cur;
        st[++cur]=h[i];
    }
    cout<<ans<<endl;
    return 0;
}

OK，再看下一个前置知识。

前置知识——笛卡尔树

【模板】笛卡尔树

题目入口。

思路

以当前为根，从左往右走，如果能放在当前右子树，否则就一直往上找，直到找到当前的权值 $p_i$ 比当前点的权值 $p_i$ 大，则符合条件，放在其右子树。对于向上找时跳过的不符合条件的点，则将其放在当前接入点的左儿子。 那么，这样子的复杂度就是 $O(N^2)$。考虑将向上遍历直到找到当前的权值 $p_i$ 比当前点的权值 $p_i$ 大这一步骤优化，即找到先前序列中位于该位置之前的以一个大于该值的树。由此想到了单调栈。 所以做法大致是贪心和单调栈。

code

注意要输入解绑，不然会 TLE（实践出真知）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5;
int st[N];
int a[N];
int n;
int l[N],r[N];
void build(){
	int top=0,cur=0;
	for(int i=1;i<=n;i++){
		while(cur&&a[st[cur]]>a[i]) cur--;
		//cur:插在某个结点的右子树上
		if(cur) r[st[cur]]=i;
		//cur<top:插在某个结点的左子树上
		if(cur<top) l[i]=st[cur+1];
		st[++cur]=i;
		top=cur;
	}
}
signed main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build();
	int ans=0;
	for(int i=1;i<=n;i++) ans^=1LL*i*(l[i]+1);
	cout<<ans<<" ";
	ans=0;
	for(int i=1;i<=n;i++) ans^=1LL*i*(r[i]+1);
	cout<<ans<<endl;
	return 0;
}

前置：最近公共祖先（LCA）

【模板】最近公共祖先（LCA）

题目入口。

大致思路

就原本是两个点一步一步往上跳直到跳到同一点上。优化的方法是根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先，结束；否则，将两个节点同时上移，查询最近公共祖先（两个过程均使用倍增加速）。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,rt;
vector<int>g[N];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
int f[N][21];//f[i][j] 结点i往上跳2^j步的祖先结点
//f[i][j]=f[f[i][j-1]][j-1]
int d[N];//d[i] 结点i处于第几层
void dfs(int u,int fa)
{
	f[u][0]=fa;
	for(int i=0;i<(int)g[u].size();i++)
	{
		int v=g[u][i];
		if(v==fa) continue;
		d[v]=d[u]+1;
		dfs(v,u);
	}
}
int get_lca(int x,int y)
{
	//d[x]>d[y]
	if(d[x]<d[y]) swap(x,y);
	int cha=d[x]-d[y];
	for(int i=20;i>=0;i--)
		if(cha>>i&1) x=f[x][i];//x和y处于同一层
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	n=read();m=read();rt=read();
	for(int i=1;i<n;i++) 
	{
		int x=read(),y=read();
		g[x].push_back(y);g[y].push_back(x);
	}
	d[rt]=1;
	dfs(rt,rt);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	while(m--)
	{
		int x=read(),y=read();
		printf("%d\n",get_lca(x,y));
	}
	return 0;
}

最后看本题

思路

题目要求编号单调递增，可以满足小根堆的性质，权值可以满足左小右大，即二叉搜索树的限制。

所以所谓生成阶段就是生成了一颗笛卡尔树。且权值是第一关键字，编号是第二关键字。

最大得分就树的直径，可以枚举树的重心 $r$，判断每个节点于 $k/2$ 之间的关系并统计答案即可。

思路和官方题解比较相近，主要是实现方式不同。

code

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+50,M=1e5+5,mod=1e9+7;
const double pi=acos(-1);
int n,k,rt;
struct node
{
    int a,b;//编号，权值
}Qian[N];
bool cmp(node a,node b){return a.a<b.a;}
int r_son[N],l_son[N];
void build()
{
    stack<int>s;
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&Qian[s.top()].b>Qian[i].b)
        {
            l_son[i]=s.top();
            s.pop();
        }
        if(!s.empty())r_son[s.top()]=i;
        s.push(i);
    }
    while(!s.empty())
    {
        rt=s.top();
        s.pop();
    }
}
vector<int>g[N];
void rebuild()
{
    for(int i=1;i<=n;i++)
    {
        if(l_son[i])
        {
            g[i].push_back(l_son[i]);
            g[l_son[i]].push_back(i);
        }
        if(r_son[i])
        {
            g[i].push_back(r_son[i]);
            g[r_son[i]].push_back(i);
        }
    }
}
int f[2005][32];//倍增信息
int dep[N];//点深度
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;f[u][0]=fa;
    for(auto v:g[u])if(v!=fa) dfs(v,u);
}
void Wula()
{
    dfs(rt,0);
    for(int j=1;j<20;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);//x>=y,跳y
    int dis=dep[x]-dep[y];
    for(int i=0;i<11;i++)
        if(dis>>i&1) x=f[x][i];
    if(x==y) return x;
    for(int i=10;i>=0;i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int path(int x,int y)
{
    return max(0,dep[x]+dep[y]-2*dep[LCA(x,y)]);
}
int main()
{
	cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>Qian[i].a,Qian[i].b=i;
    sort(Qian+1,Qian+n+1,cmp);
    build();
    rebuild();
    Wula();
    int AC=1e9+7;
    if(k%2==0)
    {
        int sd=k/2;
        for(int i=1;i<=n;i++)
        {
            int cnt=0;
            for(int j=1;j<=n;j++)
            {
                int ad=path(i,j);
                cnt+=(ad>sd?1:0);
            }
            AC=min(AC,cnt);
        }
        cout<<AC<<endl;
    }
    else
    {
        int Ying=k/2;
        for(int i=1;i<=n;i++)
        {
            for(auto v:g[i])
            {
                int cnt=0;
                for(int j=1;j<=n;j++)
                {
                    int ad=path(i,j),ad2=path(v,j);
                    cnt+=(ad>Ying&&ad2>Ying?1:0);
                }
                AC=min(AC,cnt);
            }
        }
        cout<<AC<<endl;
    }
    return 0;
}

最后在此处鸣谢 FRZ，Win，QC 等人对笔者的帮助。