Processing math: 1%

YZOJ P2050 [FJOI2013]圆形游戏

YZOJ P2050 [FJOI2013]圆形游戏

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

难度:8.0

  • 题目描述

在一个无穷大的桌面上有 n 个圆形,保证任意两个圆相离或者相含,不存在相切或相交。现在 Alice 和 Bob 在玩一个圆形游戏,以 Alice 为先手,双方以如下步骤轮流游戏:

1,选定一个圆 A,把 A 以及所有完全在 A 内部的圆都删除;

2,如果在自己回合无法找到可删除的圆,则输掉比赛。

假设 Alice 和 Bob 都非常聪明,请问最终谁能够取得胜利?请编程输出最终获胜的人。

  • 输入格式

输入数据的第一行为一个正整数 T,表示数据组数。

接下来 T 组数据,对于每组数据,第一行包含 1 个正整数 n,表示圆形的个数。

之后 n 行,每行为 3 个整数 xyr ,分别表示圆形的圆心坐标以及圆的半径。

  • 输出格式

假设 Alice 最后获胜,则输出一行 “Alice”(不包括引号),否则输出 “Bob” 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

100\% 的数据满足 T \leq 100n \leq m20000\left|x\right|, \left|y\right|, r \leq 10^8

 

 

 …

YZOJ P2358 [ZJOI 2012]Naive – Matrix

YZOJ P2358 [ZJOI 2012]Naive – Matrix

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

难度:7.0

  • 题目描述

给出一个 R \times C 的矩阵,上面有 N0,其他的都是 1,现在给出这些 0 的位置,要求求出有多少个子矩阵包含至少一个 0

  • 输入格式

第一行输入三个整数 RCN

接下来 N 行,每行两个整数 xy,表示 0 的坐标。

  • 输出格式

输出一个数表示子矩阵的个数。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 100\% 的数据,R, C \leq 40000N \leq \min\{R \times C,100000\},所有 0 的位置两两不同且随机生成。

 

 

 

Source: BZOJ 2658…

YZOJ P3791 餐馆

YZOJ P3791 餐馆

时间限制:2000MS      内存限制:524288KB

难度:6.0

  • 题目描述

在一条东西向的街道上有 n 个餐馆,从西向东编号为 1n,第 i 个餐馆和第 i+1 个餐馆的距离为 a_i

吃货小W喜欢到这条街道的餐馆里吃饭。现在,小W得到了 m 张餐票,每张餐票可以用于在街道上的任一餐馆里吃一餐。在第 i 个餐馆中,使用第 j 张餐票吃饭,可以获得的美味度为 b_{i,j} 。注意,每张餐票最多用一次,但在同一餐馆内可以使用任意多张餐票。

小W打算用完这 m 张餐票。他可以选择任一餐馆作为起点,每次吃饭时,可以选择一个餐馆,然后从当前位置(上次吃饭的地点,如果不存在则为起点)出发前往该餐馆并用任意一张未用过的餐票吃一餐,直到吃完 m 餐为止。小W希望最大化每次吃饭的美味度之和减去路上经过的总路程的值。

  • 输入格式

输入第一行包含两个正整数 n,m

第二行包含 n-1 个正整数 a_1,a_2,\cdots,a_{n-1}

接下来 n 行,每行包含 m 个正整数,其中第 i 行第 j 个数为 b_{i,j}

  • 输出格式

输出一行一个整数,表示所求的最大值。

  • 样例输入

  • 样例输出

  • 样例说明

最优方案如下:以餐馆 1 为起点,在餐馆 1 使用第 1 张餐票、第 3 张餐票,然后前往餐馆 2 使用第 2 张餐票、第 4 张餐票。

  • 数据规模与约定

对于所有数据,nm \leq 10^6n \geq 2a_i, b_{i, j} \leq 10^9

 

 

 

Source:ARC067 F – Yakiniku