思维|Codeforces Round #531 E. Monotonic Renumeration（思维题）思维|codeforces

题目链接

题意：
给出一个ａ数组，让你构建ｂ数组，要求满足下列条件：

b1=0;

for every pair of indices i and j such that 1≤i,j≤n, if ai=aj, then bi=bj (note that if ai≠aj, it is still possible that bi=bj);

for every index i∈[1,n?1] either bi=bi+1 or bi+1=bi+1.
最后要求的是组成ｂ数组的方案数目

【思维|Codeforces Round #531 E. Monotonic Renumeration（思维题）】思路：
首先要注意到两个相同的数之间的数一定相同，我们把整个ａ数组分成若干块，每块之间满足b[i] = b[i + 1]或者b[i] + 1 == b[i + 1]，每块内部全都要一致。至于怎么分成若干块，显然，单独看一个数，从这个数出现开始，到这个数最后一次出现的位置之间肯定是要看成是一块的。从某种程度上来说，每个数代表了一个区间，我们要把所有有交集的区间并起来作为一个块。举个例子来说明一下：假如 a = {1, 2, 1, 3, 3, ２, 4, 4, 7}，那么就可以分成两块分别是{1, 2, 1, 3, 3, 2}, {4, 4, 7}，解释一下，很显然两个１肯定要放在一块内，二者之间还夹了一个２，所以数字２的区间要和数字１的区间合并在一起，就成了{1, 2, 1, 3, 3, 2}。求出块数，因为第一块已经定了，为０（因为题目规定b[1] = 0)，所以说第一块的情况为一种，其余的每块都有两种情况，所以最终的答案就是2x-1中情况（其中ｘ代表块数）。

#include #include #include #include #include using namespace std; typedef long long ll; const int maxn = 2 * 1e5 + 100; const ll mod = 998244353; int n; int a[maxn]; int overpos[maxn]; map < int, int > ma; ll qpow(ll a, ll b) {//快速幂取模 ll res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }int main() { //freopen("in.txt", "r", stdin); cin >> n; for(int i = 1; i <= n; ++ i) { scanf("%d", &a[i]); } for(int i = n; i >= 1; i --) {//求出每个a[i]出现的最后位置，也就是从后往前第一次出现的位置 if(ma.find(a[i]) == ma.end()) { ma[a[i]] = i; } overpos[i] = ma[a[i]]; } int begins = 1; ll ans = 0; while(begins <= n) { ans++; int en = overpos[begins]; for(int i = begins; i <= overpos[en] && i <= n; ++ i) {//注意跳出循环的条件，数组下标是en en = max(en, overpos[i]); } begins = en + 1; } ll cnt = qpow(2, ans - 1); cout << cnt << endl; return 0; }