凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

CSP-J2023 赛后总结_csp-j2023 公路

作者：凡人多烦事01 | 2024-02-09 18:18:03

踩

csp-j2023 公路

· 比赛概况

洛谷自测：

总分： 165 / 400

T1	T2	T3	T4
AC	55	0	10

T2很可惜，因为累加器没开 $long$ $long$ ，WA了45分（QwQ）

· 比赛过程

按照顺序主攻前两题

第一题，不出意外不是一道纯暴力能秒的题，是一道需要推规律的约瑟夫环

第二题，读题以为挺难，其实不然，预处理 + 循环累加就能过，可惜忘记开 long long 了。。。

第三题，我太弱，读不懂题目一堆奇妙的不明数学语言，暴力也没法打，只能不可以总司令，循环输出 NO ，一分没骗到

第四题，万恶的图论，赛前练的全忘了，输出-1，拿了10分

· 题目分析

ps : T3 T4 直到赛后也没看懂。。。所以这里我只说前两题

（我会继续研究 T3 T4 ，看懂后尽快更新这篇博客）

T1【小苹果（apple) 】

· 题目大意

共有 $n$ 个苹果线性排列，每天从左侧第 $1$ 个苹果起，每间隔 $2$ 个苹果拿走一个苹果，每次拿完后，将剩下的苹果按原来的顺寻重新排成一列。

问：

1. 多少天能取走所有的苹果

2. 第 $n$ 个苹果是在第几天被拿走的

· 赛中思考

先打了个暴力，看眼样例发现 $n$ $\leq$ 10^18 ，暴力肯定过不了全部样例，但是暴力代码也不要删掉，因为可以在写出正确代码后用来写对拍验证（对拍我们待会说），最终也是推出了规律，详见题解部分。

· 解题思路

首先要明确本题是一道典型的约瑟夫环问题，暴力过不了，考虑优化思路

我们用数字代表这个苹果的编号，每次标红的数字为被拿走的苹果的编号，当 $n$ = 8 时，

第 0 天（初始状态）： 1 2 3 4 5 6 7 8

第 1 天：1 2 3 4 5 6 7 8

= 2 3 5 6 8

第 2 天：2 3 5 6 8

= 3 5 8

第 3 天：3 5 8

= 5 8

第 4 天：5 8

= 8

第 5 天：8

= 无

则当 $n$ =8 时，5 天能拿完所有苹果，编号为 $n$ (8) 的苹果第 5 天被拿走。

首先看第一问：多少天能取走所有苹果

这个问题等价与 求第几天时苹果的数量等于0 ，那我们就可以求出每次会减少多少苹果，再用当前苹果数减去即可。

根据刚才举的样例，可以发现每次取苹果时，只要苹果的数量不为 0 ，总是要取走第 1 个苹果

然后 $2$ ~ $n$ 这个范围里，因为每隔两个苹果都要取走一个，也就是每 $3$ 个苹果都要拿走一个，

所以这个部分共要取走 $(n-1)/3$ 个苹果。

综上所述，记当前剩余的苹果数量为 $cnt$ ，则当前需取走的苹果数量为 $1+((cnt-1)/3)$

只需要循环对 $cnt$ 做减法并判断天数即可

现在我们再来看第二问：第 $n$ 个苹果是在第几天被拿走的

首先，如果第 $n$ 个苹果没有被取走，那么它一定排在这个序列的最后，所以想要判断第 $n$ 个苹果当前是否被取走，就判断一下当前这个序列的最后一个位置是否会被取走，根据上面第一问说的，每次会拿走第一个，后面 $2$ ~ $cnt$ 这个序列每有三个苹果就会取走一个，所以就判断一下 $cnt-1$ （也就是当前苹果数量-1 ，也可理解为 $2$ ~ $cnt$ 这个序列的苹果数量）是否可以被 3 整除

如果可以，就把当前的天数记录下来并标记为已取走，避免重复计算，最后输出即可

奉上代码

· AC代码 & 赛时代码


#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout);
	cin>>n;
	long long cnt=n,ans=0,ans1=0;
	bool flag=0;
	if(n==1){
		cout<<"1 1";
		return 0;
	}
	while(cnt>0){
		ans++;
		if((cnt-1)%3==0&&flag==0){
			ans1=ans;
			flag=1;
		}
		cnt-=(1+((cnt-1)/3));
	}
	cout<<ans<<' '<<ans1;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

· 附

这里给大家介绍一种竞赛中非常有用的一种技巧——对拍

首先：什么是对拍？它的用途是什么呢？

对拍是一种在赛场或平时验证某一程序的正确性的程序，它可以检测你写出的 “正解程序”是否是正确的

对拍有两种实现方式，一种是写程序，一种是朴素的手动对拍（手动判断数据是否一致）

其中手动对拍非常的简单，只需要你写一个保证可以通过部分数据的暴力程序，和一个优化后但不确定正误的程序，分别执行，并使用相同的输入数据，对比两个程序的输出是否一致即可。

接下来我们来说一下对拍的程序实现：

想要对拍需要三个程序：

1.一个保证对的朴素算法命名为 bl.cpp ，编译运行生成 bl.exe

2.正解代码，或优化后的代码命名为 true.cpp ，编译运行生成 true.exe

3.随机数生成函数 rand.cpp ，编译运行生成 rand.exe

4.创建一个名为 data.in 的文件，用来输入随机数据

5.创建 bl.out 和 true.out 分别用来接收 1 和 2 两个程序的输出

6.创建一个对拍 C++ 项目，在里面调用以上的文件并比较，最后反馈出结果

对拍程序代码：


#include<bits/stdc++.h>
int main(){
    for(int i=1;i<=S;i++){
     	system("rand.exe");
     	double start=clock();
     	system("true.exe");
     	double end=clock();//计算所用的时间，可以时间clock()函数，分别记录时间Start,End，相减即可得出答案
     	system("bl.exe");
     	if(system("fc true.out bl.out")){
     		puts("Wrong Answer!");
     		return 0;
		}
		else{
			printf("Accepted! 测试点 %d  用时：%lf",i,end-start);
		}
	}
	return 0;
}

随机数rand.cpp的代码，数据范围要根据实际题目的数据范围定，下面的代码可以重复生成<mod 的随机数


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll Random(ll mod)
{
    ll ans = 2147483647;
    return ans = ans * rand() % mod + 1;
}
 
int main(){
    ll n;
    ll mod=();//根据题目定范围
    while (1)
    {
        n = Random(mod); 
        printf("%lld\n", n);
    }
    return 0;
}

正解代码的模板，注意前面 freopen 的写法


#include<bits/stdc++.h>
int main(){
	freopen("data.in","r",stdin);
	freopen("true.out","w",stdout);
	
	//程序 
	fclose(stdin);
	fclose(stdout);
	return 0;
}

暴力的模板，同样注意 freopen


#include<bits/stdc++.h>
int main(){
	freopen("data.in","r",stdin);
	freopen("bl.out","w",stdout);
	
	//程序 
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2【公路（road）】

· 题目大意

小苞准备开着车沿着公路自驾。

公路上一共有 $n$ 个站点，编号为从 $1$ 到 $n$ 。其中站点 $i$ 与站点 $i+1$ 的距离为 $v_{i}$ 公里。

公路上每个站点都可以加油，编号为 $i$ 的站点一升油的价格为 $a_{i}$ 元，且每个站点只出售整数升的油。

小苞想从站点 $1$ 开车到站点 $n$ ，一开始小苞在站点 $1$ 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 $d$ 公里。问小苞从站点 1 开到站点 $n$ ，至少要花多少钱加油？

· 赛中思考

一道贪心的题目（？），我的思路是预处理一下，算出每一段路的油是从哪个站点加的，然后累加求和，最后输出

· 解题思路

首先读入数据，注意，因为路程的数量为 $n-1$ ，所以输入时要做好处理

然后我开了两个数组， $minn$ [] 和 $id$ [] ，

其中 $minn$ 数组是用来前缀和(又像是动态规划) 求当前这个站点以及站点前的油钱最小值，

$id$ 数组是用来存当前从（ $i-1$ ）~ $i$ ，这段距离消耗的油是从哪个站点加的。

然后开始循环判断，找到一段 $id[i]$ 的值相等的序列，表示这一段连续的路程的油都是从 $id[i]$ 的站点加的，然后把这个站点的路程累加，

因为只出售整数升的油，所以需要加一个上取整函数 $ceil()$ ，

然后————这里又有一个细节，因为加了上取整函数，所以可能会比计划要走的距离多走一部分，

比如说：站点 1 到 2 之间的距离为 10 公里，每一升油可以走 4 公里，这时 ceil( 10 / 4 ) 为 3 ，

3 * 4 = 12 也就是买的 3 升油实际上可以走 12 公里，所以在计算后面的距离的时候就要减去这 2 公里

这一部分就不需要多走一遍了，所以要把每一次计划走的距离减去这个多走的距离，避免重复计算，然后注意处理好下标的变化，最后输出即可

· AC代码


#include<bits/stdc++.h>
using namespace std;
int minn[100005];
int id[100005];
int n,d,v[100005],a[100005],x=0;
long long ans=0;
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	cin>>n>>d;
	for(int i=2;i<=n;i++) cin>>v[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	minn[1]=a[1];
	id[1]=1;
	for(int i=2;i<n;i++){
		if(a[i]<minn[i-1]){
			id[i]=i;
		}
		if(a[i]>=minn[i-1]){
			id[i]=id[i-1];
		}
		minn[i]=min(minn[i-1],a[i]);
	}
	id[n]=id[n-1];
	for(int i=1;i<n;){
		int j;
        long long sum=0;
		for(j=i+1;j<=n&&id[j-1]==id[i];j++){
			sum+=v[j];
		}
		sum-=x;
		x=ceil(1.0*sum/d)*d - sum;
		ans+=ceil(1.0*sum/d)*minn[i];
		i=j-1;
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

~~呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜我的45分 QwQ~~

· 赛后总结

这次的比赛其实发挥的并不是很好，前两题思路完全没错，可是竟然犯了数据类型的问题，

这次比赛我是奔着省一去的，但这 45 分，可能让我与它擦肩而过，也许这次充满遗憾，

可仔细一想，收获确实满满

虽有一些遗憾，但这毕竟我初中生涯的第一年，之后的路还长，谁也说不准未来会怎样

昨夜测完分后，漫步于小区：品碎玉之清辉兮，感世事之难料；觉枯蝶之须臾兮，叹年华之易老。

可转念一想——玉虽碎兮，已放清辉，不觉碎之可憾；蝶虽谢兮，已历春秋，不感谢之可惜。过去了的不必叹息，曾经逝去的，都将成为下一步航行的羽翼，助逐梦者扬帆远航。

“凡所过往，皆为序章”，把苦水铸成利剑，破现实之魔障，就彼岸之辉煌。这不正是CSP2023对我的意义吗？

~~（这辈子不会再犯 long long 开成 int 的错了）~~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/72620