社区讨论

USACO12月 月赛翻译

SSuperiority
灌水区参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@m4nvi7h0
此快照首次捕获于
2024/12/14 15:46
去年
此快照最后确认于
2024/12/14 15:56
去年
查看原帖

问题描述

奶牛贝茜又回到学校啦！她正在做数学作业，其中她需要将正整数舍入到10的幂。
将一个正整数舍入到最近的 10b10^b，其中 bb 是一个正整数，贝茜首先会找到从右往左数的第 bb 位数字，记为 xx。
​ 如果 x≥5x \geq 5，贝茜会将 10b10^b 加到当前值上。 ​ 然后，贝茜会将从右往左的第 bb 位数字以及其右侧的所有数字设置为 0。
例如，如果贝茜想把 456 舍入到最近的 10210^2（百位），她会先找到从右往左的第 2 位数字，即 5。这意味着 x=5x = 5。因为 x≥5x \geq 5，贝茜会将 100 加到 0 上。最后，贝茜会将从右往左的第 2 位及其右侧的所有数字设置为 0，得到 500。
然而，如果贝茜将 446 舍入到最近的 10210^2，结果将是 400。
在查看贝茜的作业后，爱尔西认为自己发明了一种新的舍入方法：链式舍入。为了将数字链式舍入到最近的 10b10^b，爱尔西会首先舍入到最近的 10110^1，然后是最近的 10210^2，依此类推，直到最近的 10b10^b。
贝茜认为爱尔西的方法是错的，但她忙于数学作业，没时间验证她的怀疑。于是她让你统计有多少个整数 xx（满足 2≤x≤N2 \leq x \leq N，1≤N≤1091 \leq N \leq 10^9），使得将 xx 舍入到最近的 10b10^b 与链式舍入到最近的 10b10^b 的结果不同，其中 PP 是满足 10P≥x10^P \geq x 的最小整数。

输入格式

你需要处理多个测试用例。
输入的第一行包含一个整数 TT（1≤T≤1051 \leq T \leq 10^5），表示测试用例的数量。接下来的 TT 行每行包含一个整数 NN。每个测试用例的 NN 是唯一的。

输出格式

输出 TT 行，第 ii 行包含一个整数，表示在第 ii 个测试用例中，满足条件的整数 xx 的数量（xx 的范围是 2 到 NN）。

样例输入

CPP
4
1
100
4567
3366

样例输出

CPP
0
5
183
60

解释

考虑样例中的第二个测试用例。数字 48 应该被统计，因为 48 链式舍入到最近的 10210^2 是 100（48→50→10048 \to 50 \to 100），但 48 舍入到最近的 10210^2 是 0。
对于第三个测试用例，有两个整数被统计：48 和 480。48 链式舍入到 100，而不是 0，480 链式舍入到 1000，而不是 0。然而，67 不被统计，因为它链式舍入到 100，与直接舍入的结果相同。

评分标准

输入 2-4：N≤103N \leq 10^3 输入 5-7：N≤106N \leq 10^6 输入 8-13：无额外限制。

问题作者

Weiming Zhou

问题描述

农夫约翰 (Farmer John) 有一块立方体形状的奶酪块，位于三维坐标系中。奶酪块的范围从 (0,0,0)(0, 0, 0) 到 (N,N,N)(N, N, N)，其中 2≤N≤10002 \leq N \leq 1000。农夫约翰将执行 QQ 次操作，其中 1≤Q≤2⋅1051 \leq Q \leq 2 \cdot 10^5。

操作说明

每次操作中：
  • 农夫约翰会移除奶酪中从坐标 (x,y,z)(x, y, z) 开始的 1×1×11 \times 1 \times 1 小立方体，并扩展到 (x+1,y+1,z+1)(x+1, y+1, z+1) ，其中 0≤x,y,z<N0 \leq x, y, z < N 。
  • 保证操作前该位置有奶酪存在。

任务要求

在每次操作之后，输出一个整数，表示可以将一个 1×1×N1 \times 1 \times N 的砖块放置在剩余的奶酪块中的不同合法方案的数量。满足以下条件：
  1. 砖块不能与被移除的空间重叠。
  2. 砖块的每个顶点坐标必须是整数，且在范围 [0,N][0, N ] 内。
  3. 砖块可以在任意方向上旋转。

输入格式

  • 第一行包含两个整数 NN 和 QQ。
  • 接下来的 QQ 行中，每行包含三个整数 x,y,zx, y, z，表示要移除的小立方体的坐标。

输出格式

对于每次操作，输出一个整数，表示当前剩余的奶酪块中砖块的不同放置方案数量。

样例输入

PLAINTEXT
2 5
0 0 1
0 1 1
1 0 1
1 1 0
1 1 0

样例输出

PLAINTEXT
0
0
1
2
5
经过前三次更新后，横跨 [0,1]×[0,2]×[0,1][0,1] \times [0,2] \times [0,1] 的 1×2×11\times2\times1 横跨 [0,1]×[0,2]×[0,1][0,1]\times[0,2]\times[0,1] 的砖块 没有与剩余的奶酪重叠，因此它对答案有贡献

题目描述

农场主约翰正试着向埃尔西描述他最喜欢的 USACO 比赛，但她不明白他为什么这么喜欢。他说："我最喜欢的是贝西说‘It's Mooin'Time’（是哞哞的时候了）并在比赛现场哞哞叫的时候。
埃尔西还是不明白，于是农夫约翰下载了竞赛的文本文件，并试图解释他的意思。比赛被定义为一串长度为 N（3≤N≤20000）的小写字母。“哞 "一般定义为子串cicjcjc_i c_j c_j，其中某个字符cic_i后面直接出现两个字符cjc_j，而ci≠cjc_i \neq c_j。根据农夫约翰的说法，贝西经常哞哞叫，所以如果某个哞哞叫在比赛中出现至少 FF（1≤F≤N1\le F \leq N）次，那可能就是贝西发出的。
不过，农夫约翰的下载文件可能已损坏，文本文件中最多可能有一个字符与原始文件不同。考虑到可能出现的错误，请打印贝西可能发出的所有 “哞哞 ”声，按字母顺序排列。
输入格式（输入来自终端/stdin）：
第一行包含 N 和 F，分别代表字符串的长度和贝西发出 “哞哞 ”声的频率阈值。
第二行包含长度为 N 的小写字母字符串，代表比赛
输出格式（打印输出到终端/stdout）：
打印出贝西可能发出的 “哞哞 ”声的数量，然后是按词典排序的 “哞哞 ”声列表。每条 “哞哞 ”声都应单独成行。

输入样例

CPP
10 2

zzmoozzmoo

样例输出：

CPP
1
moo
在这种情况下，任何字符变化都不会影响答案。贝西发出的唯一一声哞叫是 "moo"。

样例输入

CPP
17 2
momoobaaaaaqqqcqq

样例输出：

CPP
3
aqq
baa
cqq

输入样例

CPP
3 1
ooo

样例输出：

CPP
25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
动物园
数据：
数据点 4-8： N≤100
数据点 9-13： 无额外限制。
问题归功于 苏哈斯-纳加尔

回复

共 3 条回复，欢迎继续交流。

正在加载回复...