上海站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发的废物不配说了，注意这题坑点就是文件夹名可能可以重复，他只需要满足父亲的所有子节点中不出现重复就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=1010,M=1010;
int h[N],e[M],ne[M],idx;
int d[N];
bool st[N];
set<pair<int,int>>S;
int n,m;
map<string,int>mp[N];
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int cnt;
int res=0;
bool vis[N];
void dfs(int u)
{
   
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(vis[j])
		continue;
		vis[j]=true;
		if(!st[j])
		{
   
			res++;
			continue;
		}
		dfs(j);
	}
}
int main()
{
   
	int t;
	cin>>t;
	while(t--)
	{
   
		res=0;
		 cnt=0;
		 S.clear();
		memset(st,0,sizeof st);
		memset(vis,0,sizeof vis);
		memset(h,-1,sizeof h);
		idx=0;
		for(int i=0;i<N;i++)
		mp[i].clear();
		cin>>n>>m;
		string s;
		string ss;
		for(int i=0;i<n;i++)
		{
   
			cin>>s;
			int last=0;;
			
			for(int j=0;j<s.size();j++)
			{
   
				ss.clear();
				ss+=s[j];
				int k=j+1;
				while(k<s.size() && s[k]!='/')
				ss+=s[k],k++;
				if(!mp[last].count(ss))
				mp[last][ss]=++cnt,add(last,cnt);
				int ct=mp[last][ss];
				last=ct;
				j=k;
			}
		}
		for(int i=0;i<m;i++)
		{
   
			cin>>s;
			int last=0;
			for(int j=0;j<s.size();j++)
			{
   
				ss.clear();
				ss+=s[j];
				int k=j+1;
				while(k<s.size() && s[k]!='/')
				ss+=s[k],k++;
				if(!mp[last].count(ss))
				mp[last][ss]=++cnt,add(last,cnt);
				int ct=mp[last][ss];
				st[ct]=true;
				last=ct;
				j=k;
			}
		}
		dfs(0);
		cout<<res<<endl;
	}
	return 0;
}