数学（九）
C - Minimum Glutton
排序加贪心
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin＞＞n;
ll x, y;
std::cin＞＞x＞＞y;
std::vector＜int＞ a(n), b(n);
for (int i = 0; i＜n; i++)
{
std::cin＞＞a[i];
}
for (int i = 0; i＜n; i++)
{
std::cin＞＞b[i];
}
std::sort(a.rbegin(), a.rend());
std::sort(b.rbegin(), b.rend());
int ans = n;
ll sum = 0;
for (int i = 0; i＜n; i++)
{
sum += a[i];
if (sum＞x)
{
ans = std::min(ans, i + 1);
break;
}
}
sum = 0;
for (int i = 0; i＜n; i++)
{
sum += b[i];
if (sum＞y)
{
ans = std::min(ans, i + 1);
break;
}
}
std::cout＜＜ans＜＜"\n";
return 0;
}
D - K-th Nearest
二分到b 的距离
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, q;
std::cin＞＞n＞＞q;
std::vector＜int＞ a(n);
for (int i = 0; i < n; i++)
{
std::cin＞＞a[i];
}
std::sort(a.begin(), a.end());
while (q--)
{
int b, k;
std::cin＞＞b＞＞k;
auto check = [&](int dis)
{
int p1 = std::lower_bound(a.begin(), a.end(), b - dis) - a.begin();
int p2 = std::upper_bound(a.begin(), a.end(), b + dis) - a.begin() - 1;
return p2 - p1 + 1＜k;
};
int l = -1, r = 2e8;
while (l＜r)
{
int mid = (l + r + 1) / 2;
if (check(mid))
l = mid;
else
r = mid - 1;
}
std::cout＜＜l + 1＜＜"\n";
}
return 0;
}
E - Maximum Glutton
到E 直接开始破防，确实是 dp 功力还不行
枚举前面i 个里面选 j 个，甜度不超过 k 的最小代价，然后可以把第一维滚掉
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin＞＞n;
int x, y;
std::cin＞＞x＞＞y;
std::vector＜int＞ a(n + 1), b(n + 1);
for (int i = 1; i ＜= n; i++)
{
std::cin＞＞a[i]＞＞b[i];
}
std::vector dp(n + 1, std::vector＜int＞(x + 1, y + 1));
dp[0][0] = 0;
for (int i = 1; i ＜= n; i++)
{
auto ndp = dp;
for (int j = 1; j ＜= i; j++)
{
for (int k = a[i]; k ＜= x; k++)
{
ndp[j][k] = std::min(ndp[j][k], dp[j - 1][k - a[i]] + b[i]);
}
}
dp.swap(ndp);
}
int ans = 0;
for (int j = 0; j＜n; j++)
{
for (int k = 0; k ＜= x; k++)
{
if (dp[j][k] ＜= y)
ans = std::max(ans, j + 1);
}
}
std::cout＜＜ans＜＜'\n';
return 0;
}
F - Range Connect MST
赛时没仔细想盲猜线段树优化建图然后就一直冲E 去了，打完一看直接升温
可以将图分成两个部分一边是1 ∼ N，另一边是 N＋1 ∼ N＋Q，操作完第二个部分所有节点一定会连到第一个部分，代价是 ∑Gᵢ，然后只要考虑第一个部分
每次操作会有[Lᵢ，Rᵢ] 中所有点和点 N＋i 连接，总共 Rᵢ – Lᵢ＋1 条边，相当于 [Lᵢ，Rᵢ] 中的点连成链，然后 N＋i 连到这个区间（怎么连不重要），我们只需要暴力把 x 连接到 x＋1(x＜Rᵢ) 如果 [Lᵢ，Rᵢ] 内某个区间
已经相连，直接跳过这个区间，这个操作用并查集很容易实现，根据上面连接方式，每个点的祖先一定大于或者等于它，最后只要判断 1 的祖先是不是 N 判断是否连通
至于最小生成树问题，存下每次询问然后排序
struct DSU
{
int n;
std::vector＜int＞ fa, size;
DSU(int n) : n(n), fa(n + 1), size(n + 1, 1) { std::iota(fa.begin(), fa.end(), 0); }
int find(int x)
{
if (x != fa[x])
{
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int x, int y) // x -＞ y
{
x = find(x), y = find(y);
if (x == y)
return;
// if (size[x]＞size[y])
//
std::swap(x, y);
fa[x] = y, size[y] += size[x];
}
bool same(int x, int y)
{
return find(x) == find(y);
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, q;
std::cin＞＞n＞＞q;
std::vector＜std::array<int, 3＞＞ quries(q);
for (auto &[c, l, r] : quries)
{
std::cin＞＞l＞＞r＞＞c;
}
std::sort(quries.begin(), quries.end());
ll ans = 0;
DSU dsu(n);
for (auto [c, l, r] : quries)
{
ans += c;
int x = dsu.find(l);
while (x＜r)
{
dsu.merge(x, x + 1);
x = dsu.find(x);
ans += c;
}
}
if (dsu.find(1) != n)
{
ans = -1;
}
std::cout＜＜ans＜＜'\n';
return 0;
}
G - Last Major City
前有典题...
斯坦纳树，模板代码几乎原封不动放上去就能过，原理得仔细学习，代码倒是很简单
dp[S][i]表示以 i 为根，节点集合为 S 的最小路径长，有
dp[S][i]＝min(dp[S][i]，dp[T][i]＋dp[S ⨁ T][i])，T ⊆ S
然后再对 S 做一个最短路就可以了
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m, k;
std::cin＞＞n＞＞m＞＞k;
std::vector＜std::vector＜std::pair＜int, int＞＞＞ g(n);
for (int i = 0; i＜m; i++)
{
int a, b, c;
std::cin＞＞a＞＞b＞＞c;
a--, b--;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
const ll inf = 1e18;
std::vector dp(1＜＜(k - 1), std::vector＜ll＞(n + 1, inf));
for (int i = 0; i＜k - 1; i++)
{
dp[1＜＜i][i] = 0;
}
for (int s = 1; s＜(1＜＜k - 1); s++)
{
for (int t = (s - 1) & s; t＞0; t = (t - 1) & s)
{
for (int i = 0; i＜n; i++)
{
dp[s][i] = std::min(dp[s][i], dp[t][i] + dp[s ^ t][i]);
}
}
// dij
std::priority_queue＜std::pair＜ll, int＞＞ q;
std::vector＜bool＞ vis(n);
for (int i = 0; i＜n; i++)
{
if (dp[s][i] != inf)
q.push({-dp[s][i], i});
}
while (!q.empty())
{
auto [_, x] = q.top();
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (auto [y, w] : g[x])
{
if (dp[s][x] + w＜dp[s][y])
{
dp[s][y] = dp[s][x] + w;
q.push({-dp[s][y], y});
}
}
}
}
for (int i = k - 1; i＜n; i++)
{
std::cout＜＜dp[(1 << k - 1) - 1][i]＜＜"\n";
}
return 0;
}
本文使用 Zhihu On VSCode 创作并发布
