东莞市做网站的,东莞优化哪家好,湛江网站建设湛江,怎么样开发app软件P8925 「GMOI R1-T2」Light
让我们好好观察样例解释的这一张图#xff1a; 左边第 1 1 1 个像到 O O O 点的距离 #xff1a; L 2 2 L L\times22L L22L
右边第 1 1 1 个像到 O O O 点的距离 #xff1a; R 2 2 R R\times22R R22R
左边第 2 2 2 个像到 O O O 点…P8925 「GMOI R1-T2」Light
让我们好好观察样例解释的这一张图 左边第 1 1 1 个像到 O O O 点的距离 L × 2 2 L L\times22L L×22L
右边第 1 1 1 个像到 O O O 点的距离 R × 2 2 R R\times22R R×22R
左边第 2 2 2 个像到 O O O 点的距离 右边第 1 1 1 个像到达 L L L 的距离是 2 R L 2RL 2RL 。而这样子距离 O O O 还差一个 L L L 最终结果就是 2 L 2 R 2L2R 2L2R
右边第 2 2 2 个像到 O O O 点的距离 同理可得 2 R 2 L 2R2L 2R2L
递推得到
左边第 n n n 个像到 O O O 点的距离 右边第 n − 1 n-1 n−1 个像到 O O O 点的距离加上 2 L 2L 2L
右边第 n n n 个像到 O O O 点的距离 左边第 n − 1 n-1 n−1 个像到 O O O 点的距离加上 2 R 2R 2R
然后我们打出一张表
左边第 n n n 个像到 O O O 点的距离右边第 n n n 个像到 O O O 点的距离 1 1 1 2 L 0 R 2L0R 2L0R 2 R 0 L 2R0L 2R0L 2 2 2 2 L 2 R 2L2R 2L2R 2 R 2 L 2R2L 2R2L 3 3 3 4 L 2 R 4L2R 4L2R 4 R 2 L 4R2L 4R2L 4 4 4 4 L 4 R 4L4R 4L4R 4 R 4 L 4R4L 4R4L
最后找一找系数的规律
对于左边第 n n n 个像到 O O O 点的距离 L L L 的系数是 2 , 2 , 4 , 4... 2,2,4,4... 2,2,4,4... 很明显两个一周期。利用向下取整的特性得到式子 ⌊ n 1 2 ⌋ × 2 \lfloor\frac{n1}{2}\rfloor\times2 ⌊2n1⌋×2 R R R 的系数是 0 , 2 , 2 , 4... 0,2,2,4... 0,2,2,4... 除了第一个外两个一周期也可以利用向下取整的特性得到式子 ⌊ n 2 ⌋ × 2 \lfloor\frac{n}{2}\rfloor\times2 ⌊2n⌋×2
最后再乘以各项变量就行了 ⌊ n 1 2 ⌋ × 2 L ⌊ n 2 ⌋ × 2 R \lfloor\frac{n1}{2}\rfloor\times2L\lfloor\frac{n}{2}\rfloor\times2R ⌊2n1⌋×2L⌊2n⌋×2R
注意由于算的是距离最后的答案需要取相反数输出 − ( ⌊ n 1 2 ⌋ × 2 L ⌊ n 2 ⌋ × 2 R ) -(\lfloor\frac{n1}{2}\rfloor\times2L\lfloor\frac{n}{2}\rfloor\times2R) −(⌊2n1⌋×2L⌊2n⌋×2R)
对于右边第 n n n 个像到 O O O 点的距离同理得到 ⌊ n 1 2 ⌋ × 2 R ⌊ n 2 ⌋ × 2 L \lfloor\frac{n1}{2}\rfloor\times2R\lfloor\frac{n}{2}\rfloor\times2L ⌊2n1⌋×2R⌊2n⌋×2L
AC代码
#include bits/stdc.h
using namespace std;
long long t,l,r;
int main()
{scanf(%lld,t);scanf(%lld%lld,l,r);for(long long i0;it;i){char a;long long b;getchar();scanf(%c%lld,a,b);if(aL)printf(%lld\n,-(b1)/2*2*l-b/2*2*r);else if(aR)printf(%lld\n,(b1)/2*2*rb/2*2*l);}return 0;
}AC记录
