成都网站建设十强企业,在哪个网站做整形,wordpress动态图片不显示,东方建设官方网站题目
给定一个长为n(n2e5)的排列#xff0c;你可以执行以下操作若干次#xff0c;
每次你可以选择一个区间[l,r]#xff0c;只保留这个区间内的最小值#xff0c;将其他值都删除
删完之后前后位置会自动接上#xff0c;形成一个新的数组
求这样操作若干次后#…题目
给定一个长为n(n2e5)的排列你可以执行以下操作若干次
每次你可以选择一个区间[l,r]只保留这个区间内的最小值将其他值都删除
删完之后前后位置会自动接上形成一个新的数组
求这样操作若干次后所有得到的不同的数组的方案数
答案对998244353取模
思路来源
aging1986代码
题解
dp[i]表示只考虑[1,i]i作为最后一个元素必取时合法的方案数 考虑i能续在哪些值后面作为后继
比如序列10 5 6 8 9 7
只考虑7这个值时
1. 可以什么都不操作7可以在9后面
2. 可以操作[9,7]用7把9删了7在8后面
3. 操作[8,9,7]用7把9和8删了7在6后面
4. 操作[5,6,8,9]用5把剩下的删了7在5后面
5. 7无法在10后面因为10和7之间的值无法把4删掉 观察这个过程可以维护一个单增的栈
比如7加入前栈内从底到顶依次是5 6 8 9
7的加入使得8和9都弹栈最后把7加入进去 dp[7]dp[8]dp[9]dp[5]dp[6]
即dp值来源于两部分一部分是最终栈中的dp值之和一部分是本次弹栈的位置的dp值之和
所以可以分成两部分维护分别维护单调栈自底到顶的dp值之和和dp值的前缀和
转移时根据位置加上这两部分贡献即可注意判断栈弹空的情况 从左到右扫完之后求的是前缀合法的情况
那么此时单调栈自底到顶还是单增的栈底的值可以把上面的值再删掉
所以考虑枚举最后一个保留的位置是什么枚举单调栈中的值求和
所以最终答案就是单调栈内的dp值之和
代码
// #includebits/stdc.h
#includeiostream
// #includemap
// #includerandom
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,ll P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
//mt19937_64 rng((ll) chrono::steady_clock::now().time_since_epoch().count());
const int N3e510,mod998244353;
int t,n,c,a[N],stk[N],dp[N],sum[N],sum2[N];
int main(){sci(t);while(t--){sci(n);c0;dp[0]sum[0]1;rep(i,1,n){sci(a[i]);while(c a[stk[c]]a[i]){c--;}dp[i](sum2[c]sum[i-1])%mod;//printf(i:%d c:%d stk:%d\n,i,c,stk[c]);if(c)dp[i](dp[i]-sum[stk[c]]mod)%mod;stk[c]i;sum[i](sum[i-1]dp[i])%mod;sum2[c](sum2[c-1]dp[i])%mod;//printf(i:%d dp:%d\n,i,dp[i]);}printf(%d\n,sum2[c]);//最后一个值是哪个值栈底小栈顶大左侧自然满足右侧没有被pop说明也满足}return 0;
}
