题目来源:
题意:给定排列 p,每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价,求给 p 排升序最优策略下最小代价的期望,对 998244353 取模。
思路:最优策略,感觉有点像dp,但其实不是,枚举又怕超时间了,可以将问题等价转化一下:
因为枚举的是可以设置分割点的区间,分割点k格一个,所以把这个区间向前移动k的倍数格
因此,可以将所有的区间向前移动,一次k格,与其他区间出现交集,
但是需要考虑两端的交集,这是一个问题。
可以将一个区间的左端点+1,右端点右边的位置-1,然后求前缀和。这样可以得到,每个位置的数值就是重叠在上面区间的个数。
最后找一下有没有满足条件的数值。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; #define INF 0x3f3f3f3f int t,n,k; #define N 5e5+5 int a[500005]; unordered_map<ll,int>m; int f[500005]; int main() { cin>>q; while(q--) { cin>>n>>k; bool flag=false; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]>k||a[i]<1)flag=true; f[i]=0; } if(flag) { printf("NO\n"); continue; } int cnt=0; f[0]=1; m.clear(); for(int i=1;i<=n;i++) { if(m[a[i]]==0)cnt++; m[a[i]]++; if(i>k) { m[a[i-k]]--; if(m[a[i-k]]==0)cnt--; } if(cnt==k||cnt==i) f[i]=i-k>=0?f[i-k]:1; } m.clear(); cnt=0; for(int i=n;i>=max(n-k,0);i--) { if(cnt==n-i&&f[i]==1) { flag=true; break; } if(m[a[i]]==0) cnt++; m[a[i]]++; } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }