\(\tt noip\) 之后的第一场线上赛，感觉手感退化了很多啊，不知道上红的目标能不能如期实现呢？

D. Not Quite Lee

题目描述

数轴上有 \(n\) 个窗口，第 \(i\) 个窗口的长度为 \(b_i\)（包含这么多连续的整数），定义一个窗口的权值为包含数字的和，问有多少个窗口的子序列满足存在一种滑动方案使得权值和为 \(0\)

\(n\leq 2\cdot 10^5\)

解法

考虑调整法，一开始可以取总和为 \(\sum \frac{c_i(c_i-1)}{2}\) 的窗口组合，那么滑动相当于把权值 \(+c_i\) 或者 \(-c_i\)，那么合法的充要条件是存在序列 \(\{x_i\}\) 满足 \(\sum c_i\cdot x_i=\sum\frac{c_i(c_i-1)}{2}\)

根据裴蜀定义可以转化为 \(\sum\frac{c_i(c_i-1)}{2}|\gcd(c_1,c_2...c_n)\)，但是好像还是不可做。

我们观察 \(\sum\frac{c_i(c_i-1)}{2}\) 有什么性质，其中特殊的是 \(2\) 这个常数，这提示我们可以着重讨论奇偶性。

然后观察到如果原序列中存在奇数那么一定合法，因为此时一定满足 \(\sum \frac{c_i(c_i-1)}{2}|\gcd\)，尝试扩展这个观察，也就是把每个子序列在满足 \(\gcd|2^l\) 的最大的 \(l\) 处统计。

对于 \(l>0\)，我们把限制拆成 \(\sum\frac{c_i(c_i-1)}{2}|2^l\and \sum\frac{c_i(c_i-1)}{2}|\frac{g}{2^l}\)，也就是满足 \(c_i|2^l\and c_i\not| 2^{l+1}\) 的有偶数个并且至少有 \(1\) 个，所以可以用容斥原理简单计算。

#include <cstdio>
const int M = 200005;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[M],pw[M];
signed main()
{
	n=read();pw[0]=1;
	for(int i=1;i<=n;i++)
	{
		int x=read(),cnt=0;
		while(x%2==0) cnt++,x/=2;
		a[cnt]++;
		pw[i]=pw[i-1]*2%MOD;
	}
	int ans=pw[n]-pw[n-a[0]],y=n-a[0];
	for(int i=1;i<=30;i++)
	{
		int x=y;y-=a[i];
		if(x-1<=y) continue;
		ans+=pw[x-1]-pw[y];
	}
	printf("%lld\n",(ans%MOD+MOD)%MOD);
}

E. AmShZ and G.O.A.T.

题目描述

定义一个序列为坏当且仅当严格大于平均数的数量 大于 严格小于平均数的数量。

问最少删除多少个元素使得最后的序列的任何子序列都不为坏。

\(n\leq 2\cdot 10^5\)，保证原序列单增。

解法

考虑转化判据，原序列的任何子序列不为坏当且仅当原序列的任何一个长度为 \(3\) 的子序列不为坏，必要性显然，下证充分性：

考虑对于如果 \(a_{i+1}-a_i<a_i-a_1\)，那么 \(\{1,i,i+1\}\) 就是一组坏的序列。否则我们可以知道对于任何一个子序列都有 \(c_{\lceil\frac{k}{2}\rceil}\leq AVG\)（因为是凸函数，中间位置一定在下方），这足以说明不存在坏的子序列。

就上面这个简单的证明我证了一周，当然是边学文化课有空余时间再证的

那么我们只需要保证 \(a_{i+1}-a_i\geq a_i-a_1\) 就可以得到好的序列，考虑一个一个加数，那么新数与首项的距离每次一定翻倍，所以在非常数序列的情况下，序列长度是 \(O(\log a)\) 的。

所以我们枚举首项，然后贪心地找最近合法的下一项，注意特判相等的情况，那么时间复杂度 \(O(n\log n\log a)\)

总结

本题的难点其实是结论，这种类型就是判断最基本的情况就有了充分性。

证明方法难以用语言表达，自己体会一下吧

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 200005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int T,n,ans,a[M];
signed main()
{
	T=read();
	while(T--)
	{
		n=read();ans=0;
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int i=1;i<=n;i++)
		{
			if(a[i]==a[i-1]) continue;
			int j=i,res=1;
			while(j<=n)
			{
				j=lower_bound(a+j+1,
				a+n+1,2*a[j]-a[i])-a;
				if(j<=n) res++;
			}
			ans=max(ans,res);
		}
		printf("%d\n",n-ans);
	}
}