感觉最近啥题都不会
所以这个题也不会
题目链接
题意
一个数轴上有 个机器人和 个出口，初始坐标各不相同。
现在可以进行若干次操作，每一次操作可以让所有机器人全体向左走一格，或全体向右走一格。
一个机器人走到出口以后，这个机器人就会消失。
所有机器人都消失后，操作就结束了。
求有多少种机器人走出出口的方案（两种方案不同，当且仅当存在机器人，使得它所在的出口不同）。
。
题解
首先可以发现一些事情，例如每一个机器人只可能从它最左边第一个出口，或者最右边第一个出口离开。
特别地，如果某一个机器人在第一个出口以前，或最后一个出口以后，它就只有一个方案，我们可以把它去掉。
进一步，我们设第
个机器人左边第一个出口和他相距 ，右边第一个和他相距 。
考虑什么时候会出现矛盾。
如果有两个机器人 ， 从左出， 从右出，且 、。
那么这个方案一定就是不合法的，因为此时无论让 先出还是让 先出都是不可能的。
而只要不出现这种情况，就一定是合法的。
每一次只需要找出向左走的
最小的 和向右走的 最小的 ，那么 和 必然有一个能走。
现在我们知道了哪些情况是合法的，就差计数了。
考虑将所有点以
为第一关键字从小到大、
为第二关键字从大到小排序。
那么 且 的条件等价于 且 。
考虑设 表示前 个机器人中，已经确定要向右出的最小的
时的方案数是多少。
线段树或树状数组优化转移即可，复杂度为 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=1000000007;
int num[200002];
int in[100001];
int id[100001];
int l[100001];
int r[100001];
int a[100001];
int b[100001];
ll t[200002];
int n,m,k,len;
inline int lowbit(int i){ return i&(-i);}
inline void add(int x,ll y)
{
while(x<=len)
{
t[x]+=y;
if(t[x]>=mod) t[x]-=mod;
x+=lowbit(x);
}
}
inline ll get(int x)
{
ll ans=0;
while(x)
{
ans+=t[x];
if(ans>=mod) ans-=mod;
x-=lowbit(x);
}
return ans;
}
int main()
{
k=read(),m=read();
for(int i=1;i<=k;i++) in[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
for(int i=1;i<=k;i++) if(in[i]>b[1]&&in[i]<b[m]) a[++n]=in[i];
num[len=1]=0;int now=1;
for(int i=1;i<=n;i++)
{
while(now<m&&a[i]>b[now+1]) now++;
l[i]=a[i]-b[now],r[i]=b[now+1]-a[i];
num[++len]=l[i],num[++len]=r[i];
}
sort(num+1,num+len+1);
len=unique(num+1,num+len+1)-num-1;
for(int i=1;i<=n;i++)
{
l[i]=lower_bound(num+1,num+len+1,l[i])-num;
r[i]=lower_bound(num+1,num+len+1,r[i])-num;
id[i]=i;
}
sort(id+1,id+n+1,[](int x,int y)
{
if(l[x]!=l[y]) return l[x]<l[y];
return r[x]>r[y];
});
add(1,1);
for(int i=1;i<=n;i++)
{
int p=id[i],q=id[i-1];
if(q&&l[p]==l[q]&&r[p]==r[q]) continue;
ll num=get(r[p]-1);
add(r[p],num);
}
printf("%lld\n",get(len));
return 0;
}
|
感谢观看！