首页 > 其他分享 >[ARC115E] LEQ and NEQ 题解

[ARC115E] LEQ and NEQ 题解

时间:2024-09-27 14:45:44浏览次数:9  
标签:int 题解 sum ARC115E times LEQ MAXN aligned dp

我这场打的 VP,结果 E 思考的时间比 A 还少。。

但是我觉得我能想出这道题还是很有意义的,写篇题解记录一下。

首先应该都不难想到动态规划吧?我们先使用暴力 DP:设 \(dp_{i,j}\) 表示处理完前 \(i\) 个数,第 \(i\) 个数为 \(j\) 的方案数。我们考虑进行分类讨论:

  • \(a_i≥a_{i-1}\):此时 \(j\) 有两种取值范围,分别是 \(1\leq j\leq a_{i-1}\) 以及 \(a_{i-1}<j\leq a_i\)。对于后者的范围,我们发现 \(j\) 怎么取都不会影响到 \(i-1\) 的取值,我们设 \(f_i=\sum_{1\leq j\leq a_i}dp_{i,j}\),因此这一部分的 \(dp_{i,j}=f_{i-1}\)。对于 \(1\leq j\leq a_{i-1}\),我们就要考虑到 \(x_{i-1}≠x_i\) 的限制。根据容斥原理,我们用 \(f_{i-1}\) 减去 \(dp_{i-1,j}\) 的情况就行了,于是得到下面的转移:

\[dp_{i,j}= \begin{cases} f_{i-1}-dp_{i-1,j} & 1\leq j\leq a_{i-1} \\ f_{i-1} & a_{i-1}<j\leq a_i \end{cases} \]

  • \(a_i<a_{i-1}\):这个时候无论 \(j\) 取 \([1,a_i]\) 的什么值都有可能受到 \(x_{i-1}\) 的影响。不过思路还是用上面的容斥,我们得到:

\[dp_{i,j}=f_{i-1}-dp_{i-1,j} \]

知道这些之后,我们要得到的答案就是:

\[ans=\sum_{i=1}^n\sum_{j=1}^{a_{i}}dp_{i,j}=\sum_{i=1}^nf_i \]

因此,若要在题目所给的数据范围限制下快速得到答案,我们必须想办法快速处理出 \(f_i\) 的值。

0x01

对于 \(a_i≥a_{i-1}\) 的情况,我们直接加和:

\[\begin{aligned} f_i&=\sum_{j=1}^{a_{i-1}}(f_{i-1}-dp_{i-1,j})+\sum_{j=a_{i-1}+1}^{a_i}f_{i-1}\\ &=a_{i-1}\times f_{i-1}+(a_i-a_{i-1})\times f_{i-1}-\sum_{j=1}^{a_{i-1}}dp_{i-1,j}\\ \end{aligned} \]

根据 \(f_i\) 的定义可知,等式右边减去的式子其实就是 \(f_{i-1}\),因此合并同类项得到:

\[f_i=f_{i-1}\times (a_i-1) \]

0x02

对于 \(a_i<a_{i-1}\) 的情况,我们同样进行数学计算:

\[\begin{aligned} f_i&=\sum_{j=1}^{a_i}(f_{i-1}-dp_{i-1,j})\\ &=a_i\times f_{i-1}-\sum_{j=1}^{a_i}dp_{i-1,j} \end{aligned} \]

化简最多也就能变成这样,内层的求和还是不能省去。本题有价值的思路来了:我们想象一下 \(\sum_{j=1}^{a_i}dp_{i-1,j}\) 的实际意义。我们假设现在的 \(a_{i-1}\) 不再是原来的 \(a_{i-1}\),而是被强制修改为了 \(a_i\) 的值,那么 \(\sum_{j=1}^{a_{i-1}}dp_{i-1,j}=f_{i-1}\) 其实就是 \(\sum_{j=1}^{a_i}dp_{i-1,j}\)。

于是 \(\sum_{j=1}^{a_i}dp_{i-1,j}\) 就相当于把 \(a_{i-1}\) 换成 \(a_i\) 之后所处理出来的 \(f_{i-1}\),令这个 \(f_{i-1}\) 为 \(f'_{i-1}\)。所以:

\[f_{i}=a_i\times f_{i-1}-f'_{i-1} \]

我们再继续展开,去考虑 \(f'_{i-1}\) 的求法。其实就是不断重复上述过程进行递归,直到当前已经递归到了边界或者 \(a_{i-1}\leq a_i\) 的情况。

但是极限数据不允许我们暴力递归。我们令 \(f'_j\) 表示当 \(a_j=a_i\) 时处理出来的 \(f_j\)。为了方便分析,我们造一组数据 \(a=\{1,3,3,3,2\}\)。接着,我们按照上述方法求 \(f_5\):

\[\begin{aligned} f_5&=a_5\times f_4-f'_4\\ &=a_5\times f_4-a_5\times f_3+f'_3\\ &=a_5\times f_4-a_5\times f_3+a_5\times f_2-f'_2\\ &=a_5\times f_4-a_5\times f_3+a_5\times f_2-f_1\times (a_5-1)\\ &=a_5\times (f_4-f_3+f_2)-f_1\times (a_5-1) \end{aligned} \]

结合上述推理,我们可以使用单调栈求出 \([1,i-1]\) 中最靠后的 \(\leq a_i\) 的元素下标 \(l_i\),则有:

\[f_i=a_i\times(f_{i-1}-f_{i-2}+f_{i-3}\dots ±f_{l_i+1})-[±f_{l_i}\times(a_i-1)] \]

不难发现可以通过将 \(i\) 分为奇数和偶数去处理前缀和,然后求出 \(f_{i-1}-f_{i-2}+f_{i-3}\dots\) 的值,后面的 \(f_{l_i}\times (a_i-1)\) 的正负判断也可以利用 \(i-l_i\) 的奇偶。

最后注意一下各种取模就行了,代码也比较短小:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
const int MOD=998244353;
int n,a[MAXN];
long long dp[MAXN],sum[MAXN],num[MAXN];
int stk[MAXN],cnt,l[MAXN];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		while(cnt&&a[stk[cnt]]>a[i])	cnt--;
		l[i]=stk[cnt],stk[++cnt]=i;
	}
	dp[1]=a[1]%MOD,sum[1]=a[1]%MOD;
	for(int i=2;i<=n;i++)
	{
		if((i-1)&1)	dp[i]=sum[i-1]+num[l[i]]-sum[l[i]]-num[i-1]+MOD*2,dp[i]%=MOD;
		else	dp[i]=num[i-1]+sum[l[i]]-num[l[i]]-sum[i-1]+MOD*2,dp[i]%=MOD;
		dp[i]*=a[i],dp[i]%=MOD;
		int g=((i-l[i]-1)&1)?-1:1;
		if(!l[i])	dp[i]+=g*a[i],dp[i]+=MOD,dp[i]%=MOD;
		else	dp[i]+=dp[l[i]]*(a[i]-1)%MOD*g,dp[i]+=MOD,dp[i]%=MOD;
		if(i&1)	sum[i]=sum[i-2]+dp[i],num[i]=num[i-1];
		else	num[i]=num[i-2]+dp[i],sum[i]=sum[i-1];
		sum[i]%=MOD,num[i]%=MOD;
	}
	cout<<dp[n];
	return 0;
}

标签:int,题解,sum,ARC115E,times,LEQ,MAXN,aligned,dp
From: https://www.cnblogs.com/SuporShoop/p/18435710

相关文章

  • 9.27今日错题解析(软考)
    目录前言信息安全——网络攻击算法基础——二分查找数据库系统——数据库设计过程前言这是用来记录我每天备考软考设计师的错题的,今天知识点为网络攻击、二分查找和数据库设计过程,大部分错题摘自希赛中的题目,但相关解析是原创,有自己的思考,为了复习:),最后希望各位报考......
  • [GXOI/GZOI2019] 逼死强迫症 题解
    看到\(N\leq2\times10^9\)的范围,一眼矩阵快速幂优化DP。首先考虑朴素DP怎么写。根据题目所给信息,我们设\(dp_{i,0}\)表示前面\(i\)个方砖,并且已经使用了\(2\)个\(1\times1\)的方砖,\(dp_{i,1}\)则表示前面\(i\)个方砖,没有使用任何一个\(1\times1\)的方砖。......
  • [CERC2015] Digit Division 题解
    \(O(n^2)\)做法和大部分人最开始一样,我也想的是DP。设\(dp_i\)表示用前面\(i\)个字符拆分得到的答案。既然是统计方案数,我们肯定是根据前面的答案累加。考虑在\([1,i-1]\)中选择一个\(j\),如果\([j+1,i]\)的字符组成的数字能够被\(m\)整除,那么\(dp_i\)就可以累加......
  • [JLOI2015] 有意义的字符串 题解
    拿到题目,我们首先分析一下这个奇怪的式子:\[\lfloor(\frac{b+\sqrt{d}}{2})^n\rfloor~\text{mod}~p\]重点肯定是在里面的那个式子里面,最显眼的肯定也就是那个\(\sqrt{d}\),根据整体形式,我们可以联系一元二次方程的求根公式\(x=-\dfrac{-b\pm\sqrt{b^2-4ac}}{2a}\),这里也是一......
  • 「KDOI-06-S」消除序列 题解
    分享一个应该很少人想到的做法。首先贪心地想,第一种操作肯定最多选择一次。比如如果选择了下标\(i\)和\(j\)进行第一种操作,那么就等价于在\(\max\{i,j\}\)进行了一次操作。由于代价是非负数,则我们最多只用执行一次。当然也可以不使用这种操作。有了这个思路,我们先考虑不使......
  • 「TAOI-2」Ciallo~(∠・ω< )⌒★ 题解
    手玩了一个小时终于做出来了,这不得写一篇题解记录一下??下面设\(s\)的长度为\(n\),\(t\)的长度为\(m\)。考虑分类讨论:如果\(s\)中有一个子串\(s'\)与\(t\)完全相同(可以用哈希进行比较),设\(s'\)是\(s\)的第\(l\)到第\(r\)个字符组成的字符串,则我们可以删除\([1,......
  • 三星G8 OLED显示器S34BG850SC,使用DP线连接电脑,显示器黑屏问题解决。
    这个问题在网上好像很多人问,但是每个人的情况不同,总之我也是遇到了。事情大概:PC机显卡的DP口通过显示器自带的MiniDP线和显示器相连,这个没什么好说的了,原配只送MiniDP线,想必买这台显示器的人都是先用的这根线。然而我有一台NUC,通过雷电口也连接到了这台显示器。所以我这台G8是......
  • [TJOI2010] 天气预报 题解
    分析一下题目,大致意思就是给定一组常数\(a_i\),然后有一个递推式\(w_i=\sum_{j=1}^{n}w_{i-j}\timesa_{j}\),让你求出\(w_m\)对于\(4147\)取模的值。根据这个\(1\leqm\leq10^7\)的恐怖范围,姑且算到了\(O(m)\)的时间复杂度。但是观察一下这个递推式,发现\(O(m)\)跑......
  • ABC262G 题解
    LISwithStack观察到\(n\le50\),考虑区间dp。设\(dp(l,r,x,y)\)表示区间\([l,r]\)中选出的子序列的最小值\(\gex\),最大值\(\ley\)的方案数。根据栈的性质,设元素\(x\)入栈的时间为\(in_x\),出栈时间为\(out_x\),那么所有元素构成的区间\([in_x,out_x]\)两......
  • 2024-2025专题二题单 - 题解
    A-MoneyinHand(记忆化搜索)原题链接题解B-GoodGraph(并查集)原题链接题解C-IceSkating(dfs求连通块)原题链接题解D-TheLakes(dfs求连通块,连通块内累加,多组数据注意初始化)原题链接题解E-LearningLanguages(建图,dfs统计连通块个数,答案为个数-1)原题链接题......