756(Div.3)

A. Make Even

题意

给定一个数字 $n$ ，每次可以翻转一个前缀，问最少几次可以使数字 $n$ 变成偶数。

分析

1. 本身就是偶数，不需要反转。
2. 第一位是偶数，整个翻转，一次。
3. 只有中间存在偶数，把它翻转到第一位，再翻转一次，两次。
4. 不存在偶数，-1。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;

void solve ()
{
    string n; cin >> n;
    int f = false;
    for (int i = 0; i < n.size(); i ++ ) if ((n[i] - '0') % 2 == 0) f = true;
    if (!f) cout << -1 << endl;
    else if ((n.back() - '0') % 2 == 0) cout << 0 << endl;
    else if ((n[0] - '0') % 2 == 0) cout << 1 << endl;
    else cout << 2 << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

B. Team Composition: Programmers and Mathematicians

题意

给定两个数字 $a$ 和 $b$ ，每次从 $a$ 和 $b$ 里取4个作为一组，每个数字至少取一个。问最少能取几组。

分析

如果 $a < b$ ，设 $b - a = d$ ，先尽量把差值抵消，每次 $a$ 取一个， $b$ 取三个，差值减 $2$ ，组成 $min(a, d / 2)$ 组。

然后差值小于 $2$ ，每次就可以两个数字都取两个，贪心保证 $a$ 和 $b$ 都尽量取完。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;

void solve ()
{
    int a, b; cin >> a >> b;
    if (a > b) swap(a, b);
    int d = b - a;
    if (a < d / 2) cout << a << endl;
    else cout << (a - d / 2) / 2 + d / 2 << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

C. Polycarp Recovers the Permutation

题意

对于长度为 $n$ 的一个排列和空序列 $ans$，每次取 $min(leftmost, rightmost)$ ，如果取 $leftmost$ ，插入序列 $ans$ 的最左边，然后删除 $leftmost$ ，反之插入 $ans$ 最右边，然后删除。只有一个数字时，可以插最左边或者最右边。

给出 $ans$ 序列，问是否存在排列使得操作后的结果为 $ans$ ，输出这个排列。

分析

首先，最后插入的数字一定是排列里最大的数字。也就是它一定在 $ans$ 的左\右。

我们检测 $ans$ 的首尾是否有一个为 $n$ ，如果不存在一定无解。

如果存在：

1. ans[1] = n。我们把 $ans[1]$ 放到原数组的最左边，由于它是最大的，这样右边的数字一定是从后往前放，每次放最右边的，那么对于 $[2, n]$ 的数字，它们是逆序存储在 $ans$ 里的，翻转 $[2, n]$ 即可。
2. ans[n] = n。对于 $[1, n-1]$ 的数字，它们同样也是逆序存储的，翻转 $[1, n-1]$ 即可。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int n, a[N];

void solve ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    if (a[1] != n && a[n] != n) return cout << -1 << endl, void();
    if (a[1] == n) reverse(a+2, a+n+1);
    else if (a[n] == n) reverse(a+1, a+n);
    for (int i = 1; i <= n; i ++ ) cout << a[i] << " \n" [i == n];
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

D. Weights Assignment For Tree Edges

题意

给定 $n$ 个结点的无根树和序列 $b, p$ ，$b_i$ 表示 $i$ 结点的父结点，其中 $b_{root} = root$ ，现在要给树上的每个边赋正权值，使得每个结点到根的距离 $dist_i$ 满足 $p$ 的排序。即如果在 $p$ 数组中 $i$ 点位置在 $j$ 前面 ，则 $dist_i < dist_j$ 。

分析

因为给边赋的权值一定为正数，那么对于一个结点，它的排名不可能比父结点靠前，也就是说 $p$ 数组满足拓扑序。

对于 $p = [3, 1, 2, 5, 4]$ ，构造 $dist_3 = 0(第一个一定是根节点), dist_1 = 2, dist_2 = 3 \ldots $ ，满足枚举的顺序，这个是结点到根的距离，只要记录一下父结点到跟的距离，相减就是这个边的权值。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int b[N], p[N];
int ans[N], dis[N]; // ans为结点到父结点的边权，dis为结点到根节点的边权

void solve ()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    for (int i = 1; i <= n; i ++ ) cin >> p[i];
    for (int i = 1; i <= n; i ++ ) ans[i] = dis[i] = -1;
    ans[p[1]] = dis[p[1]] = 0; // 根节点为0
    for (int i = 2; i <= n; i ++ )
    {
        int j = p[i]; // 计算第i名
        if (dis[b[j]] == -1) return cout << "-1\n", void(); // 排名比父结点前
        ans[j] = i - dis[b[j]]; // 边权
        dis[j] = i; // 到root的距离
    }
    for (int i = 1; i <= n; i ++ ) cout << ans[i] << " \n"[i == n];
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

E1. Escape The Maze (easy version)

题意

在一棵树形迷宫中，共有 $n$ 个结点。有 $k$ 个 vlad 的朋友，分别在 $x_1, x_2, x_3 \ldots$ 结点。vlad 从 $1$ 号结点出发，问，在所有朋友都同时移动时，vlad是否一定可以走到一个叶子节点（过程中不被朋友抓住）？

分析

多源最短路问题，从所有朋友出发，求出到达 $i$ 结点的最短路程。再从 vlad出发，求是否存在一条到达叶子的路径，使得路径上每个点的最短路径都比朋友的短。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 400010, INF = 0x3f3f3f3f;

int n, k;
int h[N], e[M], ne[M], idx;
int q[N]; // 从朋友出发
int d[N]; // 朋友到达i房间的最短时间
bool st[N];
PII mq[N]; // 从 vlad 出发

void add (int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}

void solve ()
{
    cin >> n >> k;
    idx = 0;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = -1;
        d[i] = INF;
        st[i] = false;
    }
    int hh = 0, tt = -1;
    for (int i = 1; i <= k; i ++ )
    {
        int x; cin >> x;
        q[++ tt] = x;
        d[x] = 0;
    }
    for (int i = 1, u, v; i < n && cin >> u >> v; i ++ ) add(u, v), add(v, u);
    while(hh <= tt)
    {
        int room = q[hh ++ ];
        for (int i = h[room]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[room] + 1)
            {
                d[j] = min(d[j], d[room] + 1);
                if (!st[j]) q[++ tt] = j, st[j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i ++ ) st[i] = false;
    hh = 0, tt = 0;
    mq[0] = {1, 0};
    while(hh <= tt)
    {
        int r = mq[hh].first, t = mq[hh].second;
        hh ++ ;
        if (t >= d[r]) continue;
        if (ne[h[r]] == -1 && r != 1 && t < d[r]) return cout << "YES\n", void();
        for (int i = h[r]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j]) mq[++ tt] = {j, t + 1}, st[j] = 1;
        }
    }
    cout << "NO\n";
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

E2. Escape The Maze (hard version)

题意

如上，求出最少的朋友数量，使得只有这些朋友在迷宫时，无论 vlad 如何走，都能抓住 vlad。

分析

同样先求出所有朋友到达其他点的最短路，在 vlad 的 BFS中，如果到达这个点比某个朋友慢，就累计一个朋友到答案里。

这个算法中不存在某个朋友被累加多次的可能。因为在距离 vlad 最近的那个被抓住的点上，BFS不会往下扩展，而是向其他子结点拓展，此时这个朋友一定比 vlad 慢，否则这个点就不是距离 $1$ 号点（vlad出发点）最近的点了。

Code

for (int i = 1; i <= n; i ++ ) st[i] = false;
st[1] = true; // 防止根的子结点重新跑回来
hh = 0, tt = 0;
int cnt = 0;
bool escape = false;
mq[0] = {1, 0};
while(hh <= tt)
{
    int r = mq[hh].first, t = mq[hh].second;
    hh ++ ;
    if (t >= d[r]) { cnt ++ ; continue; }
    if (ne[h[r]] == -1 && r != 1) { escape = true; break; }
    for (int i = h[r]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) mq[++ tt] = {j, t + 1}, st[j] = 1;
    }
}
if (escape) cout << -1 << endl;
else cout << cnt << endl;

F. ATM and Students

题意

给定长度为 $n$ 的序列和数字 $s$，找出最长的区间 $[l, r]$，使得对于任意 $i \subset [l, r]$，$pre_i - pre_{l-1} + s \ge 0$ 。

其中 $pre_i$ 表示前缀和。

分析

双指针，维护 $[i, j]$ 使得这一段区间和加上 $s$ 大于等于 $0$ 即可。

这样的维护不会使得存在某个 $k$ ，$[i, k]$ 的和小于 $0$，而$[i, j]$ 的和大于 $0$ 的情况，因为在 $j$ 为 $k$ 时，就已经把 $i$ 提升到 $j + 1$ 了，贡献长度为 $0$ 。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;

int a[N];

void solve ()
{
    int n, s, ret = -1, l = 1, r = 1; cin >> n >> s;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] += a[i-1];
    for (int j = 1, i = 1; j <= n; j ++ )
    {
        while(i <= j && a[j] - a[i - 1] + s < 0) i ++ ;
        if (ret < j - i + 1)
        {
            ret = j - i + 1;
            l = i, r = j;
        }
    }
    if (ret == 0) cout << "-1\n";
    else cout << l << ' ' << r << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}