LibreOJ 516

【Problem Link】

#516. 「LibreOJ β Round #2」DP 一般看规律

【题意】

输入n个数,m个替换规则,x换成y.输出每次替换后最近的两个相同的数相距多少.如果没有相同的,输出MAX_INT.

【题解】

每个数字只与他的前驱和后继产生贡献。构建n个set,每次将较小的暴力合并到大的上面,通过lower_bound来找到他的前驱和后继。懒得离散化可以用map来存set。

【Source Code】

github: #516 DP一般看规律.cpp


#include<bits/stdc++.h>
using namespace std;
int ans,n,m,num,x,y;
map<int,set<int> > mp;///数字->数字下标集映射

void insert_update(int q,int index){
    set<int> &r=mp[q];
    set<int>::iterator it=r.lower_bound(index);
    if(it!=r.end()) ans=min(ans,*it-index);///右边相邻第一个
    if(it!=r.begin()) it--,ans=min(ans,index-*it);///左边相邻第一个
    r.insert(index);
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        ans=2147483647;mp.clear();
        for(int i=0;i<n;++i){
            scanf("%d",&num);
            insert_update(num,i);
        }
        for(int i=0;i<m;++i){
            scanf("%d%d",&x,&y);
            if(x==y){printf("%d\n",ans);continue;}
            set &r=mp[x],&t=mp[y];
            if(r.size()>t.size())swap(r,t);
            for(set<int>::iterator si=r.begin();si!=r.end();si++)
                insert_update(y,*si);
            r.clear();
            printf("%d\n",ans);
        }
    }
    return 0;
}