0%

没错,教练给我们留的良心暑假作业qwq —— 打 $10$ 场 Edu 比赛并写题解。

相比于之前 CF 比赛的题解,部分内容有轻微调整。

  1. 删去了 题目大意代码实现。(部分题目会有代码)
  2. 增加了 比赛情况所用算法相关拓展赛后总结
  3. 解题思路 相对会更简单,重心主要在 所用算法&相关拓展
阅读全文 »

一道不错的树上差分题。

如果我们考虑暴力遍历每个人的路径与每个节点上的观察员比较,时间效率太低。

不如转化问题,考虑节点 $i$ 观察员能观察到多少个人。

Part 1

乍一看也不好处理,那么我们继续简化问题,首先我们假设只有上升的路径且令 $t=1$,也就是一条路径的终点是根节点,那就是这样的情况:

【图片】

那么不难想到,当且仅当观察员在 $[s,1]$ 的路径(图中的蓝色路径)上时,才有可能会有贡献,如图。

【图片】

假设我们设点 $x$ 的深度为 $dep_x$,那么如果观察员 $i$ 能在第 $w_i$ 秒观察到的话则需满足式子:

这样的话我们可以去用桶存储,每当走到一个起点 $s$,就把 $h_{dep_s}$ 的值加 $1$,最后查询只需要去查 $h_{w_i+dep_i}$ 即可。

$\text{Q1}$:$s$ 点的子树是否会被影响到?

$\text{A1}$: 答案很明显,不会影响到,所以要特殊处理,在 dfs 操作时,要在当前节点的子树遍历后再更新桶数组。

$\text{Q2}$:如何统计答案。

$\text{A2}$:看起来是直接访问 $dep_{w_i+dep_i}$,但是有多条路径的话,会因为之前的记录导致答案不对。但是可以在走到当前这个点时记录 $tmp_1$,走完所有子树回溯到这个点时记录答案 $tmp_2$,这样形成的差值 $tmp_2-tmp_1$ 就是答案。

Part 2

让我们增加一点情况,假设仍然是上升的情况,但终点不为 $1$ ,那就是如下情况:

【图片】

同样地,只有在这条路径(蓝色)中的观察员才有可能被观察到,那么我们现在考虑更新。

因为终点不一定在根节点,有删除的可能。我们要分为两个时间点,一个是开始统计的时候一个是结束统计的时候。

开始统计自然同上,当 dfs 时已遍历完它的子树时计入。

结束统计也很简单,当从这条路径的终点节点 $t$ 走出时,将 $h_{dep_s}$ 减掉。

Part 3

考虑向下走的情况。

打 cf 这么久了,和同学一起写了个 cf 比赛专用缺省源。

$\text{created on 2021.7.24}$

$\text{updated on 2021.7.25}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <iostream>
#include <cmath>
#define ios std::ios::sync_with_stdio(0)
#define mem(name,value) memset(name,value,sizeof(name))
#define ok puts("ok")
#define yes puts("yes")
#define no puts("no")
#define Yes puts("Yes")
#define No puts("No")
#define YES puts("YES")
#define NO puts("NO")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
const int Inf = 0x3f3f3f3f;
const ll Lnf = 0x3f3f3f3f3f3f3f3f;

template <typename T>
inline T Min(T a,T b) {return a<b ? a : b;}
template <typename T>
inline T Max(T a,T b) {return a>b ? a : b;}
template <typename T>
inline T Abs(T x) {return x>0 ? x : -x;}
template <typename T>
inline T GetMin(T tmp[],int l,int r) {T res=Inf;for(int i=l;i<=r;i++) res=min(res,tmp[i]); return res;}
template <typename T>
inline T GetMax(T tmp[],int l,int r) {T res=-Inf;for(int i=l;i<=r;i++) res=max(res,tmp[i]); return res;}
template <typename T>
inline T GetSum(T tmp[],int l,int r,int mod) {ll sum=0;for(int i=l;i<=r;i++) if(mod==-1) sum+=tmp[i]; else sum=(sum+tmp)%mod; return sum;}
template <typename T>
inline void GetFrac(T tmp[],int l,int r,int mod) {tmp[l-1]=1;for(int i=l;i<=r;i++) tmp[i]=(tmp[i-1]*i)%mod;}
template <typename T>
void Print(T tmp[],int l,int r,int type) {if(type==1) for(int i=l;i<=r;i++) cout<<tmp[i]<<' '; if(type==2) for(int i=l;i<=r;i++) cout<<tmp[i]; if(type==3) for(int i=l;i<=r;i++) cout<<tmp[i]<<'\n';}

void checkf(bool flag,string Y,string N) {cout<<((flag==true) ? Y : N)<<'\n';}
ll qpow(ll x,ll p,ll mod) {ll base=x,res=1%mod;while(p!=0){if(p&1) res=(res*base)%mod;p>>=1;base=(base*base)%mod;} return res;}


const int Mod = 1e9+7;
const int base = 131;
const int maxn1 = 5e5+5;
const int maxn2 = 5000+5;
const int maxn3 = 500+5;
const int len = 100+5;

int T,n,m,k;
int a[maxn1];

void solve()
{
//Code once,think twice!

}

int main()
{
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}


阅读全文 »

本篇文章主要是为了讲述明白轻重链剖分的基本原理与长链剖分的优化方式,并不在本篇文章里讲述多道例题。

阅读全文 »