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 #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 到达 ::: info 说明 本题实际上直接搬自 CSP-J 2019 纪念品，原题链接：https://www.luogu.com.cn/problem/P5662 ::: ## 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 #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 #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