CZOI2023题解

T1 哈希

看起来可能要用到一些高深的知识。实际上，观察到 mod 比较小，我们暴力枚举字符串，最多枚举（一般情况） mod 个不同的字符串，就一定可以找到产生哈希冲突的字符串了。

比较关键的是枚举字符串的长度。题目中mod最大为 $3\times 10^8$ $26^6$差不多也是这个数，所以至少要枚举6位，否则可能把所有字符串都枚举完也不能找到产生碰撞的。

标准算法

cpp
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
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<sstream>
#define int long long
using namespace std;

int t,base,mod,tar;

inline int Hash(string str,int base,int mod){
	int res=0;
	for(int i=0;i<str.size();i++){
		res=(res*base%mod+(int)str[i])%mod; 
	}
	return res;
}

inline void push(string x){
	if(Hash(x,base,mod)==tar){
		cout<<x;
		exit(0);
	}
}

void dfs(string x){
	if(x.size()>=8) return;
	push(x);
	for(int i=0;i<26;i++){
		string y=x+(char)('a'+i);
		dfs(y);
	}
}

signed main(){
	cin>>base;cin>>mod;
	string str;cin>>str;
	tar=Hash(str,base,mod);
	dfs("a");
	return 0;
}

标程中枚举了8位字符串。由于一开始dfs时，第一位字符是固定的，所以实际上是枚举了7位。

如果改为枚举7位（实际上是枚举6位），可能会将 $3\times 10^8$ 的复杂度跑满，所以需要枚举的位数多一些，但也不能太多。

时间复杂度 $O(玄学)$

期望得分 $90-100pts$

T2 拆分

题面非常简洁，但是确实这几道题里面最难的

结合样例给的解释，我们可以很快写出一个暴力算法

算法一

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

int a[10000];
int ans=0;
int n;

void dfs(int s1,int s2){
	if(s1==n){
		ans=max(s2,ans);
		return;
	}
	
	for(int i=2;i<=n-s1;i++){
		dfs(s1+i,s2*i);
	}
}

int main(){
	cin>>n;
	dfs(0,1);
	cout<<ans; 
	return 0;
}

我们观察到，题目最后的答案只和n有关，而对于测试点1-5，n最大只有50，因此我们可以打表

cpp
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
#include<iostream>
using namespace std;

int ans[51];

int main(){
	ans[1]=1;
	ans[2]=2;
	ans[3]=3;
	ans[4]=4;
	ans[5]=6;
	ans[6]=9;
	ans[7]=12;
	ans[8]=18;
	ans[9]=27;
	ans[10]=36;
	ans[11]=54;
	ans[12]=81;
	ans[13]=108;
	ans[14]=162;
	ans[15]=243;
	ans[16]=324;
	ans[17]=486;
	ans[18]=729;
	ans[19]=972;
	ans[20]=1458;
	ans[21]=2187;
	ans[22]=2916;
	ans[23]=4374;
	ans[24]=6561;
	ans[25]=8748;
	ans[26]=13122;
	ans[27]=19683;
	ans[28]=26244;
	ans[29]=39366;
	ans[30]=59049;
	ans[31]=78732;
	ans[32]=118098;
	ans[33]=177147;
	ans[34]=236196;
	ans[35]=354294;
	ans[36]=531441;
	ans[37]=708588;
	ans[38]=1062882;
	ans[39]=1594323;
	ans[40]=2125764;
	ans[41]=3188646;
	ans[42]=4782969;
	ans[43]=6377292;
	ans[44]=9565938;
	ans[45]=14348907;
	ans[46]=19131876;
	ans[47]=28697814;
	ans[48]=43046721;
	ans[49]=57395628;
	ans[50]=86093442;
	int n;cin>>n;
	cout<<ans[n];
	return 0;
}

时间复杂度 O(1)

期望得分 10pts

对于测试点6-10，虽然n依然很小，但是暴力算法已经无法胜任。可以通过各种奇怪的剪枝、优化来获得更高的分数

算法二

我们考虑对于一个已经拆分出来的数 $a_i$，将其继续拆分会不会更优，将 $a_i$ 继续拆分为 $a_i-k$ 和 $k$，有：

$$k\times (a_i-k)\ge a_i$$

$$a_i\ge \frac{k^2}{k-1}$$

对于不等式右边，上下同时除以 $k^2$，再令 $t=\frac{1}{k}$ 分母可化为二次函数形式，开口朝下，有最大值，即原式有最小值4，此时 $k=2$
这样一来，我们得到了一个结论：对于 $a_i\ge 4$ 有 $2\times (a_i-2)\ge a_i$。

也就是说，一个大于等于4的数，一定可以继续被拆分。换句话说，最后拆分出来的数中，一定只会含有 1，2，3。显然，如果拆分出来了1，那么这个方案肯定不是最优的。所以最后拆分出来的数只有2和3

那么对于特殊性质的测试点，我们将n全部拆成3。

最后答案为 $3^{\frac{n}{3}}$，使用快速幂

cpp
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
#include<iostream>
#define int long long
using namespace std;

const int mod=1000000007;
inline int pow1(int a,int p){
	int res=1;
	do{
		if(p&1) res=res*a%mod;
		a=a*a%mod;p>>=1;
	}while(p);
	return res;
}
inline int pow2(int a,int p){
	int res=1;
	do{
		if(p&1) res=res*a;
		a=a*a;p>>=1;
	}while(p);
	return res;
}

signed main(){
	int n,type;
	cin>>n>>type;
	if(n%3==0){
		if(type==0){
			cout<<pow2(3,n/3);
		}else{
			cout<<pow1(3,n/3);
		}
	}
	return 0;
}

时间复杂度 $O(logn)$

结合算法一期望得分38pts

算法三

我们可以有一种直观的感觉：拆成的3越多越好，下面我们来证明一下
设一个数 $k$ 拆分成 $n$ 个2和 $m$ 个3，即有 $2n+3m=k$

我们将2的数量增加 $3d$，3的数量减少$2d$。之所以这样增加和减少，是因为这样做依然可以满足 $2(n+3d)+3(m-2d)=2n+3m=k$。我们只需要证明

$$2^n\times 3^m\ge 2^{n+3d}\times 3^{m-2d}$$

$$2^n\times 3^m\ge 2^n\times 2^{3d}\times \frac{3^m}{3^{2d}}$$

$$1\ge \frac{2^{3d}}{3^{2d}}=(\frac{8}{9})^d$$

即得证

这样一来，我们进行分类讨论

当 $n\%3=0$ 时，答案为 $3^{\frac{n}{3}}$

当 $n\%3=1$ 时，答案为 $3^{\frac{n}{3}-1}\times 2\times 2$

当 $n\%3=2$ 时，答案为 $3^{\frac{n}{3}}\times 2$

cpp
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
121
122
123
124
125
#include<iostream>
#include<cstring>
#define int long long
using namespace std;

struct Lint{
	int num[2000],len;
	char op;
	Lint(){memset(num,0,sizeof(num));len=1;op='+';}
	Lint(int a){
		memset(num,0,sizeof(num));len=1;op='+';
		int t=0;
		while(a){
			t++;
			num[t]=a%10;
			a/=10;
		}
		len=t;
	}
};
Lint operator*(Lint a,Lint b){
	Lint c;
	c.len=a.len+b.len+1;
	for(int i=1;i<=a.len;i++){
		for(int j=1;j<=b.len;j++){
			c.num[i+j-1]+=a.num[i]*b.num[j];
		}
	}
	for(int i=1;i<=c.len;i++){
		if(c.num[i]>=10){
			c.num[i+1]+=c.num[i]/10;
			c.num[i]%=10;
			c.len=max(c.len,i+1);
		}
	}
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
}
Lint operator/(Lint a,int b){
	Lint c;
	c.len=a.len;
	int d=0;
	for(int i=a.len;i>=1;i--){
		d=d*10+a.num[i];;
		c.num[i]=d/b;
		d%=b;
	}
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
} 
void print(Lint a){
	if(a.op=='-') cout<<"-";
	if(a.len==0) cout<<0;
	else{
		for(int i=a.len;i>=1;i--){
			cout<<a.num[i];
		}
	}
	cout<<endl;
}

const int mod=1000000007;
inline int pow1(int a,int p){
	int res=1;
	do{
		if(p&1) res=res*a%mod;
		a=a*a%mod;p>>=1;
	}while(p);
	return res;
}
inline int pow2(int a,int p){
	int res=1;
	do{
		if(p&1) res=res*a;
		a=a*a;p>>=1;
	}while(p);
	return res;
}
inline Lint pow3(Lint a,Lint p){
	Lint res(1);
	do{
		if(p.num[1]&1) res=res*a;
		a=a*a;p=p/2;
	}while(p.len);
	return res;
}

signed main(){
	int n,type;
	cin>>n>>type;
	if(type==1){
		if(n%3==0){
			cout<<pow1(3,n/3);
		}
		if(n%3==1){
			cout<<pow1(3,n/3-1)*4%mod;
		}
		if(n%3==2){
			cout<<pow1(3,n/3)*2%mod;
		} 
	}else{
		if(n<=50){
			if(n%3==0){
				cout<<pow2(3,n/3);
			}
			if(n%3==1){
				cout<<pow2(3,n/3-1)*4%mod;
			}
			if(n%3==2){
				cout<<pow2(3,n/3)*2%mod;
			} 
		}else{
			if(n%3==0){
				print(pow3(Lint(3),n/3));
			}
			if(n%3==1){
				print(pow3(Lint(3),n/3-1)*Lint(4));
			}
			if(n%3==2){
				print(pow3(Lint(3),n/3)*Lint(2));
			} 
		}
	}
	return 0;
}

时间复杂度 $O(logn)$

期望得分100pts

值得一提的是，高精度+快速幂，而不是一个一个乘起来可以降低时间复杂度。不过本题并没有特意去卡，放开了时限

快速幂时使用高精除以低精而不是高精除以高精

另一种解法

我们可以在打表的时候顺便输出最优拆分方案的方案内容，就可以发现规律

这样一来这道题就成了大水题了

T3 到达

T4 纯爱

题目很长，需要理解清楚题意才能着手这道题。为了防止各位看不懂题意，出题人还在题目中加了个比较全面的例子。

首先，对于一个询问天数 $t_i$，想要让Umy 完全攻略 Merry 所用的时间大于 $t_i$，由于增加的速度为 $v$，所以好感度总共至少要增加 $v_i\times v$。没有产生矛盾的话，好感度增加 $L$ 就攻略掉了。现在多出来了至少 $v_i\times v-L$，显然是因为产生了矛盾。因为我们要产生最少的矛盾，我们优先触发使好感度下降最多的矛盾。特判 $v_i\times v-L＜0$ 的情况。

算法一

cpp
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
#include<iostream>
#include<algorithm>
#include<cstdio>
#define int long long
using namespace std;

inline int read(){
	int res=0,ch=getchar(),f=1;
	while(!isdigit(ch) and ch!=EOF){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+(ch-'0');
		ch=getchar();
	}
	return res*f;
}

int n,L,v;
int a[2000010];

signed main(){
	n=read(),L=read(),v=read();
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		a[i]=x-y;
	}
	sort(a+1,a+n+1,[](int x,int y){
		return x>y;
	});
	int q=read();
	while(q--){
		int t=read();
		t=t*v-L;
		if (t<0){
			printf("0\n");
		}else{
			int ans=0;
			for(int i=1;i<=n;i++){
				t-=a[i];
				ans++;
				if(t<0) break;
			} 
			if(t>=0) printf("kdl\n");
			else printf("%lld\n",ans);
		}
	}
	return 0;
}

时间复杂度 $O(nlogn+qn)$

期望得分50pts

算法二

考虑进一步优化。

我们发现，对于每个询问，我们都是从前往后去一个一个减处理出来的 $a[i]$ ，中间做了许多重复操作。

我们使用前缀和优化，令 $s[i]=a[i]+s[i-1]$ 。这样，我们只需要找到第一个大于 $v_i\times v-L$ 的 $s[]$ 即可

cpp
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
#include<iostream>
#include<algorithm>
#include<cstdio>
#define int long long
using namespace std;

inline int read(){
	int res=0,ch=getchar(),f=1;
	while(!isdigit(ch) and ch!=EOF){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+(ch-'0');
		ch=getchar();
	}
	return res*f;
}

int n,L,v;
int a[2000010],s[2000010];

signed main(){
	n=read(),L=read(),v=read();
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		a[i]=x-y;
	}
	sort(a+1,a+n+1,[](int x,int y){
		return x>y;
	});
	for(int i=1;i<=n;i++){
		s[i]=a[i]+s[i-1];
	}
	int q=read();
	while(q--){
		int t=read();
		t=t*v-L;
		if (t<0)
			printf("0\n");
		else if (s[n]>t)
			printf("%lld\n",upper_bound(s+1,s+n+1,t)-s);
		else
			printf("kdl\n");
	}
	return 0;
}

时间复杂度 $O((n+q)logn)$

期望得分100pts

注意，需要开long long，否则测试点#6和#7会wa。另外本题还需要快读或者cin/cout关闭流同步，否则最后三个测试点会tle