杂题选做

· · 个人记录

都是思博题，全是思维没有技巧

P4006 小 Y 和二叉树

分析

首先可以贪心地确定第一个数，即度数 \leq 2 的编号最小的节点

假设这个节点为 u，钦定 u 为最左边的节点，分类讨论 u 的度数情况：

先讨论 u 的度数是 2，则与 u 相连的有一个右儿子 v，父亲 fa

建立一颗新的树，假设 u 为根，v 为 u 的左儿子，fa 为 u 的右儿子，那么假设将 u 子树的遍历顺序改为先序遍历，那么顺序即为 u-v-fa，发现与原来的树的中序遍历相同。

在原树上，v 是 u 的儿子，所以 v 的子树应该也是中序遍历，在新树上也一样，所以新树上 v 及其子树都采取中序遍历。

而 fa 是 u 的父亲，u 和 v 的遍历方式不会影响 fa 的中序遍历，可以直接将 fa 看成新的最左边的节点，即 u，这样就成为了一个子问题，可以递归解决。

再讨论度数为 1 的情况，假设在原树上 u 的相连点为 v，那么在新树上如果 v 成为了 u 的左儿子，那么原树上 v 就是 u 的右儿子；如果 v 成为了 u 的右儿子，那么原树上 v 就是 u 的父亲

总的来说，就是先将 u 提为根节点，然后按照如下规则 dfs：

  1. 如果当前节点是先序遍历，那么其左儿子为中序遍历，右儿子为先序遍历
  2. 如果当前节点是中序遍历，那么其左右儿子都是中序遍历

接下来再来考虑如何使字典序最小

先以 u 为根，树形 DP 求出子树内度数 \leq 2 的编号最小的点的编号，假设当前节点为 x，则有：

x 处为前序遍历

若新树上 x 有一个儿子 y，如果 dp_y<y，那么新树上 y 是 x 的左儿子；否则就是右儿子

若新树上 x 有两个儿子 y,z，如果 dp_y<dp_z，则新树上 y 是 x 的左儿子，z 是 x 的右儿子；否则 z 是 x 的左儿子，y 是 x 的右儿子

x 处为中序遍历

若新树上 x 有一个儿子 y，如果 dp_y<x，则 y 是 x 的左儿子，否则 y 是 x 的右儿子

若新树上 x 有两个儿子 y,z，如果 dp_y<dp_z，则新树上 y 是 x 的左儿子，z 是 x 的右儿子；否则 z 是 x 的左儿子，y 是 x 的右儿子

#include<bits/stdc++.h>
#define inf INT_MAX
using namespace std;
inline 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<<1)+(x<<3)+(c&15),c=getchar();
    return x*f;
}
int n,in[1000005],rt,f[1000005];
vector<int>e[1000005];
void dp(int u,int fa){
    f[u]=(in[u]<=2?u:inf);
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v^fa)dp(v,u),f[u]=min(f[u],f[v]);
    }
}
void dfs(int u,int fa,int op){//op=1:中序,op=0:先序 
    vector<int>son;
    for(int i=0;i<e[u].size();i++){
        if(e[u][i]^fa)son.push_back(e[u][i]);
    }
    if(!op){//先序 
        printf("%d ",u);
        if(son.size()==1){
            if(f[son[0]]<son[0])dfs(son[0],u,1);//中序遍历
            else dfs(son[0],u,0); 
        }else if(son.size()==2){
            if(f[son[0]]<f[son[1]]){
                dfs(son[0],u,1);
                dfs(son[1],u,0);
            }else{
                dfs(son[1],u,1);
                dfs(son[0],u,0);
            }
        }
    }else{//中序
        if(son.size()==0)printf("%d ",u);
        else if(son.size()==1){
            if(f[son[0]]<u){
                dfs(son[0],u,1);
                printf("%d ",u);
            }else{
                printf("%d ",u);
                dfs(son[0],u,1);
            }
        }else if(son.size()==2){
            if(f[son[0]]<f[son[1]]){
                dfs(son[0],u,1);
                printf("%d ",u);
                dfs(son[1],u,1);
            }else{
                dfs(son[1],u,1);
                printf("%d ",u);
                dfs(son[0],u,1);
            }
        } 
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        in[i]=read();
        for(int j=1,x;j<=in[i];j++){
            x=read();
            e[i].push_back(x);
        }
        if(!rt&&in[i]<=2)rt=i;
    }
    dp(rt,0),dfs(rt,0,0);
    puts(""); 
    return 0;
}

ARC066E Addition and Subtraction Hard

分析

贪心考虑如何加括号时最优

发现一个左括号在减号之后才有意义，而在当前括号后的第一个左括号之前的数都是产生负贡献的，第二个括号以后的数都能产生正贡献：括号后所有数取反，即要让括号中的总和最小，发现括号中还有加号的情况，只需要跟上一个减号括在一起变成负数即可

故枚举负号位置，即第一个大括号的位置，计算贡献即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline 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<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,num[100005],sum[100005],ne[100005],sum_po[100005],cnt,res;
char c[100005];
signed main(){
    cin>>n;
    c[0]='+';
    for(int i=1;i<=n;i++){
        cin>>num[i];
        if(i^n)cin>>c[i];
        if(c[i-1]=='+')sum[i]=sum[i-1]+num[i];//没有更改符号时的前缀和 
        else ne[++cnt]=i,sum[i]=sum[i-1]-num[i];
        sum_po[i]=sum_po[i-1]+num[i];//全部取正数的前缀和 
    }
    res=sum[n],ne[cnt+1]=n;//ne[]记录负号位置 
    for(int i=1;i<=cnt;i++){//枚举负号位置 
        int ans1=sum[ne[i]];//当前负号之前的所有数之和 
        int ans2=sum[ne[i+1]-1]-sum[ne[i]];//当前负号到下一个负号之间的和 
        int ans3=sum_po[n]-sum_po[ne[i+1]-1];//下一个负号后均产生正贡献 
        res=max(res,ans1-ans2+ans3);
    }
    cout<<res<<endl;
    return 0;
}

P3802 小魔女帕琪

分析

好难，个人认为难度高于绿

首先先考虑施法 7 次就能释放一次七重奏的情况：

假设第一个数已定，设为 a_1，接下来的数为 a_2,a_3,...,a_7，宝石总和为 n

则第一个数已定的情况下，成功释放七重奏的概率为：\large \frac{a_1}{n}\times \frac{a_2}{n-1}\times \frac{a_3}{n-2}\times ... \times \frac{a_7}{n-6}

这种排列有 7! 个，故总概率为 \large 7!\times \frac{a_1}{n}\times \frac{a_2}{n-1}\times \frac{a_3}{n-2}\times ... \times \frac{a_7}{n-6}

再考虑施法 8 次能释放一次七重奏的情况：

由于魔法发动互不影响，故概率为：

P=\frac{a_1}{n}\times(7!\times \frac{a_1-1}{n-1}\times \frac{a_2}{n-2}\times \frac{a_3}{n-3}\times ... \times \frac{a_7}{n-7})+\frac{a_2}{n}\times (7!\times \frac{a_1}{n-1}\times \frac{a_2-1}{n-2}\times \frac{a_3}{n-3}\times ... \times \frac{a_7}{n-7})\times ...\times \frac{a_7}{n}\times (7!\times \frac{a_1}{n-1}\times \frac{a_2}{n-2}\times \frac{a_3}{n-3}\times ... \times \frac{a_7-1}{n-7})

设 R=\prod a_i，先提取公因式，有：

P=\frac{7!\times(a_1-1+a_2-1+...+a_7-1)\times (a_1\times a_2\times ... \times a_7)}{n(n-1)(n-2)...(n-7)} \because a_1+a_2+...+a_7-1-1-1-1-1-1-1=n-7 \therefore P=7!\times \frac{a_1}{n}\times \frac{a_2}{n-1}\times \frac{a_3}{n-2}\times ... \times \frac{a_7}{n-6}

发现与施法 7 次就能释放一次七重奏的概率相等，于是可以得出：

在第任意次触发一个七重奏的概率与在第 7 次就触发一个七重奏的概率相等

而能触发七重奏的最多次数应该为 n-6

所以答案为： (n-6)\times R/(n\times (n-1)\times (n-2)\times ...\times (n-7))

#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;
inline 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<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int a[10],sum;
double ans=1;
int main(){
    for(int i=1;i<=7;i++)a[i]=read(),sum+=a[i];
    if(sum<7)puts("0.000");
    else{
        for(int i=1;i<=7;i++)ans=ans*1.0*a[i]/(sum-i+1);
        printf("%.3lf\n",ans*1*2*3*4*5*6*7*(sum-6));
    }
    return 0;
}

AGC008D K-th K

分析

对于第 i 个数第 i 次出现在 X_i 的位置，包括了两个限制：

  1. 1$ 至 $X_i-1$ 中有 $i-1$ 个 $i
  2. X_i+1$ 至 $n^2$ 中有 $n-i$ 个 $i

故有一个构造方法为：每次贪心选 X_i 最小的一个 i，在当前最前面 i-1 个空位填上 i ；再贪心选 X_i 最大的一个 i，在当前最后面 n-i 个空位中填上 i；若无法满足则不合法

#include<bits/stdc++.h>
using namespace std;
inline 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<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,pos[505],vis[505*505],num[505*505],ans[505*505];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        pos[i]=read();
        if(vis[pos[i]]){puts("No");return 0;}
        vis[i]=1,num[pos[i]]=ans[pos[i]]=i;
    }
    int p=1;
    for(int i=1;i<=n*n;i++){
        if(num[i]){
            for(int j=1;j<=num[i]-1;j++){
                while(ans[p])++p;
                if(p>i){puts("No");return 0;}
                ans[p]=ans[i];
            }
        }
    }
    p=n*n;
    for(int i=n*n;i;i--){
        if(num[i]){
            for(int j=1;j<=n-num[i];j++){
                while(ans[p])--p;
                if(i>p){puts("No");return 0;}
                ans[p]=ans[i];
            }
        }
    }
    puts("Yes");
    for(int i=1;i<=n*n;i++)printf("%d ",ans[i]);
    puts("");
    return 0;
}

AGC006D Median Pyramid Hard

分析

由于转移的条件是中位数，所以只关系数之间的大小关系

很典地将序列变成 01 串，大于中位数的是 1，否则是 0

手推发现两个相同的相邻数会一起往上走

所以只需要找到离中间最近的一组相邻一样的两个数，就可以得到最上面是什么数

由于序列长度为奇数，故不存在两组距离相同的相邻数

注意需要特判没有相邻相同数的情况

#include<bits/stdc++.h>
using namespace std;
inline 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<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,a[200005];
inline bool check(const int &k){
    for(int i=0;i<n-1;i++){
        if((a[n+i]<=k&&a[n+i+1]<=k)||(a[n-i]<=k&&a[n-i-1]<=k))return 1;
        else if((a[n+i]>k&&a[n+i+1]>k)||(a[n-i]>k&&a[n-i-1]>k))return 0;
    }
    return a[1]<=k;
}
int main(){
    n=read();
    for(int i=1;i<=2*n-1;i++)a[i]=read();
    int l=1,r=2*n-1;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}