用map和兩個數組保存和一個數左右距離最近相同的數的位置

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <map> #define FRER() freopen("in.txt","r",stdin) #define FREW() freopen("out.txt","w",stdout) #define go int T;cin>>T;while(T--) using namespace std; const int maxn = 2e5 + 7; int a[maxn]; map<int,int> cur1; map<int,int> cur2; int Left[maxn]; int Right[maxn]; bool judge(int l,int r){if(r-l<=1) return true;int i = l , j = r-1;int pos = -1;while(i<=j){if(Left[i]<l&&Right[i]>=r){pos = i;break;}if(Left[j]<l&&Right[j]>=r){pos = j;break;}i++;j--;}if(pos==-1) return false;return judge(l, pos)&&judge(pos+1, r);return true; } int main(){//FRER();//FREW();int n;go{cur1.clear();cur2.clear();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);//cout<<cur1[a[i]]<<"**"<<endl;if(!cur1[a[i]]) Left[i] = -1;else Left[i] = cur1[a[i]];cur1[a[i]] = i;}for(int i=n;i>=1;i--){//cout<<cur2[a[i]]<<"**"<<endl;if(!cur2[a[i]]) Right[i] = 0x3f3f3f3f;else Right[i] = cur2[a[i]];cur2[a[i]] = i;} // for(int i=1;i<=n;i++){ // cout<<Left[i]<<" "<<Right[i]<<endl; // }printf("%s\n",judge(1, n+1)?"non-boring":"boring");} }

?

轉載于:https://www.cnblogs.com/seven7777777/p/10278655.html

總結

以上是生活随笔為你收集整理的UVA 1608 Non-boring sequences(瞎搞)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。