Codeforces C. k-Amazing Numbers (#673 Div.2) (思维 / 区间枚举 / 最小前缀)

本文主要是介绍Codeforces C. k-Amazing Numbers (#673 Div.2) (思维 / 区间枚举 / 最小前缀)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题意： 给出一个序列a，试问对于 1~n 的所有k，是否所有k长度的连续区间里的数都有共同的数交集，并输出这个数集中的min，否则输出 -1.

思路：

• 考虑相同数之间最少需要多长的k才能都包含到。枚举一个数和序列开头，中间数之间的差，最后一个数和序列结尾。
• 用一个ans[k]记录最少需要长度的k中最小的数字是哪个。ans[k]=min(ans[k],i)。
• 最后再维护下ans的最小前缀即可。

代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
//#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9 + 7;
const int  N = 3e5 + 100;ll t, n, ans[N];
vector<ll> v[N];
int main()
{IOS;cin >> t;while(t --){cin >> n;for(ll i = 0; i <= n+10; i ++) ans[i] = inf, v[i].clear();for(ll i = 1; i <= n; i ++){ll x; cin >> x;v[x].push_back(i);}for(ll i = 1; i <= n; i ++){if(!v[i].empty()){ll md = 0;for(ll j = 1; j < v[i].size(); j ++)md = max(md, v[i][j]-v[i][j-1]);md = max(md, v[i].front());md = max(md, n-v[i].back()+1);ans[md] = min(ans[md],i);}}for(ll i = 2; i <= n; i ++) ans[i] = min(ans[i], ans[i-1]);for(ll i = 1; i <= n; i ++){if(ans[i] != inf) cout << ans[i] << " ";else cout << "-1" << " ";}cout << endl;}
return 0;
}

这篇关于Codeforces C. k-Amazing Numbers (#673 Div.2) (思维 / 区间枚举 / 最小前缀)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---