1919810

ABC 289F

给你一个矩形区域, 用a,b,c,d 标识
矩形区域 $R = {(x,y) | a - 0.5 \leq x \leq b + 0.5,\ c - 0.5 \leq y \leq d + 0.5}$ 定义为这个区域内的所有整点.

初始, 你在$(s_x,s_y)$;
问你是否可以通过$n( 0\leq n\leq 10^6)$次以下操作达到点$(t_x,t_y)$?

操作：
假设你当前在点$(s,t)$

选取矩形区域内任意整点$(x,y)$, 做中心对称操作翻转到点$(x’,y’)$

用公式表示就是: $x’=2x-s,\ y’=2y-t$

如果可以, 请打印操作过程; 不行则输出No

思考

考虑一个点的翻转操作, 容易发现这是对称的, 两次操作抵消;
其次考虑两个相邻点$(x,y),(x+1,y)$, 假设绕着$(x,y)$翻到了$(2x-s,2y-t)$, 在从这个点借助$(x+1,y)$翻转一次, 就到了$(2x+2-2x+s,2y-2y+t) = (s+2,t)$这个点;
发现了上面这个规律之后, 就容易发现$x$和$y$可以分开操作, 上面演示了横坐标的变化规律,纵坐标同理;
翻转的上界? 这种操作方式最多不超过$2*2e5$, 肯定是符合要求的.

输入 n(≤2000) h L R (0≤L≤R<h≤2000) 和长为 n 的数组 a(1≤a[i]<h)。

对于每个 a[i]，你可以把它减一，或者保持不变（换句话说，每个 a[i] 至多 -1 一次）。
定义前缀和 s[0]=a[0], s[i]=s[i-1]+a[i]。
如果 s[i]%h 落在闭区间 [L,R] 内，则分数加一。
最大化分数

先考虑搜索的写法:
假设我们当前选择第i个数字a, 之前的前缀和为s,已知

如果$L\leq s’ \leq R$ 那么+1 否则等于 $max(dfs(i + 1, s+a[i]), dfs(i + 1, s+a[i]-1))$
找到了子问题之后就容易解决了, 再来考虑边界情况