526互联

8月17日思维训练

发布时间 2023-08-18 16:54:02作者: Penguin_Chen

8月17日思维训练

CF1545B AquaMoon and Chess

题目大意：

给定一个长度为n的棋盘的状态，位置 \(i\) 为 \(1\) 代表该位置有棋子，为 \(0\) 则说明没有棋子。如果位置 \(i+2\) 是空的，位置 \(i+1\) 非空，则位置 \(i\) 的棋子可以移动到位置 \(i+2\)，反之，同理。问通过上述操作可以达到的状态数，\(mod 998244353\) 后输出

思路：

做这道题，最重要的就是发现 \(11\) 这一条性质。例如 \(11010\)，可以转化出来的有：\(11010\)，\(01110\)，\(01011\) 三种。我们发现两个 \(1\) 始终是贴在一起的，所以我们不妨把字符串分成三个部分：\(a\) 个 \(1\)，\(b\) 个 \(11\)，\(c\) 个 \(0\)。我们发现 \(1\) 是跟着 \(11\) 的移动被动移动的，所以 \(1\) 在哪里对答案没有任何影响，我们只需要处理 \(11\) 和 \(0\) 的情况，我们又发现它们可以互换位置，一共有 \(a+c\) 个位置，其中 \(a\) 个位置要给 \(11\)，那答案就为：\(C_{a+c}^{a}\)。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+1;
const int mod=998244353;
int T;
int f[maxn];
int n;
string str;
int a[maxn];
inline int power(int a,int b)
{
	int sum=1;
	while(b)
	{
		if(b&1)
			sum=(sum*a)%mod;
		a*=a;
		a%=mod;
		b>>=1;
	}
	return sum;
}
inline int C(int n,int m)
{
	return f[n]*power(f[m],mod-2)%mod*power(f[n-m],mod-2)%mod;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>T;
	f[0]=1;
	for(int i=1;i<=100000;++i)
		f[i]=(f[i-1]*i)%mod;
	while(T--)
	{
		cin>>n;
		cin>>str;
		str=" "+str;
		for(register int i=1;i<=n;++i)
			a[i]=(str[i]=='1');
		int number11=0,number0=0;
		for(register int i=1;i<=n;++i)
		{
			if(a[i]&&a[i+1])
			{
				++number11;
				++i;
			}
			number0+=(a[i]==0);
		}
		cout<<C(number11+number0,number11)<<endl;
	}
	return 0;
}

P5835 [USACO19DEC] Meetings S]

题目大意：

有两个牛棚位于一维数轴上的点 \(0\) 和 \(L\) 处。同时有 \(N\) 头奶牛位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 \(i\) 初始时位于某个位置 \(x_i\)，用一个等于 \(1\) 或 \(-1\) 的整数 \(d_i\) 表示向左还是向右走。每头奶牛还拥有重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：

如果奶牛 \(i\) 移动到了一个牛棚，则奶牛 \(i\) 停止移动

当奶牛 \(i\) 和 \(j\) 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，两只奶牛调头返回

令 \(T\) 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 \(0 \ldots T\)（包括时刻 \(T\)）之间发生的奶牛对相遇的总数。

思路：

首先，我们可以用两头奶牛相遇后掉头返回，证明奶牛从左往右的体重序列不会发生改变，这个结论先放着，接着，我们再看，我们其实是可以在时间 \(T\) 上二分的（随着时间的增加，停止移动的奶牛的体重之和是单调不减的）。那 check 函数怎么写呢？

inline bool check(int x)
{
	int L=1,R=n,cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(a[i].d==1)cnt+=(a[i].x+x>=l?a[R--].w:0);
		else cnt+=(a[i].x-x<=0?a[L++].w:0);
	}
	return cnt*2>=sum;
}

那为什么向右的奶牛可以到达 \(L\) 点，加上的重量却是当前最右端的呢？这就可以用到前面的结论了：奶牛从左往右的体重序列不会发生改变。最后，我们求出了时间 \(T\) 后，对每一个向左走的奶牛找到与它相遇的位置最有的奶牛，二分即可，最后统计答案就行了

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e4+1;
struct node
{
	int w,x,d;
}a[maxn];
int n,l,sum,ans;
int f[maxn],tot;
inline bool cmp(node x,node y){return x.x<y.x;}
inline bool check(int x)
{
	int L=1,R=n,cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(a[i].d==1)cnt+=(a[i].x+x>=l?a[R--].w:0);
		else cnt+=(a[i].x-x<=0?a[L++].w:0);
	}
	return cnt*2>=sum;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>n>>l;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i].w>>a[i].x>>a[i].d;
		sum+=a[i].w;
	}
	sort(a+1,a+n+1,cmp);
	int L=0,R=1145141919;
	while(L+1<R)//二分时间,最终答案是R 
	{
		int mid=(L+R)>>1;
		if(check(mid))R=mid;
		else	L=mid;
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i].d==-1)
		{
			int ll=0,rr=tot+1;
			int xx=a[i].x-R*2;//可以相遇的位置 
			while(ll+1<rr)
			{
				int mid=(ll+rr)>>1;
				if(f[mid]>=xx)rr=mid;
				else ll=mid;
			}
			ans+=tot-rr+1;
		}
		else
			f[++tot]=a[i].x;
	}
	cout<<ans<<endl;
	return 0;
}