CF1829G Hits Different

题目地址

题意：有这样一个塔，初始全为蓝色，第i位上的数为i²，丢球丢中第k位时，将使得第k位和他头顶的数 以及 头顶的数的头顶的数 以及...都变成红色，求红色数的和

Solution

dp转移，我们把斜着向右下的所有数转移在一起，然后从第k位数开始往右上走，答案就是所有的和

void init()
{
	int now=1;
	int limit=1e6;
	for(int i=1;i<=limit;i++)
	{
		if(now*(now+1)/2<i)now++;
		a[i]+=i*i;
		if(i+now+1<=limit)
		a[i+now+1]+=a[i];
	}
}

void solve()
{
	int n;cin>>n;
	int l=1,r=1e6;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(mid*(mid+1)/2>=n)r=mid;
		else l=mid+1;
	}
	int now=l; //二分找到n在哪一行
	int pos=n;
	int ans=0;
	while(now*(now+1)/2!=pos) 
	{
		ans+=a[pos];
		pos-=(now-1);//往回走
		now--;
	}
	ans+=a[pos];
	cout<<ans<<"\n";
}