双链表的应用

2024-05-03 20:04

文章标签 应用双链

本文主要是介绍双链表的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

cf edu161 D. Berserk Monsters

在这里插入图片描述

思路：

因为考虑到，每个怪是否死亡与其左右的怪息息相关，再者，若当前怪死亡，周围怪的相邻信息也会产生变化，由此可以想到使用双链表进行维护，双链表的维护方式有很多种，对于这一类题目，可以使用两个set去存相关的信息，以这题而言，使用一个set存所有可能死亡的怪物，另外一个set存确定死亡的怪物，每次从可能死亡的怪物中得到确定死亡的怪物编号，然后再去另外一个set中进行更新即可。

#include <bits/stdc++.h>using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"void solve()
{int n;cin>>n;vector<int> a(n+5),d(n+5);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>d[i];vector<int> l(n+5),r(n+5);set<int> x,y;//y用来存一定死亡的怪物信息for(int i=1;i<=n;i++){l[i]=i-1,r[i]=i+1;x.insert(i);//x一开始把所有怪物全部放进去}vector<int> st(n+5,1);//一个怪物只会进入一次，为了防止重复进入，所以使用st数组进行标记for(int i=1;i<=n;i++){for(auto c: x){if(d[c]<a[l[c]]+a[r[c]]){//由题意进行判断y.insert(c);st[c]=0;}}cout<<y.size()<<" ";x.clear();for(auto c: y){l[r[c]]=l[c],r[l[c]]=r[c];//双链表更新左右节点if(l[c]>=1&&st[l[c]]==1) x.insert(l[c]);if(r[c]<=n&&st[r[c]]==1) x.insert(r[c]);}y.clear();}cout<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;cin >> t;while (t--){solve();}system("pause");return 0;
}

洛谷P7912 [CSP-J 2021] 小熊的果篮

题目描述

小熊的水果店里摆放着一排 $n$ 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 $\ldots, n$ 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

输入格式

第一行，包含一个正整数 $n$ ，表示水果的数量。

第二行，包含 $n$ 个空格分隔的整数，其中第 $i$ 个数表示编号为 $i$ 的水果的种类， $1$ 代表苹果， $0$ 代表桔子。

输出格式

输出若干行。

第 $i$ 行表示第 $i$ 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

思路

和上一题几乎一样，使用双链表加上两个set进行维护即可。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"vector<int> a(N),l(N),r(N);
vector<int> st(N,1);
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];set<int> x,y;for(int i=1;i<=n;i++){l[i]=i-1;r[i]=i+1;}l[1]=n+1;r[n]=n+1;for(int i=1;i<=n;i++) x.insert(i);auto check=[&](int u){if(l[u]==n+1) return true;if(a[u]!=a[l[u]]) return true;return false;};while(!x.empty()){for(auto u: x){if(check(u)){//可以发现这类题关键在于可能信息向必然信息转换条件的检验。y.insert(u);st[u]=0;}}x.clear();for(auto c: y) cout<<c<<" ";cout<<endl;for(auto u: y){r[l[u]]=r[u];l[r[u]]=l[u];if(st[l[u]]&&l[u]!=n+1) x.insert(l[u]);if(st[r[u]]&&r[u]!=n+1) x.insert(r[u]);}y.clear();}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin >> t;while (t--){solve();}system("pause");return 0;
}