AcWing周赛42

写在前面

排名：23/2792
过题数：3/3 AK!

罚时	A(1407)	B(492)	C(205)
0:47:42	0:02:28	0:12:30	0:32:44

这段时间很多比赛，到今天我才写这个题解/反思，主要是被疫情这个..心态搞炸了吧，长沙发现了一例，那个人是深圳人，带了家里面3个，来长沙扫墓...我估计就是怕疫情严重，跑出深圳的..导致了什么呢？我回不了校，本来能周末回的，现在需要+14days，这不，她孙女又得了，我又得往后推几天...我真是心态爆炸...
好吧，讲了这么多，我还是来写一下题解吧。这一次再创新高，不过还是差一点进前20，能够被y总点名，我上一次是rk26，这一次rk23，手速还是慢了点，还有些不敢赌...

A.最小值（模拟）

题意

题目链接：AcWing 4311. 最小值 - AcWing
模拟就好，简单，但是我做了2分多钟...不应该

思路

就模拟就好，注意cout怎么输出小数:cout<<fixed<<setprecision(6)<<ans;

代码

inline void Case_Test()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>a>>b;
        t=a/b;
        ans=Min(ans,t);
    }
    ans=ans*m;
    cout<<fixed<<setprecision(6)<<ans;
}

B.出现次数（前缀和）

题意

题目链接：AcWing 4312. 出现次数 - AcWing
给出你长度为 $n$ 字符串 $s$ ，还有字符串 $st$ ，然后给出 $q$ 次询问，每次询问有 $l,r(1\leq l\leq r\leq n)$ 两个整数代表问字符串 $s$ 位置 $[l,r]$ 里面， $st$ 出现了多少次？

思路

这一看，暴力肯定是不行的，肯定会tle，所以我们换种方法。因为是离线的，只有询问，那么我们就直接预处理然后进行操作——前缀和。为什么想到前缀和？因为给出你 $[l,r]$ 查询的话，就直接能想到a[r]-a[l-1]
但是这里要注意，因为我们的 $st$ 是有长度的，所以我们可以规定只要有 $st$ ，那么我们将 $st$ 的起始位置标记为1，那么我说的长度怎么办呢？那么对于 $[l,r]$ 我们只看 $[l,r-m+1]$ 即可， $m$ 是 $st$ 的长度。
最后只需要输出a[r-m+1]-a[l-1]就好，但是要注意一下你这个询问区间的长度是否小于m。
这个题想了不少时间，速度太慢了...

代码

inline void Case_Test()
{
    cin>>n>>m>>q;
    cin>>s>>st;
    s=" "+s;st=" "+st;
    for (int i=1;i<=n-m+1;i++)
    {
        bool ok=true;
        for (int j=1;j<=m;j++)
            if (s[i+j-1]!=st[j]) ok=false;
        if (ok) a[i]++;
    }
    for (int i=1;i<=n;i++) a[i]+=a[i-1];
    while (q--)
    {
        cin>>l>>r;
        if (r-l+1<m) cout<<0<<endl;
        else cout<<a[r-m+1]-a[l-1]<<endl;
    }
}

C.满二叉树等长路径（树形DP）

题意

题目链接：4313. 满二叉树等长路径 - AcWing题库
给出深度 $n$ 的满完全二叉树(?好像叫这个)，以及每个子结点的到父亲结点的边权，现在可以对每条边权进行增加，问你至少要增加多少能够达到根节点到每一个点距离相等？

思路

这就是贪心的思路嘛，首先求出最长的那条边权 $maxn$ ，然后其他所有的点都往这条边上靠，这样的话才是最小的。
再考虑，最底层的子结点长度为f[o]，那么还差多少？肯定是maxn-f[o]，那么我需要在点o到父亲结点o>>1这条边要增加maxn-f[o]对吧？
最后，我们来看这棵树，一个结点o以及子结点o<<1和o<<1|1，如果x[lson]=4,x[rson]=5的话，那么是不是说我两条边都至少增加4？这样的话我们浪费了花费，所以我们在o往自己的父节点o>>1上增加4就好。
这样的话lson不需要增加，直接“享受”x[o]=4带来的福利，而rson只需要增加1即可
那么我进行两次dfs：
1）找到maxn
2）每次取min，贪心

代码

#define lson (o<<1)
#define rson (o<<1|1)
#define fa (o>>1)
inline void dfs1(int o)
{
    v[o]=v[fa]+a[o];//计算长度，从上面顺下来
    if (o>=dep) {f[o]=a[o];return;}//最底层了
    dfs1(lson);dfs1(rson);
    f[o]=Max(f[lson],f[rson])+a[o];//统计最大的
}
inline void dfs(int o)
{
    if (o>=dep) {x[o]=maxn-v[o];return;}
    dfs(lson);dfs(rson);
    int t=Min(x[lson],x[rson]);
    x[lson]-=t;x[rson]-=t;//可以享受父亲结点的t
    x[o]=t;//父亲结点为t
}

inline void Case_Test()
{
    cin>>n;
    dep=(1<<n);
    num=(1<<n+1)-1;
    for (int i=2;i<=num;i++)
        cin>>a[i];
    dfs1(1);
    maxn=f[1];
    dfs(1);
    for (int i=2;i<=num;i++) ans+=x[i];
    cout<<ans;
}

这里有份只需要dfs一次的代码——y总的

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2050;

int n;
int w[N];
int ans;

int dfs(int u)
{
    if (u * 2 > (1 << n + 1) - 1) return 0;

    int l = dfs(u * 2) + w[u * 2];
    int r = dfs(u * 2 + 1) + w[u * 2 + 1];
    ans += abs(l - r);
    return max(l, r);
}

int main()
{
    cin >> n;
    for (int i = 2; i <= (1 << n + 1) - 1; i ++ ) cin >> w[i];
    dfs(1);

    cout << ans << endl;
    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2831011/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。