6198
Update
又双叒叕炸了的话就到我博客上去看吧。
-
2020-7-6 这篇题解已经咕了大半年了,暑假里又开始更新
-
2020-7-10 这篇题解写完了!
引言
谔谔,月赛时做完了
算法AC
后来瞄了瞄题解发现大家都是至少
的算法
于是滚回去加优化了,把时间复杂度加速到了
的层次
然鹅实际运行时间并没有多大变化,我谔谔
那么,我是如何加速的呢?
先看原算法。
O(n^2) 算法
10 分程序
算法思路: 考虑使用动态规划解决此问题。
对于输入数据数列(记作
)前
项,欲求其答案,是否可以由前
项的答案经一定的修改后获取原序列对此的答案?发现可以。
怎么做?
在第
时刻,对于第
项的答案,设为
易证
跑遍
到
。(基于
的定义)
建立辅助数组 M[],表示
当前时刻前
项至少两项的连续上升子序列的最后一项的值的位置,如有多个位置满足,取最后一项。
请仔细咀嚼一下上面那句话,这句话十分重要。
则定理:
-
\forall A_n>A_{n-1},B_{n,n}=n,B_{n,i}=B_{n-1,i}.\\ 把M[
A_n ]赋值为
n （显然,此时单调栈
\mathrm{push} 了一次而未
\mathrm{pop} ）
-
\forall A_n\le A_{n-1}, 则
\mathrm{push} 了共
A_{n-1}-A_n+1 次,用数组M往回翻一下,翻的过程中,
\\B_{n,n}=\mathrm{M}[A_n],B_{n,i}=B_{n-1,i}+1 ,而最前面的
$B_{n,i}=B_{n-1,i}
然后我们发现
就是答案。
空间爆炸
可是二维数组B开不下(
项)!
空间复杂度是
的！
前功尽弃了么?
不！
考虑使用滚动数组B,则可以把空间榨取到
滚动数组就不细讲了,参见以下部分代码,可以意会。
注意以下代码是由
开始计数的!
...
int A[1000010],B[1000010];
int M[1000010]={0};
int main()
{
int n;scanf("%d",&n);
for(int i=0;i<n;i++)//read
scanf("%d",A+i);
for(int i=1;i<n;i++)
{
if(A[i]<=A[i-1])
{
for(int j=M[A[i]];j<i;j++)B[j]++;//QAQ
B[i]=M[A[i]]+1;
}
else M[A[i]]=i,B[i]=i+1;
}
for(int i=0;i+1<n;i++)printf("%d ",B[i]);
printf("%d\n",B[n-1]);
return 0;
}马蜂清奇就不怪我了
代码源码 (内容不太一样,是我比赛时原码)
发现
AK.
100 分程序
先不考虑带
的情况,观察样例二,发现什么?
样例二输入输出数据:
10
1 1 2 2 3 2 3 3 4 5 2 1 5 4 6 3 8 7 9 10不难发现:
-
\forall A_n>A_{n-1},A_n=A_{n-1}+1 (显然,上升时单调栈只会
\mathrm{push} 一次而不
\mathrm{pop} ,故如此)
- 首项值为
1 (同理)
考虑上述
分程序的过程,易有总使
中每项值为
的值最优情况为前一项的值再
,而首项值为
。
于是如此
预处理即可。
然后你就切了这道题。
代码略。
O(n) 算法
以上算法很快,但是如果最坏情况一切
,直接
给T掉
其实,原先上述那份代码,我打了\"QAQ\"标记的地方,可以再优化!
连续一段区间同时增加相同值,最后求总序列,你想到了什么?
树状数组
线段树
考虑使用数据结构差分数列解决。
差分数列的讲解这里与网上都有很多,此处就略去不谈了。
贴一发
的AC代码:
#include<stdio.h>
#include<algorithm>
int A[1000010],B[1000010];
int M[1000010]={0};
int main()
{
int n,wil;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",A+i);
wil=A[0]=B[0]=1;M[1]=0;
for(int i=1;i<n;i++)
if(A[i]==-1)
A[i]=A[i-1]+1;
for(int i=1;i<n;i++)
{
if(A[i]<=A[i-1])
{
B[M[A[i]]]++;
B[i]=M[A[i]]-wil;
wil=M[A[i]]+1;
}
else
{
B[i]=i+1-wil;
M[A[i]]=i;
wil=i+1;
}
}
printf("%d",wil=B[0]);
for(int i=1;i<n;i++)printf(" %d",wil+=B[i]);
putchar('\n');
return 0;
}最后
谢谢观赏!