Loading web-font TeX/Math/Italic
题目名称 3573. [USACO21Feb Gold]Count the Cows
输入输出 count.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 12
题目来源 Gravatar数声风笛ovo 于2021-04-03加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:0, 提交:0, 通过率:0%
本题关联比赛
USACO水题大战
关于 Count the Cows 的近10条评论(全部评论)

3573. [USACO21Feb Gold]Count the Cows

★★☆   输入文件:count.in   输出文件:count.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

如同平常一样,Farmer John 的奶牛们分散在他的最大的草地上。草地可以看作是一个由正方形方格组成的巨大的二维方阵(想象一个巨大的棋盘)。

奶牛分布在草地上的方式相当迷人。对于每一个满足 x\ge 0 以及 y\ge 0 的方格 (x,y),当对于所有整数 k\ge 0\left\lfloor \frac{x}{3^k}\right\rfloor\left\lfloor \frac{y}{3^k}\right\rfloor 除以三的余数的奇偶性均相同时,有一头奶牛位于 (x,y)。换言之,两个余数均为奇数(均等于 1),或均为偶数(均等于 02)。例如,满足 0\le x,y<9 的方格中,包含奶牛的方格在下图中用 1 表示。

        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

FJ 对他的草地上的某个特定区域内的奶牛数量感兴趣。他进行了 Q 个询问,每个询问由三个整数 x_i,y_i,d_i 组成。对每个询问,FJ 想要知道有多少奶牛位于 (x_i,y_i)(x_i+d_i,y_i+d_i) 的对角线上的方格内(包括两端)。

【输入格式】

输入的第一行包含 Q1\le Q\le 10^4),为询问的数量。

以下 Q 行每行包含三个整数 d_ix_iy_i0\le x_i,y_i,d_i\le 10^{18})。

【输出格式】

输出 Q 行,每个询问输出一行。

【样例输入】

8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000

【样例输出】

11
0
4
3
1
2
2
1000000000000000001

【数据规模与约定】

测试点 2 满足对于每一个询问有 d_i\le 100

测试点 3-6 满足对于每一个询问有 x+d=3^{30}-1 以及 y=0

测试点 7-12 没有额外限制。

【来源】

USACO 二月公开赛 Gold 组