Hanatomizu Hanatomizu

Popular posts

1. Pandas备考复习笔记

2. Python基础语法学习笔记

3. ABC416C Concat(X Th) 题解

   题目传送门 ABC416C

   0x01 思路

   注意到数据范围 \(1 \leq N \leq 10\)，\(1 \leq K \leq 5\)，可以考虑直接 dfs 暴力枚举每一种组合。

   0x02 复杂度分析

   dfs 内枚举 $n$ 个字符串，深度为 \(K\)，复杂度 \(O(N^K)\)。找第 $x$ 小的可以使用 nth_element()，线性复杂度。故总复杂度为 \(O(N^K)\)。

   0x03 示例代码

   #include <bits/stdc++.h>
   using namespace std;
   using ll = long long;
   inline void umax(int &x, int y) {(x < y) && (x = y);}
   inline void umin(int &x, int y) {(x > y) && (x = y);}
   
   int n, k, x;
   vector<string> s;
   string re[100005];
   int cnt;
   
   void dfs(int deps, string ss) {
       if (deps == 0) { return re[++cnt] = ss, void(); }
       for (int i = 1; i <= n; ++i) {
           dfs(deps-1, ss+s[i]);
       }
   }
   
   signed main(){
       #ifdef HANATOMIZU_LOCAL_TEST
       freopen("input.in", "r", stdin);
       #endif // HANATOMIZU_LOCAL_TEST
       ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   
       cin >> n >> k >> x;
       s.resize(n+1);
       for (int i = 1; i <= n; ++i) {
           cin >> s[i];
       }
       dfs(k, string());
       nth_element(re+1, re+x, re+cnt+1);
       cout << re[x] << endl;;
   
       return 0;
   }
   

4. Kupc2021_c题解

   题目传送门

   思路

   首先根据题目可以知道：

   1. 在最优解的情况下第 $i$ 个硬币在第 $i$ 个游戏机（题中的 Gacha）中使用。

      题中 $B_j < B_{j+1} (1 \leq j \leq N-1)$ 可以得到。

   2. 整个移动过程可以视作为从 $0$ 开始向正方向移动，得到若干硬币后走回去玩没有玩的游戏机。

   得出了以上结论，dp 的思路就清晰了。

   设 $dp_i$ 为玩了前 $i$ 个游戏机时 $B_i$ 的最小值，$m$ 为玩了前 $i$ 个游戏机的迂回成本最小值。得到状态转移方程： $$m \gets \min(m, dp_{i-1} - A_i \times 2)$$ $$dp_i \gets \min(m, dp_{i-1} + B_i \times 2) + B_i \times 2$$

   值得注意的是，对于 $A_i > B_i$ 的情况（即硬币在游戏机前面），可以直接忽略该硬币，把硬币的位置设置为游戏机的位置（即 $A_i \to B_i$）。因为在去往游戏机的路上一定会捡到该硬币。

   得到答案为： $$ ans = \min(dp_n) + \min_{0 \leq i < n}(dp_i + B_n - A_{i+1}) + A_n $$

5. Lorem_ipsum

   Lorem ipsum dolor sit amet, consectetur adipiscing elit. In vel vehicula ligula, faucibus pulvinar nisl. Curabitur molestie dui in porttitor elementum. Aliquam sed cursus mi. Ut fermentum metus non volutpat ultricies. Cras quis pulvinar nisi. Integer tempor tortor erat, ac eleifend orci faucibus quis. Donec pretium scelerisque urna et volutpat. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum elit odio, eleifend quis arcu vitae, feugiat pretium nisl. Morbi fringilla augue enim, vitae egestas massa dapibus ac. Nullam posuere aliquet scelerisque.