【2024NOI模拟赛08】二分 做题记录

有 $n$ 个灯泡，每个灯泡有一个参数 $a_i$ 表示若 $[1,i-1]$ 中有 $\ge a_i$ 个灯泡点亮了那么第 $i$ 个灯泡会自动点亮。

给定 $m$，求至少手动点亮多少个灯泡才能保证总共有 $m$ 个灯泡被点亮。

$1\le m\le n\le 5\times 10^7$，要求线性。

困难 Div2 C。

注意到 $m$ 越小越好，$n$ 越大越好。

考虑倒着做。观察到若 $a_n\le m-1$，那么限制可以转化为前 $n-1$ 个灯泡中有 $m-1$ 个被点亮，并且这样转化一定不劣；否则 $a_n$ 不可能被点亮，可以直接扔掉。

最终会有一个时刻 $n=m$，这时直接从前往后贪心求出代价即可。

时间复杂度 $O(n)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

inline int read()
{
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}

const int S=50000005;

int n,m,a[S];

int main()
{
	freopen("bs.in","r",stdin);
	freopen("bs.out","w",stdout);
	n=read(),m=read();
	a[1]=read();
	int k=read();
	for(int i=1,j=2;i<=k;i++)
	{
		int c=read(),x=read(),y=read(),z=read();
		while(c-->0)
		{
			a[j]=(1ll*x*a[j-1]+y)%z;
			j++;
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(a[i]<m) m--;
		if(i==m) break;
	}
	int ans=0;
	for(int i=1,ct=0;i<=m;i++) if(a[i]>=i) ans++;
	printf("%d\n",ans);
	return 0;
}