【LYZS2024寒假训练】第二周题单总结与分析

本文主要是介绍【LYZS2024寒假训练】第二周题单总结与分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构是计算机科学的一个核心领域，它研究如何高效地组织和存储数据以便访问和修改。这包括数组、链表、栈、队列、哈希表、树、图等结构。选择合适的数据结构对于解决特定问题和优化算法性能至关重要。

基础知识指路：

【期末复习】数据结构

注：本次讲解题目为题单中难度为“普及− ”、“普及/提高− ”的题目，其它题目的讲解请私聊博主。

一、普及-

二、普及/提高-

一、普及-

【模板】字符串哈希

题目要求实现字符串哈希，计算给定的字符串中，不同的有多少个。

思路：

设置一个基数base和一个数组a，存储每个字符串的哈希值。
使用哈希函数hashe计算每个字符串的哈希值。
循环读取每个字符串。对每个字符串，计算哈希值并把结果存放到数组a。
对数组a排序，使相同的哈希值相邻。最后比较相邻的哈希值是否相等，计算得到不同字符串的数量，输出结果。

#include<iostream>
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
int prime=233317; //质数
ull mod=212370440130137957ll;ull hashe(char s[]){int len=strlen(s);//字符串长度ull ans=0;for (int i=0;i<len;i++)//计算哈希值
//遍历字符串中每个字符，将字符的ASCII码与技术相乘并取模，再加上一个质数，得到最终的哈希值。ans=(ans*base+(ull)s[i])%mod+prime;return ans;
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s);a[i]=hashe(s);}sort(a+1,a+n+1);for(int i=1;i<n;i++){if(a[i]!=a[i+1])ans++;}printf("%d",ans);return 0;
}

【模板】堆

思路：实现最小堆（也就是用一个最小堆实现“数列”），按要求操作。

定义了一个结构体node，表示堆中的节点
使用优先队列priority_queue实现最小堆
根据输入的操作类型进行相应的操作

// 定义一个结构体，表示堆中的节点
struct node {long long w; // 节点的值// 重载小于运算符，用于比较两个节点的大小bool operator < (const node &x) const {return x.w < w;}
};// 使用优先队列实现最小堆
priority_queue<node> q;
int n; // 操作次数int main() {int a, b;cin >> n; // 输入操作次数for (int i = 1; i <= n; i++) {cin >> a; // 输入操作类型if (a == 1) {cin >> b; // 输入要加入数列的整数q.push((node){b}); // 将整数加入最小堆中}if (a == 2) {cout << q.top().w << endl; // 输出最小堆中的最小值}if (a == 3) {q.pop(); // 删除最小堆中的最小值}}return 0;
}

二、普及/提高-

[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

思路：

（考虑到输入数据中的数值大小，使用常规排序则long long仍然不可行）用堆表示一个数列，堆元素是每”堆“果子的重量。

考虑到节省体力的要求，由定律可得，对数列元素排序（升序或者降序都可以），求相邻元素的和，直到最后只剩下一个元素。

定义一个结构体node
定义一个优先队列q，存储node类型的对象。
定义两个node类型的变量b和c，以及整型变量n、a和ans。
在main函数中，首先读取整数n，表示数列的长度。
使用循环读取n个整数，并将它们作为node对象插入到优先队列q中。
当优先队列q的大小大于等于2时，执行以下操作： a. 弹出优先队列q中的顶部元素，赋值给变量b。 b. 再次弹出优先队列q中的顶部元素，赋值给变量c。 c. 将b和c的w值相加，更新b.w的值。 d. 将b.w累加到ans中。 e. 将更新后的b重新插入到优先队列q中。
输出最终的ans值。

#define maxn 20000005
struct node{//堆int w;//堆元素中表示每种果子的数目bool operator < (const node &x) const{//重载<用于排序return x.w<w;//实现在输入时就能升序排列}
};
priority_queue<node>q;//优先队列q存放node类型对象。这个队列的元素表示了每堆果子的数目
node b,c;//两个node类型变量
int n,a,ans;//数列长度（果子种类数）、数列元素（下一行输入中，第i种果子的数目）；结果
int main(){n=read();for(int i=1;i<=n;i++)//输入a=read(),q.push((node){a});while(q.size()>=2){//如果只有一堆，那么不用耗费体力；如果有2堆或者以上数量的果子，就要合并b=q.top(),q.pop();c=q.top(),q.pop();b.w=b.w+c.w;ans+=b.w;q.push(b);}write(ans);return 0;
}

优先队列是一种数据结构，它能够按照元素的优先级顺序进行插入和删除操作。在这段代码中，优先队列用于维护一个最小堆（min heap），其中的元素按照它们的权重值（w）从小到大排序。

优先队列的实现通常基于二叉堆（binary heap）的数据结构。二叉堆是一种特殊的完全二叉树，它具有以下性质：

每个节点的值都大于或等于其子节点的值（最小堆）。
每个节点的值都小于或等于其子节点的值（最大堆）。

在这段代码中，优先队列通过重载运算符 "<" 来实现自定义的比较逻辑。当两个节点的权重值相同时，优先队列会根据它们在内存中的存储顺序来决定它们的优先级。

使用优先队列的好处是可以高效地获取堆中的最小元素（或最大元素），并且可以在对数时间内插入和删除元素。这使得优先队列非常适合处理需要频繁访问最小（或最大）元素的问题，例如本段代码中的求和问题。

滑动窗口 /【模板】单调队列

# define maxn 1000001 
struct heap_queue{//队列 int n,k,a[maxn];int q[maxn],head,tail,p[maxn];//q单调队列，p对应编号。void read() {//输入函数 scanf("%d %d",&n,&k);for(int i=1;i<=n;++i)scanf("%d",&a[i]);}void heap_max() {//求单调最大值：head=1;tail=0;//头尾赋值原因：类似普通队列， //head要严格对应首元素，tail要严格对应尾元素//故当tail>=head时，说明有元素。//最初队列为空，要考虑这个特殊情况。for(int i=1;i<=n;++i) {//遍历 序列 while(head<=tail&&q[tail]<=a[i])//队列中有元素，并且窗口队尾的元素比这个未入队的元素小 tail--;//队尾向前一个 q[++tail]=a[i];//新的队尾入队 p[tail]=i;//队尾的标号变成入队元素的编号 while(p[head]<=i-k)//队首存在，这个窗口还可以向后滑动（也就是队首编号还没有达到它能达到的最大值i-k） head++;//队首编号+ if(i>=k)printf("%d ",q[head]);// 输出窗口滑动的最小值 }printf("\n");}void heap_min(){//求单调最小值 head=1;tail=0;for(int i=1;i<=n;++i)for(int i=1;i<=n;++i) {while(head<=tail&&q[tail]>=a[i])tail--;q[++tail]=a[i];p[tail]=i;while(p[head]<=i-k)head++;if(i>=k)printf("%d ",q[head]);}printf("\n");}
}he;int main(){he.read();he.heap_min();he.heap_max();return 0;
}

单调队列是一种特殊的队列，它的特点是队中的元素保持单调递增或递减。在算法编程中，单调队列常用于解决一些需要维护区间性质的问题，例如求滑动窗口的最小值、最大值等。

单调队列的特性如下：

队中元素保持单调性：队头元素一定是当前队列中的最小（或最大）值。
队中元素的位置关系：队头元素的前一个元素（如果有的话）一定（单调递增队列中）小于等于/（单调递减队列中）大于等于队尾元素。（注：”前一个元素”可能是指队列中位于队头元素之前的元素，即在队头元素入队之前已经在队列中的元素。）
队中元素的出队顺序：当新元素入队时，如果满足单调性，则直接入队；否则，将队尾元素依次出队，直到新元素可以入队为止。

【模板】树状数组 2

定义一个长整型数组inn用于存储输入的数据，一个长整型数组tree用于存储树状数组的值。
lowbit(ll num)函数用于获取num的最低位的1所对应的值。例如，如果num是8（二进制表示为1000），那么lowbit(num)返回的就是4（二进制表示为100）。
add(ll s,ll num)函数用于更新树状数组。参数s表示要更新的位置，num表示要增加的值。这个函数会从s开始，每次将s加上s的最低位的1所对应的值，然后将num加到tree[s]上，直到s大于n。
ask(ll s)函数用于查询前s个元素的和。参数s表示要查询的位置。这个函数会从s开始，每次将s减去s的最低位的1所对应的值，然后将tree[s]加到结果上，直到s小于1。
main()函数首先读取n和q，然后读取n个整数存入inn数组。然后进行q次操作，每次操作首先读取mod，如果mod等于1，那么就读取x、y和s，然后调用add(x,s)和add(y+1,-s)来更新树状数组；如果mod等于2，那么就读取x，然后调用ask(x)来查询前x个元素的和，最后将结果加上inn[x]并输出。

#define ll long long
using namespace std;
ll n,q,mod,x,y,s,inn[500001],tree[500001];
ll lowbit(ll num){return num&-num;
}
void add(ll s,ll num){for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;
}
ll ask(ll s){ll ans=0;for(ll i=s;i>=1;i-=lowbit(i))ans+=tree[i]; return ans;
}
int main(){scanf("%lld%lld",&n,&q);for(int i=1;i<=n;i++) scanf("%lld",&inn[i]);for(int i=1;i<=q;i++){scanf("%lld",&mod);if(mod==1){scanf("%lld%lld%lld",&x,&y,&s);add(x,s);add(y+1,-s);}if(mod==2){scanf("%lld",&x);printf("%lld\n",inn[x]+ask(x)); }}return 0;
}

树状数组是一种高效的数据结构，用于处理区间和查询和单点更新的问题。

【模板】并查集

int n,m,z,x,y,f[10086];
/*
f[10086]数组用于存储每个元素的父节点信息，初始时每个元素的父节点都是它自己。
find(int k)函数用于查找元素k所在的集合的代表元素（根节点），通过递归的方式找到根节点，并在路径压缩的过程中更新每个元素的父节点为根节点，以优化后续查询的效率。
*/
inline int find(int k){if(f[k]==k)return k;return f[k]=find(f[k]);
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=m;i++){cin>>z>>x>>y;if(z==1)
//将x和y所在的集合合并，即将x所在集合的代表元素的父节点设置为y所在集合的代表元素。f[find(x)]=find(y);if(z==2){
//判断x和y是否属于同一个集合，即判断它们的代表元素是否相同。if(find(x)==find(y))cout<<'Y'<<endl;else cout<<'N'<<endl;}}return 0;
}

并查集是一种用于处理不相交集合的合并和查询问题的数据结构。
【模板】树状数组 1

    int n,m,tree[2000010];int lowbit(int k){return k & -k;}void add(int x,int k){while(x<=n){tree[x]+=k;x+=lowbit(x);}}int sum(int x){int ans=0;while(x!=0){ans+=tree[x];x-=lowbit(x);}return ans;}int main(){cin>>n>>m;for(int i=1;i<=n;i++){int a;scanf("%d",&a);add(i,a);}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a==1)add(b,c);if(a==2)cout<<sum(c)-sum(b-1)<<endl;}return 0;}

【模板】最近公共祖先（LCA）

求LCA的方法非常多，有倍增求LCA，DFS求LCA等。

DFS求LCA：

构建一个无向图（此处使用前向星）

通过深度优先搜索（DFS）来找到两个节点的最近公共祖先。

#define maxn 500006
int x, m, n, s, v, ans;
struct {int to, from;
} edge[maxn << 1]; // 定义边的结构体，用于存储边的起始点和终点
int cnt, head[maxn]; // 计数器，节点数组
void add(int s, int e) {
// 添加节点和边以构建树++cnt; // 计数器加一edge[cnt].from = head[s]; // 连接节点和边edge[cnt].to = e; // 下一条边head[s] = cnt; // 节点数量
}
int depth[maxn]; // 路径的高度
int f[40][maxn]; // 树
void dfs(int son, int fa) {
// 记录深度在DFS中
// son是当前节点，fa表示父节点或高度depth[son] = depth[fa] + 1; // 父节点和子节点之间的高度f[0][son] = fa; // 第一个节点int i;for (i = 1; (1 << i) <= depth[son]; i++) // 根据高度构建树f[i][son] = f[i - 1][f[i - 1][son]]; // son;dp// son的第2^i个祖先是其第2^(i-1)+2^(i-1)个祖先for (i = head[son]; i; i = edge[i].from)if (edge[i].to != fa)dfs(edge[i].to, son);
}
int lca(int x, int y) { // 寻找最近公共祖先int i;if (depth[x] < depth[y]) { // 使深度相同int c;c = x;x = y;y = c;}for (i = 20; i >= 0; i--)if ((depth[x] - depth[y]) >= (1 << i))x = f[i][x]; // 转换为相同的深度if (x == y)return x;for (i = 20; i >= 0; i--)if (f[i][x] != f[i][y])x = f[i][x], y = f[i][y];return f[0][x];
}
int tm, tmp;
int main() {int i;scanf("%d%d%d", &n, &m, &s);for (i = 1; i < n; i++) {scanf("%d%d", &tm, &tmp);add(tm, tmp);add(tmp, tm);}dfs(s, 0);for (i = 1; i <= m; i++) {scanf("%d%d", &tm, &tmp);printf("%d\n", lca(tm, tmp));}return 0;
}

【模板】ST 表

int f[100010][21],n,m,l,r;/*
f[100010][21]：二维数组，用于存储ST表。第一维表示数列中的元素位置，第二维表示区间长度的对数。
l、r：查询区间的左右边界。
*/
inline int query(int l,int r){int k=log2(r-l+1);//计算区间长度的对数kreturn max(f[l][k],f[r-(1<<k)+1][k]);//对拆出来的区间，分别求最大值}inline void st(int n){//构建ST表。对于每个区间长度i（从1到20），遍历所有可能的起始位置j，计算f[j][i]的值for(int i=1;i<=20;i++)for(int j=1;j+(1<<i)<=n+1;j++)//限制边界f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);return ;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&f[i][0]);st(n);for(int i=1,l,r;i<=m;i++){scanf("%d%d",&l,&r);printf("%d\n",query(l,r));}return 0;}

ST表（Sparse Table，稀疏表）是一种数据结构，主要用于解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。

ST表的核心思想是预处理和存储所有可能的区间查询结果，以便在O(1)的时间复杂度内回答查询。这种数据结构特别适合处理可重复贡献问题，即一个问题的答案可以由其子问题的答案组合而成。

定义与原理：ST表通过构建一个二维数组来存储数列的信息，其中一维表示数列中的元素位置，另一维表示区间长度的对数。数组中的每个元素f[i][j]代表了数列中某个特定区间的最大值。这个区间由位置i和2的j次幂确定，即从位置i开始，长度为2^j的区间。
构建方法：构建ST表的过程包括两个步骤。首先，初始化数组的第一维，即直接存储数列中每个元素的位置。然后，对于每个可能的区间长度（从1到log(n)），遍历所有可能的起始位置，并更新数组的相应元素，使其存储该区间内的最大值。这个过程使用了动态规划的思想，即利用已经计算好的更小区间的结果来计算当前区间的最大值。
查询方法：当需要查询一个区间[l, r]的最大值时，首先计算区间长度的对数k，然后在ST表中查找位置l和r对应的元素f[l][k]和f[r-(1<<k)+1][k])
性能分析：ST表的预处理时间复杂度为O(nlogn)，因为需要对每个可能的区间长度进行遍历。查询时间复杂度为O(1)，因为只需要常数次的操作即可得到答案。
应用场景：除了区间最值查询，ST表还可以用于解决其他可重复贡献问题，如区间按位和、区间按位或等。

【模板】单调栈

遍历数组
利用单调栈的性质，找到每个位置左侧第一个比它大的元素的位置，并将结果存储在数组f中
、输出数组f中的每个元素作为结果。

#define MAXN 3000005 // 定义最大数组长度为3000005
int n, a[MAXN], f[MAXN]; // 定义变量n、数组a和f，用于存储输入数据和计算结果
stack<int> s; // 定义一个整数类型的栈sint main() {scanf("%d", &n); // 从标准输入读取一个整数n，表示数组的长度for (int i = 1; i <= n; i++)scanf("%d", &a[i]); // 从标准输入读取n个整数，存储到数组a中for (int i = n; i >= 1; i--) {while (!s.empty() && a[s.top()] <= a[i])s.pop(); // 如果栈不为空且栈顶元素小于等于当前元素，则弹出栈顶元素f[i] = s.empty() ? 0 : s.top(); // 如果栈为空，则将f[i]设为0；否则将f[i]设为栈顶元素的索引s.push(i); // 将当前元素的索引压入栈中}for (int i = 1; i <= n; i++)printf("%d ", f[i]); // 输出每个位置对应的结果值return 0;
}

单调栈是一种数据结构，它满足单调性，即栈中的元素按照一定的顺序排列。这种数据结构通常用于解决一些特定的算法问题，如寻找数组中下一个或上一个最大元素的问题。

单调栈的主要特点和应用如下：

单调性：单调栈中的元素保持单调递增或递减的顺序。
用途：它可以用于解决NGE（Next Greater Element）问题，即对于序列中的每个元素，找到下一个比它大的元素。此外，单调栈还可用于解决视野总和、最大子和等问题。
操作：单调栈支持插入和读取元素，以及解决离线问题。
时间复杂度：O(n)

这篇关于【LYZS2024寒假训练】第二周题单总结与分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！