数学（九）

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

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 创作并发布

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。