hdu2021多校4

发表于 2021-07-29 分类于 hdu ，多校

比赛链接

1001

签到题，给出的项除了常数以外都是不收敛的。

于是判断有 $x$ 的项是否为 $0$ 即可。

1002

签到题，暴力枚举起始点，用桶记录个数即可。

也可套用点分治做法做到 $O (n \log n)$ 。

1003

题意

求所有长度为 $n$ 的01字符串的最短循环节的出现次数。

$n \leq 10^{9}, \sum n \leq 10^{10}$ 。

题解

设 $g_{n}$ 表示答案， $f_{i}$ 表示最小循环节长度为 $i$ 的字符串个数。

有： $g_{n} = \sum_{i = 1}^{n} ⌊ \frac{n}{i} ⌋ f_{i}$ 。

考虑 $f_{i}$ 如何求：

当 $m \leq \frac{n}{2}$ 时， $2^{m} = \sum_{i | m} f_{i}$ 。

而当 $m > \frac{n}{2}$ 后，上式就不成立了。因为周期引理不再适用。

但可以发现，此时的 $⌊ \frac{n}{i} ⌋ = 1$ ，于是我们还是通过补集转换，转去算 $2^{n} - \sum_{i = 1}^{⌊ \frac{n}{2} ⌋} f_{i}$ 。

于是有 $g_{n} = 2^{n} + \sum_{i = 1}^{\frac{n}{2}} (⌊ \frac{n}{i} ⌋ - 1) f_{i}$ 。

整除分块，又因为有 $2^{n} = f * 1$ ，杜教筛筛出 $f_{i}$ 的前缀和即可。发现跑一次算 $f_{i}$ 前缀和的杜教筛就能算出整除分块里的所有的前缀和。

这里记录一下杜教筛的过程：若有积性函数 $f$ ，要算 $f$ 的前缀和 $S_{n} = \sum_{i = 1}^{n} f_{i}$ 找到另外两个积性函数 $h, g$ 使得 $h = f * g$ 。

$\sum_{i = 1}^{n} h_{i} = \sum_{i = 1}^{n} \sum_{j | i} f (j) g (\frac{i}{j}) = \sum_{i = 1}^{n} g_{i} \sum_{j = 1}^{⌊ \frac{n}{i} ⌋} f_{i} = \sum_{i = 1}^{n} g_{i} S_{⌊ \frac{n}{i} ⌋}$

于是就可以了。

需要预处理 $O (n^{\frac{2}{3}})$ 前的 $f_{i}$ 的前缀和。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}

const int N=1e6;

int s[N+3],f[N+3];
inline void init(int n)
{
	ll nw=1;
	fo(i,1,n)
	{
		nw=(nw*2)%mod;
		f[i]=Dec(nw,f[i]);
		s[i]=Add(s[i-1],f[i]);
		for(int j=i+i;j<=n;j+=i)
			f[j]=Add(f[j],f[i]);
	}
}
int n,n2,tot;
ll a[300000];
inline int id(int x) {return x<=n2?x:tot-n/x;}

ll calc_g(int m)
{
	if(!m) return 0;
	if(a[id(m)]!=-1) return a[id(m)];
	ll ans=Dec(Pow(2,(m+1)),2);
	for(int l=2,r;l<=m;l=r+1)
	{
		r=m/(m/l);
		ans=Dec(ans,1ll*(r-l+1)*calc_g(m/l)%mod);
	}
	return a[id(m)]=ans;
}
inline ll calc_f(int _n)
{
	n=_n; n2=sqrt(n+0.3); tot=1;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		a[tot++]=((r<=N)?s[r]:-1);
	}
	int m=n/2;
	ll ans=Pow(2,n);
	for(int l=1,r;l<=m;l=r+1)
	{
		r=min(m,n/(n/l));
		ans=Add(ans,1ll*(n/l-1)*(calc_g(r)-calc_g(l-1)+mod)%mod);
	}
	return ans;
}

int main()
{
	init(1e6);
	CASET printf("%lld\n",calc_f(read()));
	return 0;
}

1004

题意

给出一个由小写字母组成的字符串 $S$ ，及每个字符的权值。一个串的价值为其每个字符的权值之和。

求 $S$ 所有不同的子串中，价值为第 $k$ 小的价值是多少。没有则输出 $- 1$ 。

两个子串相同当且仅当他们长度相同且对应每一位字符均相等。

$n \leq 10^{5}$ 。

题解

真的是，好久不写，都忘了SAM的性质了。

二分答案，建出SAM后，每个节点对应着 $l e n_{i} - l e n_{f a_{i}}$ 个子串。且长度连续，均为当中最长串的后缀。

于是在每个节点里面再二分一次找到串的个数就好了。

注意！需要记录SAM中每个串的终止位置！即right集合当中的任意一个即可。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
const int S=26;

namespace SAM{
	int ne[N][S],fa[N],len[N],las,siz,idx[N];
	inline void init()
	{
		for(int i=1;i<=siz;i++) memset(ne[i],0,sizeof(ne[i])),fa[i]=len[i]=0;
		las=siz=1;
	}
	inline void extend(int c,int id)
	{
		int cur=++siz;
		idx[cur]=id+1;
		len[cur]=len[las]+1;
		int p=las;
		for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur;
		if(!p) fa[cur]=1;
		else
		{
			int q=ne[p][c];
			if(len[q]==len[p]+1) fa[cur]=q;
			else
			{
				int clone=++siz;
				len[clone]=len[p]+1; idx[clone]=idx[q];
				memcpy(ne[clone],ne[q],sizeof(ne[q]));
				fa[clone]=fa[q];
				for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=clone;
				fa[cur]=fa[q]=clone;
			}
		}
		las=cur;
	}
}

int n,m,sum[N],val[30];
ll k;
char s[N];
int L[N],R[N],id[N];
inline ll get()
{
	ll ss=0;
	m=SAM::siz;
	fo(i,2,SAM::siz) id[i]=SAM::idx[i],L[i]=SAM::len[SAM::fa[i]]+1,R[i]=SAM::len[i],ss+=SAM::len[i]-SAM::len[SAM::fa[i]];
	return ss;
}

inline ll check(int x)
{
	ll ss=0;
	fo(i,2,m) if(sum[id[i]]-sum[id[i]-L[i]]<=x)
	{
		int l=L[i],r=R[i],mid;
		for(;l<=r;)
		{
			mid=(l+r)>>1;
			if(sum[id[i]]-sum[id[i]-mid]<=x) l=mid+1;
			else r=mid-1;
		}
		ss+=(r-L[i]+1);
	}
	return ss;
}
int main()
{
	CASET
	{
		n=read(); cin>>k;
		scanf("%s",s);
		SAM::init();
		ff(i,0,strlen(s)) SAM::extend(s[i]-'a',i);
		fo(i,0,25) val[i]=read();
		if(get()<k)
		{
			puts("-1");
			continue;
		}
		fo(i,1,n) sum[i]=sum[i-1]+val[s[i-1]-'a'];
		int l=0,r=n*100,mid;
		for(;l+1<r;)
		{
			mid=(l+r)>>1;
			if(check(mid)>=k) r=mid;
			else l=mid;
		}
		printf("%d\n",r);
	}
	return 0;
}

1008

题意

$n \times m$ 的网格图，从 $(1, 1)$ 开始，每次能往上或往右走一格，走到 $(n, m)$ 。有 $k$ 个点不能经过。问有可能走到的格子有多少个。

$n, m, k \leq 10^{5}$ 。

题解

补集转换，变为求哪些格子走不到。

对于一条斜向上的线段，不能走的格子将形成一个直角三角形或等腰梯形。

考虑斜着的扫描线，这样相当于是若干条不相交的线段组成。随着扫描线的右移，中间的线段长度将集体 $- 1$ ，两端的线段有可能不减。

用链表维护这些线段，插入一个点时判断能否与左右两端的线段合并，或本身就在线段里面。

线段长度减一的话暴力枚举链表中的每一个元素即可，长度减到 $0$ 后将其删除。

这样做的复杂度是对的，因为线段原始的总长不会超过 $k$ 。

时间复杂度 $O (n + m + k)$ 。不知为何跑得很慢。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;

struct node{
	int x,y;
};
node p[N];

vector<int> adj[N];
inline void add(int x,int y){adj[x].pb(y);}

struct line{
	int y,len;
};

line s[N<<1];

int n,m,k,L[N],R[N];

inline bool cmp(const int &x,const int &y)
{
	return p[x].y>p[y].y;
}

int main()
{
	CASET
	{
		n=read(); m=read(); k=read();
		ll ans=1ll*n*m;
		fo(i,1,n+m) adj[i].clear();
		fo(i,0,n+m+1) L[i]=R[i]=0;
		R[0]=n+m+1; L[n+m+1]=0;
		fo(i,1,k) p[i].x=read(),p[i].y=read(),add(p[i].x+p[i].y,i);
		fo(i,2,n+m) sort(all(adj[i]),cmp);
		int u;
		fo(i,1,n+m)
		{
			for(int j=R[0];j!=n+m+1;j=R[j])
			{
				s[j].len--;
			}
			if(R[0]!=n+m+1)
			{
				u=R[0];
				if(s[u].y==i-2&&i<=m+1) s[u].len++,s[u].y=i-1;
				u=L[n+m+1];
				if(s[u].y==s[u].len+1&&i<=n+1) s[u].len++;
			}

			for(int j=R[0];j!=n+m+1;j=R[j])
			{
				if(s[j].len==0)
				{
					L[R[j]]=L[j];
					R[L[j]]=R[j];
					j=L[j];
				}
			}
			int j=R[0];
			s[0].y=1000000000;
			for(auto v:adj[i])
			{
				for(;j!=n+m+1&&s[j].y>=p[v].y;j=R[j]);
				j=L[j]; k=R[j];
				if(!j)
				{
					s[v].y=p[v].y; s[v].len=1;
					R[0]=L[k]=v;
					L[v]=0; R[v]=k;
					j=v;
					if(k==n+m+1) continue;
				}
				else
				{
					if(s[j].y-s[j].len+1<=p[v].y)
					{
						continue;
					}
					else
					{
						if(s[j].y-s[j].len==p[v].y) s[j].len++;
						else
						{
							s[v].y=p[v].y; s[v].len=1;
							R[j]=L[k]=v;
							L[v]=j; R[v]=k;
							j=v;
						}
					}
				}
				if(k!=n+m+1)
				{
					if(s[j].y-s[j].len==s[k].y)
					{
						s[j].len+=s[k].len;
						int t=R[k];
						L[t]=j; R[j]=t;
					}
				}
			}
		
			ll k=0;
			for(int j=R[0];j!=n+m+1;j=R[j]) ans-=s[j].len,k+=s[j].len;
		}
		printf("%lld\n",ans);
	}
	return 0;
}