首页 > 代码库 > Unique Encryption Keys (思维题 预处理)
Unique Encryption Keys (思维题 预处理)
题目
题意:给m个数字, q次询问, 询问b到e之间如果有重复数字就输出, 没有就输出OK
思路:用f[i]数组 记录从i开始向后最近的有重复数字的 位置, 如 1 3 2 2, 则f[1] = 4;
如果离a最近的重复数字的位置 都大于b, 就说明没有重复数字。
f[]数组需要预处理,从后向前。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <map> 6 #define Min(a, b)((a)>(b)?(b):(a)) 7 using namespace std; 8 const int maxn = 1000000+10; 9 int a[maxn], f[maxn]; 10 11 int main() 12 { 13 int m, q, b, e, i; 14 while(~scanf("%d%d", &m, &q)) 15 { 16 if(m==0&&q==0) 17 break; 18 for(i = 1; i <= m; i++) 19 scanf("%d", &a[i]); 20 memset(f, 0, sizeof(f)); 21 map<int, int>mp; 22 f[m] = m+1; 23 mp[a[m]] = m; 24 for(i = m-1; i >=1; i--) 25 { 26 if(mp[a[i]]==0) 27 f[i] = f[i+1]; 28 else 29 f[i] = Min(mp[a[i]], f[i+1]); 30 mp[a[i]] = i; 31 } 32 while(q--) 33 { 34 scanf("%d%d", &b, &e); 35 if(f[b]>e) 36 cout<<"OK"<<endl; 37 else 38 cout<<a[f[b]]<<endl; 39 } 40 } 41 return 0; 42 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。