首页 > 其他分享 >CSP-CCF★★201803-2碰撞的小球★★

CSP-CCF★★201803-2碰撞的小球★★

时间:2024-09-11 20:22:44浏览次数:14  
标签:int 碰撞 线段 位置 小球 偶数 CCF 201803 CSP

目录

一、问题描述

二、解答

三、总结


一、问题描述

问题描述

  数轴上有一条长度为L(L为偶数)的线段,左端点在原点,右端点在坐标L处。有n个不计体积的小球在线段上,开始时所有的小球都处在偶数坐标上,速度方向向右,速度大小为1单位长度每秒。
  当小球到达线段的端点(左端点或右端点)的时候,会立即向相反的方向移动,速度大小仍然为原来大小。
  当两个小球撞到一起的时候,两个小球会分别向与自己原来移动的方向相反的方向,以原来的速度大小继续移动。
  现在,告诉你线段的长度L,小球数量n,以及n个小球的初始位置,请你计算t秒之后,各个小球的位置。

提示

  因为所有小球的初始位置都为偶数,而且线段的长度为偶数,可以证明,不会有三个小球同时相撞,小球到达线段端点以及小球之间的碰撞时刻均为整数。
  同时也可以证明两个小球发生碰撞的位置一定是整数(但不一定是偶数)。

输入格式

  输入的第一行包含三个整数n, L, t,用空格分隔,分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。
  第二行包含n个整数a1, a2, …, an,用空格分隔,表示初始时刻n个小球的位置。

输出格式

  输出一行包含n个整数,用空格分隔,第i个整数代表初始时刻位于ai的小球,在t秒之后的位置。

样例输入

3 10 5
4 6 8

样例输出

7 9 9

样例说明

样例输入

10 22 30
14 12 16 6 10 2 8 20 18 4

样例输出

6 6 8 2 4 0 4 12 10 2

数据规模和约定

  对于所有评测用例,1 ≤ n ≤ 100,1 ≤ t ≤ 100,2 ≤ L ≤ 1000,0 < ai < L。L为偶数。
  保证所有小球的初始位置互不相同且均为偶数。

二、解答

(1)思路:建立一个球的结构体,存放球当前所在位置和方向。利用for循环,记录时间是从1到t,先根据上一秒所在位置进行当前时刻小球运动方向的判断,再进行位置的计算。

(2)难点在于:如何确定两个小球是否碰撞(在这一块我纠结了好长时间,说明在for循环的遍历上我还是有所欠缺┭┮﹏┭┮)

第一版:错误原因:看似是每一个球都与其他球进行了比较,当坐标相同时,方向交换。因为小球速度相同,所以碰撞只能在异向上发生。但是,这样写其实重复了2次,最后交换又交换,就相当于没有交换了。

​​for (int i = 1; i <=n; i++)//检查两球是否碰撞
{
	
	for(int m=1;m<=n;m++)
	{
		
		if (ball[i].a == ball[m].a && (i != m))
		{
			bool x = ball[i].flag;
			ball[i].flag = ball[m].flag;
			ball[m].flag =x;
			
		}
	}
		
}

第二版:错误原因:以为只有相邻序号的球才能发生碰撞,所以直接没有用两个for循环,而是将i分别与i-1和i+1两个相邻的位置进行比较。但是,由样例二可以看到,其实这些球放置很随意,可能序号小的球放在了序号大的球的老后面,并不是只有相邻序号的球才能发生碰撞

第三版:错误原因:执着于使用第一版两个for循环语句,也不知道改动一下,甚至引入了vector,典型地将简单问题复杂化了。并且写的逻辑也是有问题的。

v.clear();
for (int i = 1; i <=n; i++)//检查两球是否碰撞
//也可能不按照顺序摆放
{
	
	for(int m=i+1;m<=n;m++)
	{
		bool re = false;
		for (int k = 0; k < v.size(); k++)
		{
			if(m==v[k])
			{
				re = true;
			}
		}
		if (ball[i].a == ball[m].a && (i != m))
		{
			bool x = ball[i].flag;
			ball[i].flag = ball[m].flag;
			ball[m].flag =x;
			v.push_back(m);
		}
	}
		
}

最终版:去除掉了画蛇添足的vector,第二个for循环直接从i+1开始,非常简单地就解决了两球碰撞的问题。

for (int i = 1; i <=n; i++)//检查两球是否碰撞
//也可能不按照顺序摆放
{
	
	for(int m=i+1;m<=n;m++)
	{
		
		if (ball[i].a == ball[m].a && (i != m))
		{
			bool x = ball[i].flag;
			ball[i].flag = ball[m].flag;
			ball[m].flag =x;
			
		}
	}		
}

(3)完整代码

#include<iostream>
//#include<vector>
using namespace std;
//小球的位置和方向(左或右)
struct Ball {
	int a;//位置
	bool flag;//true表示向右
	//bool move;//true表示之前移动过
}ball[101];
int main()
{
	int n, L, t;
	cin >> n >> L >> t;
	for (int i = 1; i <= n; i++)
	{
		cin >> ball[i].a;//初始位置,所有小球的初始位置互不相同且均为偶数。
		ball[i].flag = true;//初始方向均为向右
		//ball[i].move = false;//之前未移动过
	}
	//小球到达线段端点以及小球之间的碰撞时刻均为整数。
	//两个小球发生碰撞的位置一定是整数(但不一定是偶数)。
	//碰撞后小球的相对位置没有发生,只是方向发生了改变
	//小球速度相同,所以碰撞只能在异向上发生
	//vector<int>v;
	for (int j = 1; j <= t; j++)
	//注意这里是从1开始,而不是0;因为是先判断方向,然后在加或减坐标
	{
		//v.clear();
		//主要问题出在这里!!!
		for (int i = 1; i <=n; i++)//检查两球是否碰撞
	    //也可能不按照顺序摆放
		{
			
			for(int m=i+1;m<=n;m++)
			{
				//bool re = false;
				/*for (int k = 0; k < v.size(); k++)
				{
					if(m==v[k])
					{
						re = true;
					}
				}*/
				if (ball[i].a == ball[m].a && (i != m))
				{
					bool x = ball[i].flag;
					ball[i].flag = ball[m].flag;
					ball[m].flag =x;
					//v.push_back(m);
				}
			}		
		}
		for (int i = 1; i <= n; i++)//检查球是否碰到边缘
		{
			if(ball[i].a==L&&ball[i].flag==true)
			{
				ball[i].flag = false;
			}
			if (ball[i].a == 0 && ball[i].flag == false)
			{
				ball[i].flag = true;
			}
			
		}
		for (int i = 1; i <= n; i++)
		{
			if(ball[i].flag==true)
			{
				ball[i].a += 1;
			}
			else if (ball[i].flag == false)
			{
				ball[i].a = ball[i].a - 1;
			}
			
		}
		
	}
	for (int i = 1; i <= n; i++)
	{
		cout << ball[i].a << " ";
	}
	return 0;
}

三、总结

又是在一个地方卡了好久。。。仍然是看似简单、实际上没那么简单的for循环的应用上出现了问题。。。

标签:int,碰撞,线段,位置,小球,偶数,CCF,201803,CSP
From: https://blog.csdn.net/2301_79705447/article/details/142068824

相关文章

  • CSP-CCF ★★201709-2公共钥匙盒★★
    一、问题描述问题描述有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后,再将钥匙放回到钥匙盒中。钥匙盒一共有N个挂钩,从左到右排成一排,用来挂N个教......
  • CCF201712-4行车路线
    题目问题描述小明和小芳出去乡村玩,小明负责开车,小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走,每走1公里小明会增加1的疲劳度。小道不好走,如果连续走小道,小明的疲劳值会快速增加,连续走s公里小明会增加s2的疲劳度。例如:有5个路口,1号路口到2号路口为......
  • CSP-S 2023
    T1直接\(10^{5}\)枚举状态就过了,合法的非零差分数量只可能为\(1,2\)(\(0\)相当于没转,按照题意“都不是正确密码”是不符的)需要注意的是形如09111->10111这样的合法状态#include<bits/stdc++.h>usingnamespacestd;intn;inta[10][9];intp[6];boolche......
  • CSP-S 2023 游记
    在CSP-S2024来临之际,补一下CSP-S2023游记CSP-S开题顺序:T1+T2+T4+T3时间分配:T130min,T21h,T42h,T330min场上即兴考试思路:快速切T1,死磕T2(没想到1h就想到了),接着T4试着AC(然后就深陷其中,红温了),T3场上忘了。T1正常发挥,T2其实也挺谁的,想到\(O(n^2)\)做法就一个......
  • 挑战不可能篇1——洛谷28分钟14道CCF GESP C++ 一级上机题&洛谷14道题题解
    扯谈今天继续挑战不可能:洛谷28分钟14道题这我个人认为不简单,算上编译、提交、命名等杂七杂八的东东之后,只剩下了大约1分钟/题。本次挑战的是CCFGESPC++一级上机题.这竟然能成功!下面附上每一题第一题第二题第三题第四题第五题第六题第七题第八题第九题第十题......
  • ZROI 2024 CSP 七连测
    Day1A.特工若两个特工\(i,j\)成功匹配,当且仅当\(x_i+y_j=x_j+y_i\),移项可得\(x_i-y_i=x_j-y_j\),所以只需要用一个map存一下每个值的数量,统计即可。B.提克塔可头考虑游戏的局面不会很多,最多只有\(3^9\)种情况,且这些情况组成了一个DAG。我们爆搜所有进程(共有\(9!\)......
  • CSP2024-18
    A题意:给出两个\(n\timesm\)的矩阵\(A,B\),一次操作可以使\(A\)或\(B\)的一行/列加一。求使\(A,B\)相等的最小操作次数。数据范围:\(n,m\le10^5,n\timesm\le10^5\)。令\(X=A-B\),则题目转化为每次可以使一行/列加减一,求使得\(X\)全零的最小操作数。设......
  • CSP模拟 矩阵操作
    涉及知识点:就是个推式子+贪心?前言感觉有点板,故记录一下以备后续所用。题意有两个$n\timesm$的矩阵\(A\)和\(B\),每次操作可以把\(A\)或者\(B\)的某一行/列全部\(+1\),最少几次操作\(A=B\)?思路首先想到的肯定是构造一个差分矩阵,即\(D=B-A\),问题转化为从一个零矩......
  • 9.10 模拟赛(炼石计划 11 月 15日 CSP-S 十连测 #10)
    炼石计划11月15日CSP-S十连测#10【补题】-比赛-梦熊联盟(mna.wang)复盘所有题先都浏览了一遍。其中T1见过。但当时是乱搞过的。但怎么乱搞的忘了。那就先做T1。有\(60\)分送的。尝试重新思考乱搞以获取剩余的\(40\)分。中间看了一眼T3。想了一分钟左右就会......
  • CSP模拟 取模
    最近开始写CSP模拟的题,实际上考的题一点也不CSP题意有一个长度为\(n\)的序列\(A\),\(0\leqA_i<k\),你可以每次选取一个区间,将区间内所有元素\(+1\),然后将区间内所有元素对\(k\)取模。问最少几次操作可以把序列中所有元素都变为\(0\)。思路假设现在有一个数列\([2,3,......