关于map
  • 板块学术版
  • 楼主Ame__
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/11/12 10:35
  • 上次更新2023/11/5 08:14:30
查看原帖
关于map
245875
Ame__楼主2020/11/12 10:35
#include<bits/stdc++.h>
    
#define LL long long
    
#define qwq double
    
#define _ 0
    
#define AME__DEBUG
    
#define LOG(FMT...) fprintf(stderr , FMT)
    
using namespace std;
    
/*Grievous Lady*/
    
const int BUF_SIZE = 1 << 12;
    
char buf[BUF_SIZE] , *buf_s = buf , *buf_t = buf + 1;
    
#define PTR_NEXT() \
{ \
    buf_s ++; \
    if(buf_s == buf_t) \
    { \
        buf_s = buf; \
        buf_t = buf + fread(buf , 1 , BUF_SIZE , stdin); \
    } \
}
    
#define mians(_s_) \
{ \
    while(!isgraph(*buf_s)) \
        PTR_NEXT(); \
    char register *_ptr_ = (_s_); \
    while(isgraph(*buf_s) || *buf_s == '-') \
    { \
        *(_ptr_ ++) = *buf_s; \
        PTR_NEXT(); \
    } \
    (*_ptr_) = '\0'; \
}
    
template <typename _n_> void mian(_n_ & _x_){
    char buf_s; while(buf_s != '-' && !isdigit(buf_s)) buf_s = getchar();
    bool register _nega_ = false; if(buf_s == '-'){ _nega_ = true; buf_s = getchar(); }
    _x_ = 0; while(isdigit(buf_s)){  _x_ = _x_ * 10 + buf_s - '0'; buf_s = getchar(); } if(_nega_) _x_ = -_x_;
}
    
const int kato = 1e6 + 10;

template <typename _n_> bool cmax(_n_ &a , const _n_ &b){ return a < b ? a = b , 1 : 0; }
    
template <typename _n_> bool cmin(_n_ &a , const _n_ &b){ return a > b ? a = b , 1 : 0; }
    
int tot , yuni[10] , base[10] , ans[kato];

struct node{
    int x;
    array<int , 10> qaq;
};

map<array<int , 10> , pair<int , array<int , 10> > > pre;

map<array<int , 10> , int> dis;

inline array<int , 10> get_A(array<int , 10> a){
    array<int , 10> rev;
    for(int i = 1;i <= 4;i ++) rev[i] = a[i + 4];
    for(int i = 5;i <= 8;i ++) rev[i] = a[i - 4];
    return rev;
}

inline array<int , 10> get_B(array<int , 10> a){
    array<int , 10> rev;
    rev[1] = a[4]; 
    for(int i = 2;i <= 4;i ++) rev[i] = a[i - 1];
    rev[5] = a[8];
    for(int i = 6;i <= 8;i ++) rev[i] = a[i - 1];
    return rev;
}

inline array<int , 10> get_C(array<int , 10> a){
    array<int , 10> rev;
    rev[1] = a[1] , rev[4] = a[4] , rev[5] = a[5] , rev[8] = a[8];
    rev[2] = a[6] , rev[3] = a[2] , rev[6] = a[7] , rev[7] = a[3];
    return rev;
}

inline bool judge(const array<int , 10> a , const array<int , 10> b){
    for(int i = 1;i <= 8;i ++) if(a[i] != b[i]) return 0;
    return 1;
}

inline int BFS(array<int , 10> a , array<int , 10> b){
    if(judge(a , b)) return 0;
    queue<array<int , 10> > q;
    array<int , 10> rev1 , rev2 , rev3 , u;
    q.push(a); dis[a] = 0;
    while(!q.empty()){
        u = q.front(); q.pop();
        rev1 = get_A(u); rev2 = get_B(u); rev3 = get_C(u);
        for(int i = 1;i <= 3;i ++){
            if(i == 1){
                if(!dis.count(rev1)){
                    dis[rev1] = dis[u] + 1; pre[rev1] = {1 , u};
                    q.push(rev1);
                    if(judge(rev1 , b)) return dis[rev1];
                }
            }else if(i == 2){
                if(!dis.count(rev2)){
                    dis[rev2] = dis[u] + 1; pre[rev2] = {2 , u};
                    q.push(rev2);
                    if(judge(rev2 , b)) return dis[rev2];
                }
            }else{
                if(!dis.count(rev3)){
                    dis[rev3] = dis[u] + 1; pre[rev3] = {3 , u};
                    q.push(rev3);
                    if(judge(rev3 , b)) return dis[rev3];
                }
            }
        }
    }
    return 114514;
}

inline void copy(array<int , 10> &a , array<int , 10> b){
    for(int i = 1;i <= 8;i ++) a[i] = b[i];
}

/*BCABCCB*/

inline int Ame_(){
#ifdef AME__
    freopen(".in" , "r" , stdin); freopen(".out" , "w" , stdout); int nol_cl = clock();
#endif
    for(int i = 1;i <= 8;i ++) mian(yuni[i]);
    swap(yuni[5] , yuni[8]); swap(yuni[6] , yuni[7]);
    for(int i = 1;i <= 4;i ++) base[i] = i;
    base[5] = 8 , base[6] = 7 , base[7] = 6 , base[8] = 5;
    array<int , 10> rev1 , rev2;
    for(int i = 1;i <= 8;i ++) rev2[i] = base[i] , rev1[i] = yuni[i];
    tot = BFS(rev2 , rev1);
    printf("%d\n" , tot); int tot1 = tot;
    while(!judge(rev2 , rev1)){
        ans[tot1 --] = pre[rev1].first;
        array<int , 10> res(pre[rev1].second);
        copy(rev1 , res);
    }
    for(int i = 1;i <= tot;i ++) ans[i] == 1 ? printf("A") : ans[i] == 2 ? printf("B") : printf("C");
#ifdef AME__TIME
    LOG("Time: %dms\n", int((clock() - nol_cl) / (qwq)CLOCKS_PER_SEC * 1000));
#endif
    return ~~(0^_^0);
}
    
int Ame__ = Ame_();
    
int main(){;}

/*
2 6 8 4 5 7 3 1
*/

对于此代码,提交之后会RERE,发现是

while(!judge(rev2 , rev1)){
        array<int , 10> res(pre[rev1].second);
        copy(rev1 , res);
    }

导致的RERE,想请教这样写有什么问题吗,在本地跑RERE的数据没有问题

2020/11/12 10:35
加载中...