ABC459

本次比赛赛时三道题，但是由于D题卡到结束也没想到自己的Yes No输出错了，就算自己过了四道题吧，悲…
刚打完比赛，顺便把题解写了

A

问题陈述

给你一个介于 $1$ 和 $10$ （含）之间的整数 $X$ 。
输出从字符串 HelloWorld 中只删除 $X$ -th 字符得到的字符串。

思路:

输出时跳过$S_{X-1}$即可。

Code

void sol()
{
    int X;
    string S="HelloWorld";
    cin>>X;
    for(int i=0;i<10;i++)
    {
        if(i+1==X)continue;
        cout<<S[i];
    }
}

B

问题陈述

给你一个由小写英文字母组成的 $N$ 字符串 $S_1, S_2, \ldots, S_N$ 。
定义 $N$ 数字 $C_1, C_2, \ldots, C_N$ 如下：

• 如果 $S_i$ 的第一个字符是 “a”、“b”、"c "之一，则 $C_i=$ 2
• 如果 $S_i$ 的第一个字符是 d、e、f 之一，则 $C_i=$ 3
• 如果 $S_i$ 的第一个字符是g、h、i中的一个，那么 $C_i=$ 是4
• 如果 $S_i$ 的第一个字符是j、k、l中的一个，那么 $C_i=$ 是5
• 如果 $S_i$ 的第一个字符是m, n, o中的一个，那么 $C_i=$ 是6
• 如果 $S_i$ 的第一个字符是p, q, r, s中的一个，那么 $C_i=$ 是7
• 如果 $S_i$ 的第一个字符是t、u、v中的一个，那么 $C_i=$ 就是 "t"。8`
• 如果 $S_i$ 的第一个字符是w、x、y、z中的一个，那么 $C_i=$ 是9

输出按此顺序连接 $C_1, C_2, \ldots, C_N$ 得到的字符串。

思路：

写一个映射函数，按题目输出即可。

Code

int F(char c)
{
    if(c>='a'&&c<='c')return 2;
    if(c>='d'&&c<='f')return 3;
    if(c>='g'&&c<='i')return 4;
    if(c>='j'&&c<='l')return 5;
    if(c>='m'&&c<='o')return 6;
    if(c>='p'&&c<='s')return 7;
    if(c>='t'&&c<='v')return 8;
    if(c>='w'&&c<='z')return 9;
}

void sol()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>S[i];
        cout<<F(S[i][0]);
    }
}

C

问题陈述

有 $N$ 个单元格，从左到右排成一行。起初，任何一个单元格中都没有放置图块。
你会得到 $Q$ 个查询，请按顺序处理它们。每个查询都是以下两种类型之一：

• 1 x:在左起第 $x$ 个单元格中放入 $1$ 个图块。然后，如果每个单元格都至少有 $1$ 个图块，则从每个单元格中移除 $1$ 个图块。
• 2 y:输出至少有 $y$ 个图块的单元格数量。

分析：

题意大概就是俄罗斯方块。

• 输入1和x时在x处堆一个方块，方块满一整排就会消除。
• 输入2和x时询问高度不小于x的列数。

思路：

用$a_i$记录第i列的高度，用$sum_j$数组统计高度为j的列数。每次当$sum_j==N$的时候，就说明高度为$j$的列数已经充满了，可以消掉，因此每次再留一个变量$mn$记录消除的次数。
当询问高度不小于x的列数时，由于我们消除掉了$mn$次，实际上就是问未消除时高度不小于$x+mn$的列数，因此输出$sum_{x+mn}$即可。

！！！注意$x+mn$是可能越界的，因此数组要开的大一些，本人因此WA了一发…

Code

void sol()
{
    cin>>N>>Q;
    while(Q--)
    {
        int n,x;
        cin>>n>>x;
        if(n==1)
        {
            a[x]++;
            sum[a[x]]++;
            if(sum[a[x]]>=N)mn++;
        }
        else
        {
            int tem=x+mn;
            cout<<sum[tem]<<'\n';
        }
    }
}

D

问题陈述

给你一个由小写英文字母组成的字符串 $S$ 。
请判断是否有可能重新排列 $S$ 中的字符，使相邻的两个字符都不相同。
给你 $T$ 个测试用例，请逐个求解。

思路：

我们统计出现最多次数的字符$c$，出现次数为$sum_c$，我们需要用其他字符作隔板，如果$sum_c$超过一半，我们就无法将所有的$c$隔开，输出No，具体来说就是：
设$S$长度为$L$，

• 当$sum_c>\lfloor \frac{L+1}{2}\rfloor$时，输出No。
• 否则，输出Yes。

对于Yes的情况，考虑如何输出。
两种思路，先按照出现次数逆序排序后。

1. 从出现最多的字符开始，先填入奇数位，再填入偶数位。
2. 将二元组$(sum_i,c)$加入大根堆中，每次取出两个，按照顺序填入后再放入大根堆中，不断进行。（赛时我采用的此方案）

复杂度$O(T\times N\log N)$

Code

void sol()
{
    string s;
    priority_queue<pair<int,char>>a;
    int maxc=0;
    cin>>s;
    for(int i='a';i<='z';i++)sum[i]=0;
    for(int i=0;i<s.size();i++)
    {
        sum[s[i]]++;
        if(sum[s[i]]>maxc)
        {
            maxc=sum[s[i]];
        }
    }
    for(int i='a';i<='z';i++)if(sum[i]>0)a.push(make_pair(sum[i],char(i)));
    if((s.size()+1)/2<maxc)
    {
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
    while(a.size())
    {
        int tsum=a.top().first;
        char tchar=a.top().second;
        a.pop();
        cout<<tchar;
        tsum--;
        if(a.empty())break;
        int xsum=a.top().first;
        char xchar=a.top().second;
        cout<<xchar;
        xsum--;
        a.pop();
        if(tsum>0)a.push(make_pair(tsum,tchar));
        if(xsum>0)a.push(make_pair(xsum,xchar));
    }
    cout<<'\n';
}

//方案1（部分）  替换对应的while循环即可
    int idx=0;
    while(a.size())
    {
        int tsum=a.top().first;
        int tchar=a.top().second;
        a.pop();
        while(idx<s.size()&&tsum>0)
        {
            s[idx]=tchar;
            tsum--;
            idx+=2;
            if(idx>=s.size())idx=1;
        }
    }
    cout<<s;

补题

E

对于本题，我一开始看到是树的处理，便有点儿畏缩了，但是实际上本题非常简单

问题陈述

有根树 $T$ ，具有 $N$ 个顶点，其中顶点编号为顶点 $1$ 、顶点 $2$ 、 $\ldots$ 、顶点 $N$ 。
顶点 $1$ 是 $T$ 的根，顶点 $i$ $(2 \leq i \leq N)$ 的（直接）父级是 $P_i$ 。

此外，顶点 $i$ $(1 \leq i \leq N)$ 有 $C_i$ 糖果。所有 $(C_1 + C_2 + \cdots + C_N)$ 糖果都可以相互区分。

高桥向 $N$ 松鼠发出指令。具体来说，他向第 $i$ -th 松鼠 $(1 \leq i \leq N)$ 发出了以下指令：

• 从以顶点 $i$ 为根的子树中选择并收集 $D_i$ 糖果。

不同的松鼠不能吃同样的糖果。
输出选择糖果的可能方式的数量（以 $998244353$ 为模）。

在这里，即使最终选择的糖果组是相同的，如果选择它们的松鼠不同，它们也会被算作不同的方式。
如果不可能所有松鼠都按照指示带回糖果，则输出 $0$ 。

分析：

由于松鼠需在$i$为根的子树中选择$D_i$个糖果，设$i$为根的子树中剩余$R_i$个糖果，则该松鼠有$\binom{R_i}{D_i}$，由于先处理根会影响子树的选择，我们需要从子树处理，而非从根开始排着处理。

思路：

通过dfs遍历子树，遍历到最深处时再处理答案，分为两种情况：

• 若$R_i<D_i$ ，则无法满足该松鼠，$ans=0$，终止dfs，输出即可。
• 若$R_i\ge D_i$ ，则$ans$乘以$\binom{R_i}{D_i}$，同时$R_i$减少$D_i$，去掉已经拿走的糖果。

对于$R$的处理，在dfs回溯时，将子节点的$R'$全加到$R$上即可。

Code

vector<int>P(maxn),C(maxn),D(maxn),R(maxn),S[maxn];
int fac[maxn],invfac[maxn],ans=1;

int qp(int x,int y)
{
    if(y==0)return 1;
    if(x==0||x==1)return x;
    int ans=1;
    while(y)
    {
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}

void inifac()
{
    fac[0]=1;
    for(int i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;
    invfac[maxn-1]=qp(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%mod;
}
int Co(int x,int y)
{
    if(y<0)return 0;
    int tem=1;
    for(int i=x-y+1;i<=x;i++)tem=i%mod*tem%mod;
    return tem*invfac[y]%mod;
}

void dfs(int x)
{
    for(auto i=0u;i<S[x].size();i++)
    {
        dfs(S[x][i]);
        R[x]+=R[S[x][i]];
    }
    R[x]+=C[x];
    if(R[x]<D[x])
    {
        ans=0;
        return;
    }
    ans=ans*Co(R[x],D[x])%mod;
    R[x]-=D[x];
}

void sol()
{
    int N;
    inifac();
    cin>>N;
    for(int i=2;i<=N;i++)cin>>P[i];
    for(int i=1;i<=N;i++)cin>>C[i];
    for(int i=1;i<=N;i++)cin>>D[i];
    for(int i=2;i<=N;i++)S[P[i]].push_back(i);
    dfs(1);
    cout<<ans<<'\n';
}

F

问题陈述

给你一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$ 。
你可以对 $A$ 执行以下操作 0 次或更多次：

• 选择一个有 $1 \le i \le N - 1$ 的整数 $i$ ，将 $A_i$ 减少 $1$ ，并将 $A_{i+1}$ 增加 $1$ 。

求使 $A$ 严格递增所需的最小运算次数。
可以证明答案小于 $2^{63}$ 。
给你 $T$ 个测试用例，请逐个求解。

分析/思路：

处理本题问题的核心是：将严格递增转化为非递减。
通过将$A_i$转化为$D_i=A_i-i$，可以同步转化以下条件：

1. $A_i<A_{i+1} \rightarrow D_i<=D_{i+1}$
2. $A_i-1,A_{i+1}+1 \rightarrow D_i-1,D_{i+1}+1$

因此我们就只需要让$D$更加“平均”即可。
那么怎么让$D$更加“平均”呢？
这里我采用归并思想：
假设我们遍历到$D_i$处，$i$前已经实现非递减（即尽可能平均），设前面的平均值为$x$。

• 如果$D_i>=x$，则满足条件，$D_i$不需要动。
• 如果$D_i<x$，则x需要从前面“借”一些过来，我们将前面那一部分与 $D_i$ 合并，那么这一部分的均值$x$会提升，而$D_i$会下降。

这样操作会将数据分解为若干块，并且块的均值满足非递减，那么我们只需要分配块内的数据，让块内也满足非递减，就能构造出最优的$D'$
显然，第二种情况是可能连续合并的，这也符合情况：如果每个数据的欠的太多，赤字太大，就需要往前面借非常多。

在我们构造出$D^{\prime}$后，我们就需要考虑怎么得出最终的$ans$了。
这里考虑$ans$是怎么一步一步累积起来的。
对于一次操作$D_i-1,D_{i+1}+1$，$ans$会增加1。
如果最后构造出 $D^{\prime}_i$ ，设 $X_i=D_i-D^{\prime}_i$ ，那么在第$i$进行了$X_i$次操作，将$D_i$的数据往后移动了一格，那么$ans$会增加 $X_i$ 。
但是实际上数据并不会只移动一格，而可能往后移动多次，假设从$D_i$处借1个大小，向后移动到 $D_{i+r}$ ，那么 $ans$ 会增加 $r$ ，而 $D$ 中体现的则是， $D_{i+1}$ 至 $D_{i+r-1}$ 不变， $D_i$ 减1， $D_{i+r}$ 加1，那么这个 $r$ 怎么来呢，我们取 $D$ 的前缀和为$P$，发现对于这一变化 $P_i$ 至 $P_{i+r-1}$均减小1，总共减小$r$，而$P_{i+r}$不变。
由此我们可以得出$ans=\sum\limits_{1}^{N}P_i-P'_{i}$。

由于$D$可能为负数，在构造块内数据的时候可能会出问题（由于C++的特性，余数可以为负）

复杂度$O(T\times N)$

Code

void sol()
{
    while(s.size())s.pop();
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
        d[i]=a[i]-i;
    }
    for(int i=1;i<=N;i++)
    {
        pair<int,int>t={1,d[i]};
        while(s.size())
        {
            auto tm=s.top();
            if((__int128)tm.second*t.first<=(__int128)t.second*tm.first)break;
            s.pop();
            t={t.first+tm.first,t.second+tm.second};
        }
        s.push(t);
    }
    int ci=N;
    while(s.size())
    {
        int k=s.top().first;
        int v=s.top().second/k;
        int r=s.top().second%k;
        if(r<0)
        {
            r+=k;
            v--;
        }
        s.pop();
        while(k--)d1[ci--]=v+bool(0<r--);
    }
    int ans=0,sum1=0,sum2=0;
    for(int i=1;i<=N;i++)
    {
        sum1+=d[i];
        sum2+=d1[i];
        ans+=sum1-sum2;
    }
    cout<<ans<<'\n';
}