A. Alyona and a Square Jigsaw Puzzle

题意

Alyona按照顺时针围绕第一个拼图放置拼图，Alyona每天会按顺序放置一定数量的拼图，如果一天结束时拼图的组装部分没有任何已开始但未完成的层，Alyona会感到开心。给出每天放置拼图的数量，询问Alyona感到快乐的天数。

数据范围

• $1\leq t\leq 500$
• $1\leq n\leq 100$
• $1\leq a_i\leq 100,a_1=1$

思路

检查每天完成添加拼图时的总拼图数是否恰好是一个奇数的平方数，若是则该天会感到快乐。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void solve() {
  cin >> n;
  ll tot = 0, ans = 0;
  for (ll i = 1; i <= n; i++) {
    cin >> a[i];
    tot += a[i];
    ld t = sqrtl(tot);
    if ((ll)t & 1 && t == (ll)t) {
      ans++;
    }
  }
  cout << ans << '\n';
}

B. Replace Character

题意

在一个长度为$n$的字符串中，执行一次这样的操作：

• 选择两个索引$i,j(1\leq i,j\leq n)$，可以选择$i = j$。
• 进行赋值$s_i:=s_j$。

要求输出在进行该操作之后，字典序最小的那个字符串。

A. Profitable Interest Rate

题意

有两种储值方式——无利可图和盈利，“盈利”可以保证盈利，但是有最低储值要求，“无利可图”类型没有利息，但是可以让“盈利”的最低储值降低。在“无利可图”储值$x$元，可以让“盈利”的最低值要求降低$2\times x$元，最低储值不能低于$0$元，两种储值均不能取出。现在Alice拥有$a$元，并想使存入“盈利”的金额越多越好，求Alice最多存入多少“盈利”类型的金额。

G. Snake Move

题意

$n\times m$的网格中有一条长度为$k$的贪吃蛇，贪吃蛇支持上下左右移动 1 格的操作，以及缩短 1 个身体长度的操作。

设$f(i,j)$为从蛇头从初始位置到达网格中点$(i,j)$所需要的最少的操作数，网格中不可到达的格子操作数设为$0$，求解输出：

A. Meaning Mean

题意

可以选择 2 个不同的索引$i,j$，将数组中这两个索引对应的数删除，然后将$\lfloor \frac{a_i+a_j}{2} \rfloor$添加到数组的最后。可知到最后只会剩下一个数，最大化最后剩余的这个数$x$，并输出。

区间动态规划一般以区间作为动态规划的阶段。

[P1880]石子合并

题目描述

在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

此篇包含尚未写完的题，事实上是一个TODO List。

TODO List

• Atlantis
• P5490 【模板】扫描线 & 矩形面积并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
• I Hate It
• 覆盖的面积
• 敌兵布阵
• P4588 TJOI2018 数学计算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
• 单峰数列 ✅ 2024-09-26
• 树上询问
• P1502 窗口的星星 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
• P2471 SCOI2007 降雨量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Atlantis & P5490 扫描线矩形面积并

Problem - 1542 (hdu.edu.cn)