2024 备战 CSP 模拟赛相关题解

发表于 分类于 ， ， ， 阅读次数： 本文字数： 7.2k 阅读时长 ≈ 7 分钟
自行车的模拟题

免责声明：视频加载因为是 github 托管，极慢，望请谅解

CSP-S 第一次模拟

T1

整体思路：二分答案 \(+\) 人类智慧剪枝。

二分四盏灯的最小耗电量之和。

che 函数考虑左上角和右下角。

↓以后网格上灯的叫法↓ ↓以后网格上灯的叫法↓
\(a\) \(b\)
\(c\) \(d\)

也就是说考虑 \(a\) 和 \(d\)。（其他任意两盏灯也可，本文以 \(a,d\) 为参考讲解）（UPD：zxz 讲到其他的会 TLE）

先两层循环枚举 \(a\) 和 \(d\) 分配的电量，然后看 \(a\) 和 \(d\) 还需要的亮度的较大值，和剩下多少电量可以分配。

如果剩下电量的一半小于 \(a\) 和 \(d\) 还需要的亮度的较大值，continue 掉（即无论怎么分配都没法使 \(a\) 或 \(d\) 亮度够）。

1
2
3
LL adneed=max(a-j/4-i,d-i/4-j);
LL lef=mid-i-j;
if(lef/2<adneed)continue;

然后，看 \(b\) 和 \(c\) 分别还需要多少电量。

1
2
LL blef=max(b-i/2-j/2,0LL);
LL clef=max(c-i/2-j/2,0LL);

但此时我们会发现一个问题：\(b\) 和 \(c\) 互相牵制。

考虑再套一层二分，二分给 \(b\) 的电量（尽量使其接近 blef，留更多给 \(c\)）。

1
2
3
4
5
6
7
8
9
ll=-1;
rr=lef+1;
while(ll+1<rr)
{
  mmiidd=ll+rr>>1;
  LL t=mmiidd+(lef-mmiidd)/4;
  if(t>=blef)rr=mmiidd;
  else ll=mmiidd;
}

最后判断一下 \(b\) 和 \(c\) 的亮度是否合法，合法就 return 1。

时间复杂度 \(O(n^2log^2 n)\)，理论要跑大约 \(6,561,000,000\) 次（约二十秒）。时间复杂度非常劣，但跑的贼快，因为显然远远跑不满（大概只能跑到理论复杂度的 \(\frac{1}{200}\)，即约 \(100\) 毫秒（我的代码跑这题测试点最多用了 \(103\) 毫秒）），所以比较推荐这种人类智慧做法。

为啥跑不满？

if(lef/2<adneed)continue; 拦下了很多不合法的。

而且内层二分的 lef 不会很高。

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<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
    x=0;
    i128 f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
    if(x<0)
    {
    	x=-x;
    	putchar('-');
    }
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
LL a,b,c,d,l=-1,r=6001,mid,ll,rr,mmiidd;
bool che(LL mid)
{
	rep(i,0,a,1)
	{
		rep(j,0,d,1)
		{
			LL adneed=max(a-j/4-i,d-i/4-j);
			LL lef=mid-i-j;
			if(lef/2<adneed)continue;
			LL blef=max(b-i/2-j/2,0LL);
			LL clef=max(c-i/2-j/2,0LL);
			ll=-1;
			rr=lef+1;
			while(ll+1<rr)
			{
				mmiidd=ll+rr>>1;
				LL t=mmiidd+(lef-mmiidd)/4;
				if(t>=blef)rr=mmiidd;
				else ll=mmiidd;
			}
			if(rr+(lef-rr)/4>=blef&&rr/4+(lef-rr)>=clef)
			{
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	cin>>a>>b>>c>>d;
	while(l+1<r)
	{
		mid=l+r>>1;
		if(che(mid))r=mid;
		else l=mid;
	}
	cout<<r<<endl;
	return 0;
}

T3

截至题解在 2024/9/4 22:40 UPD 唯一 AC，耶。

对了有一说一要是这是 OI 赛制我就只有 \(50 \ pts\)。

倒反天罡了属于是。原因是最大值变量 mc 初值写挂。

UPD：赤石了，有原题，我还调那么久/fn。

神仙贪心。

一眼贪心想到 A 和一堆 B 交错排，实际上是对的，证明略。

实际实现见注释。（其实是我不会梳理这题的思路）

UPD：临危受命，嗓子废了，不会写也得写。

但还是不会写，于是完善注释。

说一下如何想到的吧，就是上面的基础思路，然后我想到：转换次数可以不同，而且枚举转换次数不会超时，里面就按题意来贪心。

于是这个方法就出来了。

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
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	x=0;
	i128 f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x<0)
	{
		x=-x;
		putchar('-');
	}
	if(x>9)write(x/10);
	putchar((x%10)^48);
}
LL t,n,m,a,b,c,mc,sum,tt,ttt;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>a>>b>>c;
		mc=(n-1)/a+(m-1)/b+2;//初值，即 AAAABBBB 排列
    //50 pts 因为写成 (n-1)/a+(m-1)/b+1，但是 RE 至今原因不明
		tt=min(n,m/c);//可以 AB 转换的最多次数
		rep(i,1,tt,1)//枚举次数
		{
			sum=i*2;//i*2 个 A->B 或 B->A（包括了第一个和“第零个”）
			if(c>b)//i 个长度为 c 的 B 串的总贡献
			{
				sum+=(((c-1)/b)*i);
			}
      //处理剩下的 A
			if(n-i>0)//A 够
			{
				sum+=((n-i-1)/a+1);//末尾放连续的 A
			}
      //处理剩下的 B
			if(m-i*c>=1)//B 的个数够
      //为什么是 >=1 而不是 >=0 ？因为 =0 的话相当于没有能“分配”的 B，不如不讨论，>=1 的话可以扔一个在末尾（直接贡献加一，贪心地选择这样做）再讨论剩下的
			{
				sum++;//结尾的第一个 B 的贡献
				LL lef=m-c*i-1;//剩的 B 的数量（lef=left（剩下的），但我怕关键字）
        //给前面的“凑整”
				if(c<=b)//有 b 个了就已经能转
				{
					ttt=min(i,lef/(b+1-c));//min(B 串个数,(剩下的)除以(c 个凑成 b+1 个还要的))
          //b+1 是因为要 b+1 个而不是 b 个才能加一个权值
					sum+=ttt;//加贡献
					lef-=ttt*(b+1-c);//减数量
				}
				else//有 b 个还不能转
				{
					ttt=min(i,lef/(b+1-c%b));
          //min(B 串个数,(剩下的)除以(需要补的“零头”))
          //![](https://cdn.luogu.com.cn/upload/image_hosting/wihugaum.png) 放张图辅助理解
          //因为贪心的想，能补全肯定补全
					sum+=ttt;//加贡献
					lef-=ttt*(b+1-c%b);//减数量
				}
				sum+=lef/b;//剩下的全部在末尾
			}
			mc=max(mc,sum);
		}
		cout<<mc<<endl;
	}
	return 0;
}

CSP-J 第一次模拟

T4

邪门 while 加贪心。

感觉想起来比 T2、T3 更简单，也许是我的方法太过邪门了吧。

首先，一个石头一个石头跳和一次性越过多个石头没有任何区别，所以我觉得可以仅考虑每次跳一个石头。

想到 DP，\(dp_{i,j,0/1}\)，然而有后效性，我就弃置了这个想法。

然后，想起初学时学的 while 循环，觉得好像可以拿这个做。

na 记录青蛙 A 的位置，nb 同理。tyq 若为 1 则表示跳跃器在 A 手里，2 表示跳跃器在 B 手里。

讲解参见代码注释。

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
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
    x=0;
    i128 f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
    if(x<0)
    {
    	x=-x;
    	putchar('-');
    }
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
LL n,m,k,q,a[1010],b[1010],tyq=1,na,nb,sum;
int main()
{
	cin>>n>>m>>k>>q;
	rep(i,1,n,1)cin>>a[i];
	rep(i,1,n,1)cin>>b[i];
	while(na<n||nb<n)//每一次代表一个“回合”
	{
		if(tyq==1)//跳跃器在 A 手里
		{
			if(na<n&&labs(a[na+1]-b[nb])<=q)//若 A 能跳，且跳完能传递跳跃器，则 A 跳
			{
				na++;
				continue;//下一回合
			}
			if(nb<n&&b[nb+1]-b[nb]<=m)//若 B 能不带跳跃器跳，则 B 跳
			{
				nb++;
				continue;
			}
			if(nb<n&&b[nb+1]-b[nb]>m&&labs(a[na]-b[nb])<=q)//B 不能不带跳跃器跳且 A 能传递跳跃器，则传递，然后 B 跳
			{
				sum++;//次数加一
				tyq=2;//跳跃器给 B
				nb++;//B 跳
				continue;
			}
			na++;
		}
		else
		{
			if(nb<n&&labs(b[nb+1]-a[na])<=q)
			{
				nb++;
				continue;
			}
			if(na<n&&a[na+1]-a[na]<=m)
			{
				na++;
				continue;
			}
			if(na<n&&a[na+1]-a[na]>m&&labs(b[nb]-a[na])<=q)
			{
				sum++;
				tyq=1;
				na++;
				continue;
			}
			nb++;
		}
	}
	cout<<sum<<endl;
	return 0;
}