\(100+100+40+0\)，T3 卡时没卡对挂了 \(20\)。
后来发现赛时 T3 是时间复杂度和正确性都是对的，只是常数大导致我以为它跑不出来。
A.集合
给定一个序列，求有多少个子区间满足这个区间的数的集合的所有值域连续段长度都不超过 \(k\)。
答案满足单调性，双指针统计答案，权值线段树维护最长值域连续段，时间复杂度 \(O(n\log n)\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
int n,k,a[MAXN],cnt[MAXN];long long ans;
struct tree{int ansl,ansr,ans;}t[MAXN<<2];
inline void change(int l,int r,int p,int x)
{
if(l==r){t[p].ansl=t[p].ansr=t[p].ans=(cnt[x])?1:0;return ;}
int mid=(l+r)>>1;
if(x<=mid) change(l,mid,p<<1,x);
else change(mid+1,r,p<<1|1,x);
t[p].ansl=t[p<<1].ansl+(t[p<<1].ansl==(mid-l+1)?t[p<<1|1].ansl:0);
t[p].ansr=t[p<<1|1].ansr+(t[p<<1|1].ansr==(r-mid)?t[p<<1].ansr:0);
t[p].ans=max(max(t[p<<1].ans,t[p<<1|1].ans),t[p<<1].ansr+t[p<<1|1].ansl);
return ;
}
int main()
{
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>k;for(int i=1;i<=n;++i) cin>>a[i];
++cnt[a[1]];change(1,n,1,a[1]);
for(int l=1,r=2;l<=n;++l)
{
while(r<=n)
{
++cnt[a[r]];if(cnt[a[r]]==1) change(1,n,1,a[r]);
if(t[1].ans<=k){++r;continue;}
--cnt[a[r]];change(1,n,1,a[r]);break;
}
ans+=(r-l);--cnt[a[l]];if(!cnt[a[l]]) change(1,n,1,a[l]);
}
cout<<ans<<'\n';return 0;
}
B.差后队列
定义差后队列为一个数据结构，支持两种操作：
pop随机删除一个不是最大值的的数。如果只有一个数则删除该数。push插入一个数。
给定操作序列，求每次删的数的期望，以及每个数期望被删的时间（如果到最后也没被删则删除时间为 \(0\)）。
一个数如果不是最大值了，就永远不可能是最大值了，最大值只会在只有一个数时被删去。
分开考虑，先考虑求每次删除的数的期望，维护当前最大值 \(max\) 和“其他值乘上其未被删去的概率”的和 \(sum\) 与其他值的个数 \(cnt\)。
pop：
- 没有一个数：插入的数作为 \(max\)。
- 有至少一个数：\(x\) 与 \(max\) 比较大小，大的作为 \(max\)，小的插入其他值中。
push：
- \(cnt=0\)：期望是 \(max\)，然后将 \(max\) 删去。
- \(cnt>0\)：期望是 \(sum\times\dfrac{1}{cnt}\)，将 \(sum\gets sum\times(1-\dfrac{1}{cnt})\)。
然后考虑求每个数被删掉的期望时间。
如果一个数是作为最大值被删掉的，那么它被删掉的时间是一定且确定的，只考虑从“其他值”中被删掉的数的期望被删的时间。
记一次 \(cnt>0\) 的 push 操作时（\(i\) 时）的 \(cnt\) 为 \(c_i\)。
对于一个在 \(t\) 时刻加入“其他值”中的数，其被删掉期望时间是 \(\sum\limits_{i\in[t,n],c_i>0}\dfrac{i}{c_i}\times \prod\limits_{j\in[t,i-1],c_j>0} (1-c_j)\)。
相当于每个这样的答案都对应了一段后缀。所以离线下来。从 \(n\to 1\) 扫描，若为 push 操作且 \(c_i>0\) 则使 \(Ans\gets \dfrac{i}{c_i}+(1-\dfrac{1}{c_i})\times Ans\)，然后使所有 \(t_j=i\) 的从“其他值”中被删掉的数 \(j\) 的 \(ans_j=Ans\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
const int MAXN=1e6+10,MOD=998244353;
int n,t[MAXN],c[MAXN];
long long inv[MAXN],MAX,maxn,sum,cnt,ans[MAXN];
typedef pair<int,int> P;vector <P> v;
int main()
{
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;inv[0]=inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=(-inv[MOD%i]*(MOD/i)%MOD+MOD)%MOD;
for(int i=1;i<=n;++i)
{
int opt,x;cin>>opt;
if(!opt)
{
cin>>x;
if(!MAX) MAX=x,maxn=i;
else if(x>MAX) sum+=MAX,MAX=x,t[maxn]=i,maxn=i,cnt+=1;
else sum+=x,t[i]=i,cnt+=1;sum%=MOD;
}
else
{
if(!cnt){ans[i]=MAX,ans[maxn]=i,MAX=0;}
else
{
ans[i]=sum*inv[cnt]%MOD,c[i]=cnt;
sum=(sum+MOD-ans[i])%MOD,cnt-=1;
}
}
}
for(int i=1;i<=n;++i) if(t[i]) v.push_back({t[i],i});
sort(v.begin(),v.end());long long ANS=0;
for(int i=n,cur=v.size()-1;i>=1;--i)
{
if(c[i]) ANS=(ANS*(c[i]-1)%MOD+i)%MOD*inv[c[i]]%MOD;
while(cur>=0&&v[cur].first==i)
ans[v[cur].second]=ANS,--cur;
}
for(int i=1;i<=n;++i) cout<<ans[i]<<' ';
cout<<'\n';return 0;
}
C.蛋糕
记 \(F(l,r,p)\) 为 \([l,r]\) 中都只考虑 \(p\) 层以上的部分的最小代价，答案为 \(F(1,n,0)\)。
记 \(min_{l,r}\) 为 \([l,r]\) 中最小的数的下标，\(max_{l,r}\) 同理。
对于 \(F(l,r,p)\) 考虑先对于所有 \([l,r]\) 的 \(p+1\sim a_{min_{l,r}}\) 层都切下来的最小代价，为：
\[F(l,min_{l,r}-1,a_{min_{l,r}}+1)+F(min_{l,r}+1,r,a_{min_{l,r}}+1)+\dfrac{(a_{max_{l,r}}-p+a_{max_{l,r}}-(a_{min_{l,r}}-1))\times (a_{min_{l,r}}-p)}{2} \]另一种方法是将最大值那一列拿走单独切掉，最小代价为 \(F(l,max_{l,r}-1,p)+F(max_{l,r}+1,r,p)+(a_{max_{l,r}}-p)\)，与前者取 \(\min\)。
肯定是从这两种情况转移，可以感性理解，题解说有效状态数是 \(O(n^2)\) 的，可以感性理解。
考虑枚举区间最大值的最底下的块如何划分。一种方法是选择最大值所在的一列；否则设选择区间 \(x,y\) 同时减去其最小值，容易发现这种操作改为先操作 \([l,r]\) 再操作 \([x,y]\) 代价不变，并且周围两边更小了，因此这样不劣。因此转移变成了 \(O(1)\)。
有效状态数实际上是 \(O(n^2)\) 的。首先发现必要条件是 \(l=1\vee a_{l-1}< k\vee a_{l-1}>\max_{i\in[l,r]}a_i\) 且 \(r=n\vee a_{r+1}< k\vee a_{r+1}>\max_{i\in[l,r]}a_i\) ，具体来说这个条件是考虑缩小边界的时候要么用最小值更新 \(k\) 要么用最大值缩小，所以区间两个端点应该都要满足这两条件。然后发现对于每个 \(k\)，其满足条件的 \([l,r]\) 区间的数量实际上是 \(O(n)\) 个的。实际上后面这个东西是相当于把所有 \(a_i>k\) 的极长段建笛卡尔树。
手写哈希表记搜可过。
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3010, MH = 10000141;
int n, a[MAXN], pre[MAXN], f[MAXN][MAXN], g[MAXN][MAXN], c;
int h[MH + 10];
struct E
{
long long v, w, t;
} e[6000050];
void A(long long x,int a)
{
e[++c] = {x, a, h[x % MH]};
h[x % MH] = c;
}
int Q(long long x)
{
for (int i = h[x % MH]; i; i = e[i].t)
if (e[i].v == x)
return e[i].w;
return -1;
}
inline int DO(int l, int r, int p)
{
if (l > r)
return 0;
if (l == r)
return a[l] - p;
if (Q(((1ll * l * MAXN + r) << 32) + p)!=-1)
return Q(((1ll * l * MAXN + r) << 32) + p);
int m = f[l][r], ans = 0, MAX = a[g[l][r]];
ans = ((MAX << 1) - p - a[m] + 1) * (a[m] - p) / 2 + DO(l, m - 1, a[m]) + DO(m + 1, r, a[m]);
ans = min(ans, DO(l, g[l][r] - 1, p) + DO(g[l][r] + 1, r, p) + (MAX - p));
return A(((1ll * l * MAXN + r) << 32) + p, ans), ans;
}
signed main()
{
freopen("cake.in", "r", stdin);
freopen("cake.out", "w", stdout);
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i], pre[i] = pre[i - 1] + a[i];
for (int i = 1; i <= n; ++i)
{
f[i][i] = g[i][i] = i;
for (int j = i + 1; j <= n; ++j)
f[i][j] = (a[j] < a[f[i][j - 1]]) ? j : f[i][j - 1],
g[i][j] = (a[j] > a[g[i][j - 1]]) ? j : g[i][j - 1];
}
cout << DO(1, n, 0) << '\n';
return 0;
}
D.字符替换
不会。
标签：cnt,NOIP,22,int,max,sum,MAXN,联测,include From： https://www.cnblogs.com/int-R/p/NOIP-A-22.html