牛客练习赛115

https://ac.nowcoder.com/acm/contest/64819

A Mountain sequence

题意

定义序列 $a$ 为山峰序列当存在一个 $j$ 满足： $a_i\leq a_{i+1}(1\leq i\leq j-1),a_i\geq a_{i+1}(j\leq i\leq n-1)$。现给定一个长度为 $n$ 的序列，有多少种方法可以使重排后的序列为山峰序列。

数据范围：$1\leq n\leq 10^5$。

题解

最大值一定会放在中间。然后接着考虑次大值，假设它有 $x$ 个，那么一共有 $x+1$ 种方案：全放左边，$1$ 个放右边……全放右边。依此类推，可以得到答案就是除最大值以外的所有值出现次数加一的乘积。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=998244353;
map<int,int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        mp.clear();
        int n;cin>>n;
        int mx=1;
        for(int i=1;i<=n;i++)
        {
            int a;cin>>a;
            mp[a]++;
            mx=max(mx,a);
        }
        ll ans=1;
        for(auto i:mp) 
            if(i.first!=mx) ans=ans*(i.second+1)%p;
        cout<<ans<<'\n';
    }
    return 0;
}

C Find the maximum slope

题意

给定一个长度为 $n$ 的数组 $a$。并给出 $q$ 次操作：每次将一个区间内的数加上 $x$。定义一个数组的倾斜度为 $\max_{1\leq i,j\leq n,i\neq j}|\dfrac{a_i-a_j}{i-j}|$。求出最初和每次操作后的倾斜度。

数据范围：$2\leq n\leq 5\times 10^5,1\leq q\leq 10^5$。

题解

一个重要的观察是：倾斜度一定在相邻两点处取到。考虑两点中间的一个点，它与两点斜率至少有一个不小于两点连线的斜率（画个图就能发现）。所以，问题就成了求 $\max|a_i-a_{i-1}|$，差分数组然后multiset维护一下就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],d[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    multiset<int,greater<int>> s;
    for(int i=1;i<n;i++) d[i]=a[i+1]-a[i],s.insert(abs(d[i]));
    cout<<*s.begin()<<'\n';
    while(q--)
    {
        int l,r,x;cin>>l>>r>>x;
        if(l!=1)
        {
            s.erase(s.lower_bound(abs(d[l-1])));
            d[l-1]+=x;
            s.insert(abs(d[l-1]));
        }
        if(r!=n)
        {
            s.erase(s.lower_bound(abs(d[r])));
            d[r]-=x;
            s.insert(abs(d[r]));
        }
        cout<<*s.begin()<<'\n';
    }
    return 0;
}

D Genealogy in the trees

题意

给定一棵 $n$ 个结点的根为 $1$ 的树，树边为父结点向子结点的有向边。给出 $m$ 个点对 $(p_i,q_i)$，$q$ 次询问。每次询问给出点对 $(a,b)$，回答有多少个 $i$ 满足 $p_i$ 可以到达 $a$ 并且 $b$ 可以到达 $q_i$。

数据范围：$1\leq n,m,q\leq 3\times 10^5$。

题解

dfs。当遇到 $p_i$ 时，在 $q_i$ 位置加一，当遇到 $a_i$ 时，对 $b_i$ 求子树内贡献和，离开 $p_i$ 时，$q_i$ 位置减一。dfs序+树状数组就可以实现。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,q,c[N],qry[N];
int dfn,l[N],r[N];
vector<int> g[N],p[N];
vector<pair<int,int>> a[N];
int lowbit(int x) {return x&-x;}
void add(int x,int k)
{
    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int query(int l,int r) {return query(r)-query(l-1);}
void dfs0(int u,int fa)
{
    l[u]=++dfn;
    for(int v:g[u])
        if(v!=fa) dfs0(v,u);
    r[u]=dfn;
}
void dfs(int u,int fa)
{
    for(int i:p[u]) add(l[i],1);
    for(auto i:a[u]) qry[i.first]=query(l[i.second],r[i.second]);
    for(int v:g[u])
        if(v!=fa) dfs(v,u);
    for(int i:p[u]) add(l[i],-1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;cin>>x>>y;
        p[x].push_back(y);
    }
    for(int i=1;i<=q;i++)
    {
        int x,y;cin>>x>>y;
        a[x].push_back({i,y});
    }
    dfs0(1,0);
    dfs(1,0);
    for(int i=1;i<=q;i++) cout<<qry[i]<<'\n';
    return 0;
}

F Jewel maximizing magic

题意

给定一个 $n$ 个数的可重集合，每次取出两个数，并将两个数的异或放回集合。问 $n-1$ 次操作放回的所有数异或和最大为多少。

数据范围：$1\leq n\leq 3\times 10^5,0\leq a_i<1024$。

题解

该问题等价于 $n$ 个数里挑 $k$ 个数异或起来的最大值。$n$ 和 $k$ 有这样的关系：$(n\bmod 3)+(k\bmod 3)\equiv 1\pmod 3$。然后直接dp就行了。