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;
}