2022牛客OI赛前集训营-提高组（第六场） 赛后总结

A.我是 A 题

考场一顿容斥+单调栈+$O(n^3)O(n^3)$ 但基本 $n\le 20n\backslash le20$ 的枚举，然而还是 $O(nlogn)O(nlogn)$ 大常数被卡95pts（太菜不会 pair 类型的基数排序）QAQ。

首先我们由题可以分析出两个性质：

$11$.每次操作至少有一个 A/B/C；

$22$.数据完全随机。

因此可以先找到 最大的 $cc$ 记为 $highhigh$，答案累加上 $A\times B\times highA\backslash times\; B\backslash times\; high$。

接着从 $CC$ 枚举到 $high+1high+1$，记 $maxh[i]maxh[i]$ 表示 $aa$ 坐标为 $ii$ 时，$bb$ 坐标的后缀最大值，每次答案累加上 ${\sum }_{i=1}^{A}maxh[i]\backslash sum\_\{i=1\}^A\; maxh[i]$。

这里从 $CC$ 开始枚举是因为 $cc$ 坐标大的会影响坐标小的，由于 $A,B,CA,B,C$ 与 $nn$ 同阶，理论时间复杂度 $O(n^2)O(n^2)$，但由于数据随机，为 $O(\mathrm{能}\mathrm{过})O(能过)$。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __int128_t i128;
const int MAXN = 3e7 + 10;
int n, A, B, C, u[MAXN], v[MAXN], w[MAXN],maxh[MAXN];
i128 ans=0;
ull Rand (ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
ull work(ull x,ull y)
{
    x^=(x<<23);
    return x^y^(x>>17)^(y>>26);
}
void GetData () {
    ull x, y;
    cin >> n >> A >> B >> C >> x >> y;
    for (int i = 1; i <= n; i++) {
        u[i] = Rand(x, y) % A + 1;
        v[i] = Rand(x, y) % B + 1;
        w[i] = Rand(x, y) % C + 1;
        if (Rand(x, y) % 3 == 0) u[i] = A;
        if (Rand(x, y) % 3 == 0) v[i] = B;
        if ((u[i] != A) && (v[i] != B)) w[i] = C;
    }
}
void print(i128 x)
{
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
void solve()
{
    int high=0;
    for(int i=1;i<=n;++i) if(u[i]==A && v[i]==B) high=max(high,w[i]);
    ans=(i128)A*B*high;
    for(int h=C;h>high;--h)
    {
        for(int i=1;i<=n;++i) if(w[i]==h)  maxh[u[i]]=max(maxh[u[i]],v[i]);
        for(int i=A;i>=1;--i) maxh[i]=max(maxh[i],maxh[i+1]);
        for(int i=1;i<=A;++i) ans+=maxh[i];
    }
}
int main()
{
    GetData();
    solve();
    print(ans);
    return 0;
}

B.我是 B 题

55pts的状压+5pts的特殊性质应该是好打的，然而考场数组开小了（悲）。

然而正解看完后发现好像有手就行

设 $dp[i][j]dp[i][j]$ 表示到第 $ii$ 个机器时，目标物品排名为 $jj$ 的概率。

这里采用刷表法好写一点：

枚举质量为 $rnkrnk$ 的物品；

初始值 $dp[1][rnk]=1dp[1][rnk]=1$；

转移方程：

$dp[i+1][j-1]+=dp[i][j]\times (1-(1-p_i{)}^{j-1})dp[i+1][j-1]+=dp[i][j]\backslash times(1-(1-p\_i)^\{j-1\})$ //删除的是j前面的数，不可能让j前面的数全部逃掉

$dp[i+1][j]+=dp[i][j]\times (1-p_i{)}^{j}dp[i+1][j]+=dp[i][j]\backslash times(1-p\_i)^j$ //删除的是j后面的数，j及j前面的数必须全部逃掉

答案 ${\sum }_{rnk=1}^{n}dp[n][1]\times rnk\backslash sum\_\{rnk=1\}^n\; dp[n][1]\backslash times\; rnk$。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=305;
const int MOD=1e9+7;
int p[MAXN],mypow[MAXN][MAXN],dp[MAXN][MAXN];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;++i)
	{
		scanf("%d",&p[i]);
		mypow[i][0]=1;
		for(int j=1;j<=n;++j) mypow[i][j]=(long long)mypow[i][j-1]*(1-p[i]+MOD)%MOD;
	}
	int ans=0;
	for(int rnk=1;rnk<=n;++rnk)
	{
		memset(dp,0,sizeof(dp));
		dp[1][rnk]=1;
		for(int i=1;i<n;++i)
			for(int j=1;j<=n-i+1;++j)
			{
				if(j) (dp[i+1][j-1]+=(long long)dp[i][j]*(1-mypow[i][j-1]+MOD)%MOD)%=MOD;
				if(j<n-i+1) (dp[i+1][j]+=(long long)dp[i][j]*mypow[i][j]%MOD)%=MOD;
			}
		(ans+=(long long)dp[n][1]*rnk%MOD)%=MOD;
	}
	cout<<ans;
	return 0;
}

C.我是 C 题

犯了写莫名奇妙的错误然后 $30->1530->15$……

由于 $b_{i}b\_i$ 单调不增，若区间 $[l,r][l,r]$ 不合法，则其子区间一定不合法。

于是可以分治，对于每个区间所有出现次数小于 $b_{r-l+1}b\_\{r-l+1\}$ 的数字全部删掉，若当前区间什么数都没删，则合法，更新答案。

每次找到一个不合法的数，以此数为中心往两边递归，用启发式合并的思想可以将复杂度优化至 $O(nlogn)O(nlogn)$。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e6+5;
int a[MAXN],b[MAXN],cnt[MAXN];
int n,ans;
void solve(int l,int r)
{
	if(r<l || r-l+1<=ans)
	{
		for(int i=l;i<=r;++i) --cnt[a[i]];
		return;
	}
	if(l==r)
	{
		--cnt[a[l]];
		if(b[1]==1) ans=1;
		return;
	}
	int pos=-1,val=b[r-l+1];
	for(int i=l;i<=r;++i)
	{
		if(cnt[a[i]]<val)
		{
			pos=i;
			break;
		}
	}
	if(pos<0)
	{
		ans=r-l+1;
		for(int i=l;i<=r;++i) --cnt[a[i]];
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)
	{
		for(int i=l;i<=pos;++i) --cnt[a[i]];
		solve(pos+1,r);
		for(int i=l;i<pos;++i) ++cnt[a[i]];
		solve(l,pos-1);
	}
	else
	{
		for(int i=pos;i<=r;++i) --cnt[a[i]];
		solve(l,pos-1);
		for(int i=pos+1;i<=r;++i) ++cnt[a[i]];
		solve(pos+1,r);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),++cnt[a[i]];
	for(int i=1;i<=n;++i) scanf("%d",&b[i]);
	solve(1,n);
	cout<<ans;
	return 0;
}

D.我是 D 题

看不懂题解码风清奇命名混乱且没有注释的代码

待补……

*//后记&总结：第一题还是花太长时间了，交完95分的代码时都8:40了，紧张的心态导致后面写题部分分屡屡出锅，OI集训营已经结束了，在CSP-S2前还是要调整好心态和适应考试状态，争取CSP-S2 300+

笔者能力有限，有未述详尽或有误之处，欢迎指正。