主要思路
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]
大概可以想到，先把所有的数除掉一个 GCD 之后再来计算出现次数最多的素因子。我们用埃筛筛一下每个数的最小素因子，然后暴力除做标记即可。
做起来很舒适的一套题。
先把曼哈顿距离做答案，然后枚举这两个点初始的方向，然后取个最小值即可。
// CF1078A.cpp
#include <bits/stdc++.h>
using namespace std;
double a, b, c, x[3], y[3];
double calcByX(double x) { return (-1.0 * a * x - c) / b; }
double calcByY(double y) { return (-1.0 * b * y - c) / a; }
int main()
{
scanf("%lf%lf%lf%lf%lf%lf%lf", &a, &b, &c, &x[1], &y[1], &x[2], &y[2]);
double ans = fabs(x[1] - x[2]) + fabs(y[1] - y[2]);
if (a != 0 && b != 0)
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
{
double pos1X, pos1Y, pos2X, pos2Y;
double pans = 0;
if (i == 0)
pos1X = calcByY(y[1]), pos1Y = y[1], pans += fabs(pos1X - x[1]);
else
pos1X = x[1], pos1Y = calcByX(x[1]), pans += fabs(pos1Y - y[1]);
if (j == 0)
pos2X = calcByY(y[2]), pos2Y = y[2], pans += fabs(pos2X - x[2]);
else
pos2X = x[2], pos2Y = calcByX(x[2]), pans += fabs(pos2Y - y[2]);
pans += sqrt((pos1X - pos2X) * (pos1X - pos2X) + (pos1Y - pos2Y) * (pos1Y - pos2Y));
ans = min(ans, pans);
}
printf("%.10lf\n", ans);
return 0;
}
首先这题有个提示：
必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。
那么我们可以考虑直接算这个钱反复转手的最大值即可。设计状态 \(dp[i]\)，然后有转移：
\[ dp[i] = \max_{j \in [0, i)} \frac{(A_i Rate_j + B_i)f[j]}{A_j \times Rate_j + B_j} \]
这道题是要求你实现一个 Checker，来判断是否有长度相同的环。实现的主要方式是找出所有的环并放到桶里面进行统计。我们可以观察出一些简单的性质，来做一次判断：
之后，我们可以考虑把度数为 2 的点去掉，缩成一张新的图。然后，再做暴力的 DFS 来判断是否存在同长环：具体而言，选择一个起点，然后在 DFS 之后删去。
时间复杂度是 \(\Theta(n^2)\) 的。