abcdeffa's Blog

Description

给你一个有 $n$ 个点 $m$ 条边的无向图，定义两点间一条路径的权值为所经边的边权最大值，再定义两点间的最短路的长度为两点间所有路径的权值的最小值。现在有 $Q$ 次操作，为加边或求给定的 $k$ 个点对之间的最短路的长度异或和是否为 0。

保证加边操作的次数不超过 5000。

Description

一个有 $n$ 个点 $m$ 条边的无向连通图，现在允许你加一条边，问你加完边以后剩下的桥的数量的最小值，本题有多组数据。

单个测试点的时间限制为 2s。

Description

给你两个正整数 $n$ 和 $k$，问你在 $1∼n$ 中选不超过 $k$ 个数，它们的积不含平方质因子的方案数。

Description

一开始有 $n$ 个非负整数 $h_i$，接下来会进行 $m$ 次操作，第 $j$ 次操作给出一个数 $c_j$，要求你选出 $c_j$ 个大于零的 $h_i$ 并将它们减去 1。问最多可以进行多少轮操作后无法完整地完成操作。

Dsceription

一个 $n$ 个点，$m$ 条边的无向图，在第 $i$ 个点建立一个旅游站点的费用是 $c_i$。特别地，这张图中的任意两点间不存在节点数超过 $10$ 的简单路径。
现在要建造一些旅游站点，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。试求出总花费的最小值。

单个测试点的时间限制为 3s。

Description

给定一个 $1∼n$的排列 $x$，每次你可以将 $x_1∼x_i$ 翻转。试求将序列变为升序的最小操作次数，单个测试点内有 $T$ 组数据。

数据随机。

Description

有 $n$ 种商品，第 $i$ 种物品的价格为 $a_i$，价值为 $b_i$。有 $m$ 个人来购买商品，每个人每种物品只能购买一个。第 $j$ 个人有 $c_j$ 的钱，他会不停选择一个能买得起的价格最高的商品买走，如果有多个，则选择价值最高的。你需要求出每个人购买的物品的价值和。

Description

有 $n$ 张卡牌，第 $i$ 张卡牌上有一个数 $a_i$，每次可以从中选出 $k$ 张卡牌。一种选取方案的幸运值为这 $k$ 张卡牌上数的异或和。试求出所有选取方案的幸运值之和除以 $998244353$ 的余数。

Description

一个长度为 $n$ 的数轴，第 $i$ 个位置有一辆车，它会在往后的每 $c_i$ 个位置停一次，两个停靠站之间的费用为 $v_i$。现在请你求出位置 $0$ 到位置 $1 ∼ n$ 的最短距离。

Description

给你一棵有 $n$ 个点的树，有 $k$ 个点上有羊。你可以在一些点上放置牧羊人，牧羊人可以守护所有离它最近的羊。现在要让每只羊都被保护，求最少需要放置几个牧羊人，并构造出方案，给出其中一种即可。