专栏文章

Atcoder 贪心杂题

江江湖午餐票
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min3otb3
此快照首次捕获于
2025/12/01 20:03
3 个月前
此快照最后确认于
2025/12/01 20:03
3 个月前
查看原文

[AGC008B] Contiguous Repainting

Problem

有 NN 个格子横向排列成一行。从左起第 ii 个格子上写有整数 aia_i。
一开始，所有格子都是白色的。你可以任意次数重复以下操作：
  • 选择连续的 KK 个格子，将它们全部涂成白色或全部涂成黑色。在此过程中，每个格子的颜色会被覆盖。
操作结束后，所有黑色格子上所写整数的总和即为得分。请你求出可能得到的最大得分。

Solution

考虑最后一次操作，一定会将一段长为 k 的区间变成白色或黑色。但是其余的操作，可以将其他的任何一个地方变成任意一种颜色。
枚举即可。

[AGC008C] Tetromino Tiling

Problem

由 44 个正方形格子连接而成的形状称为“俄罗斯方块”（Tetromino）。我们将下图中的 77 种俄罗斯方块依次称为 I、O、T、J、L、S、Z 型。
a60bcb8e9e8f22e3af51049eda063392.png
すぬけ君分别拥有 aIa_I 个 I 型、aOa_O 个 O 型、aTa_T 个 T 型、aJa_J 个 J 型、aLa_L 个 L 型、aSa_S 个 S 型、aZa_Z 个 Z 型俄罗斯方块。他想从这些俄罗斯方块中选出 KK 个，拼成一个高 22 行、宽 2K2K 列的矩形。拼放时需要遵守以下规则：
  • 每个俄罗斯方块可以旋转，但不能翻转。
  • 矩形的每个格子恰好被一个俄罗斯方块覆盖。
  • 不能有俄罗斯方块放在矩形外部。
すぬけ君想要拼出尽可能大的矩形。请你求出 KK 的最大值。

Solution

T、S、Z 三种形状不能选（拼不出来） ，单独的 O 肯定可行，每两个 I、J、L 也行，I+J+L 也行。
  • 如果 I、J、L 都为奇数，肯定可以拼出一个 I+J+L
  • 如果只有两个为奇数，可以把偶数的那个拆开一个，拼 I+J+L 答案更优
  • 如果只有一个，那就不管了
f(x)=2⌊x2⌋,g(x)=2⌊x−12⌋f(x) = 2 \left\lfloor \frac{x}{2} \right\rfloor,g(x) = 2 \left\lfloor \frac{x-1}{2} \right\rfloor E1={3+g(i)+g(j)+g(l),if i≠0 and j≠0 and l≠0,0,otherwise.E_1 = \begin{cases} 3 + g(i) + g(j) + g(l), & \text{if } i \neq 0 \text{ and } j \neq 0 \text{ and } l \neq 0, \\ 0, & \text{otherwise}. \end{cases} E2=f(i)+f(j)+f(l)E_2 = f(i) + f(j) + f(l) ans←o+max⁡(E1,E2)\text{ans} \leftarrow o + \max(E_1, E_2)

[AGC008D] K-th K

Problem

给定一个长度为 NN 的数列 xx。请判断是否存在一个数列 aa 满足以下所有条件，如果存在，请构造出一个这样的 aa。
  • aa 的长度为 N2N^2，并且整数 1,2,…,N1, 2, \ldots, N 各恰好出现 NN 次。
  • 对于每个 1≤i≤N1 \leq i \leq N，在 aa 中所有等于 ii 的元素中，从左往右数第 ii 个 ii，它在整个 aa 中的位置恰好是从左往右数的第 xix_i 个位置。

Solution

注意到 xix_i 越小的数显然就要先填。
能确定位置的先填，然后从前往后按照 xix_i 从小到大的顺序填，再从后往前按照 xix_i 从大往小的顺序填。

[AGC029D] Grid game

Problem

高桥君和青木君使用一个 HH 行 WW 列的格子进行游戏。在这个格子上有 NN 个障碍物，第 ii 个障碍物位于 (Xi,Yi)(X_i, Y_i)。这里，将第 ii 行第 jj 列的格子表示为 (i,j)(i, j)。此外，任意障碍物都不会在 (1,1)(1,1)，并且 (1,1)(1,1) 上放有一个棋子。
游戏由高桥君先手，二人轮流进行以下两种操作之一：
  • 将棋子移动到相邻的格子。假设棋子当前在 (x,y)(x, y)，高桥君只能将棋子移动到 (x+1,y)(x+1, y)，青木君只能将棋子移动到 (x,y+1)(x, y+1)。如果没有可以移动的格子，或者目标格子上有障碍物，则不能进行此操作。
  • 不移动棋子，直接结束本回合，保持格子状态不变。
如果连续两回合都没有移动棋子，游戏立即结束。
高桥君希望让游戏持续尽可能多的回合（包括选择不移动棋子的回合），而青木君则希望让游戏尽快结束。请你求出在双方都采取最优策略的情况下，高桥君能够进行的回合数。

Solution

高桥君能动就动，青木君希望尽可能快的走到障碍物上方。不难发现，对于每一个 xx，棋子能到的 yy 是一个区间 [1,upx][1,up_x]。统计出所有满足 y≤upxy\leq up_x 的障碍物中 xx 最小的点即可，答案为 xmin−1x_{min}-1。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...