专栏文章

NFLSHC集训Day1

JJoyce_Official
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miouq889
此快照首次捕获于
2025/12/03 01:28
3 个月前
此快照最后确认于
2025/12/03 01:28
3 个月前
查看原文

安排：

大概就是早八上课，下午做题，中午睡一下
今日大纲：
  • 复习前缀和与差分思想
  • 学习树上差分，背熟LCA板子，会做基础题
  • 学习倍增思想

复习前缀和

前缀和思想和基本模型：
前缀和，顾名思义就是左边端点为1，右边端点不限（一维）的思想，多维前缀和在理论上也是可以实现的
一维前缀和请助手小李给个图例：
那么根据图例可以知道一维前缀和的递推公式为：
SiS_i（第ii个数的前缀和）= S[i−1]S[i - 1]（第i−1i-1个数的前缀和）+ aia_i（当前数）
二维前缀和及多维前缀和也一样，小李给个图例：
那么根据图例也可以知道，二维前缀和的递推公式为：
S[i][j]S[i][j] = S[i−1][j]S[i - 1][j] + S[i][j−1]S[i][j - 1] - S[i−1][j−1]S[i-1][j-1] + a[i][j]a[i][j]
三维前缀和需要画立方体，四维及以上小李也画不出来，而且比较麻烦，就不出示了
前缀和的局限性
前缀和有一个很大的要求，数组中的元素是改不了 的，有一个元素的改动对前缀和来说都是毁灭性打击，尤其是第一项
前缀和只能在有逆运算的情况下使用，你说求最大值这种东西没有逆运算，前缀和是无法完成的
差分的思想与应用：
小李可以放假了
差分在区间修改问题里非常常见，例如有数组aa，那么差分数组bb存储的就是a[i]a[i]和a[i−1]a[i - 1]的差值，所以在区间内统一进行加减时，因为同增同减差不变，所以区间内的差是没有变化的，不用改，而不使用差分时就要用循环改，事倍功半
差分的应用场景广泛，随便看一道，例如二维差分的“地毯覆盖”什么的，而且模型和前缀和差不了多少，都是容斥原理，小李你就可以退下了，不用画图
差分的局限性：
差分和前缀和最大的不同点在于前缀和改不了，但差分可以区间改，但是这两种算法都挺卡时间复杂度的，其实都可以用线段树解决 ，但是我不想，累

学习树上差分

经典例题
老师说的基础题，上链接：
Here
树上差分其实就是把差分思想用在树上，避免逐个暴力修改，使用DFS求差分数组的前缀和，就可以达到降低复杂度的目的，但前提是你得会做LCA（最近公共祖先）
教练：LCA你们不会有人不会背吧
我：你报我身份证号得了
CPP
int LCA(int x, int y)//这是LCA最常用的倍增算法
{
	if(depth[x] > depth[y]) swap(x, y);
	int t = depth[y] - depth[x];
	for(int i = 0; i < 18; i++)
	{
		if(t&(1<<i)) y = fa[y][i];
	}
	if(x == y) return x;
	for(int i = 17; ~i; i--)
	{
		if(fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
在此之前先讲一下LCA的倍增实现：
注意到uu，vv走到最近公共祖先之前，uu，vv所在结点不相同。
而到达最近公共祖先后，再往上走仍是uu，vv的公共祖先，即uu，vv走到同一个结点，这具有二分性质。
于是可以预处理出一个2k2k的表，
fa[k][u]fa[k][u]表示uu往上走2k2k步走到的结点，令根结点深度为0，则2k2k > depth[u]depth[u]时，令fa[k][u]fa[k][u] = -1(不合法情况的处理）
不妨假设depth[u]depth[u] < depth[v]depth[v]
①将 vv 往上走 dd = depth[v]depth[v] - depth[u]depth[u] 步，此时u，v所在结点深度相同，该过程可用二进制优化。
由于 dd 是确定值，将 dd 看成2的次方的和值， dd = 2k12k1 + 2k22k2 + ... + 2km2km ，利用 fafa 数组，如 vv = fa[k1][v]fa[k1][v] ， vv = fa[k2][v]fa[k2][v] 加速。
②若此时 u=vu = v ，说明LCA已找到
③利用 fafa 数组加速 uu ， vv 一起往上走到最近公共祖先的过程。
令 d=depth[u]−depth[w]d = depth[u] - depth[w] ，虽然 dd 是个未知值，但依然可以看成2的次方的和。
从高位到低位枚举 dd 的二进制位，设最低位为第0位，若枚举到第k位，有 fa[k][u]!=fa[k][v]fa[k][u] != fa[k][v] ，则令 u=fa[k][u]u = fa[k][u] ， v=fa[k][v]v = fa[k][v] 。
最后，最近公共祖先为 fa[0][u]=fa[0][v]fa[0][u] = fa[0][v]
接下来的DFS代码就好理解了，上链接：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200100;
int n, fa[N][20];
int tag[N], depth[N];
struct edge
{
	int to;
	ll v1, v2;
};
ll ans = 0;
vector<edge> g[N];
void dfs(int u)
{
	for(edge e:g[u])
	{
		int v = e.to;
		if(v == fa[u][0]) continue;
		depth[v] = depth[u] + 1;
		fa[v][0] = u;
		dfs(v);
	}
}
void pre()
{
	for(int j = 1; j <= 17; j++)
	{
		for(int i = 1; i <= n; i++)
		{
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
}
void dfs2(int u)
{
	for(edge e:g[u])
	{
		int v = e.to;
		if(v == fa[u][0]) continue;
		dfs2(v);
		ans += min(e.v1 * tag[v], e.v2);
		tag[u] += tag[v];
	}
}
int LCA(int x, int y)
{
	if(depth[x] > depth[y]) swap(x, y);
	int t = depth[y] - depth[x];
	for(int i = 0; i < 18; i++)
	{
		if(t&(1<<i)) y = fa[y][i];
	}
	if(x == y) return x;
	for(int i = 17; ~i; i--)
	{
		if(fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

int main()
{
	int u, v;
	ll v1, v2;
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		cin >> u >> v >> v1 >> v2;
		g[u].push_back(edge{v, v1, v2});
		g[v].push_back(edge{u, v1, v2});
	}
	fa[1][0] = 0, depth[1] = 0;
	dfs(1);
	pre();
	for(int i = 1; i < n; i++)
	{
		int y = LCA(i, i + 1);
		tag[i]++; tag[y]--;
		tag[i + 1]++; tag[y]--;
	}
	dfs2(1);
	cout << ans;
	return 0;
}
这一题总结起来一句话新闻：
要加tag啊！在LCA的上方打-1的tag，在下方打+1的tag，由点化边更简单

倍增和ST表

小李我需要你
倍增的思想
话说倍增是什么东西，其实说白了就是跳石头，由一个大跳转变为多个小跳的过程，而每一次的转变都是2的k次方级别的
倍增有一些特点：
好算！只是O(nlogn)O(nlogn)级别的，而且完全符合递推思想，每一种倍增问题都可以转变为 T[T[i][j−1]][j−1]T[T[i][j-1]][j-1] 的形态，话说怎么有点像套娃呢？没关系，小李给图例：
倍增的应用场景也是很有限制的，主要有三点：规则是固定的，执行若干次；要找满足条件的最近项；终点未知
倍增的应用
前文说过的LCA，我不赘述了
以及一些老师给的经典例题：
P1
使用ST表预处理区间块的最值，支持O(1)O(1)查询。
把RMQ放进冰箱要多少步？两步：
1.先预处理 f[i][j]f[i][j]
CPP
   for (int i = 2; i <= n; i++) //lg[i]记录i转成二进制的位数
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    for (int j = 1; j <= lg[n]; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
2.再查询区间最值
CPP
    for (int x, y, i = 1; i <= m; i++) {
        cin >> x >> y;
        int l = lg[y - x + 1];
        cout << max(f[x][l], f[y - (1 << l) + 1][l]) << '\n';
    }
写完，AC代码记得背（数据太大不用快读过不去，这是板子）：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, x, y, a[N], lg[N], f[N][20];

int main()
{
	cin >> n >> m;
	lg[1] = 0;
	for(int i=2;i<=n;i++) 
	{
		lg[i]=lg[i>>1]+1;
	}
	for (int i=1;i<=n;i++) 
	{
		cin>>f[i][0];
	}
	for (int j=1;j<=lg[n];j++)
	{
		for (int i=1;i<=n-(1<<j)+1;i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	for (int i=1;i<=m;i++)
	{
		cin>>x>>y; 
		int l=lg[y-x+1];
		cout<<max(f[x][l],f[y-(1<<l)+1][l])<<endl;
	}
}
P2
这题就是为了做倍增而做倍增，还套了差分，没啥意义，当板子练练手好了
如果 f[i][j]f[i][j] 表示从 ii 进行 2j2j 次操作得到的数，则 f f 是好预处理的。同时 i 的上界也是确定的，由于范围要求，故 log2(i)log2(i) 不超过 20，即修改后的 i 不超过 2.1×1e62.1×1e6 。
代码连老师都没写，我也不放了
P3
这题要是用普通的圆环统计你不完了吗，来试一下在环上的倍增大跳，小李给个图例：
只能在向左或者向右的 len/2len/2 个点中寻找（貌似不说也是这么干）。
可以发现有一个性质，一个区间内，一旦一个端点被固定下之后，这个区间内的最大值会随着区间的扩大而非严格单调递增，那么就找到这个区间的单调性了，现在多了一个二分可以选择。
维护区间最大值，看数据范围，可以用 ST 表进行维护。
现在就有了一种做法，确定一个位置，然后向前向后分别二分进行查找。
时间复杂度为 O(nlogn) O(nlogn) 。
P4
我发现这题有图例，太好了
我看到好多人都用单调栈，但倍增也不错
不难发现，盘子溢出的水只会流到直径比它大的盘子里，但前提是体积之和要大于 V[i]V[i] ，利用倍增的思想求出从下往上第 jj 个盘子往下流，流过2的ii次方个盘子之后会停留在哪里
CPP
for(int i=1;i<=size;i++){//倍增万能公式
	for(int j=1;j<=m;j++){
		next[j][i]=next[next[j][i-1]][i-1];
	}
}
还是利用倍增的思想，求出从下往上第j个盘子流过2的ii次方个盘子需要多少，最后处理询问，完结撒花
CPP
int need[N][M];//在万能公式上稍微改一下
void init_need(){
	for(int i=1;i<=m;i++)need[i][0]=c[i];
	for(int i=1;i<=size;i++){
		for(int j=1;j<=m;j++){
			need[j][i]=need[j][i-1]+need[next[j][i-1]][i-1];
		}
	}
}
最后就是老师带着我们写的标程
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
const int M = 25;

inline void read(int &wh)
{
    wh=0;
    int f=1;
    char w=getchar();
    while(w<'0'||w>'9')
    {
      if(w=='-')f=-1;
      w=getchar();
    }
    while(w<='9'&&w>='0')
    {
      wh=wh*10+w-'0';
      w=getchar();
    }
    wh*=f;
    return;
}

int m,n,size,w[N],c[N];
 
int next[N][M];
struct node
{
  int number,data;
};
stack<node>sta;
void init_next()
{
	sta.push((node){0,1e18});
	for(int i=1;i<=m;i++)
    {
		while(!sta.empty()&&sta.top().data<=w[i])sta.pop();
		next[i][0]=sta.top().number;
		sta.push((node){i,w[i]});
	}
	while(!sta.empty())sta.pop();
	for(int i=1;i<=size;i++)
    {
		for(int j=1;j<=m;j++)
        {
			next[j][i]=next[next[j][i-1]][i-1];
		}
	}
}

int need[N][M];
void init_need()
{
	for(int i=1;i<=m;i++)need[i][0]=c[i];
	for(int i=1;i<=size;i++)
    {
		for(int j=1;j<=m;j++)
        {
			need[j][i]=need[j][i-1]+need[next[j][i-1]][i-1];
		}
	}
}

signed main()
{
	
	read(m);
    read(n);
	while((1<<size)-1<m)
    {
      size++;
      size--;
	}
	for(int i=1;i<=m;i++)
    {
		read(w[m-i+1]);
        read(c[m-i+1]);
	}
	init_next();
	init_need();
	while(n--)
    {
		int wh,th;
		read(wh);read(th);
		wh=m-wh+1;
		int now=0;
		for(int i=size;i>=0;i--)
        {
			if(now+need[wh][i]<th)
            {
				now+=need[wh][i];
				wh=next[wh][i];
			}
		}
		
		if(wh==0) printf("0\n");
		else printf("%lld\n",m-wh+1);
	}
	return 0;
}
其实快读我自己都不想写，但是为了时间复杂度我还是努力了

以及我发现的事

  • 差点要安排晚自习，一听有作业我人都麻了，俺不中嘞
  • 树上差分吓死人，还好我有助手小李和贴心老师
  • 中午回宿舍差点吵鼠，我才发现隔壁床全开声音玩phigros
  • 倍增好难，隔壁已经摆烂了
  • 舍友给我带了半杯奶茶，香香
  • 初二全在写作业，只有我一个在写题

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...