2020 icpc 上海

2020 icpc 上海

1. Mine Sweeper II 思维

大意：类似扫雷，给两个n*m 大小的矩阵A,B，‘X’表示雷，‘.’代表该位置是数字，数字的值是周围八个格子的雷的数量，问是否能不超过 n *m/2(下取整)次 *** 作，使B的数字之和等于 A。输出修改后的矩阵，如果不能输出-1

思路：看到 n*m/2 次 *** 作，下意识感觉就两种情况。显然对于 B 和 A 不一样的个数小于 *** 作限制的话，我们可以把 B 修改成和 A 一样输出就好了。对于 不一样的个数大于的情况，我们从反方向思考，那么一样的的个数一定是小于 *** 作限制的。然后就大胆猜结论，把 A 的‘.’和‘X’互换，总和不变，随便画几个没有规律的图可以验证。

代码如下：

#include 
#define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
#define frep(i,bbb,eee) for(int i=bbb;i>=eee;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define AC signed
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int N=2010,M=998244353;
int n,m;
char s[N][N];
void solve()
{
	cin>>n>>m;
	rep(i,1,n*2)cin>>(s[i]+1);
	int cnt=0;
	rep(i,1,n)
		rep(j,1,m)
		{
			if(s[i][j]!=s[i+n][j])cnt++;
		}
	if(cnt<=n*m/2)
	{
		rep(i,1,n)cout<<(s[i]+1)<<"n";
	}
	else 
	{
		rep(i,1,n)
		{
			rep(j,1,m)
			{
				if(s[i][j]=='.')cout<<"X";
				else cout<<".";
			}
			cout<<"n";
		}
	}
}
AC main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int _=1;
	//cin>>_;
	while(_--)solve();
	return 0;
}

2. Sum of Log 数位DP

大意：略

思路：我们注意到公式计算的是 l o g 2 ( i + j ) log2(i+j) log2(i+j) 下取整，自然而然的联想到二进制的最高位1，

所以我们从二进制的角度思考问题:

对于最高位 1 在第 t 位 的二元组集合：

l o g 2 ( i + j ) = t log_2(i+j) = t log2​(i+j)=t，然后问题就转化成了求 i+j=t 的个数。设个数 为cnt，该集合对最终结果的贡献就是 (t+1)*cnt。并且我们可以通过枚举最高位 1 所在的位置计算出最终答案。

接下来就是怎么求cnt，不难想到可以用数位 DP 计数：

因为 i&j=0, 那么 i+j 实际上就是 i|j，并且对于任意一位i,j 不能同时为 1。根据上面的分析我们知道，我们只需要关注的是最高位 1 在哪？，分两种情况：（1）i 贡献最高位的1。（2）j 贡献的最高位 1。

注意：数位dp过程中 把 i,j 是否到上限也看成 f 数组的状态，否则会超时。因为直接看成状态的话记忆化的集合更大了少了很多搜索。

代码如下：

#include 
#define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
#define frep(i,bbb,eee) for(int i=bbb;i>=eee;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define AC signed
// #define x first
// #define y second
#define int long long 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int N=110,M=1000000007;
int f[35][2][2],a[35],b[35],x,y;
int dp(int len,bool lm1,bool lm2)
{
	if(len==-1)return 1;
	if(f[len][lm1][lm2]!=-1)return f[len][lm1][lm2];
	int mx1=lm1 ? a[len] : 1;
	int mx2=lm2 ? b[len] : 1;
	int cnt=0;
	rep(i,0,mx1)
		rep(j,0,mx2)
			if((i&j)==0)
			{
				cnt+dp(len-1,lm1&&(i==mx1),lm2&&(j==mx2));
				cnt%=M;
			}
	return f[len][lm1][lm2]=cnt;
}
int cale(int x,int y)
{
	int len1=0,len2=0;
	mem(f,-1);
	mem(a,0);
	mem(b,0);
	while(x)
	{
		a[len1++]=x&1;
		x>>=1;
	}
	while(y)
	{
		b[len2++]=y&1;
		y>>=1;
	}
	int ans=0;
	for(int i=0;i=len2);
		if(i=len1,i==len2-1);
		t%=M;
		ans=(ans+(i+1)*t%M)%M;
	}
	return ans;
}
void solve()
{
	cin>>x>>y;
	cout<>_;
	while(_--)solve();
	return 0;
}

3. Walker 二分+分类讨论

大意：两个人初始位置分别为 p1,p2.每秒移动的长度 v1,v2。对于一段长度 [0,n],问每个位置至少被其中一个人访问过所花费的最短时间。（数据均为浮点数）

思路：根据题目我们不难发现可以二分时间，主要是怎么判定。我们可以通过时间先求出二人走的路程，然后就是分情况讨论。不妨令 p 1 < p 2 p_1

（1）考虑单独一个人走完，

（2）考虑两个人都相向而行

（3）考虑两个人相离而行

（1）其实就是两人同向的情况，（2）（3）是两人反向，所以一定包含了所有的情况

代码如下：

#include 
#define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
#define frep(i,bbb,eee) for(int i=bbb;i>=eee;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define AC signed
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int N=1010,M=998244353;
double n,p1,v1,p2,v2;
bool check(double t)
{
	double s1=t*v1;
	double s2=t*v2;
	if(s1>=p1+n||s1>=2.0*n-p1||s2>=p2+n||s2>=2.0*n-p2)return 1;
	if(s1>=n-p1&&s2>=p2)return 1;
	if(s1>=p1&&s2>=n-p2)
	{
		double x=max({p1,s1-p1,(s1+p1)/2.0});
		double y=max({n-p2,s2+p2-n,(s2+n-p2)/2.0});
		return x+y>=n;
	}
	return 0;
}
void solve()
{
	cin>>n>>p1>>v1>>p2>>v2;
	if(p1>p2)swap(p1,p2),swap(v1,v2);
	double l=0,r=10000010;
	while(r-l>1e-8)
	{
		double mid=(l+r)/2.0;
		if(check(mid))r=mid;
		else l=mid;
	}
	printf("%.10fn",l);
}
AC main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);
	int _=1;
	cin>>_;
	while(_--)solve();
	return 0;
}

总结：分类讨论先分大情况，然后细分。不要一把抓。

4. Fibonacci 签到
5. Sky Garden 计算几何

思路：数据范围不大，可以直接暴力枚举计算

6. Gitignore 模拟

大意：题目很难懂，难度并不大

思路：先不考虑那些不能删除的路径。对于那些路径，我们不难想到，要使删除的路径最少，那么删除的路径越靠前越好。但是规定了写不能删除的，我们可以把不能删除的标记。在此基础上尽量删除靠前的。代码如下：

#include 
#define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
#define frep(i,bbb,eee) for(int i=bbb;i>=eee;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define AC signed
// #define x first
// #define y second
#define int long long 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int N=1000010,M=1000000007;
int n,m;
string s[110],t[110];
map mp,d;
void solve()
{
	cin>>n>>m;
	rep(i,0,n-1)cin>>s[i];
	rep(i,0,m-1)cin>>t[i];
	mp.clear();
	d.clear();
	rep(i,0,m-1)
	{
		string tmp="";
		for(auto x:t[i])
		{
			if(x=='/')mp[tmp]=1;
			else tmp+=x;
		}
		mp[tmp]=1;
	}
	int ans=n;
	rep(i,0,n-1)
	{
		string tmp="";
		int len=s[i].size();
		rep(j,0,len-1)
		{
			auto x=s[i][j];
			if(x!='/')tmp+=x;
			if(x=='/'||j==len-1)
			{
				if(d.count(tmp))
				{
					ans--;
					break;
				}
				if(!mp.count(tmp))
				{
					d[tmp]=1;
					break;
				}
			}
		}
	}
	cout<>_;
	while(_--)solve();
	return 0;
}