比赛链接
B.一气贯通之刃
题目描述
小红拿到了一棵树，她想请你寻找一条简单路径，使得这条路径不重不漏的经过所有节点。如果不存在这样的简单路径，则直接输出−1。
简单路径是指这样一条路径，其经过的顶点和边互不相同。
解题思路
只需判断这棵树是否为一条链：一条链两端的节点度数=1，其他节点度数=2。
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>ans, deg(200005, 0);
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
for (int i = 1; i <= n; i++) {
if (deg[i] != 2) {
if (deg[i] == 1) ans.push_back(i);
else {
cout << -1 << endl;
return 0;
}
}
}
if (ans.size() == 2) cout << ans[0] << ' ' << ans[1] << endl;
else cout << -1 << endl;
return 0;
}
E.双生双宿之错
题目描述
小红定义一个数组是“双生数组”，当且仅当该数组大小为偶数，数组的元素种类恰好为 2 种，且这两种元素的出现次数相同。例如 { 1, 1, 4, 4, 1, 4 } 是双生数组。
现在小红拿到了一个长度为偶数的数组，她可以进行若干次操作，每次操作将选择一个元素，使其加 1 或者减 1。小红希望你计算将该数组变成双生数组的最小操作次数。
解题思路
中位数有这样的性质 ：所有数与中位数的绝对差之和最小。
先将数组排序，前半部分取中位数，后半部分也取中位数，分别让两部分的数向中位数靠拢。需要注意的是，两个中位数相等时不符合题意，需要将一个中位数减一，或者另一个中位数加一，判断两种情况谁的操作次数更小。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
static void solve() {
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin(), a.end());
//中位数
int left = a[(n / 2 + 1) / 2], right = a[(n / 2 + 1 + n) / 2];
int ans = 0;
if (left != right) {
for (int i = 1; i <= n / 2; i++) ans += abs(a[i] - left);
for (int i = n / 2 + 1; i <= n; i++) ans += abs(a[i] - right);
}
else {
int res = 0;
left--;
for (int i = 1; i <= n / 2; i++) res += abs(a[i] - left);
for (int i = n / 2 + 1; i <= n; i++) res += abs(a[i] - right);
left++;
right++;
for (int i = 1; i <= n / 2; i++) ans += abs(a[i] - left);
for (int i = n / 2 + 1; i <= n; i++) ans += abs(a[i] - right);
right--;
ans = min(res, ans);
}
cout << ans << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
G.井然有序之衡
题目描述
小红拿到了一个数组，她可以进行任意次以下操作：选择两个元素，使得其中一个加 1，另一个减 1。
小红希望最终数组变成一个排列，请你帮助他确定这能否实现。如果可以实现的话，还需要求出最小操作次数。
长度为 n 的排列是由 1∼n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
解题思路
当一个排列确定时，其必包含1~n，其和也唯一。
由于给定的操作无法改变数组的和（+1，-1相互抵消）， 因此可以先判断给定数组的和是否与长度为n的排列的和相同，不相同的直接输出-1。
随后将数组升序排序，每一位与1~n的排列对应，找出数组比排列大的数，累加差值为t。由于总和相同，剩下的数组比排列小的数，其差值一定与t相同。因此共有t次操作，即t组{+1，-1}。
#define int long long
using namespace std;
int sum, aim, n, t;
vector<int> a;
static void solve() {
cin >> n;
a.push_back(0);
for (int i = 1; i <= n; i++) {
cin >> t;
sum += t;
a.push_back(t);
}
if (n % 2 == 1) aim = (1 + n) / 2 * n;
else aim = (1 + n) * (n / 2);
if (sum == aim) {
int t = 0;
sort(a.begin(), a.end());
for (int i = 1; i <= n; i++) {
if (a[i] > i)t += a[i] - i;
}
cout << t << endl;
}
else
cout << -1 << endl;
}
signed main() {
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
H.井然有序之窗
题目描述
小红希望你构造一个长度为 n 的排列，需要满足第 i 个元素的范围在 [ li, ri ] 范围内。你能帮帮她吗？
长度为 n 的排列是由 1∼n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
解题思路
1.将给出的 [ li, ri ] 存储在结构体中，同时存储其编号。
struct range {
int l, r, index;
}ran[100005];
2.按照区间右端点升序，右端点相同的按照左端点降序。
bool cmp(range a, range b) {
if (a.r == b.r) return a.l > b.l;
else return a.r < b.r;
}
3.定义一个set，存储未使用的数。
set<int> unused;
for (int i = 1; i <= n; i++) unused.insert(i);
4.遍历排序好的区间，使用 lower_bound(l) 从 set 中查找未使用的数并填入 ans 数组。若 lower_bound() 找不到合法的数或者找到的数超过右区间，则不存在满足条件的排列，直接输出 −1。
完整代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct range {
int l, r, index;
}ran[100005];
bool cmp(range a, range b) {
if (a.r == b.r)return a.l > b.l;
else return a.r < b.r;
}
static void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> ran[i].l >> ran[i].r;
ran[i].index = i;
}
sort(ran + 1, ran + 1 + n, cmp);
set<int> unused;
for (int i = 1; i <= n; i++)unused.insert(i);
vector<int> ans(100005, 0);
for (int i = 1; i <= n; i++) {
//获取区间边界
int l = ran[i].l, r = ran[i].r;
//查找第一个未使用的大于等于l的数
auto it = unused.lower_bound(l);
//未找到或大于右边界
if (it == unused.end() || *it > r) {
cout << -1 << endl;
return;
}
//找到，填入此数
ans[ran[i].index] = *it;
//从未使用中删除
unused.erase(it);
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
}
signed main() {
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
如有错误欢迎指正~
京公网安备 11010502036488号