2009 Niuke Summer Multi-School Training Camp (Game 3) J LRU management(list+map Application)

Topic link: https://ac.nowcoder.com/acm/contest/883/J

 

Topic: opt p v, p is the name of the block, opt 0 is the insertion block. If it is an existing block, output the value of the existing block and put it at the end. Otherwise, insert it directly at the end and keep the number of m. If there are too many, delete the first one, opt 1 is the query block, V is the back one, 0 is the first one, and - 1 is the front one.

 

Title idea: It is a simple simulation, the main meaning is to learn the related functions of list. When opt is 0, first judge whether the name has appeared or not. If it is deleted, then let its name map = L. end (). If it is deleted, first delete it, then insert it into the back. If it is not there, then judge the number, such as If it reaches m, delete the first number and insert it, otherwise insert it directly. For opt 1, first look at whether p memory does not exist or is deleted, whether it does not exist or is deleted directly Invalid, for v=-1 see if it is begin, if it is Invalid, if it is 1, see if it is end after it+, if it is Invalid, otherwise output the value of the corresponding iterator.

I have to say that stl is really fragrant

 

The following is the code:

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define inf 0x3f3f3f3f
const int MAXN = 5e5+5;
struct node{
    string s;
    int v;
}a;
list<node>l;
unordered_map<string,list<node>::iterator >mp;
char p[MAXN];
int main()
{
    int t,q,m,opt,v;
    scanf("%d",&t);
    list<node>::iterator it;
    while(t--){
        scanf("%d%d",&q,&m);
        mp.clear();
        l.clear();
        int num=0;
        rep(i,1,q){
            scanf("%d%s%d",&opt,p,&v);
            if(!opt){
                if(mp.count(p)&&mp[p]!=l.end()){
                    it=mp[p];
                    a.s=p,a.v=(*it).v;
                    printf("%d\n",(*it).v);
                    l.erase(it);
                    l.push_back(a);
                    it=l.end();
                    it--;
                    mp[p]=it;
                }
                else{
                    if(num==m){
                        it=l.begin();
                        mp[(*it).s]=l.end();
                        l.erase(it);
                    }
                    else num++;
                    a.s=p,a.v=v;
                    l.push_back(a);
                    it=l.end();
                    it--;
                    mp[p]=it;
                    printf("%d\n",v);
                }
            }
            else{
                if(!mp.count(p)||mp[p]==l.end()){
                    printf("Invalid\n");
                    continue;
                }
                it=mp[p];
                if(v==-1){
                    if(it==l.begin()){
                        printf("Invalid\n");
                        continue;
                    }
                    else{
                        it--;
                    }
                }
                else if(v==1){
                    it++;
                    if(it==l.end()){
                        printf("Invalid\n");
                        continue;
                    }
                }
                printf("%d\n",(*it).v);
            }
        }
    }
    return 0;
}

 

Posted on Wed, 09 Oct 2019 06:59:17 -0700 by logging