526互联

The 2023 ICPC Asia Hefei Regional Contest Test D. Balanced Array

发布时间 2023-12-03 15:43:40作者: 空気力学の詩

Preface

这题赛场上出了个关键点基本都想到的做法，但因为一个地方卡住了没过去导致不得不选择弃掉这道题

赛后补了下发现\(O(n\log n)\)的做法是只差临门一脚了，但\(O(n)\)的做法还是trick性挺强的

Solution

首先考虑枚举\(k\)，不难发现此时合法的前缀一定是个连续的区间，其中区间的左端点为\(2k+1\)

那么可以先暴力验证\(a_1+a_{2k+1}\)与\(2a_{k+1}\)的大小关系，若符合则考虑往后推移的过程

我们很容易想到差分，设\(d_i=a_{i+1}-a_i\)，那么对于当前的符合条件的三元组\((1,k+1,2k+1)\)，能往后推一步的充要条件就是\(d_1+d_{2k+1}=2d_{k+1}\)

同理，如果要推\(t\)步则需要满足\(d_{1+j}+d_{2k+1+j}=2d_{k+1+j}(0\le j<t)\)

考虑利用Hash来把多位放在一起比较，利用其每一位的线性不变性，我们可以直接先Hash在加起来判断

假设要验证间隔为\(k\)，合法的前缀区间是否为\([2k+1,L]\)，则等价于判断：

\[\operatorname{hash}(1,L-2k-1)+\operatorname{hash}(2k+1,L-1)=2\operatorname{hash}(k+1,L-k-1) \]

直接用二分找到最远的合法的分界点即可，最后统计答案就随便处理以下即可

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        inline void read_int(int& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        inline int trs(const char& ch)
        {
        	if ('0'<=ch&&ch<='9') return ch-'0';
        	if ('a'<=ch&&ch<='z') return ch-'a'+10;
        	if ('A'<=ch&&ch<='Z') return ch-'A'+36;
        }
        inline void read_b62(int& x)
        {
        	x=0; char ch; while (isspace(ch=tc()));
			while (x=x*62+trs(ch),!isspace(ch=tc()));	
        }
        #undef tc
}F;
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=(X%mod1+mod1)%mod1; y=(Y%mod2+mod2)%mod2;
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}h[N],pw[N]; int n,a[N],d[N],f[N];
const Hasher seed=Hasher(31,131);
inline Hasher get_hsh(CI l,CI r)
{
	return h[r]-h[l-1]*pw[r-l+1];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (F.read_int(n),i=1;i<=n;++i) F.read_b62(a[i]);
	for (i=1;i<=n;++i) d[i]=a[i+1]-a[i];
	for (pw[0]=Hasher(1,1),i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
	for (i=1;i<=n;++i) h[i]=h[i-1]*seed+Hasher(d[i],d[i]);
	for (i=1;2*i+1<=n;++i) if (a[1]+a[2*i+1]==2*a[i+1])
	{
		int l=2*i+1,r=n,mid,ret; while (l<=r)
		if (mid=l+r>>1,get_hsh(1,mid-2*i-1)+get_hsh(2*i+1,mid-1)==Hasher(2,2)*get_hsh(i+1,mid-i-1)) ret=mid,l=mid+1; else r=mid-1;
		++f[2*i+1]; --f[ret+1];
	}
	for (i=1;i<=n;++i) f[i]+=f[i-1];
	for (i=1;i<=n;++i) putchar(f[i]?'1':'0');
	return 0;
}

但这题\(2\times 10^6\)跑1s显然就是想卡掉带\(\log\)做法，因此我们思考如何去掉这个\(\log\)

很容易发现当一段前缀\([2k+1,pos]\)合法后，其实我们就没有必要再去检验前缀小于等于\(pos\)的所有区间了

因此可以用一个指针来维护当前最靠右的合法的前缀，每次判断能否向后移动即可

总复杂度\(O(n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        inline void read_int(int& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        inline int trs(const char& ch)
        {
        	if ('0'<=ch&&ch<='9') return ch-'0';
        	if ('a'<=ch&&ch<='z') return ch-'a'+10;
        	if ('A'<=ch&&ch<='Z') return ch-'A'+36;
        }
        inline void read_b62(int& x)
        {
        	x=0; char ch; while (isspace(ch=tc()));
			while (x=x*62+trs(ch),!isspace(ch=tc()));	
        }
        #undef tc
}F;
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=(X%mod1+mod1)%mod1; y=(Y%mod2+mod2)%mod2;
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}h[N],pw[N]; int n,a[N],d[N],f[N];
const Hasher seed=Hasher(31,131);
inline Hasher get_hsh(CI l,CI r)
{
	return h[r]-h[l-1]*pw[r-l+1];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (F.read_int(n),i=1;i<=n;++i) F.read_b62(a[i]);
	for (i=1;i<=n;++i) d[i]=a[i+1]-a[i];
	for (pw[0]=Hasher(1,1),i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
	for (i=1;i<=n;++i) h[i]=h[i-1]*seed+Hasher(d[i],d[i]);
	for (j=0,i=1;2*i+1<=n;++i) if (a[1]+a[2*i+1]==2*a[i+1])
	{
		if (j<2*i+1) f[j=2*i+1]=1;
		auto check=[&](CI pos)
		{
			return get_hsh(1,pos-2*i-1)+get_hsh(2*i+1,pos-1)==Hasher(2,2)*get_hsh(i+1,pos-i-1);
		};
		while (j<n&&check(j+1)) f[++j]=1;
	}
	for (i=1;i<=n;++i) putchar(f[i]?'1':'0');
	return 0;
}