洛谷 - 队列安排(模板c++库函数链表应用)
程序员文章站
2022-05-22 10:35:27
...
题目小传送
题意:
其实我是因为要考数据结构了,不想手写链表,找了个模板题来练练手 qwq…
要让我贴手写代码?我要闹了!!!
基本介绍一下:
list<int> l;//链表的申明
list<int>::iterator it[N],it1;//链表的前向迭代器的申明,可以二维也可以一维也可零维,我的理解是存储的元素迭代器的地址
push_front(1),push_back(1);向前插入一个元素1和向后插入一个元素1
pop_front(),pop_back();//同理删除元素
l.insert(迭代器所指的位置地址,元素值)//这里才是链表改学的地方,因为链表就是因为插入元素方便才好用滴滴滴滴滴滴
//还有这个insert的返回值是插入的元素的迭代器位置
//还有......请原谅我啰嗦,这个插入是插入这个位置的左边
l.erase(迭代器所指向的地址);//删除也方便
l.begin();//指向链表中第一个元素的位置
l.end();//指向链表中最后一个元素的后面的位置,注意不是最后一个元素!!
//这个借助迭代器遍历链表
l.size();//链表中的元素个数
l.empty();//判断是否为空,为空返回true
//基本的就是这些了,让我们a了它!!!
做了这个题效果更棒哦
AC代码:
#include <bits/stdc++.h>
inline long long read(){char c = getchar();long long x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 1e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
list<int> l;
list<int>::iterator it[N],it1;//it记录的是每一个元素的迭代器地址,it1用来遍历链表的
int vis[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,m;
cin >> n;
l.push_front(1);
it[1] = l.begin();//记录迭代器地址位置
for(int i = 2;i <= n;i++)
{
int a,b;
cin >> a >> b;
if(b == 0)
it[i] = l.insert(it[a],i);
else
{
auto s = next(it[a]);
//这个是找到it[a]这个位置的下一个位置,不能直接it[a]++,会RE,我不知道为什么。
//大概的估计,当是最后一个元素的时候,我现在插入到他的右边,但是现在的右边的这个位置是没有的,导致了RE
it[i] = l.insert(s,i);
}
}
cin >> m;
while(m--)
{
int num;
cin >> num;
if(vis[num]) continue;
else l.erase(it[num]),vis[num] = 1;//删除这个元素,再记忆化一下
}
for(it1 = l.begin();it1 != l.end();it1++)//借助迭代器遍历
cout << *it1 << " ";
}
上一篇: 洛谷 - 树状数组 (板子代码)
下一篇: 中国剩余定理