上海站2020icpc部分题解

题目链接
题意：题意很简单，就是两个人走随时都可以转弯，问最少的时间覆盖整个线段。
思路：
看了题解，分类讨论，一种是一个人把全部走完，另一种是两个人相对着走，最后一种是两个人分别把自己的一边处理完，假设x在左边，y在右边，那么可以二分判断x最右边的覆盖点与y最左边的覆盖点是否重合。
感想：
太难想了，我数学太烂了。。。一开始没有想到中间回去这种case，光顾着直溜溜的走了，主要原因还是自己贪心不好。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=210,M=10010;
double n,p1,p2,v1,v2;
double x,y;
bool check(double mid)
{
   
	double t1=x/v1;
	double t2=(n-y)/v2;
	if(t1>mid || t2>mid)	return 0;
	double a=max(0.0,(mid-2*t1)*v1);
	double b=max(0.0,(mid-2*t2)*v2);
	if(a+b>=(y-x))	return 1;
	if((mid-t1)/2.0*v1 + (mid-t2)/2.0*v2 >=(y-x))	return 1;
	if((mid-t1)/2.0*v1 + b>=(y-x))	return 1;
	if( a + (mid-t2)/2.0*v2 >=(y-x)) 	return 1;
	return 0;
}
int main()
{
   
	int t;
	cin>>t;
	while(t--)
	{
   
		cin>>n>>x>>v1>>y>>v2;
		if(x>y)
		swap(x,y),swap(v1,v2);
		double res=1e18; 
	//靠一个人走完 
		res=min((n+x)/v1,(2*n-x)/v1);
		res=min(res,min((n+y)/v2,(2*n-y)/v2));
	//相对得走
		res=min(res,max(y/v2,(n-x)/v1)) ;
	// 分别处理各自的一边 
		double l=0,r=1e9;
		while((r-l)>1e-8)
		{
   
			double mid=(l+r)/2;
			if(check(mid))	r=mid;
			else	l=mid;
		}
		res=min(res,r);
		printf("%.10lf\n",res);
	}
	return 0;

}

Mine Sweeper II
题目链接：链接
题意：
玩过扫雷的都懂了，给定a和b扫雷区，每次操作可以将b的炸弹变成数字格，把数字格变成炸弹，操作数不能超过 $n m / 2$ ，让a和b的sum相等
思路：
看了题解才发现一个扫雷图的sum值和他所有位置取反是相同的，那么直接扫描整个地图，记录a和b不同的cnt值，然后分类讨论，，但这个性质是真的看不出来，还是思维练得不够多，后来我想了想其实是对的，一个炸弹只对它周围8个非炸弹格子有贡献，然后取反以后这个贡献变成周围八个是炸弹的格子对他的贡献了，是等价的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=1010,M=10010;
char a[N][N],b[N][N];
int main()
{
   
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int i=0;i<n;i++)
	cin>>b[i];
	int cnt=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		if(a[i][j]!=b[i][j])
		cnt++;
	if(cnt<=n*m/2){
   
	for(int i=0;i<n;i++)
	{
   
		for(int j=0;j<m;j++)
		cout<<a[i][j];
		cout<<endl;
		}	
	}
	else
	{
   
		for(int i=0;i<n;i++)
			{
   
			for(int j=0;j<m;j++)
			if(a[i][j]==b[i][j])
			{
   
				if(b[i][j]=='X')
				cout<<".";
				else
				cout<<"X";
			}
			else
			cout<<b[i][j];
			cout<<endl;
			}
	}
}

链接
M题就不想说了，wa了30发的废物不配说了，注意这题坑点就是文件夹名可能可以重复，他只需要满足父亲的所有子节点中不出现重复就行了。

上海站2020icpc部分题解

全站热榜