题解：P11411 兰奇的卡牌游戏

yingxilin · 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 等人对笔者的帮助。