2024 牛客暑期多校训练营 第四场
QQ算竞小群喵 754883088
at begin
不知不觉已经是第四场了
前面几场也没有好好的做和补题 ,那就从这一场开始吧
G-Horse Drinks Water
这个问题是将军马饮水问题的变种。
已知将军的马在点$\textstyle (x_G, y_G)$处,帐篷在点$\textstyle (x_T, y_T)$处,河流位于 x 轴的正半轴和 y 轴的正半轴上,求马从河边喝水返回帐篷所需的最短距离。
about
这个题是主播队友写的
所以就不解释了
code
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int n;
double x11, x21, y11, y21;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x11 >> y11 >> x21 >> y21;
double x = min(sqrt((x11 - x21) * (x11 - x21) + (y21 + y11) * (y21 + y11)),
sqrt((x11 + x21) * (x11 + x21) + (y21 - y11) * (y21 - y11)));
printf("%.10lf\n", x);
}
return 0;
}
I-Friends
进入比赛过的最多的是 G
题,第二多的是 I
把 G
交给队友后我就来开 I
题目大意
有$\textstyle n$个人站成一排,从左到右依次为$\textstyle 1$到$\textstyle n$。在这些人中,有$\textstyle m$对朋友。
定义区间$\textstyle [l,r]$($\textstyle 1 \leq l \leq r \leq n$)为友好当且仅当区间内的每对人都是朋友。
有多少个友好间歇?
$\textstyle n$ and $\textstyle m$ ($\textstyle 1 \leq n, m \leq 10^6$)
思考一下
观察数据范围肯定是个$O(n^2)$以下的时间复杂度
那么我们想一下暴力
从每个位置开始枚举左端点,如果还是友好区间就向右暴力拓展
如果不是就break
掉
我们可以发现 一共有 m
对 关系
所以我们暴力枚举的上界是 $O(min(n^2,m))$
由此便可以通过这道题
code
// NowCoder Friends
// https://ac.nowcoder.com/acm/contest/81599/I 2024-07-25 12:04:09
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int N = 1E6 + 10;
int sum[N];
void solve() {
cin >> n >> m;
vector<set<int>> a(n + 1);
vector<int> x(n + 2);
while (m--) {
int x, y;
cin >> x >> y;
a[x].insert(y);
}
for (int i = n; i >= 1; i--) {
int j = i;
while ((i == j or a[i].count(j)) and x[i] <= x[i + 1]) x[i]++, j++;
}
int ans = 0;
for (int i = 1; i <= n; i++) ans += x[i];
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
C-Sort4
C题其实算不上难,但是我吃了三发罚时
为什么呢,因为我的思路有一点小特判遗漏了
下面解释一下如何避免掉坑
题目大意
给定长度为$\textstyle n$的排列$\textstyle ^\dagger$。在一次操作中,您最多可以从排列中选择4个元素,并任意交换它们的位置。按升序排序所需的最小操作数是多少?
$\textstyle ^\dagger$长度为$\textstyle n$的排列是由$\textstyle 1$到$\textstyle n$之间的$\textstyle n$个不同整数以任意顺序组成的数组。例如,$\textstyle [2,3,1,5,4]$是一个排列,但$\textstyle [1,2,2]$不是一个排列($\textstyle 2$在数组中出现了两次),$\textstyle [1,3,4]$也不是一个排列($\textstyle n=3$但在数组中有$\textstyle 4$)。
$\textstyle n$ ($\textstyle 1 \leq n \leq 10^6$),
$\sum\textstyle n$ across all test cases does not exceed $\textstyle 10^6$.
思考一下
$[4,2,5,1,3,6]$
比如这样一个数组
我们可以把它拆成置换环 (关于置换环 我记得 知乎-严格鸽 有很好的专题,我之前就是看他的博客了解的)
上面的数组可以拆成这样的四个环
我们可以同时将两个大小为2
的 置换环放进我们的一次操作中
可以同时给这两个环排好序
再来看复杂一点的情况
$[5 ,4, 6, 3, 1,8, 2, 7]$
我们把它拆成置换环
那么它就分成了一个大小为2
的环和一个大小为6
的环
我们知道a[6]=8,a[8]=7,a[7]=2,a[2]=4
那么我们选中6 8 7 2
这四个数进行排序,可以得到 a[2]=2,a[7]=7,a[8]=8
剩下的情况变为
我们可以发现 对于大小大于四的置换环,我们可以用一次操作使其的大小减少3
大小小于等于4
的置换环,我们可以用等于其大小的操作 来还原
于是我们发现 需要移动3
次 和移动 4
次的操作都需要单独的进行一次
需要移动2
次的 操作可以两两拼成一次
这样就可以确保是最少的操作次数
code
// NowCoder Sort4
// https://ac.nowcoder.com/acm/contest/81599/C 2024-07-25 12:21:55
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n;
vector<int> a(n + 1), mp(5), X(n + 1);
int res = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
int j = a[i], cnt = 1;
X[j] = 1;
while (!X[a[j]] and (a[i] != a[j])) j = a[j], cnt++, X[j] = 1;
if (cnt != 1)
if (cnt <= 4)
mp[cnt]++, res += cnt;
else
mp[4] += (cnt - 2) / 3, cnt -= (cnt - 2) / 3 * 3, mp[cnt]++;
}
cout << mp[4] + mp[3] + (mp[2] + 1LL) / 2LL << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
H-Yet Another Origami Problem
H
题其实是个诈骗哈
题目大意
炸鸡讨厌折纸问题!别人能轻松解决的折纸问题(例如 CF1966E 和 HDU6822),他总是解决不了。不过,今天炸鸡是出题人!轮到他给参赛者出一道非常难的折纸题了!
给定一个长度为 $\textstyle n$的数组 $\textstyle a$,你可以执行以下任意次数(可能为零)的操作:
选择一个索引 $\textstyle p$,然后执行以下两种操作之一:
-
对于所有$\textstyle i$,如$\textstyle a_i \leq a_p$,让$\textstyle a_i \gets a_i + 2(a_p - a_i)$。
-
对于所有$\textstyle i$,如$\textstyle a_i \geq a_p$,设为$\textstyle a_i \gets a_i - 2(a_i - a_p)$。
例如,如果原始数组为 $\textstyle [2,4,5,3]$,选择 $\textstyle p=2$并执行操作 1,数组将变为 $\textstyle [6,4,5,5]$。
现在,你想通过这些操作最小化数组的范围。回想一下,数组的范围是数组中最大元素和最小元素之差。
思考一下
这种用两个数之差来更改数的,一般都跟最大公因数有关系
我们发现,最后的结果就是排序以后两两之间的最大公因数
code
// NowCoder Yet Another Origami Problem
// https://ac.nowcoder.com/acm/contest/81599/H 2024-07-25 13:03:26
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(all(a));
int gcd = 0;
for (int i = 1; i < n; i++) gcd = __gcd(gcd, a[i] - a[i - 1]);
cout << gcd << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
A-LCT
这个题官方的题解很简单,这里用了另外一种办法
题目大意
注意这个问题的内存限制不寻常。
给定一棵有根的树,树上有 $\textstyle n$个节点和 $\textstyle n-1$条边。第$\textstyle i$条边可以用$\textstyle (a_i, b_i)$来描述,它表示连接节点$\textstyle a_i$和节点$\textstyle b_i$的一条边,其中节点$\textstyle a_i$是节点$\textstyle b_i$的父节点。
共有$\textstyle n-1$个查询。第$\textstyle i$个查询包含一个整数$\textstyle c_i$,询问在由$\textstyle i$条边构成的图(森林)中,从节点$\textstyle c_i$开始的最长简单路径的长度。保证不存在$\textstyle j$使得$\textstyle 1 \leq j \leq i$和$\textstyle b_j = c_i$,即$\textstyle c_i$是森林中一棵树的根。
考虑
我们先将整棵树 建出来
在$O(n)$ 的时间内 DFS
一遍 求出所有的节点的深度dep
再动态加边进行维护并查集,同时维护每个并查集内深度最深的点和深度最浅的点
答案就是深度最深的点减去深度最浅的点
code
// NowCoder LCT
// https://ac.nowcoder.com/acm/contest/81599/A 2024-07-25 14:47:57
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
struct UnionFindSet {
vector<int> F;
vector<int> rank;
int n;
UnionFindSet(int _n = 2e6 + 10) {
n = _n;
F.resize(n + 1);
rank.resize(n + 1, 1);
for (int i = 1; i <= n; i++) {
F[i] = i;
}
}
int find(int x) { return x == F[x] ? x : F[x] = find(F[x]); }
bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (rank[fx] < rank[fy]) swap(fx, fy);
F[fy] = fx;
rank[fx] += rank[fy];
return true;
}
};
void solve() {
cin >> n;
vector<int> dep(n + 1);
vector<vector<int>> G(n + 1);
vector<int> x(n + 1), y(n + 1), z(n + 1);
vector<int> in(n + 1);
for (int i = 1; i < n; i++) {
int xx, yx, zx;
cin >> xx >> yx >> zx;
x[i] = xx, y[i] = yx, z[i] = zx, in[yx]++;
G[xx].emplace_back(yx);
}
int rt = -1;
for (int i = 1; i <= n; i++)
if (!in[i]) rt = i;
UnionFindSet U(n + 1);
auto dfs = [&](auto self, int u, int fa) -> void {
dep[u] = dep[fa] + 1;
for (auto it : G[u]) {
if (it == fa)
continue;
else
self(self, it, u);
}
};
dep[rt] = 1;
dfs(dfs, rt, 0);
vector<int> mx(n + 1), mn(n + 1, INT_MAX);
for (int i = 1; i < n; i++) {
mx[U.find(x[i])] =
max({mx[U.find(x[i])], mx[U.find(y[i])], dep[x[i]], dep[y[i]]});
mx[U.find(y[i])] =
max({mx[U.find(x[i])], mx[U.find(y[i])], dep[x[i]], dep[y[i]]});
mn[U.find(x[i])] =
min({mn[U.find(x[i])], mn[U.find(y[i])], dep[x[i]], dep[y[i]]});
mn[U.find(y[i])] =
min({mn[U.find(x[i])], mn[U.find(y[i])], dep[x[i]], dep[y[i]]});
U.merge(x[i], y[i]);
if (!mx[U.find(z[i])]) {
cout << "0 ";
} else {
cout << mx[U.find(z[i])] - mn[U.find(z[i])] << " ";
}
}
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
J-Zero
这个题其实是数据水了
我用的$O(n^2)$的做法过的
不做赘述了
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
int modExp(int base, int exp, int mod) {
int result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = result * base % mod;
}
base = base * base % mod;
exp /= 2;
}
return result;
}
using i64 = long long;
template <class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template <i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const { return x; }
explicit constexpr operator i64() const { return x; }
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & { return *this *= rhs.inv(); }
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
template <>
i64 MLong<0LL>::Mod = MOD;
using mint = MLong<0LL>;
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<mint> powK(n + 1);
for (int i = 1; i <= n; ++i) {
powK[i] = modExp(i, k, MOD);
}
mint expected_value = 0;
int inv2 = modExp(2, MOD - 2, MOD);
// Precompute the prefix sum of '?' counts
vector<int> prefix_question_marks(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix_question_marks[i + 1] =
prefix_question_marks[i] + (s[i] == '?' ? 1 : 0);
}
for (int l = 0; l < n; ++l) {
if (s[l] == '0') continue; // Skip starting from '0'
for (int r = l; r < n; ++r) {
if (s[r] == '0') break; // Stop if encountering '0'
int cnt = prefix_question_marks[r + 1] - prefix_question_marks[l];
int length = r - l + 1;
mint prob = modExp(inv2, cnt, MOD);
expected_value = (expected_value + powK[length] * prob);
}
}
cout << expected_value << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}