TJOI2019 选做

Posted on | Edited on | Views:

向 $CQOI\ 2018$ 致敬?

甲苯先生的字符串

  • 矩阵快速幂.
  • 板子题.处理相邻两个字符时改一下转移矩阵里的系数就好了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=26;
struct matrix
{
	int v[MAXN][MAXN];
	matrix(){memset(v,0,sizeof v);}
	matrix operator * (const matrix &rhs) const
	{
		matrix res;
		for(int i=0;i<MAXN;++i)
			for(int j=0;j<MAXN;++j)
				for(int k=0;k<MAXN;++k)
					res.v[i][j]=add(res.v[i][j],mul(v[i][k],rhs.v[k][j]));
		return res;
	}
};
matrix fpow(matrix a,ll b)
{
	matrix res;
	for(int i=0;i<MAXN;++i)
		res.v[i][i]=1;
	while(b)
	{
		if(b&(1LL))
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
ll n;
char buf[100005];
int main()
{
	scanf("%lld%s",&n,buf);
	matrix st,trans;
	for(int i=0;i<MAXN;++i)
		st.v[i][0]=1;
	for(int i=0;i<MAXN;++i)
		for(int j=0;j<MAXN;++j)
			trans.v[i][j]=1;
	int len=strlen(buf);
	for(int i=1;i<len;++i)
	{
		int p=buf[i-1]-'a';
		int q=buf[i]-'a';
		trans.v[q][p]=0;
	}
	st=fpow(trans,n-1)*st;
	int ans=0;
	for(int i=0;i<MAXN;++i)
		ans=add(ans,st.v[i][0]);
	cout<<ans<<endl;
	return 0;
}

甲苯先生的滚榜

  • 平衡树.
  • 又是板子题.随便上个啥平衡树写一下插入,删除,查询排名.

唱、跳、rap 和篮球

顶风作案,律师函警告.

  • 容斥原理+ $dp$ 计数.
  • 为了方便,称题目中所说的一组同学为 位置 $k$ 在讨论蔡徐坤 ,要求出没有位置在讨论蔡徐坤的方案数.
  • 显然可以容斥原理搞一搞,只需对每个 $i$ 求出钦定 $i$ 个位置在讨论蔡徐坤,其它不涉及的位置乱选的方案数.
  • 其它位置乱选方案数就是有重复元素的排列数,但每个元素使用次数有限制.可以构造多项式 $(x+y+z+w)^{tot}$ , $tot=n-4i$ ,将次数符合要求的对应系数求和.
  • 二项式定理套两次,多项式展开为
    $$
    \begin{aligned}
    (x+y+z+w)^{tot}&=\sum C_{tot}^j (x+y)^j(z+w)^{tot-j}\\
    &=\sum C_{tot}^j(\sum C_j^p x^p y^{j-p})(\sum C_{tot-j}^q z^q w^{tot-j-q})
    \end{aligned}
    $$
  • 预处理组合数前缀和,把 $x,y,z,w​$ 系数都符合限制的那一段取出来计算即可.
  • 考虑怎么求钦定 $i​$ 个位置在讨论蔡徐坤的方案数.
  • 抽象一下就是选出 $i$ 个位置,相邻两个位置之差至少为 $4$ .需要求出每个 $i$ 的方案数.
  • 可以设计一个三维的 $dp​$ ,状态需要记录考虑的数目,选的数目,最后一个选的位置.
  • 注意到最后一个选的位置其实只有四种情况有区别,设 $f(j,i,0/1/2/3)$ 表示已经考虑了前 $j$ 个位置,选了 $i$ 个位置,最后选的位置分别是 $j,j-1,j-2,\leq j-3$ 时的方案数.将 $f(n-3,i,0/1/2/3)$ 求出即可.
  • 时间复杂度 $O(n^2)​$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
void upd(int x,int &y)
{
	y=add(x,y);
}
const int MAXN=1e3+10;
int n,mx;
int C[MAXN][MAXN],sumc[MAXN][MAXN];
int f[MAXN][MAXN][4];
void init()
{
	for(int i=0;i<=n;++i)
		C[i][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	for(int i=0;i<=n;++i)
	{
		sumc[i][0]=1;
		for(int j=1;j<=i;++j)
			sumc[i][j]=add(sumc[i][j-1],C[i][j]);
	}
	f[0][0][3]=1;
	for(int i=0;i<n;++i)
		for(int j=0;j<=mx;++j)
			for(int k=0;k<4;++k)
			{
				if(!f[i][j][k])
					continue;
				upd(f[i][j][k],f[i+1][j][k==3?k:k+1]);
				if(k==3)
					upd(f[i][j][k],f[i+1][j+1][0]);
			}
}
int lim[4];
int main()
{
	n=read();
	for(int i=0;i<4;++i)
		lim[i]=read();
	sort(lim,lim+4);
	mx=min(lim[0],n/4);//最多mx个位置讨论蔡徐坤 
	init();
	int ans=0,sgn=1;
	for(int i=0;i<=mx;++i)
	{
		int res=0,tmp=0;
		if(n<4)
			tmp=1;
		else
		{
			for(int k=0;k<4;++k)
				tmp=add(tmp,f[n-3][i][k]);
		}
		for(int k=0;k<4;++k)
			lim[k]-=i;
		int tot=n-i*4;
		for(int j=0;j<=tot;++j)
		{ 
			int lp=max(0,j-lim[1]);
			int rp=min(lim[0],j);
			int lk=max(0,tot-j-lim[3]);
			int rk=min(lim[2],tot-j);
			if(lp>rp || lk>rk)
				continue;
			int t1=lp?sumc[j][rp]-sumc[j][lp-1]:sumc[j][rp];
			int t2=lk?sumc[tot-j][rk]-sumc[tot-j][lk-1]:sumc[tot-j][rk];
			res=add(res,mul(C[tot][j],mul(t1,t2)));
		}
		res=mul(res,tmp);
		ans=add(ans,res*sgn);
		for(int k=0;k<4;++k)
			lim[k]+=i;
		sgn*=-1;
	}
	cout<<add(ans,P)<<endl;
	return 0;
}

甲苯先生与线段树

  • 位运算,数位 $dp$ .
  • 大概是个原题.

甲苯先生和大中锋的字符串

  • $SAM$ + 差分.
  • 建出 $SAM$ 后在 $parent$ 树上递推 $right$ 集合的大小,若其为 $k$ ,则对 $[Minlen,Maxlen]$ 内的计数器都加 $1$ .
  • 最后询问一次计数器最大值.可以修改差分,最后求前缀和,就可以做到 $O(n)$ 了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
    int out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        fh=-1,jp=getchar();
    while (jp>='0'&&jp<='9')
        out=out*10+jp-'0',jp=getchar();
    return out*fh;
}
const int Siz=26;
const int MAXN=2e5+10;
int n,k;
int ans,mxt;
int dif[MAXN];
struct SuffixAutoMation
{
	int lst,idx;
	int fa[MAXN],siz[MAXN];
	int ch[MAXN][Siz],len[MAXN];
	int A[MAXN],t[MAXN];
	SuffixAutoMation(){lst=idx=1;}
	void Extend(int c)
	{
		int p=lst,np=++idx;
		lst=np;
		siz[np]=1;
		len[np]=len[p]+1;
		while(p && ch[p][c]==0)
			ch[p][c]=np,p=fa[p];
		if(p==0)
			fa[np]=1;
		else
		{
			int q=ch[p][c];
			if(len[q]==len[p]+1)
				fa[np]=q;
			else
			{
				int nq=++idx;
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				for(int i=0;i<Siz;++i)
					ch[nq][i]=ch[q][i];
				len[nq]=len[p]+1;
				siz[nq]=0;
				while(p && ch[p][c]==q)
					ch[p][c]=nq,p=fa[p];
			}
		}
	}
	void topsort()
	{
		for(int i=1;i<=idx;++i)
			++t[len[i]];
		for(int i=1;i<=n;++i)
			t[i]+=t[i-1];
		for(int i=1;i<=idx;++i)
			A[t[len[i]]--]=i;
	}
	void solve()
	{
		topsort();
		for(int i=idx;i>=1;--i)
		{
			int u=A[i];
			siz[fa[u]]+=siz[u];
			if(siz[u]==k && u!=1)
			{
				int mx=len[u],mi=len[fa[u]]+1;
				++dif[mi];
				--dif[mx+1];
			}
		}
		int sum=0;
		for(int i=1;i<=n;++i)
		{
			sum+=dif[i];
			if(sum>=mxt)
				mxt=sum,ans=i;
		}
		printf("%d\n",mxt==0?-1:ans);
	}
	void reset()
	{
		for(int i=1;i<=n+1;++i)
			dif[i]=0;
		for(int i=0;i<=n;++i)
			t[i]=0;
		for(int i=1;i<=idx;++i)
			memset(ch[i],0,sizeof ch[i]);
		mxt=0;
		lst=idx=1;
	}
}SAM;
char buf[MAXN];
int main()
{
	int T=read();
	while(T--)
	{
		scanf("%s",buf);
		n=strlen(buf);
		scanf("%d",&k);
		cout<<k<<endl;
		for(int i=0;i<n;++i)
			SAM.Extend(buf[i]-'a');
		SAM.solve();
		SAM.reset();
	}
    return 0;
}

读入格式很诡异.用快读读 $k​$ 会炸两个点,原因不明.

大中锋的游乐场

  • 最短路.
  • 记 $dis[i][j]$ 表示从起点出发到节点 $i$ ,经过的 $1$ 减去经过的 $2$ 的数目为 $j$ 时的最短路长度.
  • 用 $Dijkstra$ 进行转移即可.