CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. 比赛总结
  3. 正文

AcWing周赛42

2022年3月17日 366点热度 0人点赞 0条评论

写在前面

排名: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
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
标签: AcWing周赛 前缀和 树形DP
最后更新:2022年3月17日

Carry

来自于湖南长沙

点赞
< 上一篇
下一篇 >

文章评论

取消回复
标签
AcWing周赛 前缀和 树形DP
文章目录
  • 写在前面
  • A.最小值(模拟)
    • 题意
    • 思路
    • 代码
  • B.出现次数(前缀和)
    • 题意
    • 思路
    • 代码
  • C.满二叉树等长路径(树形DP)
    • 题意
    • 思路
    • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS