题目传送🚪
A 排队🚪
C 拍照🚪
总结
第一类：链表
排队
这一题既可以用双向队列也可以用链表，链表熟悉亿一些，所以来讲链表
注意的点
记得用双链表
思路
与链表模板不同的地方：
-
首先这里从删除一个变成了删除k个，这意味着需要弄清楚哪个是要删除的那个是不要删的
-
这里从插入具体的数变成了插入编号，所以记得编一个
cnt数组代码：
#include<bits/stdc++.h>
using namespace std;
int idx=1,head,e[100010],l[100010],r[100010],edd=-1;
void add(int h,int k){
e[idx]=k;
l[idx]=h;
l[r[h]]=idx;
r[idx]=r[h];
r[h]=idx;
idx++;
}
void quel(int h,int k){
int le=h;
for(int i=1;i<=k-1;i++){
le=l[le];
}
r[l[le]]=r[h];
l[r[h]]=l[le];
//cout<<le<<endl;
}
void quer(int h,int k){
int re=h;
for(int i=1;i<=k-1;i++){
re=r[re];
}
r[l[h]]=r[re];
l[r[re]]=l[h];
//cout<<re<<endl;
}
void intt()
{
edd=-1;
head=0;
idx=1;
r[head]=edd;
l[edd]=head;
}
int main(){
freopen("pd.in","r",stdin);
freopen("pd.out","w",stdout);
intt();
int s,cnt=1;
cin>>s;
for(int i=1;i<=s;i++){
char x;
cin>>x;
if(x=='A') {
char f;
cin>>f;
if(f=='L'){
add(head,cnt++);
}else{
add(l[edd],cnt++);
}
}else{
char f;
int u;
cin>>f>>u;
if(f=='L'){
quer(r[head],u);
}else{
quel(l[edd],u);
}
}
}
for(int i=r[head];i!=edd;i=r[i]){
cout<<e[i]<<endl;
}
return 0;
}
插入删除
本题是明显的链表题 但是这一题用桶做优化，使得查找和删除都是O(1)！
为了完成桶优化，所以我们使用哈希表来完成目标
思路
用哈希表的原因是这里不是找第几个加入的，而是x，所以为了方便，就用STL自带的
unordered_map
注意的点
因为是双链表，所以数据范围开大点（2倍）
代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
int e[400010],l[400010],r[400010],idx=1,head,tail;
void add(int x,int h){
mp[x]=idx;
e[idx]=x;
l[r[h]]=idx;
l[idx]=h;
r[idx]=r[h];
r[h]=idx;
idx++;
}
void mevem(int h){
l[r[mp[h]]]=l[mp[h]];
r[l[mp[h]]]=r[mp[h]];
}
int main(){
freopen("insdel.in","r",stdin);
freopen("insdel.out","w",stdout);
head=0;
tail=0;
r[head]=tail;
l[tail]=head;
int q,n;
//cout<<"r[head] "<<r[head]<<endl;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
//cout<<"i " << i <<" ";
add(x,l[tail]);
}
cin>>q;
while(q--){
int x;
cin>>x;
if(x==1){
int h,up;
cin>>h>>up;
add(up,mp[h]);
}
else{
int h;
cin>>h;
mevem(h);
}
}
for(int i=r[head];i!=tail;i=r[i]){
cout<<e[i]<<" ";
}
return 0;
}
C.拍照
思路
双指针，贪心的思想来说：当只有的ID数大于1时，才将向右移。如果满足条件，取值
代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> ct,mp;
pair<int,int> a[50010];
int main(){
freopen("photo.in","r",stdin);
freopen("photo.out","w",stdout);
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].first>>a[i].second;
ct[a[i].second]+=1;
if(ct[a[i].second]==1){
sum++;
}
}
sort(a+1,a+1+n);
int r=1,l=1,cnt=0,num=0x3f3f3f3f;
while(r>=l&&r<=n&&l<=n){
if(mp[a[r].second]==0){
cnt++;
}
mp[a[r].second]++;
while(mp[a[l].second]>1){
if(mp[a[l].second]>1){
mp[a[l].second]--;
l++;
}
}
if(cnt>=sum){
num=min(num,a[r].first-a[l].first);
}
r++;
}
cout<<num;
return 0;
}
第二类：栈、堆、队列
D. 小马要做最棒的牛
表达式求值，没啥好说的，纯模拟，加栈优化
代码
#include<bits/stdc++.h>
using namespace std;
stack<int> op;
stack<long long> a;
int main(){
freopen("horse.in","r",stdin);
freopen("horse.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
int u;
cin>>u;
if(u==0){
op.push(u);
}else{
long long ans=1,cnt=0;
while(op.top()!=0&&!op.empty()){
ans++;
//cout<<op.top()<<" "<<i<<endl;
op.pop();
}
//cout<<ans<<endl;
//cout<<a.size()<<"a.size()"<<endl;
op.pop();
if(ans==1){
a.push(ans);
}
else{
for(long long i=1;i<=ans-1;i++){
cnt=(cnt+a.top())%12345678910;
a.pop();
}
cnt=(cnt*2)%12345678910;
a.push(cnt);
}
op.push(-1);
}
}
long long cnt=0;
for(int i=1;!a.empty();i++){
cnt=(a.top()+cnt)%12345678910;
a.pop();
}
cout<<cnt;
return 0;
}
E. 小田在努力切割木板
思路
正面想很难，但是将题简化成这样就明白了！
- 现在有n块木板，每合并两个木板消耗这两个模板长度总和。问能量最小消耗多少？
毫无疑问，这是合并石子的题，所以我们加上堆优化就可以轻松做出来！！
代码
#include<bits/stdc++.h>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long>> q;
int main(){
freopen("qg.in","r",stdin);
freopen("qg.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
q.push(x);
}
long long as=0,cnt=0;
while(q.size()>1){
long A,B;
A=q.top();
q.pop();
cnt++;
B=q.top();
q.pop();
q.push(A+B);
as+=A+B;
}
cout<<as;
return 0;
}
