阴

来源里的璃月港算法竞赛太细节了

好难啊

- 通行后到达时间为 $T'' = T' + 1$，余数为 $(r + 1) \bmod k$；
- 用 $T''$ 更新 $d[v][(r+1) \bmod k]$。
最终答案为 $\min_{0 \leq r < k} d[n][r]$。

有 $n$ 个景点、$m$ 条道路，巴士每 $k$ 分钟一班。每条道路有开放时间 $t_{\text{open}}$，仅当当前时间 $\geq t_{\text{open}}$ 时可通过，通行耗时 1 分钟。求从景点 $1$ 到景点 $n$ 的最早到达时间。
**思路**：
设 $d[i][r]$ 表示到达景点 $i$ 时，当前时间模 $k$ 余 $r$ 的最早绝对时间。初始状态 $d[1][0] = 0$。
对每条边 $(u, v, t_{\text{open}})$，若当前时间为 $T = d[u][r]$，则：
- 若 $T < t_{\text{open}}$，需等待至首个 $\geq t_{\text{open}}$ 的发车时刻：
等待后时间 $T' = \left\lceil \frac{t_{\text{open}} - T}{k} \right\rceil \cdot k + T$；

化简核心分两步：
1. **有理数根**：若 $\Delta$ 为完全平方数，计算分子 $-b \pm \sqrt{\Delta}$（按 $a$ 正负取较大根），分母 $2a$，用 $\gcd$ 约分为最简分数。
2. **无理数根**：将 $\sqrt{\Delta}$ 化为 $k\sqrt{r}$（$r$ 无平方因子）：枚举 $i=2$ 到 $\lfloor\sqrt{\Delta}\rfloor$，若 $i^2 \mid \Delta$，则 $\Delta \gets \Delta / i^2$，$k \gets k \cdot i$。最终根为 $\frac{-b}{2a} + \frac{\pm k}{2a}\sqrt{r}$，分别约分两部分，确保无理系数为正，按格式输出。

这题太吃操作了

https://atcoder.jp/contests/dp/tasks/dp_t

strcpy魅力时刻

**状态定义：**
设 \( dp[i] \) 表示到达站点 \( i \) 时的最小总加油花费。
**转移方程：**
\[
dp[i] = dp[i-1] + \max\left(0,\ \left\lceil \frac{v_{i-1} - r_{i-1}}{d} \right\rceil \right) \cdot \min_{1 \leq j < i} a_j
\]
其中 \( r_{i-1} \) 为到达站点 \( i-1 \) 后剩余的可行驶公里数，且 \( r_i = r_{i-1} + \left\lceil \frac{v_{i-1} - r_{i-1}}{d} \right\rceil \cdot d - v_{i-1} \)。

每天剩余苹果数更新公式：
\[
r \gets r - \left\lceil \frac{r}{3} \right\rceil = \left\lfloor \frac{2r}{3} \right\rfloor
\]
编号为 \(n\) 的苹果在当天未被拿走时，其下一天的位置更新公式：
\[
p \gets p - \left\lceil \frac{p}{3} \right\rceil
\]
它在某一天被拿走的充要条件是：
\[
p \equiv 1 \pmod{3}
\] Latex不会敲，AI转的

**等待时间的计算：**
当我们需要在一条道路前等待时，计算公式为：
\[
\text{等待周期数} = \left\lceil \frac{\text{开放时间} - \text{当前时间}}{k} \right\rceil
\]
在代码中，我们使用整数除法来实现向上取整：
\[
x = \frac{\text{na} - \text{nt} + k - 1}{k}
\]
**余数的计算：**
走过一条道路需要1分钟，所以新的余数为：
\[
\text{新余数} = (\text{当前余数} + 1) \mod k
\] AI转的一个latex版本的

粘不完

#include<bits/stdc++.h>

using namespace std;

int main(){

 freopen("bus.in","r",stdin);

 freopen("bus.out","w",stdout);

 int n,m,k;

 cin>>n>>m>>k;

 int u[20005],v[20005],a[20005];

 vector<int> g[10005];

 for(int i=0;i<m;i++){

 cin>>u[i]>>v[i]>>a[i];

 g[u[i]].push_back(i);

 }

 int d[10005][105];

 for(int i=1;i<=n;i++)for(int j=0;j<k;j++)d[i][j]=1000000000;

 d[1][0]=0;

 queue<pair<int,int>> q;

 q.push(make_pair(1,0));

 while(!q.empty

注意：本题文件名为 chessboardd 而并非 chessboard

回复 @┭┮﹏┭┮ :
失踪人口回归

回复 @金牌教师王艳�� : 可以记搜

？

原题地址：https://www.hackerrank.com/contests/w34/challenges/magic-cards

先来考虑一个排列可到达的条件是什么。
如果不是 n 排列，而是 01 序列的话，那么条件是显然的：只要对于任意 i，序列 b 的 第 i 个 1 都位于序列 a 的第 i 个 1 的右边（不一定严格），那么 a 就可以到达 b。
对于一个 n 排列 a，以及一个数 k，把 a 中大于 k 的数标为 1，剩下的数标为 0，
就能得 到一个 01 序列。如果对于任意的 k，排列 a 对应的 01 序列都能够到达排列 b 对
应的序列，那么排列 a 就可以到达排列 b。
它的必要性是显然的。至于充分性，可以观察下面这个移动策略： i 从 n 到 1 的顺
序，每次将数字 i 移到它的目标位置，令当前位置为 l，目标位置为 r，当前 (l, r] 区间的
最大数字为 a[j]，那么把 a[l] 和 a[j] 交换一下即可。
容易看出这样移动一定是可行的。
那么只要做一个 01 串 DP： F[i][j]表示到第 i 位，已经用了的集合为 j 的方案数，从一个全 0 的串开始，每次转移
是枚举第 i 位放几，即将串中的某个 0 改为 1，最后到达一个全 1 的串，且保证经过的都
是合法 01 串。

暴力是O(3^N)。
考虑meet-in-the-middle，左边的那些3^(N/2)枚举分别是不放还是放到第一组还是放到第二组，并记录下来。
右边的3^(N/2)枚举后，再2^(N/2)看看左边符合这个值的那些，就行了。
总复杂度O(6^(N/2))。
其实调整左右大小可以使得复杂度更优。
来源：USACO 2012 OPEN GOLD subsets