[ARC101D] Robots and Exits 题解

建模+树状数组优化 DP

这个建模真的神奇/bx

Statement

AT4353 [ARC101D] Robots and Exits - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

容易发现题目所指的方案和具体如何操作无关，只和每个机器人进的是 左/右 有关

显然，可以直接忽略掉坐标在最左边的坑的左边的机器人和右边的

可以想到使用一个二元组 \((x,y)\) 表示一个机器人，其中 \(x,y\) 分别表示当前机器人到左/右的距离

把这些点放在平面直角坐标系上，经过头脑风暴，发现题目成为了这样一个模型：

从 \((0,0)\) 出发，每一步可以向上/右走，一直走到超过 \((x_{max},y_{max})\)

对于形成的这条折线，如果一个点在折线下方，那么我认为这个机器人掉入了右边，否则掉进了左边

为避免歧义，可以把每个点 \((x,y)\to (x+0.5,y+0.5)\)

正确性可以这样理解，我这个折线一直走，对于一个点而言，只要折线在自己和原点围成的这个矩形内，那么自己就没有掉进洞，反正题目不管我具体操作。而一旦这条线从这个矩形的上方突破，那么我掉进了右边，对应这个点在折线下方

设 \(f_i\) 表示折线经过前 \(i\) 个点的方案数，转移式子为 \(f_i=\sum_{x_j

树状数组优化一下就是 \(O(n\log n)\) 了

Code

#include
using namespace std;
const int N = 2e5+5;
const int mod = 1e9+7;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
	int s=0,w=1; char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 
	while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
	return s*w;
} 
void inc(int &a,int b){a=a>=mod-b?a-mod+b:a+b;}
void dec(int &a,int b){a=a>=b?a-b:a+mod-b;}

struct BIT{
	int c[N];
	int lowbit(int x){return -x&x;}
	void add(int x,int v){for(;xq.y:p.x