BZOJ 1041 (YZOJ 3460) 圆规问题

圆规问题

时间限制:1000MS 内存限制:262144KB

  • 问题描述

小 C 有一个圆规,他经常用圆规在纸上作图。

有一天,小 C 准备在一个单位网格纸上作一个圆。他以某个格点为圆心,作了一个半径为 \(R\) 的圆。接着,他将圆经过的所有格子涂成黑色。注意:只有圆经过了一个格子的内部才能涂黑,只经过格子的边界不涂黑。小 C 的问题是:对于给定的半径为 \(R\) 的圆,共有多少个格子被涂黑?

这是一个 \(R=10\)的实例:

左图为小 C 作的圆,右图是将圆经过的格子涂黑后的图。可以看出,\(R=10\)时,共有 68 个格子被涂黑。

给定\(N\),计算被涂黑的格子数目。

  • 输入格式

输入文件包含一个整数\(R\),\(1 \leq R \leq 2,000,000,000\)

  • 输出格式

将被涂黑的格子数目输出到文件中。

  • 样例输入

  • 样例输出


YZOJ T1860-P2 Find

Find

时间限制:1000MS 内存限制:65536KB

  • 题目描述

我们定义两种操作

操作1的格式 :I 字符串 \(S\),加入 1 个字符串 \(S\)。

操作2的格式 :F 字符串\(S\),查找字符串\(S\)是否在当前寻找前已经出现过

注释:同一个字符串可能多次被插入和查找,字符串长度\(\left|S\right|≤20\),字符集为小写英文字母。

  • 输入格式

第一行,指令个数\(N\)。

接下来\(N\)行,每行一个指令。

  • 输出格式

对于每次查找,找到输出 ‘YES’,没找到输出 ‘NO’ 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(40\%\) 的数据 \(N≤5000\)

对于 \(100\%\) 的数据 \(N≤150000\)

 


YZOJ T1860-P1 Trie树

Trie树

时间限制:1000MS 内存限制:131072KB

  • 题目描述

给定N个01串,对于每一个01串,你需要判断:

1.如果它之前出现过,则输出之前最后出现的位置,否则

2.如果它是之前出现的某一01串的前缀,则输出0,否则

3.输出-1

  • 输入格式

第一行一个数N

接下来N行每行一个01串

  • 输出格式

共N行,每行一个数,见题目描述

  • 样例输入

  • 样例输出

  • 数据规模与约定

0<=N<=10000,01串长度不超过100,文件大小不超过1M,并保证数据的梯度

 …