Znzryb's Blog
0%

Posted on Edited on

题目大意

注意这道题目，其表述有点问题，应该要这么理解比较好。就是说在任何情况下，这个仓库容量都不能爆。

核心目标

在 nn 个顺序进行的精炼阶段中，利用初始物料 1 的数量 ss 和共享仓库容量 kk，通过选择不同的转化机器（物料 i→i+1i \to i+1），计算最终能获得的物料 nn 的最大数量。

关键约束

  • 处理顺序：必须严格按照 1→2→⋯→n1 \to 2 \to \dots \to n 的顺序处理。一旦开始处理下一阶段，就不能再返回处理上一阶段的物料。

  • 机器转化：每个阶段有若干机器可选，每台机器消耗 MIM_I 单位物料 ii 并产出 MOM_O 单位物料 i+1i+1。同一阶段内可以多次、多种类地使用机器。

  • 仓库容量限制：仓库为所有物料共享。在进行第 i→i+1i \to i+1 阶段转化时，仓库内剩余的物料 ii 数量与已产出的物料 i+1i+1 数量之和在任何时刻都不能超过 kk。

  • 物料处置：为了腾出空间满足容量限制，可以随时丢弃仓库内的物料。

样例解释

  • 样例 3 (s=4,k=10s=4, k=10，机器 1: 消耗 2 产 3)

    1. 第一次运行机器：消耗 2 个物料 1，产出 3 个物料 2。此时仓库内有 2 个物料 1 和 3 个物料 2，总数 2+3=5≤102+3=5 \le 10。
    2. 第二次运行机器：再消耗 2 个物料 1，产出 3 个物料 2。此时仓库内有 0 个物料 1 和 6 个物料 2，总数 0+6=6≤100+6=6 \le 10。
      最终产出：6。

  • 样例 4 (s=4,k=7s=4, k=7，机器 1: 消耗 2 产 4)

    1. 第一次运行机器：消耗 2 个物料 1，产出 4 个物料 2。仓库总量为 2+4=6≤72+4=6 \le 7。
    2. 第二次尝试：如果再次运行机器，产出 4 个物料 2，则总量将变为 0+8=80+8=8。由于仓库上限 k=7k=7，实际产出的物料 2 最终只能封顶为 7。
      最终产出：7。

  • 样例 5 (s=7,k=7s=7, k=7，机器 1: 消耗 3 产 5)

    1. 直接转化尝试：若消耗 3 个物料 1，剩 4 个，产出 5 个，总量 4+5=9>74+5=9 > 7，操作非法。
    2. 调整策略：必须先丢弃 2 个物料 1，使初始物料 1 降为 5。
    3. 运行机器：消耗 3 个物料 1，剩 2 个，产出 5 个，总量 2+5=7≤72+5=7 \le 7。此时剩余物料 1 不足以再次运行机器。
      最终产出：5。

样例解释

样例 关键参数 过程说明 结果
样例 3 s=4,k=10s=4, k=10 机器 (1, 2, 3) 1. 消耗 2 个物料 1 →\to 产出 3 个物料 2。仓内存放：2 (剩) + 3 (新) = 5 ≤10\le 10。
  1. 再消耗 2 个物料 1 →\to 产出 3 个物料 2。仓内存放：0 (剩) + 6 (新) = 6 ≤10\le 10。 | 6 |
    | 样例 4 | s=4,k=7s=4, k=7 机器 (1, 2, 4) | 1. 消耗 2 个物料 1 →\to 产出 4 个物料 2。仓内存放：2 + 4 = 6 ≤7\le 7。
  2. 计划再产出 4 个，但总量将达 0+8=8>70+8=8 > 7，受限于 k=7k=7，实际产出封顶为 7。 | 7 |
    | 样例 5 | s=7,k=7s=7, k=7 机器 (1, 3, 5) | 1. 若直接转化：消耗 3 个剩 4 个，产出 5 个，总量 4+5=9>74+5=9 > 7（非法）。
  3. 必须先丢弃 2 个物料 1，剩 5 个。消耗 3 个剩 2 个，产出 5 个，总量 2+5=7≤72+5=7 \le 7。
  4. 剩余 2 个物料 1 不足消耗，停止。 | 5 |

思路讲解

我们可以先想，如果我们把这个ware house的这个容量的这个限制去掉的话，是不是会好做很多？去掉的话，其实就是跑 n 个背包就好了（注意，这个其实是完全背包），只要我们能够最大化每个产品的数量，那么就一定可以贪心的得到最多的 N 的数量。

为什么是外层W内层机器呢？这个的原因其实是这样子，完全背包我们不是说那么在意这个顺序，我们可以呃外层是物品，内层是W。但是是这样子，完全背包之所以不在意乎这个顺序，是因为你放入背包当中的物品，无论以什么顺序放入都无所谓。但是这道题目由于其能够所产生的利益是与原来的这个 dp 是相关的，如果说你先用一个机器，这个机器的效率比较高，产生的DP比较多，就产生的这个值比较多的话，然后你后运行一个机器。它也是一个效率比较高的机器的话，那么可能就你就超出了题目的仓库容量的限制。呃，说白了就是这道题目先运行哪个机器，后运行哪个机器是非常重要的。我们不能够忽略这个顺序。（不能够忽略的原因已在上面给出。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll cur_material=St_material;
for (int i=2;i<=N;++i) {
    for (int w=1;w<=cur_material;++w) {
        // 顺序遍历，利用完全背包的这个性质。
        // 呃，理论上来说
        // W它有的时候不是每次都是每个输入物料都是有用的嘛。所以说它相当于也是有这个丢弃的这个作用。
        // 外层w内层机器，保证B→A交替序列能被捕获
        for (auto [input,output]:material_machine_mtx[i]) {
            if (w-input<0) {
                continue;
            }
            if (cur_material-w+dp_knapsack[i][w-input]+output <= K_depot) {
                dp_knapsack[i][w]=max(dp_knapsack[i][w],dp_knapsack[i][w-input]+output);
            }else {
              // 黄色荧光的是常量，
                ll output_rem=K_depot-output-cur_material+w;
                if (output_rem<0) {
                    continue;
                }
                dp_knapsack[i][w]=max(dp_knapsack[i][w],output_rem+output);
            }
        }
    }
    cur_material=*max_element(all(dp_knapsack[i]));
}

AC代码

AC
https://qoj.ac/submission/2019893
AC
https://codeforces.com/gym/106157/submission/362107850

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目总结：H. Hybrid Search（混合搜索）

问题描述
给定一棵以 为根、包含 个节点的树。对于树上的特定目标节点 ，你需要计算在以下两种“混合搜索”策略下， 被访问到的最小可能位置（从 开始计数）：

  1. 策略 A (BFS DFS)：从根节点开始进行 广度优先搜索 (BFS)，在某一节点 处切换为 深度优先搜索 (DFS)。切换后，搜索将仅限于 的子树内部。

  2. 策略 B (DFS BFS)：从根节点开始进行 深度优先搜索 (DFS)，在某一节点 处切换为 广度优先搜索 (BFS)。切换后，搜索将仅限于 的子树内部。

规则说明

  • *切换点 **：可以是路径上的任意节点（包括根节点 或节点 本身）。切换时 必须已被第一阶段搜索访问。

  • 搜索范围限制：一旦切换搜索类型，后续只能访问 的子树节点。这意味着为了能访问到 ，切换点 必须是 的祖先（或 本身）。

  • 邻居访问顺序：在任何搜索中，节点子树的访问顺序严格遵循输入中边出现的先后顺序。

  • 计算目标：分别输出在策略 A 和策略 B 下，节点 可能出现的最小位次。

样例解释

样例 1 ()

  • BFS DFS：最优选择是在节点 处切换。BFS 首先访问第一层及第二层部分节点，到达 后切换为 DFS 进入其子树，此时 是第 个被访问的节点。

  • DFS BFS：最优选择是在节点 或 处切换，最小位次为 。

样例 2 ()

  • BFS DFS：最小位次为 。

  • DFS BFS：即使不切换（一直使用 DFS），最小位次也可以达到 。

样例 3 ()

  • 无论哪种混合搜索，最优答案均为 。注意，如果仅使用纯 BFS 或纯 DFS，节点 的位次都是 。混合搜索通过在特定节点（如 的祖先）切换策略，跳过了其他非必要的分支，从而提前了 的访问顺序。

输入输出要求

  • 输入：第一行 ；接下来 行描述边。

  • 输出：第一行输出策略 A 的最小值，第二行输出策略 B 的最小值。

  • 数据范围：。

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目：1653. 使字符串平衡的最少删除次数

题面总结：

给定一个仅包含 ‘a’ 和 ‘b’ 的字符串 ss，要求删除最少数量的字符，使得剩余字符串达到“平衡”状态。

平衡状态定义：

不存在下标对 (i,j)(i, j) 使得 i<ji < j 且 s[i]=′b′s[i] = 'b' 同时 s[j]=′a′s[j] = 'a'。换言之，平衡后的字符串中，所有的 ‘a’ 必须出现在所有的 ‘b’ 之前（如 "aaa", "bbb", "aaabbb" 均为平衡状态）。

样例解释：

  • 示例 1： s = "aababbab"

    • 方案 A：删除下标 2 和 6 的字符，得到 "aaabbb"，删除次数 2。
    • 方案 B：删除下标 3 和 6 的字符，得到 "aabbbb"，删除次数 2。
    • 结论： 最少删除次数为 2。

  • 示例 2： s = "bbaaaaabb"

    • 方案：删除前两个 ‘b’，得到 "aaaaabb"。
    • 结论： 最少删除次数为 2。

数据范围：

  • 1≤s.length≤1051 \le s.length \le 10^5

  • s[i]s[i] 仅为 ‘a’ 或 ‘b’。

说白了就是形如AABBB，AABB，就是A在前B在后这样子的呃样子才是平衡状态。

问，把原字符串变成平衡状态，需要最少删除多少个字符？

思路讲解

思路就是切一刀。如何快速计算在这里切一刀，可以得到的收益是多少呢？可以利用前缀，后缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minimumDeletions(string s) {
        s.insert(s.begin(),'#');
        ll N=s.size();
        vector<ll> pre_a(N+2),suf_a(N+2),pre_b(N+2),suf_b(N+2);
        for(int i=1;i<=N;++i){
            pre_a[i]=pre_a[i-1]+(s[i]=='a');
            pre_b[i]=pre_b[i-1]+(s[i]=='b');
        }
        for(int i=N;i>=1;--i){
            suf_a[i]=suf_a[i+1]+(s[i]=='a');
            suf_b[i]=suf_b[i+1]+(s[i]=='b');
        }
        ll ans=INF;
        for(int i=1;i<=N+1;++i){
            ans=min(ans,pre_b[i-1]+suf_a[i]);
        }
        return ans;
    }
};

https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504

也可以用DP做DP状态设计，就是第 I 位以A结尾还是以B结尾啊，然后进行这个DP状态转移即可。

下面的代码当中，这个零代表以A结尾，一代表以B结尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func minimumDeletions(s string) int {
    // b := []byte(s)

    n := len(s)
    dp := make([][]int, 2) 

    for i := range dp {
        dp[i] = make([]int, n)
    }

    if s[0] == 'a' {
        dp[0][0] = 0
        dp[1][0] = 1
    } else {
        dp[0][0] = 1
        dp[1][0] = 0        
    }

    
    for i:=1;i<n;i++ {
        if s[i] == 'a' {
            dp[0][i] = dp[0][i-1]
            dp[1][i] = dp[1][i-1] + 1
        } else {
            dp[0][i] = dp[0][i-1] + 1
            dp[1][i] = min( dp[1][i-1], dp[0][i-1]) 
        }
    }

    return min( dp[0][n-1], dp[1][n-1] )
}

AC代码

https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697109197

https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目总结：L. Last Orders

1. 核心目标

在所有酒吧关闭前，尽可能多地喝掉按顺序给出的品脱（Pints）。任务是计算最大可饮用数量。

2. 场景规则

  • 起始状态：时间为 0，位于 1 号酒吧。

  • 饮酒消耗：第 ii 杯酒需要花费时间 tit_i。必须按 t1,t2,…,trt_1, t_2, \dots, t_r 的固定顺序饮用。

  • 地点限制：

    • 全镇共有 kk 个酒吧（对应 kk 个交叉口）。
    • 禁止连续在同一个酒吧喝两杯酒（每喝完一杯，下一杯必须换到另一个酒吧，之后可以再回来）。

  • 时间限制：每个酒吧 ii 有其绝对关门时间 cic_i。饮酒操作必须在酒吧关门之前或准时完成。

  • 移动消耗：酒吧间通过 mm 条双向道路连接，每条路有对应的行驶时间。

根据题目意思，酒馆关闭仅意味着不能在这个地方饮酒，不意味着就是该节点无法通过。

3. 样例解释

  • 样例 1：

    • 2 个酒吧，关门时间分别为 900 和 1500；酒吧 1 与 2 之间路程 90；饮酒时间序列为 60, 120, 180, 240…
    • 流程示例：
      1. 在酒吧 2 喝第 1 杯（路程 90 + 饮酒 60 = 150s ≤\le 1500，可行）。
      2. 回酒吧 1 喝第 2 杯（路程 90 + 饮酒 120 = 360s ≤\le 900，可行）。
      3. 回酒吧 2 喝第 3 杯（路程 90 + 饮酒 180 = 630s ≤\le 1500，可行）。
      4. 回酒吧 1 喝第 4 杯（路程 90 + 饮酒 240 = 960s）。此时 960 > 酒吧 1 的关门时间 900，无法在酒吧 1 喝第 4 杯。
    • 最终通过合理分配，最大可喝 4 杯。

  • 样例 2：

    • 饮酒时间非常短（2s 或 3s），但酒吧关门时间也非常早（15s 到 35s）。
    • 由于不能在同一酒吧连喝，必须频繁在 1、2、3、4 号酒吧之间切换（考虑路程 1 或 5），利用极短的饮酒时间在多个酒吧关门前完成饮用，最大可喝 7 杯。

思路讲解

这道题目还是没有那么难的。这个是我们所采用的这个状态定义。

dp[node][pint]=timedp[node][pint]=time

转移采用分段转移的这个策略，就是每次只转移一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
  ll ans=0;
  vector<vector<ll>> dp_old(N+3,vector<ll>(R+3,INF));
  //  第一个节点不喝酒，就从这里转移过来
  dp_old[1][0]=0;
  if (tim_drink[1]<=close_pub_tim[1]) {
// 第一个节点喝酒，就从这里转移
      dp_old[1][1]=tim_drink[1];
      ans=1;
  }
  for (int ci=1;ci<=R+1;++ci) {
      // 因为我们有最短路保证
      // 因此我们每次转移都必须喝酒，因为不喝酒，你来这个节点干什么？毕竟有最短路保证**
      // 不过第一个节点可以不喝酒。
      vector<vector<ll>> dp_new=dp_old;
      for (int u=1;u<=N;++u) {
    // 因为节点第一个节点可以喝酒，也可以不喝酒。所以说有的节点比别的节点转移稍微慢一拍，
    // 所以我们要照顾到转移稍微慢一拍的。所以我们从 ci 减一和 ci 转移。
          for (ll pint=ci-1;pint<=ci;++pint) {
              ll tim=dp_old[u][pint];
              for (int to=1;to<=N;++to) {
                  if (to==u) continue;
                  if (shortest_path[u][to]==INF) continue;
                  ll val=tim+shortest_path[u][to]+tim_drink[pint+1];
                  // 判断是否可以喝完这杯酒
                  if (val<=close_pub_tim[to]) {
                      dp_new[to][pint+1]=min(dp_new[to][pint+1],val);
                      ans=max(ans,pint+1);
                  }
              }
          }
      }
      swap(dp_new,dp_old);
  }
  ans=min(ans,R);
  cout<<ans<<"\n";

AC代码

AC
https://qoj.ac/submission/2015239

源代码

心路历程（WA，TLE，MLE……）

https://qoj.ac/submission/2014564

故意WA了一发，呃呃，这个是故意的。呃，我故意就是没有考虑到呃零节点，他呃就一节点他不喝酒的情况。

Posted on Edited on

题目大意

"
Pahom 从黎明开始，到日落结束，使用铲子做标记，走动的区域尽可能大。由标记点组成的多边形代表Pahom所宣称的土地。

Pahom 每秒走一米，每个标记点需要 mm 秒制作，从黎明到日落总共有 tt 秒可用时间。找出Pahom可以宣称的最大区域。

Pahom必须在结束时返回起点。
"

思路讲解

这个函数可以三分啊。对，就是可以三分嗯。

image

P的这个单调性和 tan 的单调性是相反的。

image

从图像上，可以看出其上升速度是比较缓慢的，和 x 同阶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto fx=[&](ll n) -> DB {
    ll perimeter=total_tim-n*mark_time;
    DB res=0.5*perimeter*perimeter/(2.0*n);
    res/=tan(pi/n);
    return res;
};
while (r-l>9) {
    ll mid1=l+(r-l)/3,mid2=r-(r-l)/3;
    if (fx(mid1)>fx(mid2)) {
        r=mid2;
    }else {
        l=mid1;
    }
}

AC代码

AC
https://qoj.ac/submission/2010802

心路历程（WA，TLE，MLE……）