B – Maja
考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]
考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：
这道题我在考场上打了一个错解，还骗到了 30 分。
正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。
傻逼题，不分析。
这道题非常的有趣（精心调参之后随机化程序可以拿 90 分），正解非常的巧妙。我们可以把问题化为求\(min\{ S_{i,j} \mod P, K \leq S_{i,j} \mod P\}\)。我们先用\(O(n)\)的时间来进行前缀和的预处理，之后我们倒序处理前缀和，从后往前加入 set。在加入 set 的过程中二分查找\(s[i]+k\)和\(s[i]+k-p\)这两个目标最优解，之后记录答案即可，非常的巧妙。
// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100010;
int n, k, p, ans = 0x7f7f7f7f, s[MAX_N];
set<int> st;
int main()
{
scanf("%d%d%d", &n, &k, &p);
for (int i = 1; i <= n; i++)
scanf("%d", &s[i]), (s[i] += s[i - 1]) %= p;
set<int>::iterator it;
st.insert(s[n]);
for (int i = n - 1; i >= 1; i--)
{
it = st.lower_bound(s[i] + k);
if (it != st.end())
ans = min(*it - s[i], ans);
it = st.lower_bound(s[i] + k - p);
if (it != st.end() && *it < s[i])
ans = min(*it - s[i] + p, ans);
st.insert(s[i]);
}
printf("%d", ans);
return 0;
}
哦，傻逼题。——crazydave
这道题算是套路吧，用状态压缩枚举每一维符号的状态，求出最大最小值，最大值减去最小值（最小值代表着状态相反的曼哈顿贡献）即可。
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000010;
int n, d, info[MAX_N][6], st[10], ans;
void calc(int stat)
{
int mn = (1 << 29), mx = -mn;
for (int i = 1; i <= d; i++, stat >>= 1)
st[i] = stat & 1;
for (int i = 1; i <= n; i++)
{
int acc = 0;
for (int j = 1; j <= d; j++)
acc += (st[j] == 1) ? info[i][j] : -info[i][j];
if (acc != 0)
mn = min(mn, acc), mx = max(mx, acc);
}
ans = max(mx - mn, ans);
}
int main()
{
scanf("%d%d", &n, &d);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= d; j++)
scanf("%d", &info[i][j]);
for (int i = 0; i < (1 << d); i++)
calc(i);
printf("%d", ans);
return 0;
}