Reincarnation

正因为梦易碎，才格外美好。

ZROI - 20连测Day6

发表于 分类于 ，
本文字数： 11k 阅读时长 ≈ 10 分钟

打得最烂的一集。

比赛链接：http://zhengruioi.com/contest/1472

A. 嗯鸥哀劈(noip)

题目简介

给定一个长度为 的字符串，求出最少操作使得出现子串 noip，操作如下：

  • 插入字符
  • 修改字符
  • 删除字符
  • 交换字符。

多测。

数据范围：

巨大牛魔分讨题。

考虑答案最大为 ，然后直接判即可。

似乎有比较正常的 做法，但似乎码量时空都比不过大分讨。

情况都在代码里。

AC Code
 
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
// ----- Eternally question-----
// Problem: A. 【noip赛前20天冲刺集训 day6】嗯鸥哀劈(noip)
// Contest: ZROI - 23noip赛前20天冲刺 day6
// URL: http://zhengruioi.com/contest/1472/problem/2641
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-17 18:51:58
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int Test,N;
char Str[MAXN];
inline bool check(int x,char c){ return Str[x]==c; }
inline int solve()
{
	for(int i=1;i<=N;++i) if(check(i,'n')&&check(i+1,'o')&&check(i+2,'i')&&check(i+3,'p')) return 0;
	for(int i=1;i<=N;++i)
	{
		if(check(i,'n')&&check(i+1,'o')&&check(i+2,'i')) return 1;
		if(check(i,'o')&&check(i+1,'i')&&check(i+2,'p')) return 1;
		if(check(i,'n')&&check(i+1,'o')&&check(i+2,'p')) return 1;
		if(check(i,'n')&&check(i+1,'i')&&check(i+2,'p')) return 1;
		if(check(i,'n')&&check(i+1,'i')&&check(i+2,'o')&&check(i+3,'p')) return 1;
		if(check(i,'n')&&check(i+1,'o')&&check(i+3,'i')&&check(i+4,'p')) return 1;
		if(check(i,'n')&&check(i+1,'o')&&check(i+3,'p')) return 1;
		if(check(i,'n')&&check(i+2,'i')&&check(i+3,'p')) return 1;
	}
	for(int i=1;i<=N;++i)
	{
		if(check(i,'n')&&check(i+1,'o')) return 2;
		if(check(i,'o')&&check(i+1,'i')) return 2;
		if(check(i,'i')&&check(i+1,'p')) return 2;
		if(check(i,'n')&&check(i+1,'i')) return 2;
		if(check(i,'n')&&check(i+2,'i')) return 2;
		if(check(i,'n')&&check(i+1,'p')) return 2;
		if(check(i,'n')&&check(i+2,'p')) return 2;
		if(check(i,'n')&&check(i+3,'p')) return 2;
		if(check(i,'o')&&check(i+1,'p')) return 2;
		if(check(i,'o')&&check(i+2,'p')) return 2;
	}
	for(int i=1;i<=N;++i)
	{
		if(check(i,'n')) return 3;
		if(check(i,'o')) return 3;
		if(check(i,'i')) return 3;
		if(check(i,'p')) return 3;
	}
	return 4;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		scanf("%s",Str+1);
		N=std::strlen(Str+1);
		write(solve(),'\n');
	}
	return 0;
}
/*

*/

B. 讴不死塔扣(obstacle)

题目简介

给定一个 的网格，初始在 ，其中有 个障碍物。定义 次移动为向下或者向右若干个单位，且移动的格子中不存在障碍物。

求出有多少个格子能够在不多于 次移动中到达。

数据范围：

显眼的数据范围加上题目格式，那么想到扫描线。

我们对每一行单独考虑，首先确定，因为只有向右和向下，两次向右和两次向下显然是迷惑操作，所以一定会拐一次弯。

那么分类讨论：

  • 如果先向下再向右，显然是一个前缀，如果遇到 的障碍物那么后面就不会存在这种情况的贡献。
  • 如果先向右后向下，那么首先是 的真前缀，然后每遇到一个障碍物 ，那么第 列之后就一定不会贡献。

考虑树状数组很好维护，记录 表示第 列再当前扫描线之前是否存在障碍，然后可以 维护，另外一个是单点修改前缀查询，所以 用 解决即可。

注意可能会存在两者都可以到达的部分，所以我们不能算重，稍微变换一下或者容斥一下即可。

AC Code
 
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
// ----- Eternally question-----
// Problem: B. 【noip赛前20天冲刺集训 day6】讴不死塔扣(obstacle)
// Contest: undefined - 23noip赛前20天冲刺 day6
// URL: http://zhengruioi.com/contest/1472/problem/2642
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-17 19:06:22
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
int N,M,K;
struct BIT
{
	int Tre[MAXN],Siz;
	inline void build(int n){ Siz=n;for(int i=1;i<=n;++i) Tre[i]=0; }
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline int get(int l,int r){ return query(r)-query(l-1); }
}Tre;
std::vector<int>vec[MAXN];
bool unAr[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,K);
	for(int i=1,x,y;i<=K;++i)
	{
		read(x,y);
		vec[x].push_back(y);
	}
	for(int i=1;i<=N;++i) std::sort(vec[i].begin(),vec[i].end());
	int maxlen=vec[1].size()?vec[1][0]-1:M;
	Tre.build(M);
	for(int i=maxlen+1;i<=M;++i) unAr[i]=1,Tre.add(i,1);
	ll ans=0,delta=1;
	for(int i=1;i<=N;++i)
	{
		for(int x:vec[i]) if(!unAr[x]) unAr[x]=1,Tre.add(x,1),--maxlen;
		int nowlen=vec[i].size()?vec[i][0]-1:M;
		if(!nowlen) delta=0;
		ans+=maxlen+delta*Tre.query(nowlen);
	}
	write(ans);
	return 0;
}
/*

*/

C. 钙绿(probability)

题目简介

给定一个有 位的十进制数，值域在 之间，问存在多少个数是 的倍数，且数位和 。对 求出答案。对 取模。

数据范围：

考虑朴素 ，记录状态 表示当前考虑到第 位，前 位数模 为 ，位数和为 。

转移直接 卷积，时间复杂度 。

然后发现对于 的贡献对 取模是有一个循环节的，而这个循环节中的贡献一致，所以我们视作贡献了很多次相同的数，可以进行合并。

具体地，按照 分组，设其中一组的个数为 ，我们对 作插板，将至多 个 分入 组，且每组大小不超过 ，容斥处理上升幂和下降幂系数转移。

时间复杂度 。

另外一种是对 维独立处理， 维作模意义下循环卷积， 维直接卷积，倍增优化成快速幂对 维做 ，将 扩展为 做。时间复杂度 。

然后 维可以预处理 ，枚举 点值乘积，做到 。

AC Code
 
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
118
119
120
// ----- Eternally question-----
// Problem: C. 【noip赛前20天冲刺集训 day6】钙绿(probability)
// Contest: ZROI - 23noip赛前20天冲刺 day6
// URL: http://zhengruioi.com/contest/1472/problem/2643
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-17 09:43:09
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXP=52,MAXM=1e3+10;
const int Mod=998244353;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M,P;
inline int qPow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
int Cntr[MAXP],val[MAXP],len,Tot;
int Mul[MAXM],Inv[MAXM],Down[MAXM],Uppe[MAXM];
inline void build(int n)
{
	Down[0]=Uppe[0]=1;
	for(int i=1;i<=M;++i)
	{
		Uppe[i]=(ll)Uppe[i-1]*(n+i-1)%Mod;
		Down[i]=(ll)Down[i-1]*(n-i+1)%Mod;
	}
}
inline void init(int n)
{
	Mul[0]=1;
	for(int i=1;i<=n;++i) Mul[i]=(ll)Mul[i-1]*i%Mod;
	Inv[n]=qPow(Mul[n],Mod-2);
	for(int i=n-1;~i;--i) Inv[i]=(ll)Inv[i+1]*(i+1)%Mod;
}
int Dp[2][MAXP][MAXM];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,P,M);
	init(MAXM-1);
	int firv=0;
	for(int x=1,pos=1;;pos=pos*10%P,++x)
	{
		if(Cntr[pos]){ len=x-Cntr[pos],firv=Cntr[pos];break; }
		val[++Tot]=pos,Cntr[pos]=x;
	}
	Dp[0][0][0]=1;
	for(int i=1;i<=Tot&&i<=N;++i)
	{
		int op=i&1;
		std::memset(Dp[op],0,sizeof(Dp[op]));
		int siz=i<firv?1:(N-i)/len+1;
		build(siz);
		int lim=std::min((ll)M,(ll)9*siz);
		for(int j=0;j<=lim;++j)
		{
			int x=j*val[i]%P,v=0;
			for(int k=0;;++k)
			{
				if(j-10*k<0) break;
				int vl=1ll*Down[k]*Inv[k]%Mod*Uppe[j-10*k]%Mod*Inv[j-10*k]%Mod;
				add(v,(k&1)?Mod-vl:vl);
			}
			for(int y=0;y<P;++y)
				for(int c=0;c+j<=M;++c)
					add(Dp[op][(x+y)%P][c+j],1ll*Dp[op^1][y][c]*v%Mod);
		}
	}
	ll ans=0;
	for(int i=0,op=std::min(Tot,N)&1;i<=M;++i)
	{
		add(ans,Dp[op][0][i]);
		write(ans,' ');
	}
	return 0;
}
/*

*/

题不改，题意比较神秘，题解更神秘，听说暴力剪枝有 的分。

相关文章