双链表的应用

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;
}