写在前面
排名：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
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。