20240706比赛总结

题外话：IOI赛制的一大好处是可以猜解法，密码已改，不要试图jc我

T1 公式求值

根据样例解释，显然在不进位的情况下，倒数第一位是所有位上数字的总和，倒数第二位是所有位上数字的总和减去最后一位的数字

以此类推，显然前缀和，在处理一下进位即可

代码：

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int n,ans[1000005],sum[500005],cnt;
string s;
int main()
{
	cin>>s;
	n=s.size();
	s=" "+s;
	for(int i=1;i<=n;i++)
	{
		sum[i]=s[i]-'0';
		sum[i]+=sum[i-1];
	}
	for(int i=1,j=n;i<=n;i++,j--)
	{
		ans[i]=sum[j];
	}
	for(int i=1;i<=n;i++)
	{
		ans[i+1]+=ans[i]/10;
		ans[i]=ans[i]%10;
	}
	cnt=n;
	while(ans[cnt+1])
	{
		cnt++;
		ans[cnt+1]=ans[cnt]/10;
		ans[cnt]%=10;
	}
	for(int i=cnt;i>0;i--)
	{
		printf("%d",ans[i]);
	}
	return 0;
}

T2 最长的Y

https://gxyzoj.com/d/hzoj/p/3736

当Y的个数和位置确定时，根据绝对值的几何意义，显然当终点在中间时是操作次数最小

此处可以用前缀和然后枚举中间点

然后考虑长度，因为当x可以完成时，x-1显然可以，所以直接二分即可

代码：

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,p[200005],cnt;
ll k,sum[200005];
string s;
bool check(int x)
{
	int mid=(x+1)>>1;
	int l=mid-1,r=x-mid;
	ll t1=l*(l+1)/2,t2=r*(r+1)/2,ans=1e18+1;
	for(int i=mid;i<=cnt-r;i++)
	{
		ll l_step=p[i]*l-sum[i-1]+sum[i-mid]-t1;
		ll r_step=sum[i+r]-sum[i]-p[i]*r-t2;
	//	printf("%d %d %d\n",i,l_step,r_step);
		ans=min(ans,l_step+r_step);
	}
	if(ans<=k) return 1;
	return 0;
}
int main()
{
	cin>>s;
	scanf("%lld",&k);
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]=='Y') p[++cnt]=i;
	}
	for(int i=1;i<=cnt;i++)
	{
		sum[i]=sum[i-1]+p[i];
	}
	int l=1,r=cnt;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
	//	printf("%d\n",mid);
		if(check(mid))
		{
			l=mid;
		}
		else r=mid-1;
	}
	printf("%d",l);
	return 0;
}