Znzryb's Blog
0%

2025牛客WC3-C-智乃的Notepad(Easy version)

Posted on Edited on

思路讲解

这题代码挺简单的，这个代码看起来长，实际上全部是快读模版和一些宏定义

然后我们来讲一讲，实际上就是字典树建树过程。

然后其实就是字典树每次扩充新节点++ans；最后ans就是字典树的节点数量（严格来说是不包含idx=0的节点的数量），当然此时不是答案，根据观察，所有的节点都需要被回退，只有最长的字符串不需要回退，所以答案就是

1
cout<<ans*2-maxLen<<'\n';

除了最长字符串上的节点，全部都要打一遍，然后再删除掉，故ans*2，然后最长的字符串不需要回退，-maxLen

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75219752

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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end();

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e5)+10;

inline string reads()
{
	string str="";
	char ch=getchar();
	//处理空格或回车 
	while(ch==' ' || ch=='\n' || ch=='\r')
		{
			ch=getchar(); 
		}
	//读入
	while(ch!=' ' && ch!='\n' && ch!='\r')
		{
			str+=ch;
			ch=getchar();
		} 
	return str;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int N,T;
int idx;
int nex[MAXN*10][28]; //wei[MAXN*10];
ll ans;
int L,R;

inline void buildTree(string &s){
	int node=0;
	int len=SZ(s);
	FOR(i, 0, len-1){
		if(nex[node][s[i]-'a']==0){
			nex[node][s[i]-'a']=++idx;
			node=idx;
			// wei[idx]+=len-i;
			++ans;
		}else{
			node=nex[node][s[i]-'a'];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read(),T=read();
	int maxLen=0;
	FOR(i, 1, N){
		string s;
		s=reads();
		maxLen=max(maxLen,SZ(s));
		buildTree(s);
	}
	L=read();R=read();
	cout<<ans*2-maxLen<<'\n';
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75219747

段错误

字典树一般要开10倍空间。