1.AT_abc133_d Rain Flows into Dams

题意

思路

目标数组 $b_i$，满足 $a_i=\frac{b_i+b_{i+1}}{2}$，$a_n=\frac{b_n+b_1}{2}$。因为保证 $n$ 是奇数，所以容易找出 $b_1$，后面就随便做。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,a[N];
int main()
{
	freopen("rain.in","r",stdin);
	freopen("rain.out","w",stdout);
	scanf("%lld",&n);
	ll s=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		if(i&1)s+=a[i];
		else s-=a[i];
	}
	printf("%lld ",s);
	for(int i=1;i<n;i++)
	{
		s=a[i]*2-s;
		printf("%lld ",s);
	}
	return 0;
}

2.查找

题意

思路

神秘卡空间题，归并然后精细实现即可。注意是原数组 $a$ 的绝对值在 $10^9$，不是 $a^{\prime }$，不必惊慌。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
    int x=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=7.5e6+2,M=1e6+2;
bool mst;
int n,m;
int xa[N],xb[N];
struct que
{
	int k,id;
}q[M];
int ANS[M];
bool cmp(que x,que y)
{
	return x.k<y.k;
}
bool cmp0(que x,que y)
{
	return x.id<y.id;
}
bool med;
void init()
{
	ll ca=0,cb=xb[1];
	int tick=0,pos=1;
	int z=1;
	for(int i=1;i<=n;i++)
	{
		ca+=xa[i];
		while(pos<=n&&cb<=ca)
		{
			tick++;
			while(q[z].k==tick)
			{
				ANS[q[z].id]=cb;
				z++;
			}
			cb+=xb[++pos];
		}
		tick++;
		while(q[z].k==tick)
		{
			ANS[q[z].id]=ca;
			z++;
		}
		if(z>m)break;
	}
}
int main()
{
	freopen("search.in","r",stdin);
	freopen("search.out","w",stdout);
//	printf("%.2lf\n",(&med-&mst)/1024.0/1024.0); 
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	xa[i]=read();
	for(int i=1;i<=n;i++)
	xb[i]=read();
	for(int i=1;i<=m;i++)
	{
		int k=read();
		q[i]=(que){k,i};
	}
	sort(q+1,q+m+1,cmp);
	init();
	for(int i=1;i<=m;i++)
	{
		write(ANS[i]);
		puts("");
	}
	return 0;
}

3.概率（CF451E Devu and Flowers / AT_abc200_e Patisserie ABC 2 加强版）

题意

思路

容易想到这次测试的 $1.$。我们可以用容斥原理，搞出每个数 $\in [0,m]$ 和为 $s$ 的方案数，拿到暴力分。计算一次时间复杂度为 $O(s/m)$。然后枚举左右两边的和，可以前缀和优化掉。

但是这个做法还是太没有前途了。考虑左右两半的和会出现什么情况：

• 左边的和大于右边的和；
• 左边的和等于右边的和；
• 左边的和小于右边的和。

发现第一种情况和第三种情况是对称的，于是考虑计算第二种情况的概率 $B$，然后 $\frac{1-B}{2}$。

然后我们转化一下，左边的和等于右边的和，相当于左边的和减右边的和 $=0$，相当于把右边的值域改成 $[-m,0]$。然后把右边的数每个强制加上 $m$，相当于 $2n$ 个数，每个数 $\in [0,m]$，和为 $nm$ 的方案数。就可以用上面的容斥了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e6+9;
ll mod;
ll Q,n,m,f[N];
ll qpow(ll x,int k)
{
	ll ret=1;
	while(k)
	{
		if(k&1)ret=ret*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ret;
}
ll fac[N],inv[N];
void init()
{
	fac[0]=inv[0]=1;
	for(int i=1;i<N;i++)
	fac[i]=fac[i-1]*i%mod;
	inv[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=1;i--)
	inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m)
{
	if(n<m||n<0||m<0)return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
//	freopen("pr.in","r",stdin);
//	freopen("pr.out","w",stdout);	
	scanf("%lld%lld",&mod,&Q);
	init();
	while(Q--)
	{
		scanf("%lld%lld",&n,&m);
		ll ret=0;
		for(ll i=0;i<=2*n&&i*(m+1)<=n*m;i++)
		{
			ll op=(i&1?-1:1);
			ret=(ret+op*C(2*n,i)*C(n*m-i*(m+1)+2*n-1,2*n-1)%mod+mod)%mod;
		}
		//ret:前后两个数相等的概率 
		ret=(1-ret*qpow(qpow(m+1,mod-2),2*n)%mod+mod)%mod*qpow(2,mod-2)%mod;
		printf("%lld\n",ret);
	}
	return 0;
}

4.回文

题意

思路

待补。